Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
A fast heuristic approach for large-scale cell-transmission-based evacuation route planning
Kimms A., Maassen K.  Networks 60 (3): 179-193, 2012. Type: Article
Date Reviewed: Jan 24 2013

This paper follows on the work of Daganzo [1,2], who used a cell transmission model for traffic to create evacuation plans. In this model, a cell corresponds to a segment of a street and the street cells are connected into a network. An extended version of the model accommodates varying cell sizes and multiple-lane streets, and also accounts for some areas carrying higher risks.

The drawback of Daganzo’s work is that it is computationally intensive. This paper introduces a heuristic procedure that allows the model to be used for larger-scale evacuation scenarios. The effectiveness of this heuristic is shown in a number of real-world scenarios using the city of Duisburg as an example.

The extended cell transition evacuation model, which incorporates multiple cell sizes, road lanes, and traffic flow limits, is described in detail (27 sets of equations are required to do this). The paper then describes two heuristics used to obtain computationally tractable solutions, one based on shortest path and an iterative one that minimizes risk to the evacuees. The heuristics are used to solve a static version of the extended model for which the flow connections are fixed. These solutions are then fed into the original extended model.

The nine scenarios in the paper range in size from network lengths of 23 to 83 kilometers, from 8,750 to 25,856 vehicles, and from 107 to 339 cells. The shortest path heuristic is disappointing in all but one case, while the iterative heuristic produces good results in all cases except one where the memory requirements proved excessive. The paper contains detailed tables describing the results.

Reviewer:  J. P. E. Hodgson Review #: CR140868 (1305-0417)
1) Daganzo, C. F. The cell-transmission-model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B 28, 4(1994), 269–287.
2) Daganzo, C. F. The cell-transmission-model, part II: network traffic. Transportation Research Part B 29, 2(1995), 79–93.
Bookmark and Share
  Featured Reviewer  
Heuristic Methods (I.2.8 ... )
Plan Execution, Formation, And Generation (I.2.8 ... )
Routing Protocols (C.2.2 ... )
Would you recommend this review?
Other reviews under "Heuristic Methods": Date
Exploration and exploitation in evolutionary algorithms: a survey
Črepinek M., Liu S., Mernik M.  ACM Computing Surveys 45(3): 1-33, 2013. Type: Article
Aug 21 2013
GRASP algorithms for the robust railway network design problem
García-Archilla B., Lozano A., Mesa J., Perea F.  Journal of Heuristics 19(2): 399-422, 2013. Type: Article
Jun 13 2013
A hybrid genetic algorithm for the bottleneck traveling salesman problem
Ahmed Z.  ACM Transactions on Embedded Computing Systems 12(1): 1-10, 2013. Type: Article
May 10 2013

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2014 ThinkLoud, Inc.
Terms of Use
| Privacy Policy