Browsing by Author "Lu, Qingsong"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Capacity Constrained Routing Algorithms for Evacuation Planning : A Summary of Results
    (2005-05-31) Lu, Qingsong; George, Betsy; Shekhar, Shashi
    Evacuation planning is critical for numerous important applications, e.g. disaster emergency management and homeland defense preparation. Efficient tools are needed to produce evacuation plans that identify routes and schedules to evacuate affected populations to safety in the event of natural disasters or terrorist attacks. The existing linear programming approach uses time-expanded networks to compute the optimal evacuation plan and requires a user-provided upper bound on evacuation time. It suffers from high computational cost and may not scale up to large transportation networks in urban scenarios. In this paper we present a heuristic algorithm, namely Capacity Constrained Route Planner(CCRP), which produces sub-optimal solution for the evacuation planning problem. CCRP models capaci ty as a time series and uses a capacity constrained routing approach to incorporate route capacity constraints. It addresses the limitations of linear programming approach by using only the original evacuation network and it does not require prior knowledge of evacuation time. Performance evaluation on various network configurations shows that the CCRP algorithm produces high quality solutions, and significantly reduces the computational cost compared to linear programming approach that produces optimal solutions. CCRP is also scalable to the number of evacuees and the size of the network. We also provide a discussion on the formulation of a new optimal algorithm that uses A* search to find the optimal solution for evacuation planning. We prove that the heuristic function used in this A* formulation is monotone and admissible.
  • Thumbnail Image
    Item
    Capacity Constrained Routing Algorithms for Evacuation Route Planning
    (2006-05-04) Lu, Qingsong; George, Betsy; Shekhar, Shashi
    Evacuation route planning identifies paths in a given transportation network to minimize the time needed to move vulnerable populations to safe destinations. Evacuation route planning is critical for numerous important applications like disaster emergency management and homeland defense preparation. It is computationally challenging because the number of evacuees often far exceeds the capacity, (ie.) the number of people that can move along the road segments in a unit time. 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 which models capacity as a time series and generalizes shortest path algorithms to incorporate capacity constraints. We characterize the design space for reducing the computational cost. Analytical cost model and experiment results show that the proposed algorithm is faster than the LP based algorithms and requires less memory. Experimental evaluation using various network configurations also shows that the proposed algorithm produces solutions that are comparable to those produced by LP based algorithms while significantly reducing the computational cost.