direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Matheon B18: Applications of Network Flows in Evacuation Planning

Lupe

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)

Project Description

Background

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 process.

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.

Research Program

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.

Project Output

Results

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 Theorem.

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.

Publications

[BaierErlebachHall+2010]

Baier, Georg and Erlebach, Thomas and Hall, Alex and Köhler, Ekkehard and Kolman, Petr and Pangr\?ac, Ond\vrej and Schilling, Heiko and Skutella, Martin.
Length-Bounded Cuts and Flows.
ACM Transactions on Algorithms  7, 4, 2010.


[BaumannSkutella2009]

Baumann, Nadine and Skutella, Martin.
Solving Evacuation Problems Efficiently: Earliest Arrival Flows with Multiple Sources.
Mathematics of Operations Research  34, 499–512, 2009.


[DresslerFloetteroedLaemmel+2011]

Dressler, Daniel and Flötteröd, Gunnar and Lämmel, Gregor and Nagel, Kai and Skutella, Martin.
Optimal Evacuation Solutions for Large-Scale Scenarios.
In Operations Research Proceedings 2010, 239–244. Springer, 2011.  


[DresslerGrossKappmeier+2010]

Dressler, Daniel and Groß, Martin and Kappmeier, Jan-Philipp and Kelter, Timon and Kulbatzki, Joscha and Plümpe, Daniel and Schlechter, Gordon and Schmidt, Melanie and Skutella, Martin and Temme, Sylvie.
On the use of network flow techniques for assigning evacuees to exits.
In Proceedings of the International Conference on Evacuation Modeling and Management, Procedia Engineering 3, 205–215. Elsevier Ltd, 2010.  


[DresslerSkutella2010]

Dressler, Daniel and Skutella, Martin.
An FPTAS for Flows over Time with Aggregated Arc Capacities.
In Jansen, Klaus and Solis-Oba, Roberto (ed.)SIAM Approximation and Online Algorithms, 8th International Workshop, WAOA 2010, Liverpool, United Kingdom, September 2010. Revised Papers, , 106–117. Springer, 2011.  


[KochNasrabadiSkutella2011]

Koch, Ronald and Nasrabadi, Ebrahim and Skutella, Martin.
Continuous and discrete flows over time.
Mathematical Methods of Operations Research , 2011.
To appear.


[KochSkutella2009]

Koch, Ronald and Skutella, Martin.
Nash Equilibria and the Price of Anarchy for Flows Over Time.
In Mavronicolas, Marios and Papadopoulou, Vicky G. (ed.)SIAM Proceedings of the 2nd International Symposium on Algorithmic Game Theory, , 323–334. Springer, 2009.  


[KochSkutella2011]

Koch, Ronald and Skutella, Martin.
Nash Equilibria and the Price of Anarchy for Flows Over Time.
Theory of Computing Systems  49, 71–97, 2011.


[KochSkutellaSpenke2008]

Koch, Ronald and Skutella, Martin and Spenke, Ines.
Maximum k-Splittable s,t-Flows.
Theory of Computing Systems  43, 56–66, 2008.


[SalazarSkutella2009]

Salazar, Fernanda and Skutella, Martin.
Single-source k-splittable min-cost flows.
Operations Research Letters  37, 71–74, 2009.


[SchmidtSkutella2010]

Schmidt, Melanie and Skutella, Martin.
Earliest Arrival Flows in Networks with Multiple Sinks.
Electronic Notes in Discrete Mathematics  36, 607–614, 2010.
ISCO 2010 – International Symposium on Combinatorial Optimization.


[Skutella2009]

Skutella, Martin.
An Introduction to Network Flows Over Time.
In Cook, William and Lovász, László and Vygen, Jens (ed.)SIAM Research Trends in Combinatorial Optimization, , 451–482. Springer, 2009.  


[SkutellaWeber2010]

Skutella, Martin and Weber, Alexia.
On the dominant of the s-t-cut polytope.
Mathematical Programming  124, 441–454, 2010.


[GrossSkutella2012]

Groß, Martin and Skutella, Martin.
Generalized Maximum Flows over Time.
In Proceedings of the 9th Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science 7164, 247–260. Springer, 2012.  


[KochNasrabadi2011]

Koch, Ronald and Nasrabadi, Ebrahim.
Strong Duality for the Maximum Borel Flow Problem.
In Network Optimization – 5th International Conference, INOC 2011, Lecture Notes in Computer Science 6701, 256–261. Springer, 2011.  


[SchmidtSkutella2011]

Schmidt, Melanie and Skutella, Martin.
Earliest arrival flows in networks with multiple sinks.
Discrete Applied Mathematics , 2011.
http://www.sciencedirect.com/science/article/pii/S0166218X11003593.


[GrossKappmeierSchmidt+2012]

Groß, Martin and Kappmeier, Jan-Philipp W. and Schmidt, Melanie and Schmidt, Daniel.
Approximating Earliest Arrival Flows in Arbitrary Networks.
In Epstein, Leah and Ferragina, Paolo (ed.)SIAM Algorithms – ESA 2012, , 551-562. Springer Berlin / Heidelberg, 2012.  


[KappmeierMatuschkePeis2012]

Kappmeier, Jan-Philipp W. and Matuschke, Jannik and Peis, Britta.
Abstract flows over time: A first step towards solving dynamic packing problems.
In Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings, Lecture Notes in Computer Science, 433-443. Springer, 2012.  


[GuentherMaurerMegow+2013]

Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas.
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.
In Proceedings of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), 118-128, 2013.  


[GrossSkutella2012a]

Groß, Martin and Skutella, Martin.
Maximum Multicommodity Flows over Time without Intermediate Storage.
In Epstein, Leah and Ferragina, Paolo (ed.)SIAM Algorithms – ESA 2012, , 539-550. Springer Berlin / Heidelberg, 2012.  


Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions