Contraflow network reconfiguration for evacuation planning: A summary of results

Contraflow, or lane reversal, is a way of increasing outbound capacity of a real network by reversing the direction of inbound roads during evacuations. The contraflow is considered a potential remedy to solve congestions during evacuations in context of homeland security and natural disasters (e.g., hurricanes). Currently available contraflow algorithms only tackle a single-source and multiple-destinations situation. These approaches cannot handle a multiple-sources problem which is harder due to conflicts across the optimal paths from different sources. We formally define the evacuation situations using graph and flow theory and show the NP-completeness of the contraflow problem. We propose two capacity-aware global contraflow heuristics that produce contraflow configuration in the presence of conflicts among routes preferred by different source nodes. We evaluate proposed heuristics experimentally using synthetic networks as well as real world datasets. In addition, we provide algebraic cost model. Experimental results show that our contraflow heuristics can reduce evacuation time by 30% or more.