Back to search

South Dakota State University

QPER Evacuation Planner Algorithm in Flat Time Graphs

Abstract

dc:description.abstract

Evacuation planning is of critical importance for civil authorities to prepare for natural disasters, but efficient evacuation planning in large cities is computationally challenging due to the large number of evacuees and the huge size of transportation networks. One recently proposed algorithm Capacity Constrained Route Planner (CCRP) can give sub-optimal solutions with good accuracy in less time and use less memory compared to previous approaches. However, it still cannot scale to large networks. We present an evacuation planner algorithm uses flat time graphs. Given a transportation network with nodes and edges, the proposed algorithm can be used to plan the evacuation routing that minimizes the evacuation time. We are using the quickest paths instead of the shortest paths to construct the evacuation routing. By combining the quickest paths, we can get a routing scheme that has short evacuation time and is scalable with the increase of number of evacuees. The simulation results show that our algorithm is scalable and the found evacuation routes have short evacuation time. We modified the algorithm finding the quickest paths to select the quickest shortest paths that are the quickest among the shortest paths. This modification increases the algorithm's execution time but decreases the evacuation time by using more paths.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis - University Access Only
Discipline thesis:degree_discipline
Electrical Engineering and Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Neupane, Bipin Chandra

Identifiers

dc:identifier.*
Repository record dc:identifier
https://openprairie.sdstate.edu/etd2/1823

Chain of custody

source
Harvested from
South Dakota State University
Base URL
openprairie.sdstate.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Neupane, Bipin Chandra. QPER Evacuation Planner Algorithm in Flat Time Graphs. Thesis - University Access Only thesis, https://openprairie.sdstate.edu/etd2/1823