On-the-Fly Nearest-Shelter Computation in Event-Dependent Spatial Networks in Disasters

Pei-Hsuan Tsai, Chun Lung Lin, Jyun Nan Liu

Research output: Contribution to journalArticle

3 Citations (Scopus)


Numerous approaches have been proposed to solve shortest path query problems (SPQPs) in either static or time-dependent spatial networks; however, these approaches are neither appropriately nor efficiently used to find the nearest shelter with fastest paths in disaster evacuations. In disasters, segments of a path computed and saved as the fastest might become impassable. The nearest shelter differs for people depending on their locations and can also change on the basis of an unpredictable and highly dynamic edge cost (e.g., maximum passable vehicle speed), which is influenced by disaster events. To solve this problem, this paper proposes a dynamic network model, which is called an event-dependent network, to represent a spatial network in a disaster. Effective approaches using multiple algorithms are proposed for on-the-fly computation of the nearest shelter and fastest paths in a disaster. A distributed system consisting of a server and multiple mobile clients using our approaches is presented for navigating the fastest paths for people to evacuate a disaster area. Real-world maps, such as a map of California, were used in our experiments. The results revealed that our approaches require less than 2 ms to find a new nearest shelter and its fastest paths, which is faster than other approaches for solving the fastest-path problem.

Original languageEnglish
Article number7055365
Pages (from-to)1109-1120
Number of pages12
JournalIEEE Transactions on Vehicular Technology
Issue number3
Publication statusPublished - 2016 Mar 1

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Aerospace Engineering
  • Automotive Engineering
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'On-the-Fly Nearest-Shelter Computation in Event-Dependent Spatial Networks in Disasters'. Together they form a unique fingerprint.

  • Cite this