An Exact Price-Cut-and-Enumerate Method for the Capacitated Multitrip Vehicle Routing Problem with Time Windows

We consider the capacitated multitrip vehicle routing problem with time windows (CMTVRPTW), where vehicles are allowed to make multiple trips. The ability to perform multiple trips is necessary for some real-world applications where the vehicle capacity, the trip duration, or the number of drivers or vehicles is limited. However, it substantially increases the solution difficulty in view of the additional trip scheduling aspect. We propose an exact price-cut-and-enumerate method (EPCEM) that solves a novel superstructure-based formulation inspired by Paradiso et al. (2020) . The EPCEM obtains a tight lower bound by an alternating column and row generation method and computes a valid upper bound in the early stage of the algorithm. It obtains an optimal solution and further proves its optimality by a new multiphase sift-and-cut method. Computationally, the EPCEM significantly outperforms the state-of-the-art exact method that only proves optimality for 9 of the 27 test instances with 50 customers. In particular, the EPCEM solves all test instances with up to 70 customers to optimality for the first time and obtains near-optimal solutions with an average optimality gap of no more than 0.3% for instances with 80 to 100 customers. From a practical point of view, solving the CMTVRPTW by the EPCEM yields a solution that, on average, uses at least 45% fewer vehicles and increases the travel cost by no more than 7% compared with the solution to the standard CVRPTW. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2022.1161 .