The heterogeneous multicrew scheduling and routing problem in road restoration

Alfredo Moreno, Douglas Alem*, Michel Gendreau, Pedro Munari

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.

Original languageEnglish
Pages (from-to)24-58
Number of pages35
JournalTransportation Research Part B: Methodological
Early online date13 Sept 2020
Publication statusPublished - Nov 2020

Keywords / Materials (for Non-textual outputs)

  • disaster relief
  • heterogeneous crew scheduling and routing
  • humanitarian logistics
  • network repair
  • road restoration problem


Dive into the research topics of 'The heterogeneous multicrew scheduling and routing problem in road restoration'. Together they form a unique fingerprint.

Cite this