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

Benchmark Transportation Routing

Frédéric Senior Optimization Scientist August 5, 2024

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. 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. Many real-world variants of the CVRP are described in our Modeling Guide for Vehicle Routing Problems.

On the Capacitated Vehicle Routing Problem, Hexaly reaches a 1.2% average gap to the best known solutions in the research in 1 minute on the CVRPLIB benchmark. This article illustrates how Hexaly performs in comparison with traditional Mixed-Integer Linear Programming (MILP) solvers like Gurobi and general-purpose solvers OR-Tools and OptaPlanner commonly used to solve Vehicle Rouging problems in business and industry. We have added the dedicated Vehicle Routing library named “jsprit” to the benchmark because it is used by many software developers through the GraphHopper web APIs.

Input data

A comprehensive set of instances for the 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)

Mixed-Integer Linear Programming (MILP) 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 has shown to be the best for solving the CVRP when using Gurobi with the current settings (time limit, hardware) on the given benchmark.

Vehicle Routing solver 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. The OptaPlanner and jsprit models are implemented in Java as provided in their respective documentation.

Hexaly model

The Hexaly modeling approach for the 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 this weight over all the customers visited by a truck. 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).

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, OptaPlanner, jsprit 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 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, OR-Tools 9.10, OptaPlanner 9.44, and jsprit 1.9. All solvers 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. The table below presents the average gap between feasible solutions found by each solver and the SOTA as reported here.

Hexaly finds solutions close to best known solutions for instances with 1,000 customers in less than 1 minute. Despite specializing in solving Vehicle Routing problems, OR-Tools delivers poor-quality solutions (> 5% gap), even for medium-sized instances; OptaPlanner and jsprit perform worse (>10% gap). Gurobi fails to find decent solutions in 1 minute of running time, even for small-sized instances; additional experiments show the results remain the same with 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 MILP solvers. The resulting model for the CVRP is compact and natural while providing much better and faster results than a state-of-the-art MILP solver like Gurobi or the other solvers and libraries commonly used in business and industry like OR-Tools, OptaPlanner, and jsprit (GraphHopper), particularly for large-scale instances.

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