Project B18

Applications of Network Flows in Evacuation Planning

DFG Research Center Matheon Technische Universität Berlin
Duration: October 2007 - May 2010, May 2010 - May 2014
Project director: Prof. Dr. Martin Skutella
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.
Tel: +49 (0)30 - 314 78 654
email: skutella 'at' math.tu-berlin.de
Researcher: Martin Groß
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.
Tel: +49 (0)30 - / 314 27 448 
email: gross 'at' math.tu-berlin.de
Jan Philipp Kappmeier
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.
Tel: +49 (0)30 - / 314 78 658 
email: kappmeier 'at' math.tu-berlin.de
Ronald Koch
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.
Tel: +49 (0)30 - / 314 78 657 
email: koch 'at' math.tu-berlin.de
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)
Software: ZET Evacuation Tool (ZET)


Project description.

Background and Motivation.

Routing flow to optimize network performance is a fundamental problem arising in the management of large-scale traffic and communication networks. Many such problems can be modelled and solved efficiently by network flow techniques. On the other hand, it is often difficult or even impossible to impose optimal or near-optimal routing strategies on the traffic in a network since users of the network are free to act according to their own interests, without regard to overall network performance. In the sense of classical game theory, network users are independent agents participating in a noncooperative game. That is, they act in a purely selfish manner and we expect the routes chosen by users to form a Nash equilibrium (or user equilibrium).

Nash equilibria in static flow networks with latencies on the arcs are well studied and tight bounds on the "price of anarchy", which measures the quality of a selfish routing according to an optimal routing of a supervisor, are known. One main drawback of this model is that it only deals with static network flows. While static network flows are useful to model a variety of optimization problems, they fail to capture a crucial element of many routing problems: routing occurs over time. A flow over time specifies a flow rate entering an arc for each point in time.

Another crucial element in many applications is the variation of time taken to traverse an arc with the current (and maybe also past) flow situation on an arc. In the classical static flow setting this phenomenon can easily be taken into account by introducing cost (or latency) functions on the arcs (as mentioned above). But if we also allow flow variation over time, it is already a highly nontrivial problem to map these two aspects into an appropriate and tractable mathematical network flow model.

The goal of this project is to study Nash equilibria in networks with flow variation over time and thus to build a bridge between two important but so far seperate research areas that have moved into the focus of the network optimization community within the last years. We want to understand, model, and characterize the behavior of selfish users in traffic and communication networks. The expected results of this project can constitute an important building block for the future development of traffic management systems.

Research program.

Although many researchers have tried to generalize the model and results of static point of view to the setting of flows over time, nobody has even come up with a suitable mathematical model yet. The main problem here is the huge impact of the behavior of every single user on the entire system. In contrast to the static flow model the decision of one user X to change his route can potentially effect the transit times experienced by other users on arcs that are neither on the old nor on the new route of user X. Therefore even the existence of Nash equilibria is not obvious for almost all known models of flow-dependent transit times.

In [2] we present a reasonable model that seems to be suitable for our purposes. This model builds upon the assumption that the transit times of arcs are constant but each arc has bounded capacity such that only a limited number of users (flow particles) can enter the arc at every point in time. If more users wish to traverse an arc than the arc can handle, there is a waiting queue at the tail of the arc such that arriving users can enter the arc on a first-come, first-served basis. The length of the waiting queue and the transit time of an arc therefore add up to the actual flow-dependent transit time that is experienced by the users. This model is quite realistic for the case of communication networks. For road traffic networks it only roughly reflects the actual real-world situation. But on the other hand, very similar models are used in the context of road traffic simulation.

Within this project we want to achieve the following general goals:

  1. Prove existence and uniqueness results for Nash equilibria in the described model.
  2. Provide good characterizations of Nash equilibria and study their structural properties.
  3. Develop efficient algorithms for computing Nash equilibria.
  4. Implement these algorithms and obtain empirical results for real-world road networks.
  5. Prove upper and lower bounds on the price of anarchy.

Our approach will be to start with restricted special cases and then try to generalize/extend our observations to more general setting. Here we plan to proceed as follows:

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.

Regarding the Research Program we have answered all of questions for shortest path networks with a single source and sink (such networks include networks with zero transit times). For general single-source single-sink networks, we have given answers to 1. and 2. and partial answers to the other questions. The remaining challenges are proving that the developed algorithms are efficient, and showing upper bounds on the price of anarchy in these networks. An even bigger challenge is the multi-commodity setting with several sources and sinks; here all five questions are still open.

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.

For the case of shortest path networks we can compute Nash equilibria in polynomial time. Moreover, still for the case of shortest path networks, we show that dynamic Nash flows are earliest arrival flows; hence the price of anarchy is 1 in this case. For networks with arbitrary transit times the price of anarchy is Ω(m) where m is the number of arcs in the network. In this general case we have developed two algorithms, which we conjecture to have polynomial time complexity. We can currently prove that these iterative algorithms converge within an exponential number of steps.

Further results. We shortly mention selected further achievements on static and dynamic network flows that we have obtained during this funding period. We have successfully finalized and improved our work on computing earliest arrival flows (system optima) in networks with several sources with given supplies and a single sink. Various static network flow problems with constraints on the set of flow carrying paths are considered. We report on observations and results for using network flow techniques within a simulation tool for evacuation planning. We study flows over time in the more general setting of time-varying network parameters (e.g., time-varying capacities, transit times, costs etc.).

Publications.

[7] R. Koch, E. Nasrabadi and M. Skutella and A. Weber. Continuous and discrete flows over time. Mathematical Methods of Operations Research, to appear.
[7] M. Skutella and A. Weber. On the dominant of the s-t-cut polytope. Mathematical Programming, 124:441-454, 2010.
[1] N. Baumann and M. Skutella. Solving evacuation problems efficiently: Earliest arrival flows with multiple sources. Mathematics of Operations Research, 34(2):499-512, 2009.
[2] R. Koch and M. Skutella. Nash equilibria and the price of anarchy for flows over time. in Marios Mavronicolas (ed.): Proceedings of the 2nd International Symposium on Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 5814, pp. 323-334, Springer, Berlin, 2009.
[3] D. Dressler, M. Groß, J.-P. Kappmeier, T. Kelter, J. Kulbatzki, D. Plümpe, G. Schlechter, M. Schmidt, M. Skutella, and S. Temme. On the use of network flow techniques for assigning evacuees to exits. in Proceedings of the First International Conference on Evacuation Modeling(ICEM), 2009. Submitted.
[4] F. Salazar and M. Skutella. Single-source k-splittable min-cost flows. Operations Research Letters, 37(2):71-74, 2009.
[5] M. Skutella. An introduction to network flows over time. In W. Cook, L. Lovász, and J. Vygen (ed.): Research Trends in Combinatorial Optimization, pages 451-482. Springer, Berlin, 2009.
[6] R. Koch, M. Skutella, and I. Spenke. Maximum k-splittable s,t-flows. Theory of Computing Systems, 43(1):56-66, 2008.

Software.

[1] D. Dressler, M. Groß, M. Kabbash, J.-P. Kappmeier, S. Kardung, T. Kelter, J. Kulbatzki, D. Plümpe, M. Preuß, G. Schlechter, M. Schmidt, M. Skutella, S. Temme, and M. Woste. Software tool ZET developed in a student project on evacuation planning. 2008.

Outreach.

[1] H. Dambeck. Raus, Raus, Raus! Spiegel Online, 2009, Article based on an interview with M Skutella.
[2] R. Nestler. Panik, die große Unbekannte. Tagesspiegel, printed version, 17.06.2009, Article based on an interview with M Skutella.