Prioritized Maximum Multi-Commodity Flow in Evacuation Planning

Due to different disasters, natural or human-made hazards, the world is facing the problem of significant physical damage, loss of lives, and destruction of the environment every year. To save the lives of evacuees, efficient evacuation planning is essential. Prioritization is the process of deciding the relative importance or urgency of things or objects. It helps to focus on the objectives and goals in an efficient way. The evacuation process with prioritization of the evacuees is relevant on solving large-scale disaster management problems. Prioritization of evacuees based on case sensitivity or risk of life is one of the best and most reliable ways for post-disaster evacuation planning. In this chapter, we introduce an evacuation planning problem with priority order of evacuees based on case sensitivity to maximize the flow and develop a multi-commodity flow model for the priority-based evacuation planning problem. We present an algorithm to solve the maximum static flow problem in polynomial time complexity. Similarly, for the maximum dynamic flow problem, a polynomial time approximation algorithm and a pseudo-polynomial time optimal solution in a time expanded network are presented.