LocalSolver 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 comparing practically 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 thousands of points to deliver.

In this post, we analyze the performance and scalability of LocalSolver, a general-purpose optimization solver, on the biggest instances used during the challenge, for which the state of the art was improved. We considered the dataset from Arnold, Gendreau, and Sörensen in 2017. The given problems, with sizes from 3,000 to 30,000 points to serve, have been tested with LocalSolver 11.0 using the CVRP model directly available from LocalSolver’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 i7-7700K (4 cores, 4.2 GHz, 8MB cache) and 64GB RAM.

In the below table, we present the gap, expressed in %, between solutions found by LocalSolver and the best-known solutions reported in the CVRPLIB.

Instance Size 1 min 10 min 1 hour
Leuven1 3,000 2.3 1.8 1.7
Leuven2 4,000 6.7 5.6 5.0
Antwerp1 6,000 2.5 1.9 1.7
Antwerp2 7,000 5.2 4.2 3.5
Ghent1 10,000 2.7 2.1 1.8
Ghent2 11,000 6.6 5.6 4.9
Brussels1 15,000 4.0 3.3 2.7
Brussels2 16,000 6.7 5.8 5.0
Flanders1 20,000 2.8 2.2 1.9
Flanders2 30,000 6.9 5.7 4.9
Gaps in % to best-known solutions in the literature.

LocalSolver finds solutions with small gaps, 4.6% on average over the 10 instances, in only 1 minute of running time. On the huge, 30,000-point instance, LocalSolver delivers a solution with a 6.9% gap. Within 1 hour of computation time, the worst gap observed decreases to 5%, even for the largest instance involving 30,000 points. The average gap over the whole dataset is reduced to 3.8% within 10 minutes and 3.3 % 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 LocalSolver and Gurobi on smaller instances here.

To illustrate the quality of the solution obtained by LocalSolver 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 drawn partially 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.