Hexaly, Gurobi, OR-Tools on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)
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.8% average gap in 1 minute on the Solomon, Gehring, and Homberger research 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.
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 to the best known solution in %. We use Hexaly 13.0, Gurobi 11.0, a state-of-the-art MILP solver, and OR-Tools 9.8, 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 best known 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 greater than 10% for instances with more than 600 customers.
The table below presents the average gap between the feasible solutions found by the solvers and the best known solutions.
| Hexaly 13.0 | Gurobi 11.0 | OR-Tools 9.8 | |
|---|---|---|---|
| 100 | 0.2 | 5.5 | 0.7 |
| 200 | 0.7 | 9.6 | 2.6 |
| 400 | 2.2 | 31.6 | 8.2 |
| 600 | 3.1 | 72.3 | 11.4 |
| 800 | 3.6 | 186.1 | 12.6 |
| 1000 | 4.2 | 190.0 | 12.8 |
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. 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.