Matheon B18: Applications of Network Flows in Evacuation Planning
- © DFG Matheon
|Duration:||October 2007 - May
2010, May 2010 - May 2014|
|Project heads:||Martin Skutella
|Researcher:||Martin Groß |
Jan-Philipp Kappmeier 
|Former researcher:||Ronald Koch
|Support:||DFG Research Center
"Mathematics for Key Technologies" (Matheon
Evacuation, the process of moving people out of
potentially dangerous areas, is a key response to many threats.
Planning such an evacuation is therefore important, especially in
large-scale emergencies, where routing becomes non-trivial. This
projects deals with the optimization and simulation of the evacuation
In practice, evacuation planning is usually done with the help of simulation tools that build upon particle systems and social force models, cellular automata, and multi-agent systems. These tools are able and mostly built to give a realistic evaluation of particular evacuation scenarios. Their common drawback are the rather long computation times and the fact that their only optimization potential lies in iteratively evaluating and comparing different scenarios.
Routing flow optimally in order to improve network performance is an important and successful approach in many large-scale traffic and communication networks. Network flows have been proven to be a useful tool to model and solve many of these problems. One of the main advantages is that network flows can be computed very efficiently even in huge networks as they show up in various real-world applications.
However, in the standard model of network flows, there is no temporal dimension. As a consequence, aspects like flow variation over time, flow travel time and delays cannot be modeled by them directly. Flows over time (also called dynamic flows) solve this problem by introducing transit times as an attribute for arcs.
In the context of flows over time, earliest arrival flows capture an important goal 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. Three different objectives can be achieved simultaneously: (1) Minimizing the total time needed to send the supplies of all sources to the sink, (2) fulfilling the earliest arrival property, and (3) minimizing the average time for all flow needed to reach the sink. Although network flow based approaches to evacuation planning have been studied in the literature, flows over time have not been incorporated into evacuation planning tools yet.
Besides the inherent temporal dimension of evacuation planning, there are many more characteristics that cannot be modeled with standard network flows or flows over time. It is therefore necessary to come up with more general network flow models that are able to capture important aspects of evacuation planing. For example, it is often difficult or even impossible to impose optimal or near-optimal routing strategies on users of a network (like, e.g., evacuees) who are free to act according to their own interests, without regard to overall network performance. In a seminal paper Roughgarden and Tardos study Nash equilibria in static flow networks with latencies on the arcs and prove bounds on the "price of anarchy''. Models for dynamic Nash equilibria exist as well but these models are computationally intractable.
The main focus of the project
will be on applying network flow techniques in evacuation planning and
general pedestrian traffic. Our main goal is to bridge the gap between
simulation based and optimization based approaches. The software
package ZET  provides an excellent basis since it features both a
cellular automaton for realistic evacuation simulations and a graph
model for network flow computations. Thus, with the help of
simulations we can immediately verify and test results obtained by
network flow computations. So far we have obtained preliminary results
on assigning evacuees to emergency exits of a building based on static
and dynamic network flow computations. These results are promising and
show the great potential of our approach. We will consider the
following questions and problems: (a) determining good estimates for
evacuation times and other characteristics quickly (faster than
simulation); (b) assigning evacuees to emergency exits; (c)
determining good evacuation routes under various side constraints; (d)
identifying and avoiding bottlenecks; (e) analyzing and optimizing
pedestrian traffic in more general situations (not only evacuation).
We expect that our insights and results on Nash flows will turn out to
be particularly useful in (a) and (d).
In order to be able to solve the above questions in a satisfying way, we have to develop and study refined network flow models that capture essential characteristics of pedestrian traffic more precisely than standard network flows. The most important examples are: (1) more general Nash flows over time under various assumptions on individual behavior; (2) confluent network flows (evacuation routes); (3) flows over time with commodity-dependent transit times (individual traits of persons); (4) network flows over time with aggregate arc capacities (bounds on the number of persons that can travel along an arc simultaneously); (5) earliest arrival flows with multiple sinks - existence and characterization of suitable networks. For all of the above mentioned network flow models we will study their complexity and aim at developing theoretically as well as practically efficient algorithms that can be implemented within ZET.
We were able to characterize, analyze, and compute Nash equilibria in networks with flow variation over time. Our work builds a bridge between two important but so far separate research areas that have moved into the focus of the network optimization community within the last years: flows over time and Nash equilibria. We have introduced a suitable mathematical model for Nash equilibria in the context of flows over time. This model is closely related to well-studied models in road-traffic simulation. Among other results, we presented bounds on the price of anarchy for our model (see [KochSkutella2009]).
We have succeed in defining Nash equilibria and in proving that there always exists a unique Nash equilibrium even if capacities of arcs vary over time. In our context, system optima are given by earliest arrival flows which are computable efficiently. Considering the amount of flow that has arrived in the sink at time θ in an earliest arrival flow and in a Nash flow, and choosing the worst ratio between these values over all θ defines the price of anarchy.
Network flows over time model the temporal dynamics of network flow
problems occurring in a wide variety of applications. Research in this
area has been pursued in two different and mainly independent
directions with respect to time modeling: discrete and continuous time
models. In [KochNasrabadiSkutella2011] we deploy measure theory in
order to introduce a general model of network flows over time
combining both discrete and continuous aspects into a single model.
Here, the flow on each arc is modeled as a Borel measure on the real
line (time axis). In [KochNasrabadi2011] we formulate the maximum
Borel flow as an infinite dimensional linear program in a space of
measures. We define a dual problem and prove a strong duality result.
We show that strong duality is closely related to a MaxFlow-MinCut
When studying the behavior of people in an evacuation scenario we recognize among others the following aspects. First, everyone acts egoistic according to leave the evacuation area as fast as possible. And second, the time needed for traversing the network is not constant over time due to congestion effects, for example. Both aspects are not covered by standard flow over time models. In fact, we need a flow over time model where transit times vary over time depending on the flow behavior which enables us to consider the egoistic selfish routing. Based on a very general flow model we define so called consistent flow over time models.
The class of consistent flow models contains the very popular deterministic queuing model (see [KochSktuella2011]). We characterize Nash equilibria and it turns out that they are not unique. The price of stability is the ratio between the best Nash equilibrium and a system optimum with respect to some objective functions. For evacuation scenarios a natural objective function is the amount of flow which has arrived at the sink until some given point in time. In order to compute the price of stability we extend the well-known successive shortest path algorithm constructing an earliest arrival flow to the case of time-varying capacities. In total, we compute the price of stability for four different objective functions which are all optimized by an earliest arrival flow.
A more applied track of research is pursued in [DresslerGrossKappmeier+2010] where we present a method to assign evacuees to exits they should use in a building evacuation using both, static min cost flow and flows over time. The results are compared with each other and a different approach using game theoretic methods. We show that both flow based approaches have advantages and disadvantages in certain structures in the network representing the building. The effect of the exit choice has been verified using simulation with our software tool ZET .
It is well known that earliest arrival flow does not always exist in networks with several sources and sinks. In [SchmidtSkutella2011] we give a first characterization of networks that permit an earliest arrival flow even in the case of multiple sinks, if all arcs have zero transit time.
In [GrossSkutella2012], we study the concept of generalized flows over time and show that, while the problem is hard in general, there is a practically efficient FPTAS for an interesting special case. We further highlight structural similarities to the earliest arrival flow problem. We hope that we can exploit these similarities further; and we want to use generalized flows themselves to deal with lossy networks in evacuation settings. An example for loss in such scenarios is expected loss on arcs with a failure probability.
In [DresslerSkutella2011], we study the arc capacity model of Melkonian, where the flow of an arc is not bounded by a capacity for the flow entering an arc, but by a capacity for the total flow on an arc. Such capacities are of particular relevance in congested networks that occur frequently in evacuation scenarios. We present a generalization of both the classical model and Melkonian's model and describe an FPTAS for it. In [DresslerFloetteroedLaemmel+2011], we study an approach for evacuation optimization based on a two-stage algorithm, using a customized minimum cost flow algorithm that is then refined towards a Nash equilibrium or a marginal social cost based approach. We then test this approach on a scenario based on the city of Padang, in Indonesia that is frequently threatened by tsunamis.
To verify the quality of the simulation and check the quality of the estimated evacuation time obtained by the earliest arrival flow computation in ZET, we modeled a large multi storied building belonging to university (the "Telefunkenhochhaus'') and measured the evacuation times in a test evacuation in cooperation with the SDU team of TU Berlin. The results show, that the obtained evacuation times of the network flow algorithms are indeed lower bounds of the actual evacuation times. The results also show that the evacuation times are small, compared to the actual and simulated evacuation times. Test simulations show that this happens because commodity dependent transit times are not yet incorporated in the network flow model we use.
|Author||Koch, Ronald and Skutella, Martin|
|Title of Book||Proceedings of the 2nd International Symposium on Algorithmic Game Theory|
|Editor||Mavronicolas, Marios and Papadopoulou, Vicky G.|
|Series||Lecture Notes in Computer Science|