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 be reversed is computationally complex and exact analytical solutions would have unrealistically high 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, and 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 million¹. The department of homeland security in the nationwide report for the year 2006 identified a significant inadequacy in evacuation planning effort for using multiple modes of transport to evacuate people from different risk zones². According to the report, only less than 20% of state and 10% of urban areas have sufficiency in their 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 make traffic flow more efficiently by identifying lanes to be reversed, and by establishing optimal evacuation routes for passenger cars and buses.

Lane reversals have been a proven strategy to improve evacuation efficiency in an emergency situation. 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 needs to be considered. The illustration in Figure 1 describes how lane reversals would help in improving 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, which is half of that for the original network.

A complexity study performed on these types of network flow problems³ 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 Fulkerson⁴ studied the maximum dynamic flow problem, where one tries to maximize the flow sent 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 the arc costs as travel times on the arcs. 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 involves replacing each directed arc with an undirected arc with increased capacity would allow 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 correctness of this transformation are provided in reference⁵.  The problem becomes NP-hard³ for multiple sources and multiple sinks. The problem is NP-hard for single origin/single destination scenarios if we consider the cost of reversing an arc. These results indicate that the optimization problems are computationally difficult and polynomial time algorithms are available only to 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 every pair of origin destinations 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-hard³, and it is modeled with a large number of variables. The solution developed attempts to exploit the combinatorial structure of the problem. The researchers are proposing to use the column generation procedure, where the 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 the convergence to an optimal solution and the researchers are currently experimenting with the numerical acceleration of this convergence.

References

1. Contraflow Plan for the Florida Intrastate Highway System, Technical Memorandum, Version 1, June 6, 2005.
2. Department of Homeland Security (DHS), Nationwide Plan Review, Phase II review, 2006.
3. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979.
4. L.R. Ford and D.R. Fulkerson. Flows in Networks. PrincetonUniversity Press, 1962.
5. S. Rebennack, A. Arulselvan, L. Elefteriadou, and P.M. Pardalos. Complexity Analysis for Maximum Flow Problems with Arc Reversals, Journal of Combinatorial Optimization (accepted).