LocalSolver vs Google OR-Tools on the Pickup and Delivery with Time Windows (PDPTW)

Benchmark Transportation Vehicle Routing

Nicolas Senior Optimization Scientist April 10, 2023

In the Pickup and Delivery with Time Windows (PDPTW), a fleet of vehicles must collect and deliver items according to the demand of customers, and must do so during their opening hours. The vehicles start and end their routes at a common depot. Each customer can only be served by one vehicle. The goal is to assign a sequence of customers to each truck of the fleet minimizing the total distance traveled such that each item is picked up then delivered by the same vehicle, and the capacity of the truck is respected at any point in the tour.

This page illustrates how LocalSolver outperforms traditional general-purpose optimization solvers on this challenging problem. Since MIP solvers like Gurobi struggle to reach feasibility on this problem, we compare LocalSolver’s performance with Google OR-Tools 9.6, known as a state-of-the-art Constraint Programming (CP) solver.

Input data

The instances used in are instances from Li & Lim benchmark, composing a diverse set of instances derived from CVRPTW instances in which customers were paired together to create pickups and deliveries. The number of customers to visit varies from 100 up to 1000.

Mathematical models of the Pickup and Delivery with Time Windows (PDPTW)

OR-Tools model

The OR-Tools model for the PDPTW is available on GitHub. It uses OR-Tools routing dimensions to handle capacity and time-windows constraints. Pickup and delivery constraints are modeled thanks to comparison operators to ensure each pair to belong to the same route and in correct order.

LocalSolver model

The LocalSolver modeling approach for the CVRPTW consists of one list variable per truck. The coverage of all customers is ensured through a partition constraint. The respect of truck capacity all along the route is ensured using a recursive array, a lambda function and a and constraint covering each step of the route.

The pickup and delivery constraints are model using contains operator to make sure that each pair of pickup and delivery belongs to the same route, and indexOf operator to ensure that pickup happens before the delivery.

The time-windows constraint handling and distance computation are performed in the exact same was as in the CVRPTW. The total lateness is minimized as the first objective (soft constraint), followed by the total distance as the second objective.

function model() {
    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);

        // A truck is used if it visits at least one customer
        truckUsed[k] <- c > 0;

        // The quantity needed in each route must not exceed the truck capacity
        // at any point in the sequence
        routeQuantity[k] <- array(0..c-1, (i, prev) => prev + demands[sequence[i]]);
        constraint and(0..c-1, i => routeQuantity[k][i] <= truckCapacity);

        // Pickups and deliveries
        for [i in 0..nbCustomers-1 : pickupIndex[i] == -1] {
            constraint contains(sequence, i) == contains(sequence, deliveryIndex[i]);
            constraint indexOf(sequence, i) <= indexOf(sequence, deliveryIndex[i]);
        }

        endTime[k] <- array(0..c-1, (i, prev) => max(earliestStart[sequence[i]],
                i == 0 ? distanceDepot[sequence[0]] :
                prev + distanceMatrix[sequence[i - 1]][sequence[i]])
                + serviceTime[sequence[i]]);

        homeLateness[k] <- truckUsed[k] ?
               max(0, endTime[k][c - 1] + distanceDepot[sequence[c - 1]] - maxHorizon) :
               0;

        // Distance traveled by truck k
        routeDistances[k] <- sum(1..c-1,
                i => distanceMatrix[sequence[i - 1]][sequence[i]]) + (truckUsed[k] ?
                (distanceDepot[sequence[0]] + distanceDepot[sequence[c - 1]]) :
                0);

        lateness[k] <- homeLateness[k] + sum(0..c-1,
                i => max(0, endTime[k][i] - latestEnd[sequence[i]]));
    }

    // Total lateness, must be 0 for a solution to be valid
    totalLateness <- sum[k in 1..nbTrucks](lateness[k]);

    // Total distance traveled
    totalDistance <- round(100 * sum[k in 1..nbTrucks](routeDistances[k])) / 100;

    minimize totalLateness;
    minimize totalDistance;
}

Google OR-Tools and LocalSolver results on the Pickup and Delivery with Time Windows (PDPTW)

We compare both solvers’ performance with two solving times: 1 minute and 10 minutes. We use LocalSolver 11.5 and Google OR-Tools 9.6. Both are used with default parameters. The OR-Tools search strategy is set to the recommended guided local search. We ran them on a server equipped with an Intel Xeon E3-1230 v6 (4 cores, 3.5 GHz, 8MB cache) and 32GB RAM.

As the objective of both models is to minimize distance only, while the literature generally optimizes the number of used trucks first followed by the distance, we compare the results to the best known solutions obtained from an internal benchmark using the distance-only objective convention. The average gaps are presented in the table bellow:

LocalSolver finds solutions close to best known solutions for instances with up to 1,000 customers in less than 1 minute. Google OR-Tools finds solutions close to best known solutions for smallest instances, but quickly struggles to find quality solutions as the size increases, especially in 1 minute.

Conclusion

LocalSolver offers a concise and straightforward approach to the Pickup and Delivery with Time Windows (PDPTW) based on list decision variables. The resulting model provides much better solutions than Google OR-Tools 9.6 on the PDPTW instances.

You can find the complete model of the Pickup and Delivery with Time Windows (PDPTW) and many other Vehicle Routing problems in Python, Java, C#, C++, and LSP in our Example Tour.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange about your optimization problems.