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

Autor(es)

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

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 275, n. 1, p. 16-34, MAY 16 2019.
• Citações Web of Science: 3

Resumo

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)

• Processo FAPESP: 16/23366-9 - Modelos e métodos de solução para variantes do problema de roteamento de estoques
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 16/15966-6 - Programação e roteamento de equipes de trabalho na restauração de redes sob incerteza
• Beneficiário: Alfredo Daniel Moreno Arteaga
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 15/26453-7 - Cadeia de suprimentos humanitária: modelos e métodos de solução
• Beneficiário: Douglas José Alem Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular