Exact Methods for the Cumulative Capacitated Vehicle Routing Problem With Time Windows

ABSTRACT This article studies the cumulative capacitated vehicle routing problem with time windows (CCVRPTW). The CCVRPTW consists of deciding the routing schedules for a set of homogeneous capacitated vehicles such that the latency, that is, the sum of the service start times at the customers, is minimized and the time windows as well as the vehicle capacities are respected. Two new formulations are considered—a compact two‐index formulation (solved using a general‐purpose MIP solver) and a path‐based formulation. A branch‐price‐and‐cut (BPC) algorithm is developed for solving the path‐based formulation. The methods are compared against an existing compact three‐index formulation. Computational results indicate that the proposed two‐index formulation outperforms the three‐index one in terms of bounds (upper and lower) and computation times. The BPC stands as the state‐of‐the‐art method, being able to solve to proven optimality 84% of the benchmark instances in reasonable computation times. Moreover, the structural differences of the CCVRPTW compared to the classical cost‐based vehicle routing problem with time windows are analyzed, exploring the trade‐off between cost and latency through the constrained method. We observe that regardless of the geographical distribution and width of the time windows: (i) optimal latency‐based solutions generally lead to poor‐quality solutions in terms of cost (and vice versa), and this effect is much more pronounced for wide time windows, and (ii) it is possible to find relatively dense Pareto fronts. Finally, additional managerial insights related to the number of available vehicles as well as the effect of neglecting the time windows and vehicle capacities are presented.