Hexaly, Gurobi, OR-Tools on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

Benchmark Transportation Routing

Frédéric Senior Optimization Scientist June 28, 2024

In the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), a fleet of delivery vehicles with uniform capacity must serve customers with known demand for a single commodity. The vehicles start and end their routes at a joint depot. Each customer can only be served by one vehicle and must be visited within its time window. The objective is to assign a sequence of customers to each truck in the fleet, which minimizes the total distance traveled so that all customers are served during their time window, and the sum of demands served by each truck doesn’t exceed its capacity. This problem extends the Capacitated Vehicle Routing Problem (CVRP). Many other variants of the CVRP are described in our Modeling Guide for Vehicle Routing Problems.

On the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), Hexaly reaches a 1.9% average gap to the best known solutions in the research in 1 minute on the Solomon, Gehring, and Homberger benchmark. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi 11.0, and dedicated vehicle routing solvers, like OR-Tools, on this challenging problem.

Input data

The instances used in this benchmark are Solomon instances and Gehring & Homberger instances, composing a diverse set of instances: customer locations are chosen to be clustered, randomized, or both, and time windows can either be tight or loose. The number of customers to visit varies from 100 up to 1000.

Mathematical models of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

Mixed-Integer Linear Programming (MILP) model

The results reported for Gurobi are obtained using a mixed-integer linear programming model based on the Miller-Tucker-Zemlin (MTZ) formulation approach to the CVRPTW presented in this article. It consists of a quadratic number of binary variables representing the succession of two customers in the tours, a linear number of real variables modeling the cumulated demand along the tour, and a linear number of real variables modeling the arrival time at each customer. Constraints associated with cumulated demand and increasing arrival time along tours prevent the appearance of sub-tours in the solution.

After careful experiments, we have chosen this MILP modeling approach for Gurobi. Other approaches, such as Dantzig–Fulkerson–Johnson (DFJ) and Multi-Commodity Flow (MCF), are possible. The MTZ formulation has shown to be the best for solving the CVRPTW when using Gurobi with the current settings (time limit, hardware) on the given benchmark.

Vehicle routing models

The OR-Tools model is implemented in C++. It comes from its documentation and uses the Routing Model API with callbacks for the distance matrix.

Hexaly model

As for the CVRP, 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 total weight of a tour is computed using a lambda function to sum this weight over all the customers visited by a truck. This quantity is then constrained not to exceed truck capacity.

Each customer’s end time of service is computed using a recursive array and a lambda function, ensuring that each customer is visited after the beginning of its time window. The end time can then be used to compute the lateness of the customer by comparing it with the end of the customer time window. The truck’s total lateness corresponds to the sum of latenesses observed when serving customers and the lateness at depot return. 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 nonempty tours).

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 <- c > 0;

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

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

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

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

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

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

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

    minimize totalLateness;
    minimize totalDistance;
}

Hexaly, Gurobi, OR-Tools results on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

We compare all solvers’ performance after 1 minute of running time. At the end of the running time, we measure the gap in % to the best solutions known in the literature, also called State Of The Art (SOTA). These solutions can be found here. Note that these SOTA solutions are computed using dedicated algorithms, using arbitrary long running times on specific hardware.

We use Hexaly 13.0, Gurobi 11.0, a state-of-the-art MILP solver, and OR-Tools 9.10, a well-known vehicle routing solver. All are used with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM.

Hexaly finds solutions close to the SOTA solutions for instances with up to 1,000 customers. Gurobi struggles to find feasible solutions for instances with more than 400 customers. For example, Gurobi only found feasible solutions in 46 of the 60 instances with 1,000 customers. OR-Tools finds solutions with a gap to the SOTA greater than 10% for instances with more than 600 customers.

Conclusion

Hexaly offers an innovative modeling approach based on list variables, partition constraints, lambda function, and recursively defined arrays. This approach makes the mathematical modeling of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) more straightforward and concise than traditional MILP solvers. The resulting model for the CVRPTW is natural and compact while providing much better results, particularly for large-scale instances.

In our Example Tour, you can find the complete model of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and many other Vehicle Routing problems in Python, Java, C#, C++, and LSP.