{"id":{"repo_id":"sdstate","oai_identifier":"oai:openprairie.sdstate.edu:etd2-2821"},"canonical_url":"https://search.ndltd.org/etd/sdstate/oai:openprairie.sdstate.edu:etd2-2821","repository":{"repo_id":"sdstate","name":"South Dakota State University","base_url":"https://openprairie.sdstate.edu/do/oai/"},"display":{"title":"QPER Evacuation Planner Algorithm in Flat Time Graphs","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.","abstract_html":"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&#x27;s execution time but decreases the evacuation time by using more paths.","abstract_has_math":false,"creators":["Neupane, Bipin Chandra"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis - University Access Only","degree_discipline":"Electrical Engineering and Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T09:05:50Z","subjects":[],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://openprairie.sdstate.edu/etd2/1823","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://openprairie.sdstate.edu/etd2/1823","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://openprairie.sdstate.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aopenprairie.sdstate.edu%3Aetd2-2821","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Neupane, Bipin Chandra"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2025-10-29T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2011-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering and Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - University Access Only"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://openprairie.sdstate.edu/etd2/1823"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["QPER Evacuation Planner Algorithm in Flat Time Graphs"]}]}],"canonical_facts":{"dc:creator":["Neupane, Bipin Chandra"],"dc:date.available":["2025-10-29T07:00:00Z"],"dc:date.created":["2011-01-01T08:00:00Z"],"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."],"dc:identifier":["https://openprairie.sdstate.edu/etd2/1823"],"dc:title":["QPER Evacuation Planner Algorithm in Flat Time Graphs"],"thesis:degree_discipline":["Electrical Engineering and Computer Science"],"thesis:degree_level":["Thesis - University Access Only"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T09:05:50Z"}