Spatio-temporal Networks: Modeling, Storing, and Querying Temporally-Detailed Roadmaps - Space-Time Integration in Geography and GIScience - page 98

In this section we describe the Evacuation Route Planning (ERP) problem from
a computational perspective. In a typical evacuation planning scenario, the spatial
structure is represented and analyzed as a network model with non-negative integer
capacity constraints on the nodes and edges. With additional information pertaining
to initial locations of all evacuees and their final destinations, the ERP problem
produces a set of origin and destination routes for evacuees. Consider a simple
building ERP problem in Fig. 6.12 a. Each room, corridor, staircase, and exit of the
building is represented as a node and each pathway from one node to another node
is represented as an edge. Every node has two attributes: maximum node capacity
and initial node occupancy. For example, the maximum capacity of node N 1 is 50,
indicating that the node can hold at most 50 evacuees at any time step. The initial
occupancy is shown to be 10, which means 10 evacuees prepare to move out of
the node. Every edge has two attributes: maximum edge capacity and travel time.
For example, the maximum edge capacity of N 4 N 6 is 5, indicating that at most
5 evacuees can traverse the edge. The travel time of this edge is 4, which means it
takes 4 time steps to traverse the edge. Suppose we initially have 10 evacuees at node
N 1, 5 at node N 2, and 15 at node N 8, the ERP produces evacuation routes as shown
in Fig. 6.12 b. The objective of the ERP problem is to minimize the computational
cost of producing the evacuation plan while minimizing evacuation time.

6.17 Capacity Constrained Route Planner

CCRP is based on an iterative approach for creating a complete evacuation plan. In
each iteration, the algorithm searches for a route R with the earliest arrival time
to any destination node from any source node, taking previous reservations and
possible wait times into consideration. Then, CCRP computes the actual number of
evacuees that will travel through R . This number is affected by the available capacity
of R and the remaining number of evacuees. The maximum number of evacuees
to be sent on R is then determined as the minimum of the available capacities on
the component edges in R ; CCRP reserves the node and edge capacity on R for
those evacuees. The algorithm terminates when all the evacuees have been given an
evacuation route to any of the destinations.
A key step in CCRP is to determine the route R with the earliest arrival time.
A naive way to obtain the route R could involve executing Dijkstra's algorithm
(Dijkstra 1959 ;Cormenetal. 2001 ) (generalized to work with edge capacities and
travel times) for every of source and destination nodes, followed by selecting the
minimum. However, this becomes a major performance bottleneck and adversely
effects the scalability of the algorithm (Lu et al. 2005 , 2007 ). This bottleneck is
handled in CCRP by adding a pseudo source node S 0 and edges with zero travel
time and infinite capacity between S 0 and all other source nodes.