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

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 and then delivered by the same vehicle, and the capacity of the truck is respected at any point in the tour.

Hexaly Optimizer reaches near-optimal solutions within 60 seconds of running time on the Pickup and Delivery Problem with Time Windows. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers on this challenging problem. Since MIP solvers like Gurobi struggle to reach feasibility on this problem, we compare Hexaly’s performance with Google OR-Tools 9.6, known as a state-of-the-art Constraint Programming (CP) solver.

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 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. 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 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 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-windows constraints and distance computation in the exact same way 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 Hexaly 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 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 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.

The literature generally optimizes the number of used trucks first and then the total distance. However, as the objective of both models is 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 OR-Tools
Size 1 min 10 min 1 min 10 min
100 0.2 0.0 1.5 0.3
200 0.3 0.1 6.2 2.1
400 1.3 0.4 11.4 9.1
600 2.3 1.0 28.6 10.1
800 2.6 1.0 58.0 11.5
1000 3.7 1.3 130.6 11.6
Average gaps to best known solutions.

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 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 discuss your optimization problems.

Share