Evacuation planning problems on uniform path length network with prioritized destinations

Abstract

Optimization models for evacuation with capability of holding evacuees at intermediate places are of particular interest when all the evacuees cannot be sent to the safe destination. We study the maximum flow evacuation planning problem that aims to lexicographically maximize the evacuees entering a set of capacitated terminals with respect to a given prioritization. We propose a polynomial time algorithm for the problem modeled on uniform path length (UPL) network. We also extend the solution idea to solve quickest flow evacuation planning problem that lexicographically minimizes the time required to fulfill the demands of evacuees at such terminals. Moreover, we consider an earliest arrival version of the problem with sufficient vertex capacities, and propose a polynomial time algorithm for uniform path length two terminal series parallel (UPL-TTSP) network.