By: Panos Pardalos, Ph.D., Distinguished Professor (ISE), and Ashwin Arulselvan, doctoral student (ISE)
Department of Industrial & Systems Engineering
This article is based on ongoing research under CMS Project # 2008-005
Purpose of study: Minimize the total evacuation time for a given highway network
Approach: Make traffic flow more efficiently by identifying lanes to be reversed and by establishing optimal evacuation routes for passenger cars and buses.
Conclusions to-date:
- Identifying the optimal set of lanes to reverse is computationally complex, and exact analytical solutions would require unrealistically long running times.
- The problem is solved in two steps: first, the lanes to be reversed are identified, and then the optimal evacuation routes are established for the reconfigured network.
- The model provides evacuation routes for passenger cars and, for each origin-destination pair, the frequency of departures for buses.
The Florida Division of Emergency Management reported that Hurricane Frances required 1.8 million people to be evacuated, Hurricane Ivan required 545,000 and Hurricane Jeanne required 4.4 million1. The Department of Homeland Security, in its nationwide 2006 report, identified a significant inadequacy in evacuation planning for using multiple modes of transport to evacuate people from different risk zones. According to the report, less than 20% of states and 10% of urban areas have sufficient plans for accommodating multiple modes of transport. Some of the important measures in an evacuation plan that are listed in the report include contraflow measures, identifying evacuation routes and consideration of alternative and safe modes of transportation besides the personal vehicles used by the evacuees.
The objectives of this study are to improve traffic flow by identifying lanes to be reversed and establishing optimal evacuation routes for passenger cars and buses.
Lane reversals have proven to be a strategy for improving evacuation efficiency in emergency situations. Generally, the lane reversal strategies vary depending on the need. For instance, lane reversals due to work zones or incidents do not require a global strategy, as these pertain to a specific link in the network. On the other hand, emergency situations and sporting events that require mass transit would require more sophisticated lane reversal plans. Also, for hurricanes, the intensity of the hurricane and the population in the area to be evacuated need to be considered. The illustration in Figure 1 shows how lane reversals would help improve flow. The numbers in parentheses indicate the capacity and the travel time of the arc, respectively.
Figure 1a presents a directed graph with four nodes. O indicates origin and D destination. In Figure 1a, it takes 1 time unit to send 2 units of flow from node O to node 1 and 2 time units to send 3 units of flow from node 1 to node D. Thus, the time required for evacuating 21 units of flow from O to D, using all the possible routes, is 10.
The graph in figure 1b is a reconfigured graph with lane reversals, and it takes 1 time unit to send 5 units of flow from node O to 1 and 2 time units to send 4 units of flow from node 1 to node D. Thus along the path O-1-D we can send 2 units of flow in 3 time units in the original network, whereas in the reconfigured network we could send 4 units of flow in 3 time units. In this reconfigured network, the evacuation time for 21 units of traffic is 5, half that of the original network.
A complexity study performed on these types of network flow problems3 indicated that these types of problems are computationally hard (i.e., they require exponential running times) Several issues may arise during a reconfiguration of a network. These include permitting only a subset of arcs (i.e., lanes of roadway segments) to be reversed, imposing a switching cost to the arcs involved in the reversals, and considering multiple origins and destinations. Ford and Fulkerson4 studied the maximum dynamic flow problem, in which one seeks to maximize the flow from source to sink within a given time horizon T, and proved that this problem is equivalent to solving a minimum cost flow problem with arc costs equal to the arc travel times. Then the optimal flow on the arcs from source to sink is decomposed into a set of paths or chains. A simple graph transformation that replaces each directed arc with an undirected arc of increased capacity would enable solving the minimum cost flow problem to identify lanes to be reversed in a single origin/single destination dynamic contraflow problem. The details of the transformation and a proof of its correctness are provided in reference 5. The problem becomes NP-hard3 for multiple sources and multiple sinks. The problem is NP-hard for single-origin/single-destination scenarios when we include the cost of reversing an arc. These results indicate that the optimization problems are computationally difficult, and polynomial-time algorithms are available only for the simplistic single-origin/single-destination network flow scenarios.
A bimodal transportation network is a reasonable assumption in an emergency situation as buses and cars could serve as the predominant modes of transportation. In this ongoing research effort, the researchers consider the bimodal evacuation problem with multicommodity flow, where travelers (or evacuees) have destination preferences from their respective origins. In this problem, there are two sets of travelers, depending on their modes of transport. It is assumed that the demands of passenger cars and bus passengers for each pair of origin-destination pairs in the network are known and do not vary. It is also assumed that the bus routes have already been established. The links of the network under consideration are shared by both cars and buses. Each link has a given travel time and a given capacity. The objective is to determine the most efficient path for passenger cars between the origins and destinations, and the frequency of the buses along their predetermined routes, without exceeding the capacity of the arcs.
This optimization problem, which considers multimodal and multicommodity flows, is non-trivial as it is NP-hard3, and it is modeled with a large number of variables. The solution developed exploits the combinatorial structure of the problem. The researchers propose using the column generation procedure, in which variables are generated iteratively and added to the model. A computationally efficient subproblem is solved at each iteration to generate a subset of variables. The entire procedure has been successfully implemented and tested in C++. This iterative procedure has difficulties with convergence to an optimal solution, and the researchers are currently experimenting with numerical acceleration of convergence.
References
- Contraflow Plan for the Florida Intrastate Highway System, Technical Memorandum, Version 1, June 6, 2005.
- Department of Homeland Security (DHS), Nationwide Plan Review, Phase II review, 2006.
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979.
- L.R. Ford and D.R. Fulkerson. Flows in Networks. PrincetonUniversity Press, 1962.
- S. Rebennack, A. Arulselvan, L. Elefteriadou, and P.M. Pardalos. Complexity Analysis for Maximum Flow Problems with Arc Reversals, Journal of Combinatorial Optimization (accepted).