Hexaly, Gurobi, OR-Tools, jsprit, OptaPlanner 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 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, minimizing the total distance traveled so that all customers are served, and the sum of demands served by each truck doesn’t exceed its capacity. Capacitated Vehicle Routing Problem (CVRP) is the core of many Route Optimization problems, wherever encountered in last-mile delivery operations or field service technician management. Many real-world variants of the CVRP are described in our Modeling Guide for Vehicle Routing Problems.
On the Capacitated Vehicle Routing Problem, Hexaly reaches a 1.3% average gap in 1 minute on the CVRPLIB research benchmark. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers like Gurobi and dedicated Vehicle Routing solvers or frameworks like OR-Tools, jsprit (GraphHopper), and OptaPlanner.
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.
Vehicle Routing solver models
The OR-Tools model is implemented in C++. It comes from its documentation and uses the Routing Model API with callbacks for the distance matrix. The jsprit and OptaPlanner models are implemented in Java as provided in their respective documentation.
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]);
}Hexaly, Gurobi, OR-Tools, jsprit, OptaPlanner results on the Capacitated Vehicle Routing Problem (CVRP)
We compare all solvers’ performance within 1 minute of running time. At the end of the running time, we measure the gap to the best known solution in %. We use Hexaly 12.5, Gurobi 11.0, OR-Tools 9.8, jsprit 1.9, and OptaPlanner 9.44. All solvers are used with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM. The table below presents the average gap between feasible solutions found by the solvers and the best known solutions.
| Hexaly 12.5 | Gurobi 11.0 | OR-Tools 9.8 | jsprit 1.9 | OptaPlanner 9.44 | |
|---|---|---|---|---|---|
| 100-200 | 0.5 | 11.5 | 2.5 | 3.9 | 4.7 |
| 200-400 | 1.3 | 17.5 | 5.4 | 8.2 | 7.4 |
| 400-600 | 1.7 | 41.0 | 5.9 | 11.5 | 10.6 |
| 600-800 | 1.6 | 586.7 | 7.2 | 17.2 | 21.6 |
| 800-1000 | 1.8 | 793.3 | 5.3 | 17.3 | 31.5 |
Hexaly finds solutions close to best known solutions for instances with 1,000 customers in less than 1 minute. Despite specializing in solving Vehicle Routing problems, OR-Tools delivers poor-quality solutions (> 5% gap), even for medium-sized instances; OptaPlanner and jsprit perform worse (>10% gap). Gurobi fails to find decent solutions in 1 minute of running time, even for small-sized instances; additional experiments show the results remain the same with an hour of computation.
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 easier than traditional MILP solvers. The resulting model for the CVRP is compact and natural while providing much better and faster results than MILP solvers like Gurobi or Vehicle Routing solvers and frameworks like OR-Tools, jsprit (GraphHopper), and OptaPlanner, particularly for large-scale instances.
In our Example Tour, 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++. Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will gladly discuss your optimization problems.