LocalSolver


Benchmark Vehicle Routing (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 vehicle, the objective is to assign a sequence of customers to each truck of the fleet minimizing the total distance travelled such that all customers are served and the total demand served by each truck does not exceed its capacity. Generalizing the Traveling Salesman Problem, the CVRP is the core of a large family of routing problems, including variants with Time Windows, multiple depots, pickup-and-delivery constraints, prize-collecting objective, preassigned deliveries, and so on. Many of these variants are described in our Modeling Guide for Routing.


Data

A comprehensive set of instances for the CVRP is available in the CVRP Library. In particular the set of "X" instances, introduced by Uchoa et al. offers test cases ranging from 100 to 1000 customers while previous instances rarely involved more than 100 customers.


LocalSolver model

The LocalSolver model for the CVRP defines one list variable per truck, and the coverage of all customers is ensured by a partition constraint. The total weight of a tour is computed with a lambda function in order to sum this weight over all 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 non empty tours). The detailed model is available in LSP, Python, Java, C++ and .Net in our example tour.


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

        // The quantity needed in each route must not exceed the truck capacity
        constraint sum(sequence, j => demands[j]) <= truckCapacity;

        // Distance travelled by truck k
        routeDistances[k] <- sum(1..c-1, i => distanceMatrix[sequence[i - 1]][sequence[i]])
             + (c > 0 ? (distanceWarehouse[sequence[0]] + distanceWarehouse[sequence[c - 1]]) : 0);
    }
    
    // Objective: minimize the distance travelled
    minimize sum[k in 1..nbTrucks](routeDistances[k]);
}

Performance

The chart below presents the results obtained with this LocalSolver model with different running times (from 10 seconds to 5 minutes) on all instances. In summary, we observe that good solutions are obtained even with short running times, and given 5 minutes of computation time, LocalSolver reaches a average gap smaller than 2%.

Curve


Contact us - Disclaimer - Copyright 2019 Innovation 24