Efficient continuous contraflow algorithms for evacuation planning problems

A productive research in the emerging field of disaster management plays a quite important role in relaxing this disastrous advanced society. The planning problem of saving affected areas and normalizing the situation after any kind of disasters is very challenging. For the optimal use of available road network, the contraflow technique increases the outward road capacities from the disastrous areas by reversing the arcs. Number of efficient algorithms and heuristics handle this issue with contraflow reconfiguration on particular networks but the problem with multiple sources and multiple sinks is NP-hard. This paper concentrates on analytical solutions of continuous time contraflow problem. We consider the value approximation earliest arrival transshipment contraflow for the arbitrary and zero transit times on each arcs. These problems are solved with pseudo-polynomial and polynomial time complexity, respectively. We extend the concept of dynamic contraflow to the more general setting where the given network is replaced by an abstract contraflow with a system of linearly ordered sets, called paths satisfying the switching property. We introduce the continuous maximum abstract contraflow problem and present polynomial time algorithms to solve its static and dynamic versions by reversing the direction of paths. Abstract contraflow approach not only increases the flow value but also eliminates the crossing at intersections. The flow value can be increased up to double with contraflow reconfiguration.