Hexaly on huge instances of the Capacitated Vehicle Routing Problem (CVRP)
The 12th DIMACS Implementation Challenge, a renowned mathematical optimization competition, focused on solving Vehicle Routing Problems (VRP). The goal of such an event, bringing together the best experts and researchers in the field, is to have a clear picture of the state of the art on a given class of problems, like VRP, by practically comparing the best algorithms from the literature with scientific rigor. Capacitated Vehicle Routing Problem (CVRP) was one of the problems addressed. During the challenge, some of the best known solutions were improved by dedicated algorithms on the largest CVRP instances, involving several thousand points to serve. Hexaly Optimizer reaches an average gap of 4.5% within 60 seconds of running time on these huge CVRP instances.
In this post, we analyze the performance and scalability of Hexaly Optimizer, a general-purpose optimization solver, on the biggest instances used during the challenge, for which the state of the art was improved. We consider the dataset introduced in 2017 by Arnold, Gendreau, and Sörensen. The given problems, with sizes from 3,000 to 30,000 points to serve, have been tested with Hexaly 12.0 using the CVRP model directly available from Hexaly’s Example Tour. As in the challenge, the objective is to minimize the total distance without restrictions on the number of used trucks. We performed this experiment on a server equipped with an Intel Core i7-7700K processor (4 cores, 4.2 GHz, 8MB cache) and 64GB RAM.
The table below presents the gap, expressed in %, between solutions found by Hexaly and the best known solutions reported in the CVRPLIB.
| Hexaly | ||||
|---|---|---|---|---|
| Instance | Size | 1 min | 10 min | 1 hour |
| Leuven1 | 3,000 | 2.1 | 1.7 | 1.6 |
| Leuven2 | 4,000 | 5.2 | 3.8 | 3.4 |
| Antwerp1 | 6,000 | 2.4 | 1.7 | 1.5 |
| Antwerp2 | 7,000 | 5.8 | 4.6 | 3.9 |
| Ghent1 | 10,000 | 2.9 | 2.1 | 1.7 |
| Ghent2 | 11,000 | 5.9 | 4.8 | 4.0 |
| Brussels1 | 15,000 | 4.0 | 3.1 | 2.5 |
| Brussels2 | 16,000 | 6.7 | 5.6 | 4.7 |
| Flanders1 | 20,000 | 3.0 | 2.4 | 1.9 |
| Flanders2 | 30,000 | 7.2 | 5.2 | 4.4 |
Hexaly finds solutions with small gaps, 4.5% on average over the 10 instances, in only 1 minute of running time. On the huge, 30,000-points instance, Hexaly delivers a solution with a 7.2% gap. Within 1 hour of computation time, the worst gap observed decreases below 5%, even for the largest instance involving 30,000 points. The average gap over the whole dataset is reduced to 3.5% within 10 minutes and 2.9 % within 1 hour.
These massive CVRP instances are out of reach for traditional Mixed-Integer Linear Programming (MILP) solvers with a direct formulation. You can find a benchmark on CVRP between Hexaly and Gurobi on smaller instances here.
To illustrate the quality of the solution obtained by Hexaly on large instances, we generated a Multi-Depot Capacitated Vehicle Routing Problem with 14,000 points to serve, corresponding to United States cities with at least 500 inhabitants, and 6 depots located among the largest cities in the country. The map below shows the solution obtained within 10 minutes of running time. For clarity, the tours have been partially drawn to avoid too much color concentration around the depot. While solely resulting from the global optimization of routes, the clustering induced by the deliveries around the depots is almost perfect.
In our Example Tour, you can find the complete model for the Capacitated Vehicle Routing Problem (CVRP), as well as for many other Vehicle Routing problems like Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) or Pickup and Delivery Problem with Time Windows (PDPTW). Code snippets are given for common programming languages like Python, Java, C#, and C++.
Are you interested in trying it out? Get free trial licenses here. For more information, don’t hesitate to get in touch with us. We will be glad to exchange with you to understand your problems and needs in optimization.