The MinMax-COVRP (MinMax Capacitated Open Vehicle Routing Problem) is a variation of the COVRP where the objective is to minimize the cost of the route that has the maximum cost, i.e., to minimize the makespan. Using this objective function of optimizing the longest route we are taking into account the balance of the routes which is relevant in many real-world problems.

In the MinMax-COVRP, as in the COVRP, there are a set of customer nodes with a specified demand and a depot where a fleet of identical capacitated vehicles is located. The traveling cost between the depot and each customer node and between each pair of customer nodes is known. The problem then consists in finding a set of routes performed by the vehicles and such that each route starts at the depot and ends at one of the customers, each customer is served once by exactly one vehicle, and the vehicle capacity cannot be exceeded.

To solve the MinMax-COVRP, a matheuristic that combines a multi-start heuristic with mixed-integer linear programming (MILP) is proposed. The multi-start heuristic is able to build good quality solutions very fast and the MILP serves the purpose of improve those solutions, where we have embedded the solutions of MILPs into a customized version of a local branching framework involving also pyramidal constraints and special permissions for reversals of route segments. Computational results on standard test problems show promising results.