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

We experimentally tested the CCRP algorithm using the road network around
the evacuation zone provided by the Minnesota Department of Transportation (Lu
et al. 2007 ) and the Census 2000 population data for each affected city (circle
in Fig. 6.13 ). The total number of evacuees was about 42,000. As can be seen
in Fig. 6.13 , our algorithm produced a much better evacuation route plan (a)
by selecting shorter paths to reduce evacuation time and (b) by utilizing richer
routes i.e., routes near the evacuation destination to reduce congestion. As a result,
evacuation egress time was reduced from 268 min under the old plan to only 162 min
with CCRP. This experiment demonstrated the effectiveness of our algorithm in real
evacuation planning scenarios to reduce evacuation time and improve existing plans.

6.19 Conclusion

Spatio-temporal networks are a key component of critical applications such as
transportation networks, sensor data analysis, and crime analysis. We discuss
existing approaches in modeling these networks and proceeds to present an approach
that is based on time aggregation of graphs. Though spatio-temporal trajectories
have been proposed to model temporal variations in spatial data, there is limited
work on spatio-temporal networks. Another approach based on replication of
networks leads to networks of enormous sizes and consequently computationally
expensive algorithms. Moreover, these models do not provide adequate support
for node/edge centric operations which might be essential in applications such as
evacuation planning, routing, and temporally enhanced ER diagrams.

References

Abou-Rjeili, A., & Karypis, G. (2006). Multilevel algorithms for partitioning power-law graphs. In
20th international parallel and distributed processing symposium, 2006. IPDPS 2006 (p. 10).
IEEE.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows . Englewood Cliffs: Prentice
Hall.
Airlines. http://www.delta.com/
Batty, M. (2005). Agents, cells, and cities: New representational models for simulating multiscale
urban dynamics. Environment and Planning A, 37 , 1373-1394.
Ben-Akiva, M. (2002). Development of a deployable real-time dynamic traffic assignment system:
Dynamit and dynamit-p user's guide . Technical Report. Cambridge: Massachusetts Institute of
Technology.
Bertsekas, D. P. (1987). Dynamic programming: Deterministic and stochastic models . Englewood
Cliffs: Prentice-Hall.
Burns, L. (1979). Transportation, temporal, and spatial components of accessibility . Lexington:
Lexington Books.
Chabini, I. (1998). Discrete dynamic shortest path problems in transportation applications:
Complexity and algorithms with optimal run time. Transportation Research Record: Journal
of the Transportation Research Board, 1645 (-1), 170-175.