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

Benchmark Transportation Routing

Frédéric Senior Optimization Scientist August 26, 2024

In the Pickup and Delivery Problem with Time Windows (PDPTW), vehicles must collect and deliver items according to customers’ demands. It must do so during opening hours. The vehicles start and end their routes at a depot. Each customer must be served by one and only one vehicle. The goal is to assign a sequence of customers to each vehicle to minimize the distance traveled while ensuring each item is picked up and then delivered by the same vehicle and the truck’s capacities are not exceeded during the tours.

On the Pickup and Delivery Problem with Time Windows (PDPTW), Hexaly reaches a 1.1% average gap to the best known solutions in 1 minute of running time on the Li & Lim benchmark. In comparison, Google OR-Tools finds reasonable solutions for small instances but quickly struggles to find quality solutions as the size increases, especially within 1 minute of running time. We don’t display the results of other general-purpose mathematical optimization solvers like Mixed-Integer Programming solvers (Gurobi, IBM ILOG Cplex, FICO Xpress) and Optaplanner: they don’t deliver any feasible solutions for all benchmark instances, even within 1 hour of computation time.

Input data

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

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

OR-Tools model

The OR-Tools model for the PDPTW is available here. It uses OR-Tools routing dimensions to handle capacity and time-windows constraints. We model pickup and delivery constraints using comparison operators to ensure each pair belongs to the same route and in the correct order.

Hexaly model

The Hexaly 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 along the route is provided using a recursive array, a lambda function, and a and constraint covering each step of the route.

The pickup and delivery constraints are modeled using the 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.

Finally, we handle the time window constraints and distance computation like 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 Hexaly results on the Pickup and Delivery Problem with Time Windows (PDPTW)

We compare both solvers’ performance with two solving times: 1 minute and 10 minutes. We use Hexaly 13.0 and Google OR-Tools 9.10. Both are used with default parameters. The OR-Tools search strategy is set to the recommended one: guided local search. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM.

In the literature, the objectives are to optimize first the number of used trucks and then the total distance. For the sake of readability, we display the gap in % to the best known solution for the total distance only. The table below presents the average gap to the best known solution for different instance sizes:

Hexaly 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 smaller instances but quickly struggles to find quality solutions as the size increases, especially in 1 minute of running time.

Conclusion

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

The Hexaly model of the Pickup and Delivery Problem with Time Windows (PDPTW) and many other Vehicle Routing problems, written using Hexaly Modeler or programming languages like Python, Java, C#, and C++, are available in our Example Tour.