Dantzig-Wolfe decomposition and valid inequalities for the vehicle routing problem with time windows and operation synchronization

This paper addresses operation synchronization in vehicle routing problems with time windows, which is characterized by the temporal interdependence between tasks conducted on different routes. We propose a novel Dantzig-Wolfe decomposition to handle operation synchronization, eliminating the issue of introducing linear costs in pricing sub-problems commonly encountered in conventional decomposition methods, without entailing time discretization. Moreover, considering that some combinations of visiting sequences (not schedules) become infeasible under the condition of operation synchronization, we propose pre-calculated bounds to tighten the search space for the restricted master problem. Furthermore, we introduce two subset-precedence-row inequalities, which are essentially Chvátal-Gomory rank-1 cuts based on a subset of the temporal precedence constraints in the master problem. We further analyze how to modify the label algorithms used to solve the pricing sub-problem so that they can accommodate the adoption of the subset-precedence-row inequalities. Numerical experiments demonstrate that the proposed Dantzig-Wolfe decomposition significantly outperforms the traditional formulation, and the valid inequalities reduce the solution time substantially.