Hexaly vs Gurobi on the Capacitated Vehicle Routing Problem (CVRP)
In the Capacitated Vehicle Routing Problem (CVRP), a fleet of delivery vehicles with uniform capacity must service customers with known demand for a single commodity. The vehicles start and end their routes at a common depot. Each customer can only be served by one vehicle. Given a fleet of vehicles, the objective is to assign a sequence of customers to each truck of the fleet minimizing the total distance traveled such that all customers are served and the sum of demands served by each truck doesn’t exceed its capacity. The CVRP is the core of a large family of Vehicle Routing problems, including variants with Time-Window or Pickup-and-Delivery constraints. Many variants of the CVRP are described in our Modeling Guide for Vehicle Routing Problems.
Hexaly Optimizer reaches a 1.2% average gap after 60 seconds of running time on the Capacitated Vehicle Routing Problem. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.1, on this challenging problem.
Input data
A comprehensive set of instances for the CVRP is available in the Capacitated Vehicle Routing Problem Library (CVRPLIB). In particular, the set of X instances introduced by Uchoa et al. offers test cases ranging from 100 to 1,000 customers to serve, while previous benchmarks rarely involved more than 100 customers.
Mathematical Models of the Capacitated Vehicle Routing Problem (CVRP)
Mixed-Integer Linear Programming (MILP) model
The results reported for Gurobi are obtained using the Miller-Tucker-Zemlin (MTZ) mixed-integer linear programming formulation approach to the CVRP. It consists of a quadratic number of binary variables representing the succession of two cities in the tours and a linear number of real variables modeling the cumulated demand along the tour to avoid sub-tours.
Hexaly model
The Hexaly modeling approach for the CVRP consists of one list variable per truck. The coverage of all customers is ensured through a partition constraint. The total weight of a tour is computed using a lambda function to sum this weight over all the customers visited by a truck. Finally, the length of each tour is computed, measuring the distances between consecutively visited customers, in addition to the distance traveled from and to the depot (for nonempty tours).
function model() {
// Sequence of customers visited by each truck
customersSequences[k in 1..nbTrucks] <- list(nbCustomers);
// All customers must be visited by the trucks
constraint partition[k in 1..nbTrucks](customersSequences[k]);
for [k in 1..nbTrucks] {
local sequence <- customersSequences[k];
local c <- count(sequence);
// Sum of demands along the route must not exceed the truck capacity
constraint sum(sequence, j => demands[j]) <= truckCapacity;
// Distance traveled by the truck
routeDistances[k] <- sum(1..c-1, i => distanceMatrix[sequence[i - 1]][sequence[i]])
+ (c > 0 ? (distanceWarehouse[sequence[0]] + distanceWarehouse[sequence[c - 1]]) : 0);
}
// Minimize the total distance traveled by all trucks
minimize sum[k in 1..nbTrucks](routeDistances[k]);
}Gurobi and Hexaly results on the Capacitated Vehicle Routing Problem (CVRP)
We compare both solvers’ performance with three solving times: 1 minute, 10 minutes, and 1 hour. At the end of the running time, we measure the gap to the best known solution in %. We use Hexaly 12.0 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used with default parameters. We ran them on a server equipped with an Intel Core i7-7700K processor (4 cores, 4.2GHz, 8MB cache) and 64GB RAM.
The chart below presents the results. The instance size is on a horizontal scale, and the gap to the best known value is on the vertical axis. For each instance, you can check out the gap found by Hexaly or Gurobi by passing your mouse cursor over the corresponding points displayed on the chart. Until 100 customers to serve, Hexaly delivers near-optimal solutions in less than 1 minute. Overall, Hexaly finds solutions with an average gap of 1.2% within 1 minute, 0.9% within 10 minutes, and 0.7% within 1 hour. On the other hand, Gurobi’s average gap remains above 23% within 10 minutes and above 10% within 1 hour.
Conclusion
Hexaly offers an innovative modeling approach based on list variables and partition constraints, making the mathematical modeling of the Capacitated Vehicle Routing Problem (CVRP) much simpler than traditional MIP solvers. The resulting model for the CVRP is compact and natural while providing much better results, particularly for large instances and limited running times.
You can find the complete model of the Capacitated Vehicle Routing Problem (CVRP) and many other Vehicle Routing problems in Python, Java, C#, and C++ in our Example Tour.
Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to discuss your optimization problems.