IDEAS home Printed from https://ideas.repec.org/p/hhs/nhhfms/2025_002.html
   My bibliography  Save this paper

Addressing Congestion in Time-Expanded Networks: A Lifeboat Allocation Model for Maritime Evacuations

Author

Listed:
  • Velez, Andres

    (Dept. of Business and Management Science, Norwegian School of Economics)

Abstract

This paper addresses the challenge of congestion in time-expanded networks, focusing on a case study related to maritime evacuations. The problem is made complex by an endogenous relationship between inputs and outputs, where the assignment of flow to an edge leads to increased congestion, which reflects in later arrivals and changes on the overall network topology. This dynamic interaction between flow and congestion is central to the problem, as it results in a feedback loop that complicates the identification of optimal evacuation paths. The study presents an iterative algorithm inspired by the network simplex method, designed to handle the evolving nature of congestion while minimizing evacuation time.

Suggested Citation

  • Velez, Andres, 2025. "Addressing Congestion in Time-Expanded Networks: A Lifeboat Allocation Model for Maritime Evacuations," Discussion Papers 2025/2, Norwegian School of Economics, Department of Business and Management Science.
    • Handle: RePEc:hhs:nhhfms:2025_002
    as

    Download full text from publisher

    File URL: https://hdl.handle.net/11250/3174247
    File Function: Full text
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bruce Hoppe & Éva Tardos, 2000. "The Quickest Transshipment Problem," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 36-62, February.
    2. Choi, W. & Hamacher, H. W. & Tufekci, S., 1988. "Modeling of building evacuation problems by network flows with side constraints," European Journal of Operational Research, Elsevier, vol. 35(1), pages 98-110, April.
    3. L. R. Ford & D. R. Fulkerson, 1958. "Constructing Maximal Dynamic Flows from Static Flows," Operations Research, INFORMS, vol. 6(3), pages 419-433, June.
    4. L. G. Chalmet & R. L. Francis & P. B. Saunders, 1982. "Network Models for Building Evacuation," Management Science, INFORMS, vol. 28(1), pages 86-105, January.
    5. Gopinath Mishra & Subhra Mazumdar & Arindam Pal, 2018. "Improved algorithms for the evacuation route planning problem," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 280-306, July.
    6. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    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. Francisco Pérez‐Villalonga & Javier Salmerón & Kevin Wood, 2008. "Dynamic evacuation routes for personnel on a naval ship," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(8), pages 785-799, December.
    2. Bretschneider, S. & Kimms, A., 2011. "A basic mathematical model for evacuation problems in urban areas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(6), pages 523-539, July.
    3. Jorge A. Huertas & Daniel Duque & Ethel Segura-Durán & Raha Akhavan-Tabatabaei & Andrés L. Medaglia, 2020. "Evacuation dynamics: a modeling and visualization framework," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 661-691, September.
    4. Nadine Baumann & Martin Skutella, 2009. "Earliest Arrival Flows with Multiple Sources," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 499-512, May.
    5. Yuya Higashikawa & Naoki Katoh, 2019. "A Survey on Facility Location Problems in Dynamic Flow Networks," The Review of Socionetwork Strategies, Springer, vol. 13(2), pages 163-208, October.
    6. Pursals, Salvador Casadesús & Garzón, Federico Garriga, 2009. "Optimal building evacuation time considering evacuation routes," European Journal of Operational Research, Elsevier, vol. 192(2), pages 692-699, January.
    7. Ismaila Abderhamane Ndiaye & Emmanuel Neron & Antoine Jouglet, 2017. "Macroscopic evacuation plans for natural disasters," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 231-272, January.
    8. Shin, Youngchul & Moon, Ilkyeong, 2023. "Robust building evacuation planning in a dynamic network flow model under collapsible nodes and arcs," Socio-Economic Planning Sciences, Elsevier, vol. 86(C).
    9. Urmila Pyakurel & Tanka Nath Dhamala, 2017. "Continuous Dynamic Contraflow Approach for Evacuation Planning," Annals of Operations Research, Springer, vol. 253(1), pages 573-598, June.
    10. Douglas Bish & Esra Agca & Roger Glick, 2014. "Decision support for hospital evacuation and emergency response," Annals of Operations Research, Springer, vol. 221(1), pages 89-106, October.
    11. Jian Li & Kaan Ozbay, 2015. "Evacuation Planning with Endogenous Transportation Network Degradations: A Stochastic Cell-Based Model and Solution Procedure," Networks and Spatial Economics, Springer, vol. 15(3), pages 677-696, September.
    12. Lovas, Gunnar G., 1995. "On performance measures for evacuation systems," European Journal of Operational Research, Elsevier, vol. 85(2), pages 352-367, September.
    13. Haghani, Milad, 2021. "The knowledge domain of crowd dynamics: Anatomy of the field, pioneering studies, temporal trends, influential entities and outside-domain impact," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 580(C).
    14. Simone Göttlich & Sebastian Kühn & Jan Peter Ohst & Stefan Ruzika, 2016. "Evacuation modeling: a case study on linear and nonlinear network flow models," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(3), pages 219-239, September.
    15. Melchiori, Anna & Sgalambro, Antonino, 2020. "A branch and price algorithm to solve the Quickest Multicommodity k-splittable Flow Problem," European Journal of Operational Research, Elsevier, vol. 282(3), pages 846-857.
    16. S Opasanon & E Miller-Hooks, 2009. "The Safest Escape problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1749-1758, December.
    17. Yosuke Hanawa & Yuya Higashikawa & Naoyuki Kamiyama & Naoki Katoh & Atsushi Takizawa, 2018. "The mixed evacuation problem," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1299-1314, November.
    18. Hong Zheng & Yi-Chang Chiu & Pitu B. Mirchandani, 2015. "On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems," Transportation Science, INFORMS, vol. 49(1), pages 13-27, February.
    19. Lim, Gino J. & Zangeneh, Shabnam & Reza Baharnemati, M. & Assavapokee, Tiravat, 2012. "A capacitated network flow optimization approach for short notice evacuation planning," European Journal of Operational Research, Elsevier, vol. 223(1), pages 234-245.
    20. Marc Goerigk & Ismaila Abderhamane Ndiaye, 2016. "Robust flows with losses and improvability in evacuation planning," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(3), pages 241-270, September.

    More about this item

    Keywords

    Onboard safety; Guidance system; Wireless communication; Lifeboat Assignment; Network flows;
    All these keywords.

    JEL classification:

    • C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:hhs:nhhfms:2025_002. 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: Stein Fossen (email available below). General contact details of provider: https://edirc.repec.org/data/dfnhhno.html .

    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.