Crew Scheduling and Routing Problem in Road Restoration via Branch-and-Price Algorithms

Alfredo Moreno (), Pedro Munari () and Douglas Alem ()
Additional contact information
Alfredo Moreno: Department of Industrial Engineering, Universidad del Norte, Barranquilla, Colombia 081007
Pedro Munari: Production Engineering Department, Federal University of São Carlos, São Carlos 13565-905, Brazil
Douglas Alem: University of Edinburgh Business School, Management Science and Business Economics Group, Edinburgh EH8 9JS, United Kingdom

Transportation Science, 2024, vol. 58, issue 4, 801-820

Abstract: This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex postdisaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation is based on enumerating crew schedules and routes while explicitly defining the relief paths. The second formulation relies on enumerating the schedules, routes, and relief paths. Finally, the third formulation builds upon the second one by including additional constraints and variables related to relief path decisions. Considering each formulation, we propose BP algorithms that rely on several enhancements, including a new dynamic programming labeling algorithm to efficiently solve the subproblems. Extensive computational results based on 648 benchmark instances reveal that our BP algorithms significantly outperform existing exact approaches, solving 450 instances to optimality, and remarkably 118 instances for the first time. Our framework is also very effective in improving the lower bounds, upper bounds, and optimality gaps that have been reported in the literature.

Keywords: road restoration; network repair; humanitarian logistics; column generation; branch-and-price (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0227 (application/pdf)

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:inm:ortrsc:v:58:y:2024:i:4:p:801-820

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().