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

Benchmark Transportation Vehicle Routing

Nicolas Senior Optimization Scientist April 10, 2023

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.

Hexaly reaches near-optimal solutions within 1 minute of running time on the Pickup and Delivery Problem with Time Windows for instances with up to 1,000 customers. 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.

We don’t display the results of Mixed-Integer Programming solvers like Gurobi and IBM ILOG Cplex because they cannot produce feasible solutions in an hour of computation for all benchmark instances.

Input data

The instances used are instances from the Li & Lim benchmark, composing a diverse set of instances 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 on GitHub. 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 12.0 and Google OR-Tools 9.6. 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 Intel Xeon E3-1230 v6 (4 cores, 3.5 GHz, 8MB cache) and 32GB RAM.

In the literature, the most common objectives are to optimize first the number of used trucks and then the total distance. However, as both models aim to minimize distance only, we compare the results to the best known solutions obtained from an internal benchmark using the distance-only objective convention. 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.

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 Google OR-Tools 9.6 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.

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