LocalSolver


Benchmark — 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. Generalizing the Traveling Salesman Problem (TSP), the CVRP is the core of a large family of route optimization 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.

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

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 subtours.

The LocalSolver 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). The detailed model is available in our Example Tour, written using the LocalSolver Modeling language (LSP), or using the LocalSolver Python, Java, C#, and C++ APIs.


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]);
}

Results

We compare both solvers' performance with three solving times: 1 minute, 10 minutes, 1 hour. At the end of the running time, we measure the gap to the best known solution in %. We use LocalSolver 10.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 i5-6500 processor (4 cores, 3.2GHz, 6MB cache) and 16GB RAM.

The chart below presents the results. The instance size is on a horizontal scale and the gap to the best known value on the vertical axis. For each instance, you can check out the gap found by LocalSolver or Gurobi by passing your mouse over the corresponding points displayed on the chart. Until 100 customers to serve, LocalSolver delivers near-optimal solutions in less than 1 minute. Overall, LocalSolver finds solutions with an average gap of 1.8% within 1 minute, 1.3% within 10 minutes, and 1.0% within 1 hour. On the other hand, Gurobi's average gap remains above 23% within 10 minutes and above 10% within 1 hour.

Conclusion

LocalSolver offers an innovative modeling approach based on list variables and partition constraints, which made 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) in Python, Java, C#, and C++, and LSP in our Example Tour.

For more information, please contact us. We will be glad to exchange with you to understand your problems and needs in optimization.

Contact us - Disclaimer - Privacy policy - Copyright 2021 LocalSolver