The heterogeneous multicrew scheduling and routing problem in road restoration. (November 2020)

• Record Type: Journal Article
• Authors: Moreno, Alfredo; Alem, Douglas; Gendreau, Michel; Munari, Pedro
• Is Part Of: Transportation research. Volume 141(2020)
• Page Start: 24
• Page End: 58
• Publication Date: 2020-11
• Subjects: Road restoration problem -- Heterogeneous crew scheduling and routing -- Network repair -- Humanitarian logistics -- Disaster relief; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2020.09.002
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: The heterogeneous multicrew scheduling and routing problem in road restoration is introduced. Three mathematical formulations and valid inequalities are developed. Valid inequalities are based on the dominance of the paths between nodes in the damaged network. The approach is validated through real-world instances based on floods and landslides in Rio de Janeiro, Brazil. Abstract: This paper introduces the heterogeneous multicrew scheduling and routing problem (MCSRP) in road restoration. The MCSRP consists of identifying the schedule and route of heterogeneous crews that must perform the restoration of damaged nodes used in the paths to connect a source node to demand nodes in a network affected by extreme events. The objective is to minimize the accessibility time defined as the time that the demand nodes remain unconnected from the source node. The main contributions of the paper include three novel mathematical formulations that differ in the way of modeling the scheduling decisions and the synchronization of the crews, and the development of valid inequalities based on some particular properties of the problem. Additionally, we prove that the MCSRP is NP-hard. Extensive numerical experiments with randomly generated instances and a case study based on floods and landslides disasters in Rio de Janeiro, Brazil, are performed to assess the efficiency and applicability of our approach. In particular, we show that the valid inequalities significantly improve the solvability of the mathematical models. In terms of managerial implications, our results suggest that the incorporation of multiple crews helps to reduce the worst-case accessibility times across the demand nodes, thus providing more equitable solutions.