Optimization Models and Algorithms for Evacuation Planning

Abstract

An important strategy, to save a life from natural or human-created disasters, is to evacuate the population from the disastrous zones to safe places. Intelligent evacuation planning requires a carefully designed traffic plan with optimal use of the facilities available. Reversing the direction of the traffic flow in the appropriate road segments, known as a contraflow approach, has been an important strategy in evacuation planning. To avoid unnecessary arc reversals, we introduce partial contraflow approach and design strongly polynomial algorithms to solve maximum static, maximum dynamic, and quickest flow problems with partial arc reversals, and polynomial-time algorithms to solve maximum static/dynamic abstract partial contraflow problems. Sometimes the travel time on an arc may change when it is reversed. We propose a network transformation that helps convert the existing contraflow algorithms to the ones with orientation-dependent transit times. To address the dependency of transit times in the flow, we extend the contraflow approach to inflow-dependent transit times and load-dependent transit times. Realizing the NP-hardness of such problems, we propose strongly polynomial (2 + )-approximation algorithms to solve the corresponding contraflow/partial contraflow problems. If facilities are to be adjusted on arcs to facilitate evacuation, there may be an increase in the evacuation time. We introduce the quickest FlowLoc model to address such a problem. We prove that the single facility case of the problem can be solved in strongly polynomial time. Proving NP-hardness of the multi-facility case, we propose two heuristics. Taking the case of a Kathmandu road network, the faster heuristic has an average optimality gap of 3.48% and an average running time of 0.17 seconds. The corresponding values for the slower heuristic are 0.18% and 1.02 seconds. The algorithms for quickest FlowLoc problem with arc reversals are also designed. With an objective to maximize the static/dynamic flows, and minimize quickest flow, the problem of choosing a single shelter location are modeled as MaxStatic, MaxDynamic, Quickest sink location problems respectively. We establish that each of such a problem can be solved in strongly polynomial time with or without arc reversals. By reversing the direction of the traffic flow towards the sink, a contraflow configuration may obstruct the paths towards the source. We model the problem of maximizing the dynamic contraflow saving a path not exceeding a given length as a mixed binary integer linear programming problem. The analogous problem of minimizing the evacuation time is modeled as a mixed binary integer programming problem with a fractional objective. A linearization strategy is suggested so that the algorithms to solve the mixed integer linear programming problems can be used. The problem of minimizing the path length and maximizing the dynamic contraflow has been modeled as a bicriteria optimization problem. A procedure using -constrained method is constructed to obtain efficient solutions. The solutions, using available software solvers, considering a road network of Kathmandu city can be obtained within 1 second. We also model the problem of minimizing the path length and evacuation time as a bicriteria problem and construct a procedure to solve it. We model a path saving model maximizing the dynamic contraflow to optimize a general objective, as a bilevel program. To solve the problem, we replace the lower level problem by Karush-Kuhn-Tucker (KKT) conditions converting it to a single level non-linear binary integer program. We linearize it using a big M method and also suggest a procedure to tune M.