Geography Reference
In-Depth Information
c
1
2
3
4
Time Step
A
A1
A2
A3
A4
B
B1
B2
B3
B4
Disk:
Page 1
C
C1
C2
C3
C4
Page 2
Page 3
D
D1
D2
D3
D4
Page 4
Fig. 6.11
(continued)
problems. Over the last decade, we developed a different approach, namely the
Capacity Constrained Route Planner (CCRP), which generalizes shortest path
algorithms by honoring capacity constraints and the spread of people over space
and time. CCRP uses Time Aggregated Graphs to reduce storage overhead and
increase computational efficiency. Experimental evaluation and field use in Twin-
cities Homeland Security scenarios demonstrated that CCRP is faster, more scalable
and easier to use than previous techniques.
There has been a considerable amount of research on route planning for
evacuation scenarios. Recent work falls into three categories: (1) Network flow
methods (Francis and Chalmet
1984
; Kisko and Francis
1985
; Kisko et al.
1998
;
Ahuja et al.
1993
; Hamacher and Tjandra
2002
) (2) Simulation methods (Ben-
Akiva
2002
; Mahmassani et al.
2004
), and (3) Heuristic methods (Hoppe and
Tardos
1994
;Luetal.
2003
,
2005
,
2007
). In contrast to previous approaches,
heuristic approaches use approximate methods to find near-optimal solutions with
minimizing the computational cost. A well known approach that falls in this
category is the Capacity Constrained Route Planner (CCRP) (Lu et al.
2003
,
2005
,
2007
). These methods use time aggregated graphs (George and Shekhar
2006
)and
evaluate a shortest route with capacity constraints to find the evacuation route at each
time step. It is useful for medium sized networks (e.g., 1-mile evacuation zone), but
has a limitation for large scale networks (e.g., 50-mile evacuation zone). (Kim et al.
2007
) present a new scalable heuristic by reusing shortest routes based on bottleneck
saturation checking. It showed a 95 % reduction in computational time with small
degradation of solution quality.
Search WWH ::
Custom Search