Abstract
Semantic computing addresses the transformation of data, both structured and unstructured into information that is useful in application domains. One domain where semantic computing would be extremely effective is evacuation route planning, an area of critical importance in disaster emergency management and homeland defense preparation. Evacuation route planning, which identifies paths in a given transportation network to minimize the time needed to move vulnerable populations to safe destinations, is computationally challenging because the number of evacuees often far exceeds the capacity, i.e. the number of people that can move along the road segments in a unit time. A semantic computing framework would help further the design and development of effective tools in this domain, by providing a better understanding of the underlying data and its interactions with various design techniques. Traditional Linear Programming(LP) based methods using time expanded networks can take hours to days of computation for metropolitan sized problems. In this paper, we propose a new approach, namely a capacity constrained routing planner for evacuation route planning which models capacity as a time series and generalizes shortest path algorithms to incorporate capacity constraints. We describe the building blocks and discuss the implementation of the system. Analytical and experimental evaluations that compare the performance of the proposed system with existing route planners show that the capacity constrained route planner produces solutions that are comparable to those produced by LP based algorithms while significantly reducing the computational cost.
Original language | English (US) |
---|---|
Pages (from-to) | 249-303 |
Number of pages | 55 |
Journal | International Journal of Semantic Computing |
Volume | 1 |
Issue number | 2 |
DOIs | |
State | Published - Jun 1 2007 |
Bibliographical note
Funding Information:This work is supported by the Army High Performance Computing Research Center (AHPCRC) under the auspices of the Department of the Army, Army Research Laboratory under contract number DAAD19-01-2-0014 and the Minnesota Department of Transportation under contract number 81655. The content does not necessarily reflect the position or policy of the government and no official endorsement should be inferred. AHPCRC and the Minnesota Supercomputer Institute provided access to computing facilities.
Funding Information:
∗This work was supported by the Army High Performance Computing Research Center contract number DAAD19-01-2-0014 and the Minnesota Department of Transportation contract number 81655. The content of this work does not necessarily reflect the position or policy of the government and no official endorsement should be inferred. Access to computing facilities was provided by the AHPCRC and the Minnesota Supercomputing Institute. †Currently at Microsoft Corporation, Redmond, WA. ‡Corresponding author.
Publisher Copyright:
© 2007 World Scientific Publishing Company.
Keywords
- Evacuation planning
- routing and scheduling
- semantic computing
- transportation network