Lower bounds for Vehicle Routing Problems

Announcement Transportation Routing

Bienvenu Optimization Scientist March 1, 2021

LocalSolver keeps on improving its capabilities to solve Vehicle Routing Problems (VRP). In addition to its unique, easy modeling features and its top performance both in speed and scalability, LocalSolver 10.0 offers a new, big feature: the computation of quality lower bounds for vehicle routing problems.

In LocalSolver, vehicle routing problems are modeled using list variables. Each list defines the route for a vehicle: the customers visited along the route in order. For example, the well-known Traveling Salesman Problem (TSP) is modeled in this way: one list variable containing the cities to visit in order, one constraint forcing all the cities to be visited, and a total distance function which is minimized.

/* LocalSolver model for the TSP */
// List variable: cities[i] is the index of the i-th city in the tour
cities <- list(nbCities);

// All cities must be visited
constraint count(cities) == nbCities;

// Minimize the total distance
obj <- sum(1..nbCities-1, i => distance[cities[i-1]][cities[i]])
      + distance[cities[nbCities-1]][cities[0]];

minimize obj;

LocalSolver 10.0 automatically detects if models with list variables contain what we call a routing structure. Consequently, lower bounds are available for all problems related to route optimization, particularly all variants around the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP). The computation of the bounds is based on the Held-Karp Lagrangian relaxation introduced in the seminal paper published by Held and Karp in 1970 and on LP relaxations introduced by Augerat, Belenguer, Benavent, Corberán, and Naddef in 1998. Our R&D team improved this research to make the methods able to scale up faced with instances involving several thousands of cities or customers.

We ran TSP and CVRP models from our Example Tour on the TSPLIB instances and CVRPLIB instances and compared the gap obtained in less than 5 minutes on a laptop. Below we show the average optimality gap found by LocalSolver on TSPLIB instances grouped by size. The lower bounds are close to zero: LocalSolver proves the exact optimality for 26 instances of the TSPLIB.

Finally, we show the average optimality gap found by LocalSolver in 5 minutes of running time on CVRPLIB instances grouped by size. Note that LocalSolver proves the exact optimality for 10 instances of the CVRPLIB.

Interested to try out LocalSolver 10.0 to solve your route optimization problems? We are at your disposal to accompany you in the discovery of LocalSolver. Just ask for your free trial license by registering here. In the meantime, don’t hesitate to contact us for any further information or support.