This version is available at https://doi.org/10.14279/depositonce-7730
This work is licensed under a CC BY-NC-ND 4.0 License (Creative
Commons Attribution-NonCommercial-NoDerivatives 4.0 International). For
more information see https://creativecommons.org/licenses/by-nc-nd/4.0/.
Terms of Use
Lämmel, G., Grether, D., & Nagel, K. (2010). The representation and implementation of time-dependent
inundation in large-scale microscopic evacuation simulations. Transportation Research Part C: Emerging
Technologies, 18(1), 84–98. https://doi.org/10.1016/j.trc.2009.04.020
Gregor Lämmel, Dominik Grether, Kai Nagel
The representation and implementation of
time-dependent inundation in large-scale
microscopic evacuation simulations
Accepted manuscript (Postprint)Journal article |
The representation and implementation of
time-dependent inundation in large-scale microscopic
evacuation simulations
Gregor L¨ammel∗, Dominik Grether, Kai Nagel
Transport Systems Planning and Transport Telematics, Berlin Institute of Technology,
10587 Berlin, Germany
Abstract
Multi Agent Simulation has increasingly been used for transportation simula-
tion in recent years. With current techniques, it is possible to simulate systems
consisting of several million agents. Such Multi Agent Simulations have been
applied to whole cities and even large regions. In this paper it is demonstrated
how to adapt an existing multi agent transportation simulation framework to
large-scale pedestrian evacuation simulation. The underlying flow model simu-
lates the traffic based on a simple queue model where only free speed, bottleneck
capacities, and space constraints are taken into account. The queue simulation,
albeit simple, captures the most important aspects of evacuations such as the
congestion effects of bottlenecks and the time needed to evacuate the endangered
area. In the case of an evacuation simulation the network has time dependent
attributes. For instance, large-scale inundations or conflagrations do not cover
all the endangered area at once.
These time dependent attributes are modeled as network change events.
Network change events are modifying link parameters at predefined points in
time. The simulation framework is demonstrated through a case study for the
Indonesian city of Padang, which faces a high risk of being inundated by a
tsunami.
Key words: multi agent simulation, large-scale evacuation simulation, time
dependent network
1. Introduction
The evacuation of whole cities or even regions is an important problem, as
demonstrated by recent events such as the evacuation of Houston in the case
of Hurricane Rita or the evacuation of coastal cities in the case of tsunamis.
∗Corresponding author. fon: +49 30 31421376; fax: +49 30 31426269
Preprint submitted to Transportation Research C March 18, 2009
One example for a highly vulnerable area is the city of Padang, West Sumatra,
Indonesia. Sumatra’s third largest city is located directly on the coast and
partially sited beneath the sea level, and thus is located in a zone of extreme
risk due to severe earthquakes and tentatively triggered tsunamis. The city
of Padang has been hit by tsunamis in the past. The most well documented
tsunamis are the ones from 1797 and 1833 [49]. Both tsunamis inundated large
parts of the city. However, these past tsunami events are hardly comparable
with the current local situation due to major changes in land use pattern. What
is more, population figures have risen strongly. Today the city has approx.
1,000,000 inhabitants and the most densely populated parts of the city are
located directly at the shore line.
The “Last-Mile Evacuation” research project [6, 41] develops a numerical
last mile tsunami early warning and evacuation information system on the basis
of detailed earth observation data and techniques as well as unsteady,
hydro-numerical modeling of small-scale flooding and inundation dynamics
of the tsunami, combined with evacuation simulations in the urban coastal hin-
terland for the city of Padang.
Since the advance warning time before the tsunami wave reaches the coast
line is only 20-40 minutes, the evacuation must be as quick as possible. Even if
not all of the estimated 1,000,000 inhabitants need to be evacuated, the number
of evacuees could be hundreds of thousands. Therefore a detailed analysis of
aspects that could influence the evacuation process is necessary. With this
analysis it should be possible to:
•Give an estimate of the evacuation time.
•Detect bottlenecks that could for example emerge at bridges.
•Detect highly endangered areas, where a vertical evacuation1seems the
only way.
Because of the complexity of the system, an analytic solution to this problem
seems to be hard. Therefore a microscopic multi-agent simulation for the city
with all its inhabitants has been developed.
Congruent with the importance of the topic, there is a large body of research
regarding emergency evacuations. As a first classification, one may differentiate
between two situations: (i) evacuation from within buildings, ships, airplanes,
etc.; (ii) large-scale citywide or regional evacuations, e.g. because of nuclear
power plants failures or because of hurricanes. Case (i) usually concerns pedes-
trian evacuation; case (ii) usually uses traffic-based evacuation.
Ongoing research concerns citywide or regional evacuations, i.e. case (ii).
The development of these tools was much influenced by the development of tools
in the areas of transport planning and traffic management. At the core of many
of these methods is a static assignment routine (e.g. [61, 52]). A typical example
1quake and tsunami proof shelters
2
for traffic-based evacuation simulation based on static concepts is MASSVAC
[29] although later versions contain dynamic aspects.
A shortcoming of static assignment is that it does not possess any consid-
eration of the time-of-day dynamics. In contrast, dynamic traffic assignment
(DTA) is defined as a distribution of time-dependent trips on routes. A typical
approach to implement DTA is day-to-day re-planning: The traffic flow simu-
lation (also called network loading) is run with pre-specified routes, route costs
are extracted, some or all of the routes are modified, the traffic flow simulation
is run again, etc., until some stopping criterion is fulfilled. Examples of stopping
criteria are that either every trip uses a route which minimizes expected travel
time (time-dependent Nash equilibrium), or it selects between different route al-
ternatives following a pre-specified distribution function (time-dependent SUE).
Many DTA packages have been tested in the evacuation context: MITSIM
[33], Dynasmart [39, 11], PARAMICS [10], and VISSIM [25]. Oak Ridge Na-
tional Laboratory has a package named “OREMS” [51] explicitly for evacuation
traffic. Publications stressing dynamic aspects of traffic-based evacuation as a
novelty can be found with dates as recent as 2000, e.g. [57, 3]. For a review, see
[2].
A good overview of pedestrian evacuation modeling and software can be
found in the books of the bi-annual conference series “Pedestrian and Evac-
uation Dynamics” [60, 16, 17, 1]. Pedestrian evacuation simulations can be
classified into microscopic and macroscopic ones. Microscopic models repre-
sent space, time, and persons on a fine-grained level. Possible microscopic
approaches are Cellular Automata (CA) [36], discretized differential equations
(“molecular dynamics (MD)”) [27, 26], or movement rules based on random util-
ity modelling [4]. Examples of software packages based on microscopic models
are Exodus [15], Myriad (www.crowddynamics.com), Egress (www.aeat-safety-
and-risk.com/html/egress.html), and PedGo [35]. Macroscopic models use the
analogy of flows of pedestrians and liquids. Examples of software packages
based on macroscopic models are Aseri [59] and Simulex (www.iesve.com). See
Refs. [32] and [38] for surveys. Compared to what is known in terms of field
measurements (e.g. [55, 68]), most if not all packages lead to similar results [56].
A large body of work (e.g. [67, 43]) uses microsimulation to investigate the
issues of contraflow evacuation, i.e. the reversal of inbound lanes of a freeway
in order to obtain additional outbound capacity. In contrast, little work seems
to exist that specifically deals with evacuation using other modes of transport
than walking for the evacuation of confined spaces, or driving for the evacua-
tion of cities or regions. Ref. [24] describes mixed evacuation traffic, geared to
Taiwanese requirements.
Once the movement model is selected, it is necessary to define the evacuation
directions. For more complex geometries, this is no longer a single movement
towards one or two exits, but may involve rather complex movments in a building
or in a street network. The arguably simplest solution is a grid-based potential
function where the “uphill direction” leads to the nearest exit [50]. The same
can be done using essentially continous spatial variables, at the expense of much
larger computing times [30]. Alternatively, routing can be done along graphs
3
[23, 20], which is a much faster technique when the abstraction to a graph is
possible.
A further distinction is if travelers can re-route while they are on their way
(within-day re-planning; en-route re-planning), or only before their trip (day-to-
day re-planning; pre-trip re-planning) [8]. Clearly, en-route re-planning capa-
bility is more realistic. It is, however, also more demanding: Adaptation of the
plans needs to be called frequently from within the network loading, rather than
only having to alternate between the network loading and the mental layers as
one does in day-to-day re-planning.
A recent development regarding pedestrian evacuation is that more behav-
ioral aspects are added. For example, people may discard the warning as irrel-
evant; they may not head for the nearest exit; people have a tendency to follow
each other (herding) [28, 42]. This is matched by a recent tendency, often by
agent-oriented software engineering groups, to make the simulated agents more
complex in order to include these behavioral aspects [48, 54]. There seems to
be universal agreement that these behavioral aspects increase evacuation times;
simulations with reduced behavioral aspects can, in consequence, still be used
as an optimistic benchmark.
To our knowledge, none of the above approaches is able to simulate large-
scale scenarios (with millions of entities) while remaining microscopic: With a
CA model, an area of 40 km×40 km translates into 1010 cells. Even if every cell
only needs 1 Byte, this still translates into 10 GByte of memory, resulting in
large simulation times. For the MD approach, the problem are the sub-second
time resolutions that are typically used [14]. DTA approaches seem the most
likely candidates, but to our knowledge their implementation of the traffic flow
dynamics usually is still too time-consuming for scenarios of that size:
Ref. [58] reports a study using Dynasmart-P consisting of 1347 nodes and
3004 links. 200,000 vehicles were loaded onto the network. The runtime for
about 30 iterations of 2 hours of simulation was almost 8 hours. This means
running one iteration with this 1347 nodes/ 3004 links scenario takes about
16 minutes. If the runtime scales with the scenario size it would be very time
consuming to run larger scenarios. In Ref. [69], the DynaMIT framework was
applied to a real-time scenario but on a small network (243 nodes and 606 links).
In that study a rolling horizon approach was chosen to have a 5 min estimation
and 30 min prediction on that network. Two iterations of estimation and two
iterations of prediction took about 1 min. If the runtime scales with the size of
the network the performance is comparable to the Dynasmart-P approach and
again too slow for large-scale scenarios.
One way to achieve faster computation with a microscopic model is to use
a model with deliberately large time steps and to computationally concentrate
on those areas (links) where the pedestrian movement actually takes place [21].
Another approach is based up on a modified queuing model [18, 62]. The queu-
ing model simplifies streets to edges and crossings to nodes; the difference to
standard queuing theory is that agents (particles) are not dropped but spill
back, causing congestion. This graph-oriented model is defined by free speed,
flow capacity, and storage capacity of the edges. This simplification leads to a
4
major speedup of the simulation while keeping results realistic. The combina-
tion of these two approaches (switching off unused links; queue model) is used
in this paper, and leads to computing speeds of about 2 min per iteration for
320 000 agents on 17 000 links.
Additional speed-ups could be gained by parallel computing [9]. On dis-
tributed architectures, however, it is necessary to serialize/de-serialize objects
that move from one CPU to another. When done automatically (e.g. [63]), we
have always found that this is rather slow and thus only suitable for scenarios
where there is little communication compared to the communication; when done
manually, it causes considerable software engineering overhead across the whole
MATSim project. Shared-memory architectures were in the past quite expen-
sive, but the recent emergence of multi-core architectures and GPUs (graphical
processing units) may be attractive options. For first steps in these directions
in the context of transportation/pedestrian projects, see matsim.org/node/238
or [64].
In the case of an evacuation simulation the network has time dependent at-
tributes. For instance, large-scale inundations or conflagrations do not cover all
the endangered area at once. One solution is to model this as a time dependent
network. Time dependent networks have been applied to evacuation planning
[44] and are often modeled as time expanded graphs [34, 53, 37]. In a time ex-
panded graph every node/edge is replicated for every time step t= 0,1, . . . , T,
and additional links are connecting the nodes between the time steps. In con-
trast, so-called time-aggregated graphs [19] omit the explicit time expansion,
and rather use a time-dependent look-up of the link cost. The notation of
that reference implies Ttime intervals which apply uniformly to all links; their
O(log T) time complexity of the link cost lookup implies that these time intervals
need not to be equally spaced.
Yet, in the case of a tsunami inundation, the structure of the link cost
changes is quite different: There is, at least in an abstract interpretation, only
a switch from “passable” to “non-passable”, but that switch can happen at
arbitrary times. With the above techniques, one would either need as many
time intervals Tas there are such switches, or several switches would need to
be combined into one time bin. In order to avoid these restrictions, this paper
introduces the following approach:
•The interface, containing the calls to the network attributes, in particular
link speeds, link capacities, and link widths, is made time-dependent, al-
lowing the implementation of arbitrary time-dependent functions behind
the interface. This corresponds to the time-aggregated graph technique.
•The implementation presented here uses so-called network change events.
The change events are applied to the edges, modifying their attributes
(free speed, flow capacity) at arbitrary points in time. A change event is
valid until the next change event will be applied.
In this paper we give a description of the simulation framework with a focus
on the time dependent aspects. The performance of the simulation framework
5
is demonstrated through a case study of the Indonesian city of Padang that
faces a high risk of being inundated by an earthquake-triggered tsunami. This
work is part of the numerical last-mile tsunami early warning and evacuation
information system project (“Last-Mile–Evacuation”) [5, 41].
The remainder of the paper is organized as follows. Section 2 gives an
overview of the simulation framework with a detailed description of the time
dependent aspects. In Section 3, we describe the evacuation scenario that was
chosen to demonstrate the simulation framework. Section 4 presents the results
of the simulation with respect of the computing performance and the evacuation
results. After a short discussion in Section 5, we conclude our work and give
some information about future work.
2. Simulation framework
The simulation framework is based on the MATSim framework for transport
simulation [45]. MATSim is implemented in Java. Since its current implemen-
tation is focused on simulation of daily motorized traffic, several adaptations
were necessary. The key elements of MATSim are:
•The agent database, where every agent represents one evacuee.
•The simulation network, based on links and nodes.
•The traffic flow simulator, where all the agents’ plans are executed.
•The plans generator, which generates an escape plan for every agent.
•There is a mechanism that allows improving the performance of the agents’
plans by repeatedly trying to find faster evacuation routes.
2.1. Synthetic population, plans, agent database
MATSim always starts with a synthetic population. A synthetic population
is a randomly generated population of individuals which is based as much as
possible on existing data such as census data. For evacuation, the synthetic
population is the collection of all synthetic individuals that are involved in the
evacuation.
Every synthetic individual possesses one or several plans. These plans are
“intentions” of the synthetic individuals, to be tested in the traffic flow simu-
lation (described later), and scored afterwards. For evacuation, the plans are
evacuation strategies. For example, such a strategy may be to leave the building
5 minutes after a second warning, and follow a predetermined route to safety.
The collection of agents together with their plans is sometimes called an agent
database.
People can have different positions within the city when a warning occurs.
For example, they can be at home or at work. Therefore, also in the evacuation
context it makes sense to consider MATSim plans in their more conventional
meaning, as a description on what a synthetic traveller intends to do during a
6
normal day. One can then run a regular traffic flow simulation with these plans,
stop it at the time of an evacuation warning, and use the positions of all agents
at the time of that warning as the initial condition to the evacuation. This will
be the subject of future work.
2.2. Time-varying network
The simulation network represents the area that is accessible by the evacuees.
In the case of a vehicular evacuation this network consists of all accessible streets.
Each street segment defines a link. The parameters of the links are the length,
capacity and the free flow speed. For a pedestrian evacuation the links in the
simulation network also consist of squares and sidewalks. The flow capacity is
given by the width of a link as described in the next section. A good way of
creating the simulation network is by extracting the needed information from
satellite imagery [66].
For evacuation simulations the network has two kinds of time-varying as-
pects. First there are the disaster related aspects (i.e. time dependent blocking
of links). And second there is the information about (experienced) link travel
times, caused by congestion. The time dependent congestion effects are impor-
tant for the agent replanning (discussed in Sec. 2.5), while the disaster related
aspects are also important for the initial plans generation (see Sec. 2.4) and the
traffic flow simulator (see Sec. 2.3). Since the object of this work is to develop
an evacuation simulation framework for large-scale scenarios, the time-varying
aspects should be handled in an efficient way.
2.2.1. Using arrays for the storage and retrieval of network change events
The disaster related time-varying aspects are modeled as network change
events. A network change event modifies parameters of a link in the network
(e.g. free speed or flow capacity). As soon as a link is no longer passable its free
speed will be set to zero.
Listing 1 Sample network change event: valid from 03:06 AM, applied to links
with id 12487, 12489 and 12491. The change event sets the free speed of the
corresponding links to zero.
<networkChangeEvent startTime="03:06:00">
<link refId="12487"/>
<link refId="12489"/>
<link refId="12491"/>
<freespeed type="absolute" value="0.0"/>
</networkChangeEvent>
The network change events are stored independent from the network in a
separate XML file. Listing 1 shows a sample network change event. The event
manipulates the links 12487, 12489 and 12491 at 03:06 AM by setting the free
speed to 0 m/s. The change values are in SI based units.
7
The network change events file are loaded at simulation start up and the
network change events will be applied to the corresponding links. The attributes
of the links that can be influenced by the change events are accessed by time
dependent getter methods (e.g. getFreespeed(double time)). These getter
methods retrieve the value that is valid for the query time. If there exists a
network change event for the given query time, then the value of this network
change event will be returned. But, as discussed in Sec. 1, it is not expected
that a network change event exists for every link and every time step. If for
a given query time no network change event exists, then the value of network
change event with the next smaller event time will be returned. The time
dependent getter methods give the flexibility to query the attributes in arbitrary
chronology.
As a consequence of this flexibility, the retrieval mechanism is not straight
forward. Two different approaches have been tested. The first approach that
has been tested is to store the network change events in a Java TreeMap. The
Java TreeMap implements a red-black tree with a complexity of O(log n) for get
operations. The second approach that has been tested is to store the network
change events in an array in chronological order and use a binary search to find
the corresponding entry. The complexity for a binary search is also a O(log n).
However, the Java TreeMap cannot operate on primitives (double, int) but the
primitives have to be converted into objects (Double, Integer). Since Java 5
this conversion is done automatically (autoboxing). The autoboxing mechanism
gives the software developer more flexibility, but produces an overhead that in-
creases the run time. A small benchmark scenario illustrates this issue. For
both approaches the retrieval time for network change events was measured.
The number of network change events was successively increased. To get a
robust result, the time was taken over 10 000 000 queries. The test was per-
formed on a 2.33 GHz CPU. Fig. 1 shows that the TreeMap implementation is
about 20% slower than the implementation using arrays and binary search.2In
consequence, the array approach was chosen to implement the time dependent
network.
2.2.2. Using hash maps for the storage and retrieval of link travel times
MATSim was originally developed for the simulation of vehicular traffic for
large cities or even regions. For this kind of simulation a temporal resolution of
15 min for the link travel times is used: The link travel times are aggregated
in 15 min time bins and the travel time values are stored in arrays (one array
for each link). For a network consisting of 100 000 links, this means a memory
consumption of about 75 MB3for the link travel time values.
For a pedestrian evacuation simulation with an expected evacuation time
2In fact, we and others [47] (Item 23) consistently find that in situations with few or no
insertions or removals after initialization, the array-based approach is faster.
3For 24 hday there are 4 ∗24 time bins, each time bin holds one double value (64 bit) and
there are 100 000 links (4 ∗24 ∗100 000 ∗64 bit ≈75 MB).
8
Timing of retrieval
time in
ms
0
100
200
300
400
500
600
700
800
900
number of change events
0 20 40 60 80 100
array
treemap
Figure 1: Comparison of the runtime performance for two different implementations of the net-
work change event retrieval. The array based approach using binary search is about 20% faster
then the approach using a Java TreeMap. The complexity of both approaches is O(log n).
of one or two hours, a resolution of 15 min is too coarse. However, a finer
resolution increases the amount of memory that is needed. To overcome this
problem, the array based implementation was replaced by an implementation
using Java HashMap. There is a HashMap for each link that stores the link
travel times. But only for those travel time bins where at least one agent has
entered the link, a travel time value is stored. This means that if for a given
travel time bin no agent enters the corresponding link, then nothing is stored
(and the free speed travel time will be used). Depending on the scenario this
can save a lot of memory.
An analytic appraisal of the memory usage or the needed execution time
in Java is difficult and depends, besides others, on the virtual machine and its
garbage collection mechanism, and on the specific scenario. Therefore it was
decided to compare the HashMap based approach with the array based approach
through a benchmark scenario. In the benchmark scenario, all link travel times
of the simulation described in Sec. 3 have been recorded and aggregated for
different travel time bin sizes. Beginning with a travel time bin size of 15 min
and ending with a travel time bin size of 1 min, the memory consumption, the
time for storing and aggregating and the time for the retrieval of the link travel
times have been measured.
The results of this benchmark test are shown in Fig. 2. At the top there
is a diagram comparing the memory usage of both approaches. Clearly, the
HashMap based approach consumes considerably less memory than the array
9
Figure 2: Comparison of two different implementations of the storage and retrieval mechanism
for the time dependent link travel times. Top: comparison of the memory consumption.
The Java HashMap based approach consumes considerable less memory than an array based
implementation. Bottom: comparison of the runtime performance. For write operations both
approaches have almost equal execution times. The array based approach is faster for read
operations.
10
based implementation. In particular, at 1-min time resolution the array-based
implementation consumes about 650 MB of memory, which, together with the
memory requirements of the remainder of the package, would make simulations
on today’s ordinary desktop computers impossible. The diagram at the bottom
compares the runtime for storage and aggregation (write) and for retrieval of
the link travel times (read). The time needed for write operations is almost
equal for both approaches. For read operations the array approach is faster. At
the same time, the execution time for a read operation is much smaller than for
a write operation. The underlying simulation run simulates the evacuation of
about 320 000 agents. On average each agent has to traverse 23.5 links before
she reaches the safe area. This means there are approximately 75 000 000 differ-
ent link travel times that have to be aggregated and stored. For the benchmark
scenario there were approximately 250 000 000 synthetic read operations4. Over-
all, for the time dependent link travel times retrieval, the small disadvantage
of the hash map approach with respect to the runtime can be tolerated for the
sake of much lower memory consumption.
2.3. Traffic flow simulator
The traffic flow simulation is implemented as a queue simulation, where
each street (link) is represented as a FIFO (first-in first-out) queue with three
restrictions [18]. First, each agent has to remain for a certain time on the link,
corresponding to the free speed travel time. Second, a link flow capacity is
defined which limits the outflow from the link. If, in any given time step, that
capacity is used up, no more agents can leave the link. Finally, a link storage
capacity is defined which limits the number of agents on the link. If it is filled up,
no more agents can enter this link. The difference to standard queueing theory
is that agents (particles) are not dropped but spill back, causing congestion. An
illustration of the queue model is shown in Fig. 3 a). The parameters of the
model are:
•Link minimum width w
•Link area A
•Link length l
•Flow capacity FC =w∗Cmax =w∗1.3p
m∗s
•Free flow speed vmax = 1.66m
s
•Storage capacity SC =A∗Dmax =A∗5.4p
m2
where Cmax is the maximum flow capacity per unit width, and Dmax is the
maximum density per unit area. The flow capacity of 1.3 persons/second per
4The network for the scenario consists of 16 978 links. For each link the travel time was
queried 20 times for 720 different time steps. (16 978 ∗20 ∗720 ≈250 000 000)
11
Figure 3: Functioning of the queue model is shown in (a) and its corresponding fundamental
diagram in (b).
meter of cross section is a fairly robust empirical parameter [68, 13], and it is the
most important parameter to determine bottlenecks. The remaining parameters
have been chosen to approximate Weidmann’s fundamental diagram [68]. For
more details, see [40].
2.4. Plans generation
Initial plans use the shortest path (according to free speed travel time) out
of the evacuation area for all agents. Within the MATSim framework a shortest
path router based on Dijkstra’s shortest path algorithm [12] has been imple-
mented. This router finds the shortest path in a weighted graph from one
node to any other, whereby the actual weights for a link are defined by a time-
dependent cost function. Since the city has to be evacuated as fast as possible,
the weights represent the (expected) travel time.
There is, however, no particular node as the target of the shortest path
calculation, as the evacuees have more than one safe place to run to. Instead,
in the underlying domain every node outside the evacuation area is a possible
destination for an agent that is looking for an escape route. To resolve this,
the standard approach (e.g. [44]) is to extend the network in the following way:
All links which lead out of the evacuation area are connected, using virtual
links with infinite flow capacity and zero length, to a special “evacuation node”.
Doing so, Dijkstra’s algorithm will always find the shortest route from any node
inside the evacuation area to this evacuation node.
2.5. Agent learning
During the simulation, each evacuee optimizes his/her personal evacuation
route to find the fastest escape route. At this point two different routing solu-
tions are considered: (1) A “shortest path” routing solution, where every evac-
uee follows the path that would be fastest in an empty network. (2) A “Nash
12
equilibrium” approach, where, via iterations every evacuating person attempts
to find a route that is optimal for him-/herself under the given circumstances
including congestion. Both approaches can be considered as benchmarks: the
first as one where congestion effects are not taken into account in the path
choice; the second one as one which might be achieved by appropriate training
or guidance while maintaining acceptability in the sense that no person could
gain by deviating from this solution. This will be discussed in more detail in
Sec. 5.
At the end of every iteration, every agent will score the performed plan.
The score of a plan is the negative of its execution time (i.e. of the necessary
time to evacuate). The scored plans remain in the agents’ memory for further
iterations. Two different learning strategies have been applied for the learning
procedure.
•The “ReRoute” strategy generates new plans with new evacuation routes
based on the information of the experienced travel times from the last
run. This uses the router described in the previous section, but now using
time-variant link travel times (Sec. 2.2.2) as link costs. The link travel
times are aggregated into 3 min time bins.
•The other strategy, “ChangeExpBeta”, decides if the just performed plan
should be used again, or if a random plan out of the memory should be
selected for the next iteration. The probability to change the selected plan
is calculated as:
pchange =min(1, α ∗eβ∗(sother −scurrent)/2),(1)
with:
–α: The probability to change if both plans have the same score
–β: A sensitivity parameter
–s{other,current}: The score of the other/current plan
Eq. 1 describes a process which slowly converges towards the logit model
probability distribution
pj=eβ∗sj
Pieβ∗si,
where piis the probability for plan ito be selected and siits current score.
This makes convergence to a steady state smoother than when all choices
are made in every iteration.
A strategy selector decides for every agent which of the strategies (ReRoute or
ChangeExpBeta) will be used. Each strategy is selected with a certain prob-
ability. These probabilities are assigned before the simulation starts, but they
can be varied during the iterations.
After re-planning every agent has a selected plan that will be executed in the
next iteration. Repeating this iteration cycle of learning, the agents’ behavior
13
will move towards a Nash equilibrium. If the system were deterministic, then a
state where every agent uses a fixed plan that is always a best response to the
last iteration would be a fixed point of the iterative dynamics, and at the same
time a Nash Equilibrium since no agent would have an incentive to unilaterally
deviate. Since, however, the system is stochastic, this statement does not hold,
and instead we look heuristically at projections of the system, e.g. the average
evacuation time. From experience it is enough to run 100 iterations until the
iterative dynamics has reached a steady state. In most (but not all) evacuation
situations, the Nash equilibrium leads to a shorter overall evacuation time than
when everybody moves to the geographically nearest evacuation point.
3. Scenario
The aim of this work is to find feasible solutions for the evacuation of the
city of Padang in the case of a tsunami. There are several aspects that have
to be taken into consideration. At first one needs a synthetic population for
the city. In this case study it is assumed that all people are at home. The
information about the distribution of the population was derived from existing
census data [7]. Approximately 320 000 people are living in the endangered area.
This means that 320 000 agents have been created for the simulation.
As discussed in Sec. 2.3, the traffic flow simulation is performed on a net-
work representing the walkable area of the city. The street map was extracted
from satellite imagery by remote sensing technologies [65] and converted into a
graph [41]. The resulting simulation network consists of 6 289 nodes and 16 978
unidirectional links.
Another important aspect is the information about safe places. In the future
it is planned to identify buildings that are suitable for a vertical evacuation. For
the time being we use a simpler approach: All areas with an elevation of more the
10 mabove sea level are defined as safe. Fig. 4 shows an image of the city with
the safe area. However, based on models of small-scale flooding and inundation
dynamics of the tsunami [22] it is not expected that all the area below 10 mwill
be flooded. Based on these simulations, one also learns that the estimated time
between the earthquake and the inundation of the city is about 28 min. The
results are backed by the results of large-scale tsunami simulations for the west
coast of Sumatra Island [46]. Adding this to the simulation, the agents were
made to learn a more risk averse behavior: they are not only trying to reach
the safe area as fast as possible, but they also try to increase the distance to
the endangered areas. In some places the flooding will reach locations that are
more than 2 km away from the shoreline.
The inundation data was provided by [22] as a time series of flooding heights
for (x, y)-coordinates with a temporal resolution of 1 min and a spatial resolu-
tion of 3 m. The queue model reproduces the inundation as a time dependent
network by varying the free speed parameter of the links. The free speed, as
discussed in Sec. 2.2, for the not inundated link is 1.66 m/s and the free speed
for an inundated link is 0 m/s. This means as soon as a link is flooded its free
speed will be set to 0 m/s. The router will, in consequence, try avoid the link
14
Figure 4: Satellite imagery of the city shows the safe area (light green) and some preliminary
results of the flooding simulation (blue area). Satellite imagery by the German Aerospace
Center, Oberpaffenhofen (2007)
15
at these times. And if, nevertheless, an agent happens to be on this link at such
a time, it will remain stuck there forever.
As explained above, we applied two different strategies for learning to the
simulation. The ReRoute strategy finds a new evacuation route for an agent,
based on the experienced travel times of the former iteration. The Change-
ExpBeta strategy implements a discrete-choice model that assigns a plan from
the agent’s memory with a probability depending on the score of the plan. In
the current setup the probability of being chosen for the ReRoute strategy is
10% and 90% for ChangeExpBeta. This setup gives a fair arrangement between
exploration and exploitation. If the probability for ReRoute (i.e. exploration) is
too low, then it could be that some promising routes will never be discovered.
On the other hand, if the probability for ReRoute is very high, the system tends
to fluctuate and will not convert to a steady state. The system would change
so fast that the agents would not get a chance to exploit their knowledge about
the system.
4. Results
Three different simulation runs were conducted. Run 1 corresponds to the
previous version of the evacuation simulation, without the time-dependent net-
work. Run 2 now includes the time-dependent network, which means that the
simulation now includes the effects of links that get flooded during the evacua-
tion. Run 3 is similar to run 1 except that here a so called 10% scenario was
chosen. This means only a 10% sample of the agents have been loaded onto
the network. To get correct results the flow capacity and storage capacity of all
links was also scaled by a factor of 0.1. Run 3 was conducted to see how the
runtime performance scales with the size of the scenario.
All runs were performed on computer with a Dual-Core CPU at 3 GHz
running a 64-Bit Java version on a Linux operation system. The simulation runs
were stopped after 200 iterations of learning. Table 1 compares the runtime
performance and memory consumption of the three runs. It is shown that
run overall runtime avg. runtime per iteration max. memory usage
1 370 min 111 s 3856 MB
2 400 min 120 s 3809 MB
3 77 min 23 s 1974 MB
Table 1: Runtime performance and memory consumption of the three different runs.
runtime performance of run 2 (with time dependent network) is slightly worse
compared to run 1 (without time dependent network). Both runs need a similar
amount of memory. This results show that applying time dependent networks
virtually make no difference regarding the runtime performance and memory
consumption. Thus the time dependent functionality has been implemented in
an efficient way.
16
Evacution progress
evacuated persons
0
50,000
100,000
150,000
200,000
250,000
300,000
350,000
time in
min
0 10 20 30 40 50 60 70
run 1 - Nash approach
run 2 - Nash approach
run 1 - shortest path
run 2 - shortest path
Figure 5: Comparison of the evacuation curves of the first iteration (“shortest path” solution)
and the last iteration (“Nash equilibrium” approach) of run-new and run-old. The curves are
truncated at 75 min.
Compared to the first and the second run run 3 is about 5 times faster and
consumes only the half amount of memory. Since “10%-runs” still yield useful
results, this means one could also run much larger scenarios on the current
hardware.
It is common to show the results of an evacuation simulation through evac-
uation curves. Fig. 5 shows such curves for the first and the last iteration of
run 1 and run 2. These curves show that the evacuation without time depen-
dent network is slightly faster in both the first and the last iteration. In the last
iteration the evacuation takes about 65 min without time dependent network
(run 1) compared to 75 min with time dependent network (run 2). In run 2
the agents are aware of the inundation; in run 1, they are not. It makes sense
that in run 2 the evacuation takes longer, since the agents take an additional
constraint into account.
Fig. 6 shows a GIS analysis of the network clearance time on a 350 m grid.
The colors of the squares indicate the difference of the clearance time for run 1
vs. run 2. A green color indicates that the clearance was faster in run 2 (with
time dependent network) and a red color indicates that it was slower. It is
shown that in run 2 the clearance of the coastal area is much faster than in
run 1. Especially the southern parts of the city are evacuated more then 10 min
earlier. This is a major progress in finding feasible solutions for the evacuation
of Padang.
Fig. 7 shows how different solutions (“shortest path” solution from run 1,
“Nash” solution from run 1, “Nash”solution from run 2) perform when exe-
cuted with the time-dependent network and the incoming tsunami wave. In
particular, highly endangered agents are colored in red. It is clearly visible that
17
Clearance time
difference
diff <= -10 min
-10 min < diff <= -5 min
-5 min < diff <= -1 min
-1 min < diff < 0 min
0 min < diff <= 1 min
1 min < diff <= 5 min
5 min < diff <= 10 min
10 min < diff
Figure 6: This figure shows a GIS analysis of the network clearance time on a 350 m grid.
The color of the squares indicate the difference of the clearance time for the simulation run
without time dependent network compared to the simulation run where the time dependent
network approach has been applied. A green color indicates that the clearance was faster with
time dependent network and a red color indicates a faster clearance without time dependent
network. The actual values are given in the legend of the figure (e.g. a green color means that
the clearance time with time dependent network was at least 10 min faster than without).
It is shown, that with time dependent network the clearance time for the highly endangered
coastal area decreases on the cost of increase of clearance time in the hinterland.
the “shortest path” solution does not leave enough time to evacuate the costal
strip. Furthermore, the “Nash” solution of run 1 would also not leave enough
time to evacuate the highly endangered area within 30 min. The results from
the “Nash equilibrium” approach of run 2 seem to be more feasible.
5. Discussion
The simulations concentrate on two types of agent behaviors: One where
every agent follows the shortest path to the safe area; one where a Nash equi-
librium is reached. Both can be considered as benchmarks:
•The first as one where agents are rational about their path choice, but
unaware of congestion effects.
•The second as a solution that could be reached by training, assuming that
agents follow the training solution also in the real situation.
In panic situations, people tend to be irrational and to display herd behavior
[28]. Still, if even the Nash equilibrium solution does not leave enough time,
18
“shortest path” solution “Nash” solution “Nash” solution
from run 1 from run 1 from run 2
Figure 7: Visualizer snapshots of the evacuation progress. The evacuation starts at 03:00 AM
and the snapshots are taken after 1 min, 15 min and 30 min.(left) The three snapshots in the
left column show the evacuation progress for the “shortest path” solution of run 1 performed
on the time dependent network. (center) The snapshots in the center column show the “Nash
equilibrium” approach of run 1 also performed on a time dependent network. (right) The
snapshots in the right column show the result of the “Nash equilibrium” approach of run 2.
The agents are colorized with respect to the time they need to evacuate. The evacuation time
increases as the color moves from green to yellow to red. Agents that did not manage to
evacuate the area that will be inundated are also colored red. Note in particular some highly
endangered agents in the shortest path solution due to congestion. The “Nash” solution of
run 1 is even worse.
19
then this would be a strong indicator that major measures would need to be
taken to rectify the situation.
It should also be stated that Nash equilibrium and system optimum do not
need to coincide – i.e. that solutions even better than the Nash equilibrium
might be possible. Such solutions would, however, be unstable in the sense
that people would have an incentive to deviate. Such solutions seem even more
improbable than Nash equilibrium solutions.
Finally, one should mention that MATSim already contains the first hooks
towards en-route replanning [31]. This would allow to add situation-based be-
havior into the simulation.
Another issue concerns the mode choice: The investigation assumes that all
evacuation is done by foot while it might be reasonable to assume that some
people use cars or cycles, and they might even leave vehicles in the street to
continue on foot if progress by vehicle becomes too slow. For the time being,
such issues are not considered. The queue model could, to a certain extent,
be parameterized to deal with mixed traffic, as long as all modes move with
the same speed. Beyond that, one would arguably need to switch to a true
two-dimensional model such as [28] or [35]. Such models could still operate on
networks [20].
In the current base case it is assumed that all people are at home. Currently
we are working on more detailed picture of the population. Based on census data
and the results of a survey with 1 000 households, that took place in April/Mai
2008 [5], we are developing a synthetic population with individual daily plans.
From this synthetic population it will be possible to derive a model of the
population distribution at any time of day. In future work it is also planned to
integrate tsunami proof shelters into the simulation framework. Therefore the
simulation framework could be extended in a way to find optimal locations for
the tsunami proof shelters.
6. Conclusions
We introduced a microscopic pedestrian simulation framework for large-scale
evacuations. It is implemented as a Multi Agent Simulation, where every agent
tries to optimize its individual evacuation plan in an iterative way. The flooding
information is modeled as network change events in the simulation framework,
which, when such events are comparatively rare, is a much sparser representation
than time-expanded or time-aggregated graphs. The network change events
approach could be easily adapted to other scenarios, for example for modeling
accidents.
The simulation framework is demonstrated through a case study based on
a tsunami evacuation of the Indonesian city of Padang. The simulation gives
plausible results regarding the predicted evacuation time and process. The
runtime performance shows that this approach is well suited for large scale
scenarios. With state of the art hardware it is no problem to simulate much
larger scenarios with over one million agents.
20
7. Acknowledgments
This project was funded in part by the German Ministry for Education and
Research (BMBF), under grants numbers 03G0666E (“last mile”) and 03NAPI4
(“Advest”). We would like to thank Hubert Kl¨upfel for the fruitful discussion
about pedestrian evacuation simulations.
References
[1] Pedestrian and Evacuation Dynamics. Proceedings of the 4th international
conference, Wuppertal, 2008. Springer, Berlin, 2008.
[2] R. Alsnih and P. Stopher. A review of the procedures as-
sociated with devising emergency evacuation plans. Work-
ing Paper ITS-WP-04-04, Institute of Transport Studies, The
University of Sydney and Monash University, 2004. See
www.itls.usyd.edu.au/publications/working papers/wp2004/its wp 04-
04.pdf.
[3] B. Barrett, B. Ran, and R. Pillai. Developing a dynamic traffic management
modeling framework for hurricane evacuation. Paper 00-1595, Transporta-
tion Research Board Annual Meeting, Washington, D.C., 2000.
[4] M. Bierlaire, G. Antonini, and M. Weber. Behavioral dynamics for pedes-
trians. In K. Axhausen, editor, Moving through nets: The physical and
social dimensions of travel. Elsevier, 2003.
[5] J. Birkmann, S. Dech, N. Goseberg, H. Kl¨upfel, G. L¨ammel, F. Moder,
K. Nagel, M. Oczipka, T. Schlurmann, N. Setiadi, F. Siegert, G. Strunz,
and H. Taubenb¨ock. Numerical last-mile tsunami early warning and eva-
cation information system (“Last-Mile – Evacuation ”). In GEOTECH-
NOLOGIEN Science Report No. 10: “Early Warning Systems in Earth
Management”, Osnabr¨uck, October 2008.
[6] J. Birkmann, S. Dech, G. Hirzinger, R. Klein, H. Kl¨upfel, F. Lehmann,
C. Mott, K. Nagel, T. Schlurmann, N. Setiadi, F. Siegert, and G. Strunz.
Numerical last-mile tsunami early warning and evacuation information sys-
tem. In L. Stroink, editor, GEOTECHNOLOGIEN Science Report No.
10: “Early Warning Systems in Earth Management”, Technical University
Karlsruhe, October 2007. Die Deutsche Biliothek.
[7] BPS. Kecamatan Dalam Angka - Subdistricts in Numbers. Satistical bureau
(BPS) Kota Padang, Padang, 2005.
[8] E. Cascetta and C. Cantarella. A day-to-day and within-day dynamic
stochastic assignment model. Transportation Research A, 25A(5):277–291,
1991.
21
[9] N. Cetin, A. Burri, and K. Nagel. A large-scale agent-based traffic mi-
crosimulation based on queue model. In Proceedings of Swiss Transport
Research Conference (STRC) Monte Verita, CH, 2003. See www.strc.ch.
Earlier version, with inferior performance values: Transportation Research
Board Annual Meeting 2003 paper number 03-4272.
[10] X. Chen and F. Zhan. Agent-based modeling and simulation of urban
evacuation: Relative effectiveness of simultaneous and staged evacuation
strategies. Paper 04-0329, Transportation Research Board Annual Meeting,
Washington, D.C., 2004.
[11] Y.-C. Chiu, P. Korada, and P. Mirchandani. Dynamic traffic management
for evacuation. Paper 05-2369, Transportation Research Board Annual
Meeting, Washington, D.C., 2005.
[12] E. Dijkstra. A note on two problems in connexion with graphs. Numerische
Mathematik, 1:269 – 271, 1959.
[13] P. DiNenno, editor. SFPE Handbook of Fire Protection Engineering. Na-
tional Fire Protection Association, Boston, 2nd edition, 1995.
[14] I. Farkas. pedsim source code, accessed 2008. See pedsim.elte.hu.
[15] E. Galea. Simulating evacuation and circulation in planes, trains, buildings
and ships using the EXODUS software. In Schreckenberg and Sharma [60],
pages 203–225.
[16] E. R. Galea, editor. Pedestrian and Evacuation Dynamics. Proceedings of
the 2nd international conference, London, 2003. CMS Press, University of
Greenwich, UK, 2003.
[17] P. Gattermann, N. Waldau, and M. Schreckenberg, editors. Pedestrian and
Evacuation Dynamics. Proceedings of the 3rd international conference,
Vienna. Springer, Berlin, 2006.
[18] C. Gawron. An iterative algorithm to determine the dynamic user equilib-
rium in a traffic simulation model. International Journal of Modern Physics
C, 9(3):393–407, 1998.
[19] B. George, S. Kim, and S. Shekhar. Spatio-temporal network databases and
routing algotihms: A summary of results. In Proceedings of International
Symposium on Spatial and Temporal Databases (SSTD‘07), 2007.
[20] C. Gloor, P. Stucki, and K. Nagel. Hybrid techniques for pedestrian simu-
lations. In Cellular automata, Proceedings, number 3305 in Lecture Notes
in Computer Science, pages 581–590. Springer, 2004.
[21] C. Gloor, P. Stucki, and K. Nagel. Hybrid techniques for pedestrian sim-
ulations. In Proceedings of Swiss Transport Research Conference (STRC)
Monte Verita, CH, 2004. See www.strc.ch.
22
[22] N. Goseberg, A. Stahlmann, S. Schimmels, and T. Schlurmann. Highly-
resolved numerical modeling of tsunami run-up and inundation scenarios in
the city of Padang, West Sumatra. In Interantional Conference on Coastal
Engineering, Hamburg, in press.
[23] S. Hamacher, H.W. Tjandra. Mathematical modelling of evacuation prob-
lems: A state of art. Berichte des Fraunhofer ITWM, 24:1–38, 2001.
[24] A. Han. TEVACS: Decision support system for evacuation planning in
Taiwan. Journal of Transportation Engineering, 116(6):821–830, 1990.
[25] L. Han and F. Yuan. Evacuation modeling and operations using dynamic
traffic assignment and most desirable destination approaches. Paper 05-
2401, Transportation Research Board Annual Meeting, Washington, D.C.,
2005.
[26] D. Helbing, L. Buzna, A. Johansson, and T. Werner. Self-organized
pedestrian crowd dynamics: experiments, simulations and design solutions.
Transportation Science, 39:1–24, 2005.
[27] D. Helbing, I. Farkas, P. Molnar, and T. Vicsek. Simulation of pedestrian
crowds in normal and evacuation situations. In Schreckenberg and Sharma
[60], pages 21–58.
[28] D. Helbing, I. Farkas, and T. Vicsek. Simulating dynamical features of
escape panic. Nature, 407:487–490, 2000.
[29] A. Hobeika and C. Kim. Comparison of traffic assignments in evacuation
modeling. IEEE Transactions on Engineering Management, 45(2):192–198,
1998.
[30] S. Hoogendoorn, P. Bovy, and W. Daamen. Microscopic pedestrian
wayfinding and dynamic modelling. In Schreckenberg and Sharma [60],
pages 123–154.
[31] J. Illenberger, G. Fl¨otter¨od, and K. Nagel. Enhancing MATSim with capa-
bilities of within-day re-planning. In Proceedings of the 2007 IEEE Intel-
ligent Transportation Systems Conference, pages 94–99, Seattle, WA, Sep
30 – Oct 3 2007.
[32] M. Jafari, I. Bakhadyrov, and A. Maher. Technological advances in evacu-
ation planning and emergency management: Current state of the art. Final
Research Reports EVAC-RU4474, Center for Advanced Infrastructure and
Transportation (CAIT), Rutgers University, NJ, 2003.
[33] M. Jha, K. Moore, and B. Pashaie. Emergency evacuation planning with
microscopic traffic simulation. Paper 04-2414, Transportation Research
Board Annual Meeting, Washington, D.C., 2004.
23
[34] D. Kaufman and R. Smith. Fastest paths in time-dependent networks
for intelligent vehicle-highway systems application. Journal of Intelligent
Transportation Systems, 1:1–11, 1993.
[35] H. Kl¨upfel. The simulation of crowd dynamics at very large events – Cali-
bration, empirical data, and validation. In Gattermann et al. [17].
[36] H. Kl¨upfel, T. Meyer-K¨onig, A. Keßel, and M. Schreckenberg. Simulating
evacuation processes and comparison to empirical results. In M. Fukui et
al, editor, Traffic and granular flow ’01, pages 449–454. Springer, Berlin
Heidelberg New York, 2003.
[37] E. Kohler, K. Langtau, and M. Skutella. Time-expanded graphs for flow-
dependent transit times. In 10th Annual European Symposium on Algo-
rithms, pages 599–611, 2002.
[38] E. Kuligowski. Review of 28 egress models. Technical report, National
Institute of Standards and Technology (NIST), Gaithersburg, MD, 2004.
[39] E. Kwon and S. Pitt. Evaluation of emergency evacuation strategies for
downtown event traffic using a dynamic network model. Paper 05-2164,
Transportation Research Board Annual Meeting, Washington, D.C., 2005.
[40] G. L¨ammel, M. Rieser, and K. Nagel. Bottlenecks and congestion in evac-
uation scenarios: A microscopic evacuation simulation for large-scale dis-
asters. In 5th Workshop on Agents in Traffic and Transportation (ATT) @
Autonomous Agents and Multiagent Systems (AAMAS) ’08, Estoril, Por-
tugal, May 2008.
[41] G. L¨ammel, M. Rieser, K. Nagel, H. Taubenb¨ock, G. Strunz, N. Gose-
berg, T. Schlurmann, H. Kl¨upfel, N. Setiadi, and J. Birkmann. Emergency
preparedness in the case of a tsunami – evacuation analysis and traffic opti-
mization for the Indonesian city of Padang. In Pedestrian and Evacuation
Dynamics [1].
[42] C. Lieberman, D. Kurowski, M. Avila, L. Ricci, N. Thomas, C. Collyer, and
B. Aguirre. Conceptual framework for simulating the pedestrian evacuation
behavior from buildings. Paper 05-2297, Transportation Research Board
Annual Meeting, Washington, D.C., 2005.
[43] E. Lim and B. Wolshon. Modeling and performance assessment of con-
traflow evacation termination points. Transportation Research Record,
1922:118–128, 2005.
[44] Q. Lu, B. George, and S. Shekhar. Capacity constrained routing algorithms
for evacuation planning: A summary of results. LNCS, 3633:291–307, 2005.
[45] MATSIM www page. MultiAgent Transport SIMulation.
http://matsim.org/, accessed 2008.
24
[46] J. McCloskey, A. Antonioli, A. Piatanesi, K. Sieh, S. Steacy, S. Nalbant,
M. Cocco, C. Giunchi, J. Huang, and P. Dunlop. Tsunami threat in the
indian ocean from a future megathrust earthquake west of Sumatra. Earth
and Planetary Science Letters, 265:61–81, 2008.
[47] S. Meyers. Effective STL: 50 specific ways to improve the use of the Stan-
dard Template Library. Addison-Wesley, 2002.
[48] Y. Murakami, T. Ishida, T. Kawasoe, and R. Hishiyama. Scenario de-
scription for multi-agent simulation. In Autonomous agents and multiagent
systems (AAMAS’03), Melbourne, Australia, July 2003.
[49] D. Natawidjaja, K.Sieh, M. Chlieh, J. Galetzka, B. Suwargadi, H. Cheng,
R. Edwards, J.-P. Avouac, and S. Ward. Source parameters of the great
Sumatran megathrust earthquakes of 1797 and 1833 inferred from coral
microatolls. Journal of Geophysical Research, 111, 2006.
[50] K. Nishinari, A. Kirchner, A. Nazami, and A. Schadschneider. Extended
floor field CA model for evacuation dynamics. IEICE Transactions on
Information and Systems, E87-D(3):726–732, 2004.
[51] Oak Ridge Evacuation Modeling System, accessed 2006. www-
cta.ornl.gov/cta/One Pagers/OREMS.pdf.
[52] J. d. D. Ort´uzar and L. Willumsen. Modelling transport. Wiley, Chichester,
1995.
[53] S. Pallottino and M. Scutella. Shortest path algorithms in transportation
models: Classical and innovative aspects. In P. Marcotte and S. Nguyen,
editors, Equillibrium and Adavanced Transportation Modelling, pages 245–
281. Kluwer, 1998.
[54] X. Pan, C. Han, K. Dauber, and K. Law. A multi-agent based framework for
the simulation of human and social behavior during emergency evacuations.
AI and Society, 22(2):113–132, 2007.
[55] W. Predtetschenski and A. Milinski. Planning for Foot Traffic in Buildings.
Amerind Publishing Co. Pvt. Ltd., New Delhi, 1978.
[56] C. Rogsch. Vergleichende Untersuchungen zur Simulation von Person-
entr¨omen. Diploma thesis, Universit¨at Wuppertal, 2005.
[57] P. Sattayhatewa and B. Ran. Developing a dynamic traffic management
model for nuclear power plant evacuation. Paper, Transportation Research
Board Annual Meeting, Washington, D.C., 2000.
[58] H. Sbayti, C.-C. Lu, and H. Mahmassani. Efficient implementation of
method of successive averages in simulation-based dynamic traffic assign-
ment models for large-scale network applications. Transportation Research
Record, (2029):22–30, 2007.
25
[59] V. Schneider and R. K¨onnecke. Simulating evacuation processes with
ASERI. In Schreckenberg and Sharma [60], pages 303–314.
[60] M. Schreckenberg and S. D. Sharma, editors. Pedestrian and Evacation
Dynamics. Proceedings of the 1st international conference, Duisburg, 2001.
Springer, 2002.
[61] Y. Sheffi. Urban Transportation Networks: Equilibrium Analysis with Math-
ematical Programming Methods. Prentice-Hall, Englewood Cliffs, NJ, USA,
1985.
[62] P. Simon, J. Esser, and K. Nagel. Simple queueing model applied to the
city of Portland. International Journal of Modern Physics C, 10(5):941–
960, 1999.
[63] R. Standish. Classdesc Library, accessed 2005. See paral-
lel.hpc.unsw.edu.au/rks/classdesc.
[64] D. Strippgen and K. Nagel. Using common graphics hardware for multi-
agent simulation with CUDA. In Proceedings of the 2nd International Con-
ference on Simulation Tools and Techniques, to appear.
[65] H. Taubenb¨ock, J. Prost, R. Kiefl, A. Roth, F. A. Ismail, G. Strunz, and
S. Dech. Risk and vulnerability assessment to tsunami hazard using very
high resolution satellite data. In C. J¨urgens, editor, Remote Sensing - New
Challenges of High Resolution, Bochum, 2008. European Association of
Remote Sensing Laboratories.
[66] H. Taubenb¨ock and A. Roth. A transferable and stable classification ap-
proach in various urban areas and various high resolution sensors. In Urban
Remote Sensing Joint Event, Paris, 2007.
[67] G. Theodoulou and B. Wolshon. Alternative methods to increase the effec-
tiveness of freeway contraflow evacation. Transportation Research Record,
1865:48–56, 2004.
[68] U. Weidmann. Transporttechnik der Fussg¨anger, volume 90 of Schriften-
reihe des IVT. Institute for Transport Planning and Systems ETH Z¨urich,
2 edition, 1993. In German.
[69] Y. Wen, R. Balakrishna, M. Ben-Akiva, and S. Smith. Online deployment
of dynamic traffic assignment: architecture and run-time management. In
Intelligent Transport Systems, IEE Proceedings, volume 153, pages 76–84,
2006.
26
