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

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.