Hexaly vs Gurobi on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

Benchmark Transportation Vehicle Routing

Nicolas Senior Optimization Scientist October 24, 2022

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 of the fleet minimizing the total distance traveled such 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.

Hexaly Optimizer finds near-optimal solutions in 60 seconds for CVRPTW instances with up to 1,000 customers. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.5, 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 25 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.

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 lateness 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;
}

Gurobi and Hexaly results on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

We compare both solvers’ performance with two solving times: 1 minute and 10 minutes. At the end of the running time, we measure the gap to the best known solution in %. We use Hexaly 12.0 and Gurobi 9.5, a state-of-the-art MIP solver. Both are used with default parameters. We ran them on a server equipped with an Intel Core i7-7700K processor (4 cores, 4.2GHz, 8MB cache) and 64GB RAM.

The histogram below presents the result concerning feasibility. A solution is considered feasible if all the constraints are respected (including the respect of time windows, meaning that the value of the first objective of Hexaly’s model must be zero). The instance size is on the horizontal axis, and the percentage of feasible solutions is on the vertical axis. Results for different time limits can be selected with the slider.

Hexaly finds feasible solutions for all instances, whatever the number of customers and the time limit. Gurobi finds feasible solutions for small instances, but it struggles to find feasibility for instances with 400 customers or more. For example, Gurobi only found feasible solutions in 9 of the 60 instances with 1,000 customers within 60 seconds.

The table below presents the average gap of feasible solutions found by the two solvers compared to the best known solutions.

Hexaly finds solutions close to best known solutions for instances with up to 1,000 customers in less than 1 minute. On the contrary, Gurobi fails to find quality solutions to instances with a few hundred customers, even with 10 minutes of solving time.

Conclusion

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

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 in our Example Tour.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to discuss your optimization problems.