Flows on Network with Intermediate Storage Capability: Evacuation Planning Perspective

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, sink and intermediate vertices, with respect to a given prioritization.

We propose a polynomial time algorithm for the problem modeled on uniform path length (UPL) network. We also apply this algorithm to solve quickest flow evacuation planning problem that lexicographically minimizes the time required to fulfill the demand of evacuees at such terminals. Moreover, we show that the algorithm solves an earliest arrival version of the problem with sufficient vertex capacities for uniform path length two terminal series parallel (UPL-TTSP) network.