January  2015, 11(1): 265-289. doi: 10.3934/jimo.2015.11.265

A survey on models and algorithms for discrete evacuation planning network problems

1. 

Central Departments of Mathematics/CSIT, IOST, Tribhuvan University, Kathmandu, Nepal

Received  May 2013 Revised  January 2014 Published  May 2014

With an increasing number of large-scale natural and man-created disasters over the last decade, there is growing focus on the application of operations research techniques for humanitarian relief in the emerging field of emergency evacuation. Even though a large diversity of models have been developed, many rely on solving network-flow problems on appropriate graphs. In this survey, we give a systematic collection of network flow models used in emergency evacuation and their applications. We especially focus on results interrelating these models. Considered models include max flows and min cost flows, lexicographic flows, quickest flows, and earliest arrival flows, as well as contraflows and time-dependent problems.
Citation: Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial & Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265
References:
[1]

S. Afandizadeh, A. Jahangiri and N. Kalantari, Determination of the optimal network configuration for emergency evacuation by simulated annealing algorithm,, in Proceedings of the 2nd WSEAS International Conference on Natural Hazards (NAHA'09), (2009), 65. Google Scholar

[2]

R. K. Ahuja, T. L. Magnati and J. B. Orlin, Network Flows: Theory, Algorithms and Applications,, Prentice Hall, (1993). Google Scholar

[3]

N. Altay and W. G. Green III, OR/MS research in disaster operations management,, European Journal of Operational Research, 175 (2006), 475. doi: 10.1016/j.ejor.2005.05.016. Google Scholar

[4]

E. J. Anderson, P. Nash and A. B. Philpott, A class of continuous network flow problems,, Mathematics of Operations Research, 7 (1982), 501. doi: 10.1287/moor.7.4.501. Google Scholar

[5]

J. E. Aronson, A survey of dynamic network flows,, Annals of Operations Research, 20 (1989), 1. doi: 10.1007/BF02216922. Google Scholar

[6]

N. Baumann, Evacuation by Earliest Arrival Flows,, Ph.D thesis, (2007). Google Scholar

[7]

N. Baumann and M. Skutella, Solving evacuation problems efficiently, earliest arrival flows with multiple sources,, in Foundations of Computer Science, (2006), 399. doi: 10.1109/FOCS.2006.70. Google Scholar

[8]

N. Baumann and M. Skutella, Earliest arrival flows with multiple sources,, Mathematics of Operations Research, 34 (2009), 499. doi: 10.1287/moor.1090.0382. Google Scholar

[9]

G. N. Berlin, The Use of Directed Routes for Assigning Escape Potential,, National Fire Protection Association, (1979). Google Scholar

[10]

D. R. Bish, Planning for a bus-based evacuation,, OR Spectrum, 33 (2011), 629. doi: 10.1007/s00291-011-0256-1. Google Scholar

[11]

S. Bretschneider and A. Kimms, Pattern-based evacuation planning for urban areas,, European Journal of Operational Research, 216 (2012), 57. doi: 10.1016/j.ejor.2011.07.015. Google Scholar

[12]

R. E. Burkard, K. Dlaska and H. Kellerer, The quickest disjoint flow problem,, Institute of Mathematics, (1991), 189. Google Scholar

[13]

R. E. Burkard, K. Dlaska and B. Klinz, The quickest flow problem,, ZOR-Methods and Models of Operations Research, 37 (1993), 31. doi: 10.1007/BF01415527. Google Scholar

[14]

M. Carey and E. Subrahmanian, An approach to modelling time-varying flows on congested networks,, Transportation Research B, 34 (2000), 157. doi: 10.1016/S0191-2615(99)00019-3. Google Scholar

[15]

L. G. Chalmet, R. L. Francis and P. B. Saunders, Network models for building evacuation,, Fire Technology, 18 (1982), 90. doi: 10.1007/BF02993491. Google Scholar

[16]

L. Chen and E. Miller-Hooks, The building evacuation problem with shared information,, Naval Research Logistics, 55 (2008), 363. doi: 10.1002/nav.20288. Google Scholar

[17]

Y. L. Chen and Y. H. Chin, The quickest path problem,, Computers and Operations Research, 17 (1990), 153. doi: 10.1016/0305-0548(90)90039-A. Google Scholar

[18]

W. Choi, H. W. Hamacher and S. Tufekci, Modeling of building evacuation problems by network flows with side constraints,, European Journal of Operations Research, 35 (1988), 98. doi: 10.1016/0377-2217(88)90382-7. Google Scholar

[19]

T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem for evacuation planning on series-parallel graph,, International Journal of Operations research, 10 (2013), 1. Google Scholar

[20]

K. F. Doerner, W. J. Gutjahr and L. V. Wassenhove, Special issue on optimization in disaster relief,, OR Spectrum, 33 (2011), 445. doi: 10.1007/s00291-011-0262-3. Google Scholar

[21]

Decision Support System for Large-Scale Evacuation Logistics, Homepage, 2012,, , (). Google Scholar

[22]

B. Eksioglu, A.V. Vural and A. Reisman, The vehicle routing problem: A taxonomic review,, Computers & Industrial Engineering, 57 (2009), 1472. doi: 10.1016/j.cie.2009.05.009. Google Scholar

[23]

L. Fleischer, Universally maximum flow with piecewise-constant capacities,, Networks, 38 (2001), 115. doi: 10.1002/net.1030. Google Scholar

[24]

L. Fleischer and E. Tardos, Efficient continuous-time dynamic network flow algorithms,, Operations Research Letters, 23 (1998), 71. doi: 10.1016/S0167-6377(98)00037-6. Google Scholar

[25]

L. K. Fleischer, Faster algorithms for quickest transshipment problem,, SIAM Journal on Optimization, 12 (2001), 18. doi: 10.1137/S1052623497327295. Google Scholar

[26]

L. K. Fleischer and M. Skutella, Quickest multicommodity flow problem,, in Integer Programming and Combinatorial Optimization, 2337 (2002), 36. doi: 10.1007/3-540-47867-1_4. Google Scholar

[27]

L. K. Fleischer and M. Skutella, Quickest flows over time,, SIAM Journal on Computing, 36 (2007), 1600. doi: 10.1137/S0097539703427215. Google Scholar

[28]

F. R. Ford and D. R. Fulkerson, Constructing maximal dynamic flows from static flows,, Operations Research, 6 (1958), 419. doi: 10.1287/opre.6.3.419. Google Scholar

[29]

F. R. Ford and D. R. Fulkerson, Flows in Networks,, Princeton University Press, (1962). Google Scholar

[30]

D. Gale, Transient flows in networks,, Michigan Mathematical Journal, 6 (1959), 59. doi: 10.1307/mmj/1028998140. Google Scholar

[31]

G. M. Gallo, M. Grigoriadis and R. E. Tarjan, A Fast parametric maximum flow algorithm and applications,, SIAM Journal of Computing, 18 (1989), 30. doi: 10.1137/0218003. Google Scholar

[32]

B. George, S. Kim and S. Shekhar, Spatio-temporal network databases and routing algorithms: A summary of results,, in Proceedings of the 11th International Symposium on Spatial and Temporal Databases (SSTD), 4605 (2007), 460. doi: 10.1007/978-3-540-73540-3_26. Google Scholar

[33]

B. George and S. Shekhar, Time-aggregated Graphs for Modeling Spatio-temporal Networks- An Extended Abstract,, in Proceedings of the Workshop at International Conference on Conceptual Modeling, (2006). Google Scholar

[34]

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization,, Springer Verlag Berlin, (1988). doi: 10.1007/978-3-642-97881-4. Google Scholar

[35]

B. Hajek and R. G. Ogier, Optimal dynamic routing in communication networks with continuous traffic,, Networks, 14 (1984), 457. doi: 10.1002/net.3230140308. Google Scholar

[36]

J. Halpern, A generalized dynamic flows problem,, Networks, 9 (1979), 133. doi: 10.1002/net.3230090204. Google Scholar

[37]

H. W. Hamacher, Min Cost and Time Minimizing Dynamic Flows,, Technical Report 83-16, (1983), 83. Google Scholar

[38]

H. W. Hamacher, S. Heller and B. Rupp, Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning,, Annals of Operations Research, 207 (2013), 161. doi: 10.1007/s10479-011-0953-9. Google Scholar

[39]

H. W. Hamacher, S. Heller and S. Ruzika, A Sandwich Approach for Evacuation Time Bounds,, in PED 2010 Conference Proceedings, (2010). Google Scholar

[40]

H. W. Hamacher and S. A. Tjandra, Mathematical Modeling of Evacuation Problems: A State of the Art,, in Pedestrain and Evacuation Dynamics, (2002), 227. Google Scholar

[41]

H. W. Hamacher and S. Tufecki, On the use of lexicographic min-cost flows in evacuation modeling,, Naval Research Logistics, 34 (1987), 487. doi: 10.1002/1520-6750(198708)34:4<487::AID-NAV3220340404>3.0.CO;2-9. Google Scholar

[42]

G. Hamza-Lup, K. A. Hua, M. Le and R. Peng, Enhancing intelligent transportation systems to improve and support homeland security,, in Proceedings of the Seventh IEEE International Conference, (2004), 250. doi: 10.1109/ITSC.2004.1398906. Google Scholar

[43]

L. D. Han, F. Yuan, S. M. Chin and H. Hwang, Global optimization of emergency evacuation assignments,, Interfaces, 36 (2006), 502. doi: 10.1287/inte.1060.0251. Google Scholar

[44]

B. Hoppe and E. Tardos, Polynomial time algorithms for some evacuation problems,, in Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, (1994), 433. Google Scholar

[45]

B. Hoppe and E. Tardos, The quickest transshipment problem,, in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, (1995), 512. Google Scholar

[46]

B. Hoppe and E. Tardos, The quickest transshipment problem,, Mathematics of Operations Research, 25 (2000), 36. doi: 10.1287/moor.25.1.36.15211. Google Scholar

[47]

B. Hoppe, Efficient Dynamic Network Flow Algorithms,, Ph.D thesis, (1995). Google Scholar

[48]

Y. C. Hung and G. H. Chen, On the quickest path problem,, Inform. Process. Lett., 46 (1993), 125. doi: 10.1016/0020-0190(93)90057-G. Google Scholar

[49]

J. Jarvis and H. Ratliff, Some equivalent objectives for dynamic network flow problems,, Management Science, 28 (1982), 106. doi: 10.1287/mnsc.28.1.106. Google Scholar

[50]

D. Kagaris and G. E. Pantziou, S. Tragoudas and C. D. Zaroliagis, On the computation of fast data transmissions in networks with capacities and delays,, in Proceedings of the Workshop Algorithms Data Structured Series, 955 (1995), 291. doi: 10.1007/3-540-60220-8_71. Google Scholar

[51]

S. Kim, B. George and S. Shekhar, Evacuation Route Planning: Scalable Heuristics,, Proceedings of the 15th International Symposium on Advances in Geographic Information Systems ACM GIS, (2007). doi: 10.1145/1341012.1341039. Google Scholar

[52]

S. Kim and S. Shekhar, Contraflow network reconfiguration for evacuation planning: A summary of results,, in Proceedings of 13th ACM Symposium on Advances in Geographic Information Systems (GIS 05), (2005), 250. doi: 10.1145/1097064.1097099. Google Scholar

[53]

S. Kim, S. Shekhar and M. Min, Contraflow Transportation Network Reconfiguration for Evacuation Route Planning,, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1. Google Scholar

[54]

T. M. Kisko and R. L. Francis, EVACNET+: A computer program to determine optimal building evacuation plans,, Fire Safety Journal, 9 (1985), 211. doi: 10.1016/0379-7112(85)90009-8. Google Scholar

[55]

R. Koch, E. Nasrabadi and M. Skutella, Continuous and discrete flows over time - a general model based on measure theory,, Mathematical Methods of Operations Research, 73 (2011), 301. doi: 10.1007/s00186-011-0357-2. Google Scholar

[56]

E. Köhler, K. Langkau and M. Skutella, Time-expanded graphs for flow-dependent transit times,, in Proceedings of ESA (eds. R. Moehring and R. Raman), 2461 (2002), 599. doi: 10.1007/3-540-45749-6_53. Google Scholar

[57]

E. Köhler, R.H. Möhring and M. Skutella, Traffic networks and flows over time,, in Algorithmics of Large and Complex Networks (eds J. Lerner, 5515 (2009), 166. Google Scholar

[58]

B. Kotnyek, An annotated overview of dynamic network flows,, Technical Report, (2004), 1. Google Scholar

[59]

G. Kotusevski and K. A. Hawick, A review of traffic simulation software,, Res. Lett. Inf. Math. Sci., 13 (2009), 35. Google Scholar

[60]

E. D. Kuligowski, R. D. Peacock and B. L. Hoskins, A review of building evacuation models,, National Institute of Standards and Technology, 1680 (2010). Google Scholar

[61]

G. J. Lim, M. R. Baharnemati, S. Zangeneh and H. R. Parsaei, A network Flow based Optimization Approach for Hurricane Evacuation Planning,, ICOVACS 2009., (2009). Google Scholar

[62]

G. J. Lim, S. Zangeneh, M. R. Baharnemati and T. Assavapokee, A capacitated network flow optimization approach for short notice evacuation planning,, European Journal of Operational Research, 223 (2012), 234. doi: 10.1016/j.ejor.2012.06.004. Google Scholar

[63]

T. Litman, Lessons from katrina and rita: What major disasters can teach transportation planners,, Journal of Transportation Engineering, 132 (2006), 11. doi: 10.1061/(ASCE)0733-947X(2006)132:1(11). Google Scholar

[64]

Q. Lu, B. George and S. Shekhar, Capacity constrained routing algotithm for evacuation planning: A summary of results,, in Proceedings of the 9th International Symposium on Spatial and Temporal Databases (SSTD), 3633 (2005), 291. doi: 10.1007/11535331_17. Google Scholar

[65]

Q. Lu, Y. Huang and S. Shekhar, Evacuation planning: A capacity constrained routing approach,, in Proceedings of the First NSF/NIJ Symposium on Intelligence and Security Informatics, 2665 (2003), 111. doi: 10.1007/3-540-44853-5_9. Google Scholar

[66]

N. Megiddo, Optimal flows in networks with multiple sources and sinks,, Mathematical Programming, 7 (1974), 97. doi: 10.1007/BF01585506. Google Scholar

[67]

N. Megiddo, Combinatorial optimization with rational objective functions,, Mathematics of Operations Research, 4 (1979), 414. doi: 10.1287/moor.4.4.414. Google Scholar

[68]

E. Miller-Hooks and S. S. Patterson, On solving quickest time problems in time-dependent, dynamic networks,, Journal of Mathematical Modelling and Algorithms, 3 (2004), 39. doi: 10.1023/B:JMMA.0000026708.57419.6d. Google Scholar

[69]

E. Minieka, Maximal, lexicographic, and dynamic network flows,, Operations Research, 21 (1973), 517. doi: 10.1287/opre.21.2.517. Google Scholar

[70]

K. Moriarty, D. Ni and J. Collura, Modeling Traffic Flow Under Emergency Evacuation Situations: Current Practice and Future Directions,, in 86th Transportation Research Board Annual Meeting, (): 07. Google Scholar

[71]

M. F. S. Osman and B. Ram, Evacuation route scheduling using discrete time-based capacity-constrained model,, IEEE, (2009), 161. Google Scholar

[72]

P. M. Pardalos and A. Arulselvan, Multimodal Solutions for Large Scale Evacuations,, Center for Multimodal Solutions for Congestion Mitigation, (2009). Google Scholar

[73]

S. Petta and A. Ziliaskopoulos, Foundations of dynamic traffic assignment: The past, the present and the future,, Networks and Spatial Economics, 1 (2001), 233. Google Scholar

[74]

A. J. Pel, M. C. J. Bliemer and S. P. Hoogendoorn, A review on travel behaviour modelling in dynamic traffic simulation models for evacuations,, Transportation, 39 (2012), 97. doi: 10.1007/s11116-011-9320-6. Google Scholar

[75]

A. B. Philpott, Continuous-time shortset path problems and linear programming,, SIAM Journal of Contral and Optimization, 32 (1994), 538. doi: 10.1137/S0363012991196414. Google Scholar

[76]

S. Rebennack, A. Arulselvan, L. Elefteriadou and P. M. Pardalos, Complexity analysis for maximum flow problems with arc reversals,, Journal of Combinatorial Optimization, 19 (2010), 200. doi: 10.1007/s10878-008-9175-8. Google Scholar

[77]

D. Richardson and E. Tardos, Cited As Personal Communication in [27],, 2002., (). Google Scholar

[78]

J. B. Rosen, S. Z. Sun and G. L. Xue, Algorithms for the quickest path problems and the enumeration of quickest paths,, Computers and Operations Research, 18 (1991), 579. doi: 10.1016/0305-0548(91)90063-W. Google Scholar

[79]

S. Ruzika, H. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs,, Networks, 57 (2011), 169. Google Scholar

[80]

F. Sayyady and S. D. Eksioglu, Optimizing the use of public transit system during no-notice evacuation of urban areas,, Computers and Industrial Engineering, 59 (2010), 488. doi: 10.1016/j.cie.2010.06.001. Google Scholar

[81]

A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch and A. Seyfried, Evacuation dynamics: Empirical results, modeling and applications,, in Encyclopedia of Complexity and Systems Science, (2009), 3142. doi: 10.1007/978-0-387-30440-3_187. Google Scholar

[82]

M. Steiner, A Survey of Earliest Arrival Flows and a Study of the Series-Parallel Case,, Technische Universität Kaiserslautern, (2009). Google Scholar

[83]

A. Stepanov and J. E. Smith, Multi-objective evacuation routing in transportation networks,, European Journal of Operational Research, 198 (2009), 435. doi: 10.1016/j.ejor.2008.08.025. Google Scholar

[84]

K. Talebi and J. M. Smith, Stochastic network evacuation models,, Computers and Operations Research, 12 (1985), 559. doi: 10.1016/0305-0548(85)90054-1. Google Scholar

[85]

S. A. Tjandra, Dynamic Network Optimization with Applications to Evacuation Planning,, Ph.D. thesis, (2003). Google Scholar

[86]

H. Tuydes and Ziliaskopoulos, Network Re-design to Optimize Evacuation Contraflow,, in Proceedings of the 83rd Annual Meeting of the Transportation Research Board, (2004). Google Scholar

[87]

H. Tuydes and A. Ziliaskopoulos, Tabu-based heuristic for optimization of network evacuation contraflow,, in Proceedings of the 85rd Annual Meeting of the Transportation Research Board, 1964 (2006), 157. doi: 10.3141/1964-17. Google Scholar

[88]

P. M. Vaidya, A new algorithm for minimizing convex functions over convex sets,, in Proc. of the 30th Ann. IEEE Symposium Foundations Computer Science, (1989), 338. doi: 10.1109/SFCS.1989.63500. Google Scholar

[89]

W. L. Wilkinson, An algorithm for universal maximal dynamic flows in a network,, Operations Research, 19 (1971), 1602. doi: 10.1287/opre.19.7.1602. Google Scholar

[90]

B. Williams, A. Tagliaferri, S. Meinhold, J. Hummer and N. Rouphail, Simulation and analysis of freeway lane reversal for coastal hurricane evacuation,, Journal of Urban Planning and Development, 133 (2007), 61. doi: 10.1061/(ASCE)0733-9488(2007)133:1(61). Google Scholar

[91]

B. Wolshon, E. Urbina and M. Levitan, National Review of Hurricane Evacuation Plans and Policies,, Hurricane Center, (2002). Google Scholar

[92]

T. Yamada, A network flow approach to a city emergency evacuation planning,, International Journal of Systems Science, 27 (1996), 931. doi: 10.1080/00207729608929296. Google Scholar

[93]

D. Yin, A scalable heuristic for evacuation planning in large road network,, in Proceedings of the Second International Workshop: IWCTS, (2009), 19. doi: 10.1145/1645373.1645377. Google Scholar

[94]

M. Yusoff, J. Ariffin and A. Mohamed, Optimization approaches for macroscopic emergency evacuation planning: A survey,, in Information Technology, (2008), 1. doi: 10.1109/ITSIM.2008.4631982. Google Scholar

[95]

M. Zeng and C. Wang, Evacuation route planning algorithm: longer route preferential,, in Advances in Neural Networks ISNN 2009 (eds. W. Yu, 5551 (2009), 1062. doi: 10.1007/978-3-642-01507-6_119. Google Scholar

[96]

X. Zhou, B. George, S. Kim, J.M.R. Wolff, Q. Lu and S. Shekhar, Evacuation planning, a spatial network database approach,, Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, (2010), 1. Google Scholar

show all references

References:
[1]

S. Afandizadeh, A. Jahangiri and N. Kalantari, Determination of the optimal network configuration for emergency evacuation by simulated annealing algorithm,, in Proceedings of the 2nd WSEAS International Conference on Natural Hazards (NAHA'09), (2009), 65. Google Scholar

[2]

R. K. Ahuja, T. L. Magnati and J. B. Orlin, Network Flows: Theory, Algorithms and Applications,, Prentice Hall, (1993). Google Scholar

[3]

N. Altay and W. G. Green III, OR/MS research in disaster operations management,, European Journal of Operational Research, 175 (2006), 475. doi: 10.1016/j.ejor.2005.05.016. Google Scholar

[4]

E. J. Anderson, P. Nash and A. B. Philpott, A class of continuous network flow problems,, Mathematics of Operations Research, 7 (1982), 501. doi: 10.1287/moor.7.4.501. Google Scholar

[5]

J. E. Aronson, A survey of dynamic network flows,, Annals of Operations Research, 20 (1989), 1. doi: 10.1007/BF02216922. Google Scholar

[6]

N. Baumann, Evacuation by Earliest Arrival Flows,, Ph.D thesis, (2007). Google Scholar

[7]

N. Baumann and M. Skutella, Solving evacuation problems efficiently, earliest arrival flows with multiple sources,, in Foundations of Computer Science, (2006), 399. doi: 10.1109/FOCS.2006.70. Google Scholar

[8]

N. Baumann and M. Skutella, Earliest arrival flows with multiple sources,, Mathematics of Operations Research, 34 (2009), 499. doi: 10.1287/moor.1090.0382. Google Scholar

[9]

G. N. Berlin, The Use of Directed Routes for Assigning Escape Potential,, National Fire Protection Association, (1979). Google Scholar

[10]

D. R. Bish, Planning for a bus-based evacuation,, OR Spectrum, 33 (2011), 629. doi: 10.1007/s00291-011-0256-1. Google Scholar

[11]

S. Bretschneider and A. Kimms, Pattern-based evacuation planning for urban areas,, European Journal of Operational Research, 216 (2012), 57. doi: 10.1016/j.ejor.2011.07.015. Google Scholar

[12]

R. E. Burkard, K. Dlaska and H. Kellerer, The quickest disjoint flow problem,, Institute of Mathematics, (1991), 189. Google Scholar

[13]

R. E. Burkard, K. Dlaska and B. Klinz, The quickest flow problem,, ZOR-Methods and Models of Operations Research, 37 (1993), 31. doi: 10.1007/BF01415527. Google Scholar

[14]

M. Carey and E. Subrahmanian, An approach to modelling time-varying flows on congested networks,, Transportation Research B, 34 (2000), 157. doi: 10.1016/S0191-2615(99)00019-3. Google Scholar

[15]

L. G. Chalmet, R. L. Francis and P. B. Saunders, Network models for building evacuation,, Fire Technology, 18 (1982), 90. doi: 10.1007/BF02993491. Google Scholar

[16]

L. Chen and E. Miller-Hooks, The building evacuation problem with shared information,, Naval Research Logistics, 55 (2008), 363. doi: 10.1002/nav.20288. Google Scholar

[17]

Y. L. Chen and Y. H. Chin, The quickest path problem,, Computers and Operations Research, 17 (1990), 153. doi: 10.1016/0305-0548(90)90039-A. Google Scholar

[18]

W. Choi, H. W. Hamacher and S. Tufekci, Modeling of building evacuation problems by network flows with side constraints,, European Journal of Operations Research, 35 (1988), 98. doi: 10.1016/0377-2217(88)90382-7. Google Scholar

[19]

T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem for evacuation planning on series-parallel graph,, International Journal of Operations research, 10 (2013), 1. Google Scholar

[20]

K. F. Doerner, W. J. Gutjahr and L. V. Wassenhove, Special issue on optimization in disaster relief,, OR Spectrum, 33 (2011), 445. doi: 10.1007/s00291-011-0262-3. Google Scholar

[21]

Decision Support System for Large-Scale Evacuation Logistics, Homepage, 2012,, , (). Google Scholar

[22]

B. Eksioglu, A.V. Vural and A. Reisman, The vehicle routing problem: A taxonomic review,, Computers & Industrial Engineering, 57 (2009), 1472. doi: 10.1016/j.cie.2009.05.009. Google Scholar

[23]

L. Fleischer, Universally maximum flow with piecewise-constant capacities,, Networks, 38 (2001), 115. doi: 10.1002/net.1030. Google Scholar

[24]

L. Fleischer and E. Tardos, Efficient continuous-time dynamic network flow algorithms,, Operations Research Letters, 23 (1998), 71. doi: 10.1016/S0167-6377(98)00037-6. Google Scholar

[25]

L. K. Fleischer, Faster algorithms for quickest transshipment problem,, SIAM Journal on Optimization, 12 (2001), 18. doi: 10.1137/S1052623497327295. Google Scholar

[26]

L. K. Fleischer and M. Skutella, Quickest multicommodity flow problem,, in Integer Programming and Combinatorial Optimization, 2337 (2002), 36. doi: 10.1007/3-540-47867-1_4. Google Scholar

[27]

L. K. Fleischer and M. Skutella, Quickest flows over time,, SIAM Journal on Computing, 36 (2007), 1600. doi: 10.1137/S0097539703427215. Google Scholar

[28]

F. R. Ford and D. R. Fulkerson, Constructing maximal dynamic flows from static flows,, Operations Research, 6 (1958), 419. doi: 10.1287/opre.6.3.419. Google Scholar

[29]

F. R. Ford and D. R. Fulkerson, Flows in Networks,, Princeton University Press, (1962). Google Scholar

[30]

D. Gale, Transient flows in networks,, Michigan Mathematical Journal, 6 (1959), 59. doi: 10.1307/mmj/1028998140. Google Scholar

[31]

G. M. Gallo, M. Grigoriadis and R. E. Tarjan, A Fast parametric maximum flow algorithm and applications,, SIAM Journal of Computing, 18 (1989), 30. doi: 10.1137/0218003. Google Scholar

[32]

B. George, S. Kim and S. Shekhar, Spatio-temporal network databases and routing algorithms: A summary of results,, in Proceedings of the 11th International Symposium on Spatial and Temporal Databases (SSTD), 4605 (2007), 460. doi: 10.1007/978-3-540-73540-3_26. Google Scholar

[33]

B. George and S. Shekhar, Time-aggregated Graphs for Modeling Spatio-temporal Networks- An Extended Abstract,, in Proceedings of the Workshop at International Conference on Conceptual Modeling, (2006). Google Scholar

[34]

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization,, Springer Verlag Berlin, (1988). doi: 10.1007/978-3-642-97881-4. Google Scholar

[35]

B. Hajek and R. G. Ogier, Optimal dynamic routing in communication networks with continuous traffic,, Networks, 14 (1984), 457. doi: 10.1002/net.3230140308. Google Scholar

[36]

J. Halpern, A generalized dynamic flows problem,, Networks, 9 (1979), 133. doi: 10.1002/net.3230090204. Google Scholar

[37]

H. W. Hamacher, Min Cost and Time Minimizing Dynamic Flows,, Technical Report 83-16, (1983), 83. Google Scholar

[38]

H. W. Hamacher, S. Heller and B. Rupp, Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning,, Annals of Operations Research, 207 (2013), 161. doi: 10.1007/s10479-011-0953-9. Google Scholar

[39]

H. W. Hamacher, S. Heller and S. Ruzika, A Sandwich Approach for Evacuation Time Bounds,, in PED 2010 Conference Proceedings, (2010). Google Scholar

[40]

H. W. Hamacher and S. A. Tjandra, Mathematical Modeling of Evacuation Problems: A State of the Art,, in Pedestrain and Evacuation Dynamics, (2002), 227. Google Scholar

[41]

H. W. Hamacher and S. Tufecki, On the use of lexicographic min-cost flows in evacuation modeling,, Naval Research Logistics, 34 (1987), 487. doi: 10.1002/1520-6750(198708)34:4<487::AID-NAV3220340404>3.0.CO;2-9. Google Scholar

[42]

G. Hamza-Lup, K. A. Hua, M. Le and R. Peng, Enhancing intelligent transportation systems to improve and support homeland security,, in Proceedings of the Seventh IEEE International Conference, (2004), 250. doi: 10.1109/ITSC.2004.1398906. Google Scholar

[43]

L. D. Han, F. Yuan, S. M. Chin and H. Hwang, Global optimization of emergency evacuation assignments,, Interfaces, 36 (2006), 502. doi: 10.1287/inte.1060.0251. Google Scholar

[44]

B. Hoppe and E. Tardos, Polynomial time algorithms for some evacuation problems,, in Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, (1994), 433. Google Scholar

[45]

B. Hoppe and E. Tardos, The quickest transshipment problem,, in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, (1995), 512. Google Scholar

[46]

B. Hoppe and E. Tardos, The quickest transshipment problem,, Mathematics of Operations Research, 25 (2000), 36. doi: 10.1287/moor.25.1.36.15211. Google Scholar

[47]

B. Hoppe, Efficient Dynamic Network Flow Algorithms,, Ph.D thesis, (1995). Google Scholar

[48]

Y. C. Hung and G. H. Chen, On the quickest path problem,, Inform. Process. Lett., 46 (1993), 125. doi: 10.1016/0020-0190(93)90057-G. Google Scholar

[49]

J. Jarvis and H. Ratliff, Some equivalent objectives for dynamic network flow problems,, Management Science, 28 (1982), 106. doi: 10.1287/mnsc.28.1.106. Google Scholar

[50]

D. Kagaris and G. E. Pantziou, S. Tragoudas and C. D. Zaroliagis, On the computation of fast data transmissions in networks with capacities and delays,, in Proceedings of the Workshop Algorithms Data Structured Series, 955 (1995), 291. doi: 10.1007/3-540-60220-8_71. Google Scholar

[51]

S. Kim, B. George and S. Shekhar, Evacuation Route Planning: Scalable Heuristics,, Proceedings of the 15th International Symposium on Advances in Geographic Information Systems ACM GIS, (2007). doi: 10.1145/1341012.1341039. Google Scholar

[52]

S. Kim and S. Shekhar, Contraflow network reconfiguration for evacuation planning: A summary of results,, in Proceedings of 13th ACM Symposium on Advances in Geographic Information Systems (GIS 05), (2005), 250. doi: 10.1145/1097064.1097099. Google Scholar

[53]

S. Kim, S. Shekhar and M. Min, Contraflow Transportation Network Reconfiguration for Evacuation Route Planning,, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1. Google Scholar

[54]

T. M. Kisko and R. L. Francis, EVACNET+: A computer program to determine optimal building evacuation plans,, Fire Safety Journal, 9 (1985), 211. doi: 10.1016/0379-7112(85)90009-8. Google Scholar

[55]

R. Koch, E. Nasrabadi and M. Skutella, Continuous and discrete flows over time - a general model based on measure theory,, Mathematical Methods of Operations Research, 73 (2011), 301. doi: 10.1007/s00186-011-0357-2. Google Scholar

[56]

E. Köhler, K. Langkau and M. Skutella, Time-expanded graphs for flow-dependent transit times,, in Proceedings of ESA (eds. R. Moehring and R. Raman), 2461 (2002), 599. doi: 10.1007/3-540-45749-6_53. Google Scholar

[57]

E. Köhler, R.H. Möhring and M. Skutella, Traffic networks and flows over time,, in Algorithmics of Large and Complex Networks (eds J. Lerner, 5515 (2009), 166. Google Scholar

[58]

B. Kotnyek, An annotated overview of dynamic network flows,, Technical Report, (2004), 1. Google Scholar

[59]

G. Kotusevski and K. A. Hawick, A review of traffic simulation software,, Res. Lett. Inf. Math. Sci., 13 (2009), 35. Google Scholar

[60]

E. D. Kuligowski, R. D. Peacock and B. L. Hoskins, A review of building evacuation models,, National Institute of Standards and Technology, 1680 (2010). Google Scholar

[61]

G. J. Lim, M. R. Baharnemati, S. Zangeneh and H. R. Parsaei, A network Flow based Optimization Approach for Hurricane Evacuation Planning,, ICOVACS 2009., (2009). Google Scholar

[62]

G. J. Lim, S. Zangeneh, M. R. Baharnemati and T. Assavapokee, A capacitated network flow optimization approach for short notice evacuation planning,, European Journal of Operational Research, 223 (2012), 234. doi: 10.1016/j.ejor.2012.06.004. Google Scholar

[63]

T. Litman, Lessons from katrina and rita: What major disasters can teach transportation planners,, Journal of Transportation Engineering, 132 (2006), 11. doi: 10.1061/(ASCE)0733-947X(2006)132:1(11). Google Scholar

[64]

Q. Lu, B. George and S. Shekhar, Capacity constrained routing algotithm for evacuation planning: A summary of results,, in Proceedings of the 9th International Symposium on Spatial and Temporal Databases (SSTD), 3633 (2005), 291. doi: 10.1007/11535331_17. Google Scholar

[65]

Q. Lu, Y. Huang and S. Shekhar, Evacuation planning: A capacity constrained routing approach,, in Proceedings of the First NSF/NIJ Symposium on Intelligence and Security Informatics, 2665 (2003), 111. doi: 10.1007/3-540-44853-5_9. Google Scholar

[66]

N. Megiddo, Optimal flows in networks with multiple sources and sinks,, Mathematical Programming, 7 (1974), 97. doi: 10.1007/BF01585506. Google Scholar

[67]

N. Megiddo, Combinatorial optimization with rational objective functions,, Mathematics of Operations Research, 4 (1979), 414. doi: 10.1287/moor.4.4.414. Google Scholar

[68]

E. Miller-Hooks and S. S. Patterson, On solving quickest time problems in time-dependent, dynamic networks,, Journal of Mathematical Modelling and Algorithms, 3 (2004), 39. doi: 10.1023/B:JMMA.0000026708.57419.6d. Google Scholar

[69]

E. Minieka, Maximal, lexicographic, and dynamic network flows,, Operations Research, 21 (1973), 517. doi: 10.1287/opre.21.2.517. Google Scholar

[70]

K. Moriarty, D. Ni and J. Collura, Modeling Traffic Flow Under Emergency Evacuation Situations: Current Practice and Future Directions,, in 86th Transportation Research Board Annual Meeting, (): 07. Google Scholar

[71]

M. F. S. Osman and B. Ram, Evacuation route scheduling using discrete time-based capacity-constrained model,, IEEE, (2009), 161. Google Scholar

[72]

P. M. Pardalos and A. Arulselvan, Multimodal Solutions for Large Scale Evacuations,, Center for Multimodal Solutions for Congestion Mitigation, (2009). Google Scholar

[73]

S. Petta and A. Ziliaskopoulos, Foundations of dynamic traffic assignment: The past, the present and the future,, Networks and Spatial Economics, 1 (2001), 233. Google Scholar

[74]

A. J. Pel, M. C. J. Bliemer and S. P. Hoogendoorn, A review on travel behaviour modelling in dynamic traffic simulation models for evacuations,, Transportation, 39 (2012), 97. doi: 10.1007/s11116-011-9320-6. Google Scholar

[75]

A. B. Philpott, Continuous-time shortset path problems and linear programming,, SIAM Journal of Contral and Optimization, 32 (1994), 538. doi: 10.1137/S0363012991196414. Google Scholar

[76]

S. Rebennack, A. Arulselvan, L. Elefteriadou and P. M. Pardalos, Complexity analysis for maximum flow problems with arc reversals,, Journal of Combinatorial Optimization, 19 (2010), 200. doi: 10.1007/s10878-008-9175-8. Google Scholar

[77]

D. Richardson and E. Tardos, Cited As Personal Communication in [27],, 2002., (). Google Scholar

[78]

J. B. Rosen, S. Z. Sun and G. L. Xue, Algorithms for the quickest path problems and the enumeration of quickest paths,, Computers and Operations Research, 18 (1991), 579. doi: 10.1016/0305-0548(91)90063-W. Google Scholar

[79]

S. Ruzika, H. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs,, Networks, 57 (2011), 169. Google Scholar

[80]

F. Sayyady and S. D. Eksioglu, Optimizing the use of public transit system during no-notice evacuation of urban areas,, Computers and Industrial Engineering, 59 (2010), 488. doi: 10.1016/j.cie.2010.06.001. Google Scholar

[81]

A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch and A. Seyfried, Evacuation dynamics: Empirical results, modeling and applications,, in Encyclopedia of Complexity and Systems Science, (2009), 3142. doi: 10.1007/978-0-387-30440-3_187. Google Scholar

[82]

M. Steiner, A Survey of Earliest Arrival Flows and a Study of the Series-Parallel Case,, Technische Universität Kaiserslautern, (2009). Google Scholar

[83]

A. Stepanov and J. E. Smith, Multi-objective evacuation routing in transportation networks,, European Journal of Operational Research, 198 (2009), 435. doi: 10.1016/j.ejor.2008.08.025. Google Scholar

[84]

K. Talebi and J. M. Smith, Stochastic network evacuation models,, Computers and Operations Research, 12 (1985), 559. doi: 10.1016/0305-0548(85)90054-1. Google Scholar

[85]

S. A. Tjandra, Dynamic Network Optimization with Applications to Evacuation Planning,, Ph.D. thesis, (2003). Google Scholar

[86]

H. Tuydes and Ziliaskopoulos, Network Re-design to Optimize Evacuation Contraflow,, in Proceedings of the 83rd Annual Meeting of the Transportation Research Board, (2004). Google Scholar

[87]

H. Tuydes and A. Ziliaskopoulos, Tabu-based heuristic for optimization of network evacuation contraflow,, in Proceedings of the 85rd Annual Meeting of the Transportation Research Board, 1964 (2006), 157. doi: 10.3141/1964-17. Google Scholar

[88]

P. M. Vaidya, A new algorithm for minimizing convex functions over convex sets,, in Proc. of the 30th Ann. IEEE Symposium Foundations Computer Science, (1989), 338. doi: 10.1109/SFCS.1989.63500. Google Scholar

[89]

W. L. Wilkinson, An algorithm for universal maximal dynamic flows in a network,, Operations Research, 19 (1971), 1602. doi: 10.1287/opre.19.7.1602. Google Scholar

[90]

B. Williams, A. Tagliaferri, S. Meinhold, J. Hummer and N. Rouphail, Simulation and analysis of freeway lane reversal for coastal hurricane evacuation,, Journal of Urban Planning and Development, 133 (2007), 61. doi: 10.1061/(ASCE)0733-9488(2007)133:1(61). Google Scholar

[91]

B. Wolshon, E. Urbina and M. Levitan, National Review of Hurricane Evacuation Plans and Policies,, Hurricane Center, (2002). Google Scholar

[92]

T. Yamada, A network flow approach to a city emergency evacuation planning,, International Journal of Systems Science, 27 (1996), 931. doi: 10.1080/00207729608929296. Google Scholar

[93]

D. Yin, A scalable heuristic for evacuation planning in large road network,, in Proceedings of the Second International Workshop: IWCTS, (2009), 19. doi: 10.1145/1645373.1645377. Google Scholar

[94]

M. Yusoff, J. Ariffin and A. Mohamed, Optimization approaches for macroscopic emergency evacuation planning: A survey,, in Information Technology, (2008), 1. doi: 10.1109/ITSIM.2008.4631982. Google Scholar

[95]

M. Zeng and C. Wang, Evacuation route planning algorithm: longer route preferential,, in Advances in Neural Networks ISNN 2009 (eds. W. Yu, 5551 (2009), 1062. doi: 10.1007/978-3-642-01507-6_119. Google Scholar

[96]

X. Zhou, B. George, S. Kim, J.M.R. Wolff, Q. Lu and S. Shekhar, Evacuation planning, a spatial network database approach,, Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, (2010), 1. Google Scholar

[1]

Urmila Pyakurel, Tanka Nath Dhamala. Evacuation planning by earliest arrival contraflow. Journal of Industrial & Management Optimization, 2017, 13 (1) : 489-503. doi: 10.3934/jimo.2016028

[2]

Xiaodi Bai, Xiaojin Zheng, Xiaoling Sun. A survey on probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 767-778. doi: 10.3934/naco.2012.2.767

[3]

Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044

[4]

Juan Carlos López Alfonso, Giuseppe Buttazzo, Bosco García-Archilla, Miguel A. Herrero, Luis Núñez. A class of optimization problems in radiotherapy dosimetry planning. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1651-1672. doi: 10.3934/dcdsb.2012.17.1651

[5]

Afaf Bouharguane, Pascal Azerad, Frédéric Bouchette, Fabien Marche, Bijan Mohammadi. Low complexity shape optimization & a posteriori high fidelity validation. Discrete & Continuous Dynamical Systems - B, 2010, 13 (4) : 759-772. doi: 10.3934/dcdsb.2010.13.759

[6]

Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289

[7]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321

[8]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018179

[9]

King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021

[10]

Zhuwei Qin, Fuxun Yu, Chenchen Liu, Xiang Chen. How convolutional neural networks see the world --- A survey of convolutional neural network visualization methods. Mathematical Foundations of Computing, 2018, 1 (2) : 149-180. doi: 10.3934/mfc.2018008

[11]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[12]

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211

[13]

Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094

[14]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[15]

Simone Göttlich, Sebastian Kühn, Jan Peter Ohst, Stefan Ruzika, Markus Thiemann. Evacuation dynamics influenced by spreading hazardous material. Networks & Heterogeneous Media, 2011, 6 (3) : 443-464. doi: 10.3934/nhm.2011.6.443

[16]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31

[17]

Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial & Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285

[18]

Qiong Liu, Ahmad Reza Rezaei, Kuan Yew Wong, Mohammad Mahdi Azami. Integrated modeling and optimization of material flow and financial flow of supply chain network considering financial ratios. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009

[19]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

[20]

Nicolas Boizot, Jean-Paul Gauthier. On the motion planning of the ball with a trailer. Mathematical Control & Related Fields, 2013, 3 (3) : 269-286. doi: 10.3934/mcrf.2013.3.269

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (63)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]