LocalSolver vs Gurobi 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 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. Below we show how LocalSolver 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 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.

LocalSolver model

As for the CVRP, the LocalSolver 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 correspond to the sum of lateness observed when serving customer 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 LocalSolver 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 LocalSolver 11.5 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 below histogram 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 LocalSolver’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.

LocalSolver finds feasible solutions for all instances, whatever the number of customers and the time limit. Gurobi finds feasible solutions for small instances, but it starts to struggle 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.

In the below table, we present the average gap of feasible solutions found by the two solvers compared to the best-known solutions.

LocalSolver Gurobi
Size 1 min 10 min 1 min 10 min
25 0.0 0.0 0.1 0.0
50 0.1 0.0 1.4 0.6
100 0.7 0.2 7.5 4.3
200 1.5 0.7 14.8 7.9
400 3.4 2.5 32.9 26.0
600 4.8 3.8 77.1 23.5
800 5.3 4.4 38.9 34.3
1000 6.5 5.3 183.4 34.9
Average gaps to best-known solutions for feasible solutions.

LocalSolver finds solutions close to best-known ones 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 hundreds of customers, even with 10 minutes of solving time.

Conclusion

LocalSolver 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 exchange about your optimization problems.

Share