An exact algorithm for the multi-trip vehicle routing problem with time windows and multi-skilled manpower

Motivated by the challenges of non-emergency patient transportation services in the healthcare industry, this study investigated a multi-trip vehicle routing problem incorporating multi-skilled manpower with downgrading. We aimed to find an optimal plan for vehicle routing and multi-skilled manpower scheduling in tandem with the objective of minimizing the total cost, including travel and staff costs, without violating time windows and lunch break constraints. To address this, two mathematical models were formulated: an arc-flow model and a trip-based set-covering model. In addition, a branch-and-price-and-cut algorithm, based on the set-covering model, was proposed to solve practical-scale instances. To determine the feasibility of the integer solutions, we introduce a feasibility check model. To address the multi-trip characteristics of the proposed problem, a novel two-phase column generation algorithm was introduced to solve the subproblem. This approach differs from traditional one-phase labeling algorithms and involves a tailored labeling algorithm for obtaining non-dominated labels in the first phase and a strategy to identify the trip with the minimum reduced cost for each label in the second phase. Furthermore, novel and efficient staff-based inequalities were developed by improving the k-path inequalities. Extensive numerical experiments were conducted to demonstrate the solution performance of the proposed algorithm and reveal managerial insights for non-emergency ambulance operations. The results demonstrate that our algorithm can successfully solve instances with up to 50 patients to optimality within two hours. Moreover, we demonstrated the value of jointly optimizing vehicle routing and staff planning, which can result in significant cost savings of up to 19.4%.