Contraflow transportation network reconfiguration for evacuation route planning

Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration (that is, ideal direction for each edge) to minimize the evacuation time. Contraflow lane reversal is considered a potential remedy to reduce congestion during evacuations in the context of homeland security and natural disasters (for example, hurricanes). This problem is computationally challenging because of the very large search space and the expense of calculating the evacuation time on a given network. To our knowledge, this paper presents the first macroscopic approaches for the solution of a contraflow network reconfiguration incorporating road capacity constraints, multiple sources, congestion, and scalability. We formally define the contraflow problem based on graph theory and provide a framework of computational structure to classify our approaches. A Greedy heuristic is designed to produce high-quality solutions with significant performance. A Bottleneck Relief heuristic is developed to deal with large numbers of evacuees. We evaluate the proposed approaches both analytically and experimentally using real-world data sets. Experimental results show that our contraflow approaches can reduce the evacuation time by 40 percent or more.