A branch-and-Benders-cut algorithm for the Crew Scheduling and Routing Problem in road restoration

Author(s)

Moreno, Alfredo ^[1] ; Munari, Pedro ^[1] ; Alem, Douglas ^[2]

Affiliation

^[1] Univ Fed Sao Carlos, Prod Engn Dept, Rod Washington Luis Km 235, BR-13565905 Sao Carlos, SP - Brazil

^[2] Univ Edinburgh, Management Sci & Business Econ Grp, Business Sch, 29 Buccleuch Pl, Edinburgh EH8 9JS, Midlothian - Scotland

• Document type: Journal article
• Source: European Journal of Operational Research; v. 275, n. 1, p. 16-34, MAY 16 2019.
• Web of Science Citations: 3

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 post-disaster 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. (C) 2018 Elsevier B.V. All rights reserved. (AU)

• FAPESP's process: 16/23366-9 - Models and solution methods for variants of the inventory routing problem
• Grantee: Pedro Augusto Munari Junior
• Support Opportunities: Regular Research Grants
• FAPESP's process: 16/15966-6 - Crew scheduling and routing in network repair under uncertainty
• Grantee: Alfredo Daniel Moreno Arteaga
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 15/26453-7 - Humanitarian supply chain: models and solution methods
• Grantee: Douglas José Alem Junior
• Support Opportunities: Regular Research Grants