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

Nan Huang, Hu Qin, Yuquan Du and Li Wang

European Journal of Operational Research, 2024, vol. 319, issue 1, 31-49

Abstract: 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%.

Keywords: Multi-trip; Multi-skilled; Manpower planning; Branch-and-price-and-cut; Two-phase column generation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724004739
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:319:y:2024:i:1:p:31-49

DOI: 10.1016/j.ejor.2024.06.025

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().