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.

[2]

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

[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.

[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.

[5]

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

[6]

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

[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.

[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.

[9]

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

[10]

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

[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.

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[21]

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

[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.

[23]

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

[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.

[25]

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

[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.

[27]

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

[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.

[29]

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

[30]

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

[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.

[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.

[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).

[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.

[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.

[36]

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

[37]

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

[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.

[39]

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

[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.

[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.

[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.

[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.

[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.

[45]

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

[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.

[47]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[58]

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

[59]

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

[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).

[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).

[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.

[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).

[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.

[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.

[66]

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

[67]

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

[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.

[69]

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

[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.

[71]

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

[72]

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

[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.

[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.

[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.

[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.

[77]

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

[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.

[79]

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

[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.

[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.

[82]

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

[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.

[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.

[85]

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

[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).

[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.

[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.

[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.

[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).

[91]

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

[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.

[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.

[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.

[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.

[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.

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.

[2]

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

[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.

[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.

[5]

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

[6]

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

[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.

[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.

[9]

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

[10]

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

[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.

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[21]

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

[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.

[23]

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

[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.

[25]

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

[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.

[27]

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

[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.

[29]

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

[30]

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

[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.

[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.

[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).

[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.

[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.

[36]

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

[37]

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

[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.

[39]

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

[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.

[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.

[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.

[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.

[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.

[45]

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

[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.

[47]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[58]

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

[59]

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

[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).

[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).

[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.

[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).

[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.

[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.

[66]

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

[67]

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

[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.

[69]

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

[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.

[71]

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

[72]

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

[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.

[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.

[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.

[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.

[77]

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

[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.

[79]

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

[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.

[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.

[82]

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

[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.

[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.

[85]

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

[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).

[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.

[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.

[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.

[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).

[91]

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

[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.

[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.

[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.

[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.

[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.

[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

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]