IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v275y2019i1p16-34.html
   My bibliography  Save this article

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

Author

Listed:
  • Moreno, Alfredo
  • Munari, Pedro
  • Alem, Douglas

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.

Suggested Citation

  • Moreno, Alfredo & Munari, Pedro & Alem, Douglas, 2019. "A branch-and-Benders-cut algorithm for the Crew Scheduling and Routing Problem in road restoration," European Journal of Operational Research, Elsevier, vol. 275(1), pages 16-34.
    • Handle: RePEc:eee:ejores:v:275:y:2019:i:1:p:16-34
    DOI: 10.1016/j.ejor.2018.11.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718309299
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.11.004?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gendron, Bernard & Scutellà, Maria Grazia & Garroppo, Rosario G. & Nencioni, Gianfranco & Tavanti, Luca, 2016. "A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks," European Journal of Operational Research, Elsevier, vol. 255(1), pages 151-162.
    2. D. Klingman & A. Napier & J. Stutz, 1974. "NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems," Management Science, INFORMS, vol. 20(5), pages 814-821, January.
    3. C. Hjorring & J. Holt, 1999. "New optimality cuts for a single‐vehicle stochastic routing problem," Annals of Operations Research, Springer, vol. 86(0), pages 569-584, January.
    4. Ching-Hui Tang & Shangyao Yan & Chia-Wei Chang, 2009. "Short-term work team scheduling models for effective road repair and management," Transportation Planning and Technology, Taylor & Francis Journals, vol. 32(3), pages 289-311, April.
    5. Tuzun Aksu, Dilek & Ozdamar, Linet, 2014. "A mathematical model for post-disaster road restoration: Enabling accessibility and evacuation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 56-67.
    6. Andie Pramudita & Eiichi Taniguchi, 2014. "Model of debris collection operation after disasters and its application in urban area," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 18(2), pages 218-243, July.
    7. Özdamar, Linet & Tüzün Aksu, Dilek & Ergüneş, Biket, 2014. "Coordinating debris cleanup operations in post disaster road networks," Socio-Economic Planning Sciences, Elsevier, vol. 48(4), pages 249-262.
    8. de Sá, Elisangela Martins & de Camargo, Ricardo Saraiva & de Miranda, Gilberto, 2013. "An improved Benders decomposition algorithm for the tree of hubs location problem," European Journal of Operational Research, Elsevier, vol. 226(2), pages 185-202.
    9. Akbari, Vahid & Salman, F. Sibel, 2017. "Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity," European Journal of Operational Research, Elsevier, vol. 257(2), pages 625-640.
    10. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    11. Maya Duque, Pablo A. & Dolinskaya, Irina S. & Sörensen, Kenneth, 2016. "Network repair crew scheduling and routing for emergency relief distribution problem," European Journal of Operational Research, Elsevier, vol. 248(1), pages 272-285.
    12. Fausto Errico & Teodor Gabriel Crainic & Federico Malucelli & Maddalena Nonato, 2017. "A Benders Decomposition Approach for the Symmetric TSP with Generalized Latency Arising in the Design of Semiflexible Transit Systems," Transportation Science, INFORMS, vol. 51(2), pages 706-722, May.
    13. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sakineh Lakzaei & Donya Rahmani & Babak Mohamadpour Tosarkani & Sepideh Nasiri, 2023. "Integrated optimal scheduling and routing of repair crew and relief vehicles after disaster: a novel hybrid solution approach," Annals of Operations Research, Springer, vol. 328(2), pages 1495-1522, September.
    2. Akbari, Vahid & Shiri, Davood & Sibel Salman, F., 2021. "An online optimization approach to post-disaster road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 1-25.
    3. Ajam, Meraj & Akbari, Vahid & Salman, F. Sibel, 2022. "Routing multiple work teams to minimize latency in post-disaster road network restoration," European Journal of Operational Research, Elsevier, vol. 300(1), pages 237-254.
    4. Souza Almeida, Luana & Goerlandt, Floris & Pelot, Ronald, 2022. "Trends and gaps in the literature of road network repair and restoration in the context of disaster response operations," Socio-Economic Planning Sciences, Elsevier, vol. 84(C).
    5. de Castro Pena, Guilherme & Santos, Andréa Cynthia & Prins, Christian, 2023. "Solving the integrated multi-period scheduling routing problem for cleaning debris in the aftermath of disasters," European Journal of Operational Research, Elsevier, vol. 306(1), pages 156-172.
    6. Aakil M. Caunhye & Nazli Yonca Aydin & H. Sebnem Duzgun, 2020. "Robust post-disaster route restoration," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(4), pages 1055-1087, December.
    7. Sanci, Ece & Daskin, Mark S., 2019. "Integrating location and network restoration decisions in relief networks under uncertainty," European Journal of Operational Research, Elsevier, vol. 279(2), pages 335-350.
    8. Zhang, Yuwei & Li, Zhenping & Zhao, Yuwei, 2023. "Multi-mitigation strategies in medical supplies for epidemic outbreaks," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    9. Ajam, Meraj & Akbari, Vahid & Salman, F. Sibel, 2019. "Minimizing latency in post-disaster road clearance operations," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1098-1112.
    10. Garay-Sianca, Aniela & Nurre Pinkley, Sarah G., 2021. "Interdependent integrated network design and scheduling problems with movement of machines," European Journal of Operational Research, Elsevier, vol. 289(1), pages 297-327.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shuanglin Li & Kok Lay Teo, 2019. "Post-disaster multi-period road network repair: work scheduling and relief logistics optimization," Annals of Operations Research, Springer, vol. 283(1), pages 1345-1385, December.
    2. Souza Almeida, Luana & Goerlandt, Floris & Pelot, Ronald, 2022. "Trends and gaps in the literature of road network repair and restoration in the context of disaster response operations," Socio-Economic Planning Sciences, Elsevier, vol. 84(C).
    3. Moreno, Alfredo & Alem, Douglas & Gendreau, Michel & Munari, Pedro, 2020. "The heterogeneous multicrew scheduling and routing problem in road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 24-58.
    4. Sakineh Lakzaei & Donya Rahmani & Babak Mohamadpour Tosarkani & Sepideh Nasiri, 2023. "Integrated optimal scheduling and routing of repair crew and relief vehicles after disaster: a novel hybrid solution approach," Annals of Operations Research, Springer, vol. 328(2), pages 1495-1522, September.
    5. Sanci, Ece & Daskin, Mark S., 2019. "Integrating location and network restoration decisions in relief networks under uncertainty," European Journal of Operational Research, Elsevier, vol. 279(2), pages 335-350.
    6. Akbari, Vahid & Shiri, Davood & Sibel Salman, F., 2021. "An online optimization approach to post-disaster road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 1-25.
    7. Ajam, Meraj & Akbari, Vahid & Salman, F. Sibel, 2019. "Minimizing latency in post-disaster road clearance operations," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1098-1112.
    8. Nabavi, S.M. & Vahdani, Behnam & Nadjafi, B. Afshar & Adibi, M.A., 2022. "Synchronizing victim evacuation and debris removal: A data-driven robust prediction approach," European Journal of Operational Research, Elsevier, vol. 300(2), pages 689-712.
    9. Sayarshad, Hamid R. & Du, Xinpi & Gao, H. Oliver, 2020. "Dynamic post-disaster debris clearance problem with re-positioning of clearance equipment items under partially observable information," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 352-372.
    10. Farzaneh, Mohammad Amin & Rezapour, Shabnam & Baghaian, Atefe & Amini, M. Hadi, 2023. "An integrative framework for coordination of damage assessment, road restoration, and relief distribution in disasters," Omega, Elsevier, vol. 115(C).
    11. Akbari, Vahid & Salman, F. Sibel, 2017. "Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity," European Journal of Operational Research, Elsevier, vol. 257(2), pages 625-640.
    12. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    13. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    14. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    15. Zhang, Yuwei & Li, Zhenping & Zhao, Yuwei, 2023. "Multi-mitigation strategies in medical supplies for epidemic outbreaks," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    16. Nader Ghaffarinasab & Bahar Y. Kara, 2019. "Benders Decomposition Algorithms for Two Variants of the Single Allocation Hub Location Problem," Networks and Spatial Economics, Springer, vol. 19(1), pages 83-108, March.
    17. Rodríguez, Jesús A. & Anjos, Miguel F. & Côté, Pascal & Desaulniers, Guy, 2021. "Accelerating Benders decomposition for short-term hydropower maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 289(1), pages 240-253.
    18. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric, 2022. "Meta partial benders decomposition for the logistics service network design problem," European Journal of Operational Research, Elsevier, vol. 300(2), pages 473-489.
    19. Laporte, Gilbert & Semet, Frederic, 1999. "An optimality cut for mixed integer linear programs," European Journal of Operational Research, Elsevier, vol. 119(3), pages 671-677, December.
    20. Maya Duque, Pablo A. & Dolinskaya, Irina S. & Sörensen, Kenneth, 2016. "Network repair crew scheduling and routing for emergency relief distribution problem," European Journal of Operational Research, Elsevier, vol. 248(1), pages 272-285.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:275:y:2019:i:1:p:16-34. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.