Network Flow Approach for Locating Optimal Sink in Evacuation Planning

Abstract

Network flow models have been widely applied for evacuation planning, which involves moving people from risk areas (sources) to safe places (sinks) using some means of transportation, to optimize traffic flow in urban road networks. The decisions related to the locations of the sinks are also important to maximize the number of evacuees or minimize time for the evacuees to reach the safe places. In this work, we consider the problems of identifying the optimal sink node out of a given set of possible sink-nodes in a single source network to maximize the flow value, and that to minimize the time to transfer a given flow value to the sink in minimum time. Designing efficient computational procedures to solve the problems, we prove that the problems can be solved with strongly polynomial time complexity. Corresponding optimal sink location problems along with identification of ideal direction of the flow based on contraflow approach are also solved in strongly polynomial time. Our results are substantiated by a case illustration based on Kathmandu road network.

Keywords

• Evacuation planning
• sink location
• network flow
• dynamic flow
• maximum flow
• quickest flow
• contraflow