An Enhanced Branch-and-Price-and-Cut Algorithm for the Multi-Trip Vehicle Routing Problem with Time Windows

In this paper, we study the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW) and its use in different scenarios, which have a common feature: vehicles can make multiple trips. This feature is widely used in the real world; not only can it reduce the number of vehicles and drivers required, but it also can reduce operating costs. However, this feature makes solving the problem more challenging than the capacitated vehicle routing problem with time windows (CVRPTW). To solve this problem, we propose a novel branch-and-price-and-cut (BPC) algorithm based on the trip-based set partitioning model, in which the linear relaxation sub-problem is solved by a two-phase column generation (CG) algorithm. First, a label-setting algorithm is used to generate feasible paths, and then the proposed strategy is used to find a time point that minimizes the reduced cost of the path. Moreover, the relaxation gap is tightened by k-path and subset-row inequalities. The BPC is easily adapted to solve CMTVRPTW and its four variants. Results show that our BPC algorithm can solve instances of up to 100 customers.