IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v328y2023i2d10.1007_s10479-023-05397-0.html
   My bibliography  Save this article

Integrated optimal scheduling and routing of repair crew and relief vehicles after disaster: a novel hybrid solution approach

Author

Listed:
  • Sakineh Lakzaei

    (K. N. Toosi University of Technology)

  • Donya Rahmani

    (K. N. Toosi University of Technology)

  • Babak Mohamadpour Tosarkani

    (University of British Columbia)

  • Sepideh Nasiri

    (K. N. Toosi University of Technology)

Abstract

After a natural disaster or a large-scale incident, some of the utility lines and essential roads around the damaged centers may be blocked by debris from the disaster. This incident can immediately restrict crucial supply distribution and affect rescue plans. Therefore, the recovery of damaged roads is an essential step to help increase the effectiveness of the relief operations and to reduce victims’ suffering. In this study, we develop a mixed-integer programming model for optimal scheduling and routing of repair crew and relief vehicles after the disaster. The objective function is to minimize the total relief time of the disaster-affected nodes and the recovery time of damaged nodes. Demand nodes are manually weighed according to a presumed degree of damage. Given the NP-hardness nature of the problem, a hybrid approach is proposed based on the Benders decomposition method and a heuristic algorithm. The heuristic algorithm is employed as an initiation algorithm to generate an initial solution for the Benders decomposition algorithm. The routing of the repair crew and relief vehicles is drawn using the Benders decomposition algorithm. To demonstrate the performance of the hybrid algorithm, an ant colony optimization algorithm is also developed. The computational results demonstrate that the proposed approach is capable of computing a near-optimal solution in less CPU time. Furthermore, the performance of this hybrid approach is distinctively superior when it comes to routing of medium to large-scale problems.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:328:y:2023:i:2:d:10.1007_s10479-023-05397-0
    DOI: 10.1007/s10479-023-05397-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-023-05397-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-023-05397-0?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. Gemma Berenguer & Pinar Keskinocak & J. George Shanthikumar & Jayashankar M. Swaminathan & Luk Van Wassenhove & Álvaro Lorca & Melih Çelik & Özlem Ergun & Pınar Keskinocak, 2017. "An Optimization-Based Decision-Support Tool for Post-Disaster Debris Operations," Production and Operations Management, Production and Operations Management Society, vol. 26(6), pages 1076-1091, June.
    2. 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.
    3. 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.
    4. 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.
    5. Ö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.
    6. Maya Duque, Pablo A. & Coene, Sofie & Goos, Peter & Sörensen, Kenneth & Spieksma, Frits, 2013. "The accessibility arc upgrading problem," European Journal of Operational Research, Elsevier, vol. 224(3), pages 458-465.
    7. Melih Çelik & Özlem Ergun & Pınar Keskinocak, 2015. "The Post-Disaster Debris Clearance Problem Under Incomplete Information," Operations Research, INFORMS, vol. 63(1), pages 65-85, February.
    8. Dhananjay Thiruvady & Andreas T. Ernst & Gaurav Singh, 2016. "Parallel ant colony optimization for resource constrained job scheduling," Annals of Operations Research, Springer, vol. 242(2), pages 355-372, July.
    9. 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.
    10. Altay, Nezih & Green III, Walter G., 2006. "OR/MS research in disaster operations management," European Journal of Operational Research, Elsevier, vol. 175(1), pages 475-493, November.
    11. Muhammad Salman Habib & Biswajit Sarkar, 2017. "An Integrated Location-Allocation Model for Temporary Disaster Debris Management under an Uncertain Environment," Sustainability, MDPI, vol. 9(5), pages 1-26, April.
    12. Dirk Briskorn & Alf Kimms & Denis Olschok, 2020. "Simultaneous planning for disaster road clearance and distribution of relief goods: a basic model and an exact solution method," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 591-619, September.
    Full references (including those not matched with items on IDEAS)

    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. 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).
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Hosseini, Yaser & Mohammadi, Reza Karami & Yang, Tony Y., 2024. "A comprehensive approach in post-earthquake blockage prediction of urban road network and emergency resilience optimization," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    9. 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).
    10. 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.
    11. Oruc, Buse Eylul & Kara, Bahar Yetis, 2018. "Post-disaster assessment routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 76-102.
    12. 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.
    13. Cheng, Cheng & Lu, Jia-Wei & Zhu, Rui & Xiao, Zuopeng & Costa, Alysson M. & Thompson, Russell G., 2022. "An integrated multi-objective model for disaster waste clean-up systems optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    14. Ulusan, Aybike & Ergun, Özlem, 2021. "Approximate dynamic programming for network recovery problems with stochastic demand," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 151(C).
    15. 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.
    16. 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.
    17. Yichen Lu & Chao Yang & Jun Yang, 2022. "A multi-objective humanitarian pickup and delivery vehicle routing problem with drones," Annals of Operations Research, Springer, vol. 319(1), pages 291-353, December.
    18. Diaz, Rafael & Behr, Joshua G. & Acero, Beatriz, 2022. "Coastal housing recovery in a postdisaster environment: A supply chain perspective," International Journal of Production Economics, Elsevier, vol. 247(C).
    19. 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).
    20. Abhishek Behl & Pankaj Dutta, 2019. "Humanitarian supply chain management: a thematic literature review and future directions of research," Annals of Operations Research, Springer, vol. 283(1), pages 1001-1044, December.

    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:spr:annopr:v:328:y:2023:i:2:d:10.1007_s10479-023-05397-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.