Dynamic Network Simplex Method for Designing Emergency Evacuation Plans
Abstract
The cell-based system optimal dynamic traffic assignment (SO-DTA) model has recently been applied to study emergency evacuation by a handful of authors. It is recognized that an optimal solution to this model may contain a phenomenon called traffic holding, which discharges flow at a lower rate than what can be achieved under the given traffic conditions. Mathematically, this is caused by the relaxation of traffic flow propagation constraints. In this paper, an optimal traffic pattern that contains no holding is always proved to exist in the context of evacuation planning. An optimal traffic pattern without holding is much easier and less costly to implement in emergency response. A dynamic network simplex method for solving the simplified SO-DTA model that represents traffic flow propagation by a point-queue model is proposed. By making full use of the network structure, the algorithm is able to identify an optimal solution without holding. For the original cell-based SO-DTA, an iterative procedure is suggested that can effectively eliminate holding in a solution obtained from a conventional linear programming algorithm.
Get full access to this article
View all access and purchase options for this article.
References
1. Hobeika A. G., and Jamei B. MASSVAC: A Model for Calculating Evacuation Times Under Natural Disasters. In Proceedings of the Conference on Emergency Planning, Simulation Series (Carroll J. M., ed.), Vol. 15, No. 1, Society for Computer Simulation, La Jolla, Calif., pp. 23–28.
2. Sattayhatewa P., and Ran B. Developing a Dynamic Traffic Management Model for Nuclear Power Plant Evacuation. Presented at 79th Annual Meeting of the Transportation Research Board, Washington, D.C., 2000.
3. Liu H. X., Ban J. X., Ma W., and Mirchandani P. B. Model Reference Adaptive Control Framework for Real-Time Traffic Management Under Emergency Evacuation. Presented at 85th Annual Meeting of the Transportation Research Board, Washington, D.C., 2006.
4. Chiu Y.-C., Rao P. K., and Mirchandani P. B. Dynamic Traffic Management for Evacuation. Presented at 84th Annual Meeting of the Transportation Research Board, Washington, D.C., 2005.
5. Sbayti H., and Mahmassani H. S. Optimal Scheduling of Evacuation Operations. In Transportation Research Record: Journal of the Transportation Research Board, No. 1964, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 238–246.
6. Ziliaskopoulos A. K. A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem. Transportation Science, Vol. 34, No. 1, 2000, pp. 37–49.
7. Daganzo F. C. The Cell Transmission Model: A Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory. Transportation Research B, Vol. 28, 1994, pp. 269–287.
8. Daganzo F. C. The Cell Transmission Model. II. Network Traffic. Transportation Research B, Vol. 29, 1995, pp. 79–93.
9. Tuydes H., and Ziliaskopoulos A. Network Redesign to Optimize Evacuation Contraflow. Presented at 83rd Annual Meeting of the Transportation Research Board, Washington, D.C., 2004.
10. Tuydes H., and Ziliaskopoulos A. Tabu-Based Heuristic Approach for Optimization of Network Evacuation Contraflow. In Transportation Research Record: Journal of the Transportation Research Board, No. 1964, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 157–168.
11. Liu Y., Lai X., and Chang G.-L. Two-Level Integrated Optimization Model for Planning of Emergency Evacuation: Case Study of Ocean City, Maryland, Under Hurricane Evacuation. Presented at 84th Annual Meeting of the Transportation Research Board, Washington, D.C., 2005.
12. Liu Y., Lai X., and Chang G.-L. Cell-Based Network Optimization Model for Staged Evacuation Planning Under Emergencies. In Transportation Research Record: Journal of the Transportation Research Board, No. 1964, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 127–135.
13. Chiu Y.-C., Villalobos J., Gautam B., and Zheng H. Modeling and Solving Optimal Evacuation Destination-Route-Flow Staging Problem for No-Notice Extreme Events. Presented at 85th Annual Meeting of the Transportation Research Board, Washington, D.C., 2006.
14. Merchant D. K., and Nemhauser G. L. A Model and an Algorithm for the Dynamic Traffic Assignment Problems. Transportation Science, Vol. 12, 1978, pp. 183–199.
15. Carey M. Optimal Time-Varying Flows on Congested Networks. Operations Research, Vol. 35, 1987, pp. 58–69.
16. Friesz T. L., Luque J., Tobin R. L., and Wie B.-W. Dynamic Network Traffic Assignment Considered as a Continuous Time Optimal Control Problem. Operations Research, Vol. 37, 1989, pp. 893–901.
17. Zhang M. H., and Nie Y. Modeling Network Flow With and Without Link Interactions: Properties and Implications. Presented at 84th Annual Meeting of the Transportation Research Board, Washington, D.C., 2005.
18. Ghali M. O., and Smith M. J. A Model for the Dynamic System Optimum Traffic Assignment Problem. Transportation Research B, Vol. 29, 1995, pp. 155–170.
19. Lo H. K. A Cell-Based Traffic Control Formulation: Strategies and Benefits of Dynamic Timing Plans. Transportation Science, Vol. 35, 2001, pp. 148–154.
20. Ahuja R. K., Magnanti T. L., and Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Inc., Upper Saddle River, N.J., 1993.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published: January 2007
Issue published: January 2007
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 82
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 41
- A Distributed Gradient Approach for System Optimal Dynamic Traffic Ass...
- Multiclass dynamic system optimum solution for mixed traffic of human-...
- Optimal Route Determination to provide Relief Following an Earthquake ...
- Emergency management systems after disastrous earthquakes using optimi...
- Optimal design of Rapid evacuation strategies in constrained urban tra...
- System optimal dynamic traffic assignment: solution structures of the ...
- Dynamic multi-objective optimization for multi-period emergency logist...
- Cooperative traffic signal and perimeter control in semi-connected urb...
- Distributed Optimization and Coordination Algorithms for Dynamic Traff...
- Simulation and Evaluation of Network Simplex Algorithm and its Extensi...
- Link-Based System Optimum Dynamic Traffic Assignment Problems in Gener...
- A study of realistic dynamic traffic assignment with signal control, t...
- Bi-objective safe and resilient urban evacuation planning
- Dynamic traffic metering in urban street networks: Formulation and sol...
- A linear bus rapid transit with transit signal priority formulation
- An exact network flow formulation for cell-based evacuation in urban a...
- Eco-system optimal time-dependent flow assignment in a congested netwo...
- Optimal queue placement in dynamic system optimum solutions for single...
- Integrating the Bus Vehicle Class Into the Cell Transmission Model
- Clearance Time Estimation for Incorporating Evacuation Risk in Routing...
- Network Simplex Plus: Complete Advanced Algorithm
- On the System Optimum Dynamic Traffic Assignment and Earliest Arrival ...
- Dynamic Resource Allocation Problem for Transportation Network Evacuat...
- Earthquake risk in urban street network: an example from region 6 of T...
- A dynamic version for the Network Simplex Algorithm
- Continuous-time dynamic system optimum for single-destination traffic ...
- A Heuristic Algorithm for the Earliest Arrival Flow with Multiple Sour...
- Optimal evacuation planning using staging and routing
- A cell based dynamic system optimum model with non-holding back flows
- Optimizing Network Flows with Congestion-Based Flow Reductions
- MIESTŲ KONKURENCINGUMO KOMPLEKSINIS VERTINIMAS REMIANTIS DARNIOS PLĖTR...
- Aerozolinės taršos siurbtuvo, aktyvinamo aeroakustiniu srautu, efektyv...
- On the holding-back problem in the cell transmission based dynamic tra...
- Cell-transmission-based evacuation planning with rescue teams
- Heuristic Solution Techniques for No-Notice Emergency Evacuation Traff...
- Extended cell-transmission-based evacuation planning in urban areas
- A cell-based Merchant–Nemhauser model for the system optimum dynamic t...
- A Network Flow Algorithm for the Cell-Based Single-Destination System ...
- Reliable evacuation planning via demand inflation and supply deflation
- Modeling of Evacuation and Background Traffic for Optimal Zone-Based V...
- What Do Different Traffic Flow Models Mean for System-Optimal Dynamic ...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
