Hexaly, Gurobi, OR-Tools on the Capacitated Vehicle Routing Problem (CVRP)

Benchmarks Transportation Routing

Julien Head of Science July 26, 2026

In the Capacitated Vehicle Routing Problem (CVRP), a fleet of delivery vehicles with uniform capacity must service customers with known demand for a single commodity. The vehicles start and end their routes at a depot. Each customer can only be served by one vehicle. Given a fleet of vehicles, the objective is to assign a sequence of customers to each truck, minimizing the total distance traveled so that all customers are served, and the sum of demands served by each truck doesn’t exceed its capacity. The Capacitated Vehicle Routing Problem (CVRP) is the core of many Route Optimization problems, wherever encountered in last-mile delivery operations or field service technician management.

On the Capacitated Vehicle Routing Problem (CVRP), Hexaly achieves on the CVRPLIB benchmark a 0.7% average gap to the best known solutions in the research community (BKS) in 1 minute of runtime. This article illustrates how Hexaly performs compared with traditional general-purpose optimization solvers such as Gurobi and OR-Tools, which are commonly used in business and industry.

Input data

A comprehensive set of instances for the Capacitated Vehicle Routing Problem (CVRP) is available in the Capacitated Vehicle Routing Problem Library (CVRPLIB). In particular, the set of X instances introduced by Uchoa et al. offers test cases ranging from 100 to 1,000 customers to serve, while previous benchmarks rarely involved more than 100 customers.

Mathematical models of the Capacitated Vehicle Routing Problem (CVRP)

Gurobi model

The results reported for Gurobi are obtained using the Miller-Tucker-Zemlin (MTZ) mixed-integer linear programming formulation approach to the CVRP. It consists of a quadratic number of binary variables representing the succession of two cities in the tours and a linear number of real variables modeling the cumulated demand along the tour to avoid sub-tours.

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 is the best for solving the Capacitated Vehicle Routing Problem (CVRP) 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

The Hexaly modeling approach for the Capacitated Vehicle Routing Problem (CVRP) 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 the weight over all the customers visited by a truck. Finally, the length of each tour is computed by measuring the distances between consecutively visited customers, in addition to the distances traveled to and from the depot (for nonempty tours).

function model() {
    // Sequence of customers visited by each truck
    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);

        // Sum of demands along the route must not exceed the truck capacity
        constraint sum(sequence, j => demands[j]) <= truckCapacity;

        // Distance traveled by the truck
        routeDistances[k] <- sum(1..c-1, i => distanceMatrix[sequence[i - 1]][sequence[i]])
             + (c > 0 ? (distanceWarehouse[sequence[0]] + distanceWarehouse[sequence[c - 1]]) : 0);
    }
    
    // Minimize the total distance traveled by all trucks
    minimize sum[k in 1..nbTrucks](routeDistances[k]);
}

Hexaly, Gurobi, OR-Tools results on the Capacitated Vehicle Routing Problem (CVRP)

We compare all solvers’ performance within 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, also called BKS. These solutions can be found here. Note that the BKS is computed using dedicated algorithms and can require an arbitrary long runtime on specific hardware.

We use Hexaly 15.0, Gurobi 11.0, and OR-Tools 9.14. All solvers 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. The table below presents the average gap between feasible solutions found by each solver and the BKS as reported here.

Hexaly finds solutions with a gap to BKS below 1% for all considered instances in less than 1 minute of runtime. Despite specializing in solving Vehicle Routing problems, OR-Tools delivers low-quality solutions (>5% gap), even for medium-sized instances. Gurobi fails to find decent solutions within 1 minute of runtime, even for small instances; additional experiments show the results remain the same after 1 hour of computation.

Conclusion

Hexaly offers an innovative modeling approach based on list variables and partition constraints, making the mathematical modeling of the Capacitated Vehicle Routing Problem (CVRP) much easier than traditional optimization solvers. The resulting model for the CVRP is compact and natural while providing much better and faster results than Gurobi or OR-Tools, particularly for large-scale instances.

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