A branch-and-benders-cut algorithm for the crew scheduling and routing problem in road restoration

Alfredo Moreno, Pedro Munari, Douglas Alem

Research output: Contribution to journalArticlepeer-review

Abstract

Extreme events such as disasters cause partial or total disruption of basic services such as water,energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers or affected areas. The Crew Scheduling and Routing Problem (CSRP) addresses decisions in postdisaster situations with the aim of minimizing the time that affected areas remain inaccessible.The integration of crew scheduling and routing decisions makes this problem too complicated to be effectively solved for practical instances using mixed integer programming (MIP) formulations recently proposed in the literature. Therefore, we propose a branch-and-Benders-cut (BBC)algorithm that decomposes the integrated problem into a master problem (MP) with scheduling decisions and subproblems with routing decisions. Computational tests based on instances from the literature show that the proposed exact method improves the results of MIP formulations and other exact and metaheuristic methods proposed in literature. The BBC algorithm provides feasible solutions and optimality gaps for instances that thus far have not been possible to solve by exact methods in the literature.
Original languageEnglish
Pages (from-to)16-34
JournalEuropean Journal of Operational Research
Volume257
Issue number1
Early online date8 Nov 2018
DOIs
Publication statusPublished - 16 May 2019

Keywords

  • combinatorial optimization
  • benders decomposition
  • branch-and-cut
  • crew scheduling and routing
  • road restoration

Fingerprint Dive into the research topics of 'A branch-and-benders-cut algorithm for the crew scheduling and routing problem in road restoration'. Together they form a unique fingerprint.

Cite this