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

Benchmarks Transportation Routing

Julien Head of Science July 24, 2026

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 to minimize the total distance traveled, ensure that all customers are served within their time windows, and that the sum of demands served by each truck doesn’t exceed its capacity. This problem extends the Capacitated Vehicle Routing Problem (CVRP).

On the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), Hexaly achieves on the Solomon, Gehring, and Homberger benchmark a 2.5% average gap to the best known solutions in the research community (BKS) in 1 minute of runtime. This page illustrates how Hexaly outperforms both traditional general-purpose optimization solvers, such as Gurobi and 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 to 1000.

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

Gurobi 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 cumulative demand and increasing arrival times along tours prevent the formation of subtours 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 been shown to be the best for solving the CVRPTW when using Gurobi with the current settings (time limit, hardware) on the given benchmark.

OR-Tools model

The OR-Tools model is implemented in Python. 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 that sums the weights of all customers visited by a truck. This quantity is then constrained to not exceed the truck’s capacity.

Each customer’s service end time 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 customer’s lateness by comparing it with the end of the customer’s 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 research literature (BKS). These solutions can be found here. Note that these BKS solutions are computed using dedicated algorithms, using arbitrary long running times on specific hardware.

We use Hexaly 15.0, Gurobi 11.0, and OR-Tools 9.14. All are used with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8 GHz, 8 MB cache) and 32 GB of RAM.

Hexaly finds solutions close to BKS for all considered instances. 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 BKS greater than 10% for instances with more than 600 customers.

Conclusion

Hexaly offers an innovative modeling approach based on list variables, partition constraints, a 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.

Our Code Templates contain the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) model and many other Vehicle Routing problems written using Hexaly Modeler or programming languages like Python, Java, C#, and C++.