Prioritized Max-FlowLoc for Evacuation Planning

Abstract

From different disasters such as earthquakes, flooding, landslides, hurricanes, blizzards, etc., thousands of people have lost their lives and millions of people have to be rescued each year. To reduce the losses from different disasters, appropriate emergency plannings are essential. The allocation of facility in an appropriate location of prioritized network are evenly used in such plannings. The prioritized maximum flow problem is to obtain the maximum flow in a network by taking a predetermined leaving pattern at the sources and/or reaching pattern at the sinks. But placing the facility on an arc, which is a very important task to supply the basic needs of the evacuees, reduces the arc capacity so that the maximum flow value in the network may be reduced. Here, we introduce the prioritized maximum static and dynamic flow location (FlowLoc) problems in a single source and multi-sink network. The mathematical models are given for both single and multi facility problems. The polynomial time algorithms are presented in single facility cases. After proving the $\mathcal{NP}$-completeness, the polynomial-time heuristics are presented for optimal or near optimal solutions in case of multi-facility cases.