IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v141y2020icp24-58.html
   My bibliography  Save this article

The heterogeneous multicrew scheduling and routing problem in road restoration

Author

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

Abstract

This paper introduces the heterogeneous multicrew scheduling and routing problem (MCSRP) in road restoration. The MCSRP consists of identifying the schedule and route of heterogeneous crews that must perform the restoration of damaged nodes used in the paths to connect a source node to demand nodes in a network affected by extreme events. The objective is to minimize the accessibility time defined as the time that the demand nodes remain unconnected from the source node. The main contributions of the paper include three novel mathematical formulations that differ in the way of modeling the scheduling decisions and the synchronization of the crews, and the development of valid inequalities based on some particular properties of the problem. Additionally, we prove that the MCSRP is NP-hard. Extensive numerical experiments with randomly generated instances and a case study based on floods and landslides disasters in Rio de Janeiro, Brazil, are performed to assess the efficiency and applicability of our approach. In particular, we show that the valid inequalities significantly improve the solvability of the mathematical models. In terms of managerial implications, our results suggest that the incorporation of multiple crews helps to reduce the worst-case accessibility times across the demand nodes, thus providing more equitable solutions.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:141:y:2020:i:c:p:24-58
    DOI: 10.1016/j.trb.2020.09.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261520303891
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2020.09.002?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. Morshedlou, Nazanin & González, Andrés D. & Barker, Kash, 2018. "Work crew routing problem for infrastructure network restoration," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 66-89.
    4. Kasaei, Maziar & Salman, F. Sibel, 2016. "Arc routing problems to restore connectivity of a road network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 177-206.
    5. 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.
    6. Rawls, Carmen G. & Turnquist, Mark A., 2010. "Pre-positioning of emergency supplies for disaster response," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 521-534, May.
    7. Hu, Shaolong & Han, Chuanfeng & Dong, Zhijie Sasha & Meng, Lingpeng, 2019. "A multi-stage stochastic programming model for relief distribution considering the state of road network," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 64-87.
    8. 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.
    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. Ö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.
    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. Quoc Trung Bui & Yves Deville & Quang Dung Pham, 2016. "Exact methods for solving the elementary shortest and longest path problems," Annals of Operations Research, Springer, vol. 244(2), pages 313-348, September.
    13. Moreno, Alfredo & Alem, Douglas & Ferreira, Deisemara & Clark, Alistair, 2018. "An effective two-stage stochastic multi-trip location-transportation model with social concerns in relief supply chains," European Journal of Operational Research, Elsevier, vol. 269(3), pages 1050-1071.
    14. Sahin, Halenur & Kara, Bahar Yetis & Karasan, Oya Ekin, 2016. "Debris removal during disaster response: A case for Turkey," Socio-Economic Planning Sciences, Elsevier, vol. 53(C), pages 49-59.
    15. 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.
    16. Nihal Berktaş & Bahar Yetiş Kara & Oya Ekin Karaşan, 2016. "Solution methodologies for debris removal in disaster response," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(3), pages 403-445, September.
    17. 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.
    18. 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.
    19. Alem, Douglas & Clark, Alistair & Moreno, Alfredo, 2016. "Stochastic network models for logistics planning in disaster relief," European Journal of Operational Research, Elsevier, vol. 255(1), pages 187-206.
    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. 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.
    2. 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).
    3. 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.
    4. Sina Nayeri & Zeinab Sazvar & Jafar Heydari, 2022. "A fuzzy robust planning model in the disaster management response phase under precedence constraints," Operational Research, Springer, vol. 22(4), pages 3571-3605, September.
    5. 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.
    6. Karen Castañeda & Omar Sánchez & Rodrigo F. Herrera & Guillermo Mejía, 2022. "Highway Planning Trends: A Bibliometric Analysis," Sustainability, MDPI, vol. 14(9), pages 1-33, May.
    7. 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).

    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. 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.
    3. 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.
    4. 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.
    5. 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.
    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. 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.
    8. 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.
    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. 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).
    11. 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.
    12. 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).
    13. 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.
    14. 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.
    15. 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.
    16. 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).
    17. 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).
    18. 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.
    19. Liu, Kanglin & Yang, Liu & Zhao, Yejia & Zhang, Zhi-Hai, 2023. "Multi-period stochastic programming for relief delivery considering evolving transportation network and temporary facility relocation/closure," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    20. Juliette García-Alviz & Gina Galindo & Julián Arellana & Ruben Yie-Pinedo, 2021. "Planning road network restoration and relief distribution under heterogeneous road disruptions," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 941-981, 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:eee:transb:v:141:y:2020:i:c:p:24-58. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.