This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Baumann, N. Articles by Skutella, M. Search for Related Content

Earliest Arrival Flows with Multiple Sources

TU Dortmund, Fakultät für Mathematik, 44221 Dortmund, Germany
TU Berlin, Institut für Mathematik, 10623 Berlin, Germany
nadine.baumann{at}udo.edu
skutella{at}math.tu-berlin.de

Earliest arrival flows capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink "as quickly as possible." The latter requirement is made more precise by the earliest arrival property, which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical result from the 1970s that, for the special case of a single source node, earliest arrival flows do exist and can be computed by essentially applying the successive shortest-path algorithm for min-cost flow computations. Although it has previously been observed that an earliest arrival flow still exists for multiple sources, the problem of computing one efficiently has been open for many years. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem.

Key Words: network flow; flow over time; earliest arrival flow; evacuation problem
History: Received: May 23, 2007; revision received: November 12, 2008;