Fast and memory-efficient algorithms for evacuation problems

We study two classical flow over time problems that capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs and sources/sinks with supplies/demands, a quickest transshipment sends the supplies from the sources to meet the demands at the sinks as quickly as possible. In a 1995 landmark paper, Hoppe and Tardos describe the first strongly polynomial time algorithm solving the quickest transshipment problem. Their algorithm relies on repeatedly calling an oracle for parametric submodular function minimization. We present a somewhat simpler and more efficient algorithm for the quickest transshipment problem. Our algorithm (i) relies on only one parametric submodular function minimization and, as a consequence, has considerably improved running time, (ii) uses not only the solution of a submodular function minimization but actually exploits the underlying algorithmic approach to determine a quickest transshipment as a convex combination of simple lex-max flows over time, and (iii) in this way determines a structurally easier solution in the form of a generalized temporally repeated flow. Our second main result is an entirely novel algorithm for computing earliest arrival transshipments, which feature a particularly desirable property in the context of evacuation planning. An earliest arrival transshipment which in general only exists in networks with a single sink - is a quickest transshipment maximizing the amount of flow which has reached the sink for every point in time simultaneously. In contrast to previous approaches, our algorithm solely works on the given network and, as a consequence, requires only polynomial space.