Dynamic network flow location models and algorithms for quickest evacuation planning

Hari Nandan Nath; Urmila Pyakurel; Tanka Nath Dhamala; Stephan Dempe

doi:10.3934/jimo.2020102

Article Contents

2021, Volume 17, Issue 5: 2943-2970. Doi: 10.3934/jimo.2020102

This issue Previous Article A

$ {BMAP/BMSP/1} $

queue with Markov dependent arrival and Markov dependent service batches Next Article Optimal reinsurance with default risk: A reinsurer's perspective

Dynamic network flow location models and algorithms for quickest evacuation planning

1.
Tribhuvan University, Bhaktapur Multiple Campus, Bhaktapur, Nepal
2.
Central Department of Mathematics, Tribhuvan University, P.O. Box 13143, Kathmandu, Nepal
3.
TU Bergakademie, Fakultät für Mathematik und Informatik, 09596 Freiberg, Germany

^* Corresponding author: Urmila Pyakurel
^* Corresponding author: Urmila Pyakurel

Received: January 2019

Revised: January 2020

Early access: June 2020

Published: September 2021

Abstract / Introduction Full Text(HTML) Figure(3) / Table(5) Related Papers Cited by

Abstract

Dynamic network flow problems have wide applications in evacuation planning. From a given subset of arcs in a directed network, choosing the suitable arcs for facility location with a given objective is very important in the optimization of flow in emergency cases. Because of the decrease in capacity of an arc by placing a facility in it, there may be a reduction in the maximum flow or increase in the quickest time. In this work, we consider a problem of identifying the optimal facility locations so that the increase in the quickest time is minimum. Introducing the quickest FlowLoc problem, we give strongly polynomial time algorithms to solve the single facility case. Realizing NP-hardness of the multi-facility case, we develop a mixed integer programming formulation of it and propose two polynomial time heuristics for its solution. Because of the growing concerns of arc reversals in evacuation planning, we introduce the quickest ContraFlowLoc problem and present exact algorithms to solve the single-facility case and heuristics to solve the multi-facility case, with polynomial time complexity. The solutions thus obtained here are practically important, particularly in evacuation planning, to systematize traffic flow with facility allocation minimizing evacuation time.

Keywords:

Mathematics Subject Classification: Primary: 90B10, 90C27, 68Q25; Secondary: 90B06, 90B20.

Citation:

Full Text(HTML)

Figure 1. Evacuation network $ N $ with arc labels (capacity, travel time)

Download: Full-size image PowerPoint slide

Figure 2.

Download: Full-size image PowerPoint slide

Figure 3. Auxiliary network $ \bar{N} $ of network $ N $ in Figure 1 with arc labels (capacity, travel time)

Download: Full-size image PowerPoint slide

Table 1. Maximum dynamic FlowLoc decisions (cf. Figure 1)

$ T $	maximum dynamic flow value when facility is placed on		Location decision
$ T $	(2, 3)	(2, 4)	Location decision
4	0	1	(2, 4)
5	4	5	(2, 4)
6	11	11	(2, 4) or (2, 3)
7	18	17	(2, 3)

| Show Table

DownLoad: CSV

Table 2. Quickest FlowLoc decisions (cf. Figure 1)

$ F $	quickest time when facility is placed on		Location decision
$ F $	(2, 3)	(2, 4)	Location decision
1	4.25	4	(2, 4)
5	5.14	5	(2, 4)
11	6	6	(2, 4) or (2, 3)
21	7.43	7.67	(2, 3)

| Show Table

DownLoad: CSV

Table 4. Computational results for some instances with $ F = 20000 $

$ \|L\| $	$ \|P\| $	Algorithm 4		Algorithm 5		MILP
$ \|L\| $	$ \|P\| $	R. time	$ T^* $	R. time	$ T^* $	R. time	$ T^* $
5	5	0.14	3209.3	0.53	2717.6	0.87	2713.5
5	7	0.16	2831.9	0.49	2707.6	1.39	2707.1
6	7	0.13	3222.1	0.65	2881.2	1.93	2878.1
8	10	0.15	2580.0	0.58	2575.0	2.92	2575.0
8	8	0.14	3189.3	0.47	3189.3	2.01	3189.3
9	10	0.15	2725.9	0.66	2593.3	3.46	2593.3
10	10	0.17	2587.8	0.73	2585.6	8.01	2585.6
11	10	0.11	2847.5	0.81	2573.9	5.69	2573.9
11	11	0.17	2586.7	0.83	2580.6	15.16	2580.6
11	15	0.20	2721.8	0.72	2710.6	52.52	2707.6
12	11	0.15	2708.2	0.73	2585.0	6.7	2585.0
12	15	0.17	2877.5	0.69	2881.2	114.77	2877.5
13	15	0.12	2588.3	0.51	2576.1	2.82	2576.1
14	15	0.24	2578.3	0.72	2579.4	645.67	2576.1
14	21	0.11	2861.9	0.69	2712.4	134.76	2595.0
15	17	0.16	3005.3	0.98	2843.1	224.36	2843.1
15	20	0.16	3036.7	1.10	2733.5	47.37	2733.5
16	17	0.16	2736.5	1.06	2722.4	221.88	2722.4
17	19	0.19	2851.9	1.29	2717.1	379.54	2716.5
18	19	0.20	2581.7	0.97	2583.3	214.78	2581.1
18	19	0.16	2589.4	1.18	2585.6	822.64	2585.6
19	20	0.24	2595.0	1.93	2607.2	-	-
19	24	0.59	3032.7	1.76	2868.8	-	-
20	25	0.18	2707.6	1.25	2707.6	-	-
21	25	0.15	2577.8	1.21	2577.8	-	-
23	25	0.14	2692.9	1.47	2575.0	-	-
23	26	0.14	2705.3	1.05	2705.3	-	-
24	26	0.20	3026.0	1.87	2863.1	-	-
26	29	0.14	2704.7	1.42	2704.7	-	-
28	40	0.20	2585.0	1.14	2585.0	-	-
28	39	0.17	2586.7	1.20	2586.7	-	-
29	34	0.16	2851.2	1.42	2851.2	-	-
30	40	0.24	2588.3	1.55	2588.3	-	-
31	38	0.17	2851.2	1.75	2851.2	-	-
31	37	0.22	2600.0	1.57	2600.0	-	-
32	40	0.17	2706.5	1.54	2706.5	-	-
37	43	0.22	2701.8	1.77	2701.8	-	-
38	41	0.21	2597.2	1.44	2598.9	-	-
39	50	0.25	2710.0	1.95	2710.0	-	-
40	50	0.09	2573.3	1.76	2571.7	-	-
41	48	0.20	2710.6	2.19	2710.6	-	-

| Show Table

DownLoad: CSV

Table 3. Percentage Deviation from the MILP objective function values

	Algorithm 4	Algorithm 5
Maximum deviation	21.55%	5.31 %
Average deviation	3.48 %	0.18%

| Show Table

DownLoad: CSV

Table 5. Quickest time calculations (cf. Example 4)

	Quickest time, $ F = 109 $
Facility placed on	Before contraflow	After contraflow
$ (2,1) $	20	15
$ (1,3) $	25.8	14.27
Location Decision	$ (2,1) $	$ (1,3) $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993.
[2]	S. An, N. Cui, X. Li and Y. Ouyang, Location planning for transit-based evacuation under the risk of service disruptions, Transportation Research Part B: Methodological, 54 (2013), 1-16. doi: 10.1016/j.trb.2013.03.002.
[3]	R. D. Armstrong and Z. Jin, A new strongly polynomial dual network simplex algorithm, Mathematical Programming, 78 (1997), 131-148. doi: 10.1007/BF02614366.
[4]	T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem on series-parallel graphs, International Journal of Operations Research, 10 (2013), 1-13.
[5]	T. N. Dhamala, U. Pyakurel and S. Dempe, A critical survey on the network optimization algorithms for evacuation planning problems, International Journal of Operations Research, 15 (2018), 101-133.
[6]	R. C. Dhungana and T. N. Dhamala, Maximum FlowLoc Problems with Network Reconfiguration, International Journal of Operations Research, 16 (2019), 13-26. doi: 10.6886/IJOR.201903_16(1).0002.
[7]	R. C. Dhungana, U. Pyakurel and T. N. Dhamala, Abstract contraflow models and solution procedures for evacuation planning, Journal of Mathematics Research, 10 (2018), 89-100.
[8]	L. R. Ford Jr. and D. R. Fulkerson, Constructing maximal dynamic flows from static flows, Operations Research, 6 (1958), 419-433. doi: 10.1287/opre.6.3.419.
[9]	M. Goerigk, K. Deghdak and P. Heßler, A comprehensive evacuation planning model and genetic soution algorithm, Transportation Research, Part E, 71 (2014), 82-97.
[10]	M. Goerigk, B. Grün and P. Heßler, Combining bus evacuation with location decisions: A branch-and-price approach, Transportation Research Procedia, 2 (2014), 783-791. doi: 10.1016/j.trpro.2014.09.088.
[11]	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-180. doi: 10.1007/s10479-011-0953-9.
[12]	S. Heller and H. W. Hamacher, The multi-terminal $q$-FlowLoc problem: A heuristic, in Lecture Notes in Computer Science, Proceedings of the International Network Optimization Conference, Springer, 6701 (2011), 523–528. doi: 10.1007/978-3-642-21527-8_57.
[13]	H. Jia, F. Ordóñez and M. Dessouky, A modeling framework for facility location of medical services for large-scale emergencies, IIE Transactions, 39 (2007), 41-55. doi: 10.1080/07408170500539113.
[14]	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-15.
[15]	S. Kongsomsaksakul, C. Yang and A. Chen, Shelter location-allocation model for flood evacuation planning, Journal of the Eastern Asia Society for Transportation Studies, 6 (2005), 4237-4252.
[16]	E. Köhler, K. Langkau and M. Skutella, Time expanded graphs for flow-dependent transit times, in European Symposium on Algorithms (eds. R. Möhring and R. Raman), Springer, 2461 (2002), 599–611. doi: 10.1007/3-540-45749-6_53.
[17]	A. Kulshrestha, Y. Lou and Y. Yin, Pick-up locations and bus allocation for transit-based evacuation planning with demand uncertainty, Journal of Advanced Transportation, 48 (2014), 721-733. doi: 10.1002/atr.1221.
[18]	M. Lin and P. Jaillet, On the quickest flow problem in dynamic networks–a parametric min-cost flow approach, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, (2015), 1343–1356. doi: 10.1137/1.9781611973730.89.
[19]	M. Ng, J. Park and S. T. Waller, A hybrid bilevel model for the optimal shelter assignment in emergency evacuations, Computer-Aided Civil and Infrastructure Engineering, 25 (2010), 547-556. doi: 10.1111/j.1467-8667.2010.00669.x.
[20]	J. B. Orlin, Max flows in $ O(nm) $ time, or better,, in Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, (2013), 765–774. doi: 10.1145/2488608.2488705.
[21]	U. Pyakurel, Evacuation Planning Problem with Contraflow Approach, PhD thesis, IOST, Tribhuvan University, Nepal, 2016.
[22]	U. Pyakurel and T. N. Dhamala, Models and algorithms on contraflow evacuation planning network problems, International Journal of Operations Research, 12 (2015), 36-46.
[23]	U. Pyakurel and T. N. Dhamala, Continuous time dynamic contraflow models and algorithms,, Advances in Operations Research - Hindawi, 2016 (2016), Art. ID 7902460, 7 pp. doi: 10.1155/2016/7902460.
[24]	U. Pyakurel and T. N. Dhamala, Continuous dynamic contraflow approach for evacuation planning, Annals of Operations Research, 253 (2017), 573-598. doi: 10.1007/s10479-016-2302-5.
[25]	U. Pyakurel and T. N. Dhamala, Evacuation planning by earliest arrival contraflow, Journal of Industrial and Management Optimization, 13 (2017), 487-501. doi: 10.3934/jimo.2016028.
[26]	U. Pyakurel, T. N. Dhamala and S. Dempe, Efficient continuous contraflow algorithms for evacuation planning problems, Annals of Operations Research, 254 (2017), 335-364. doi: 10.1007/s10479-017-2427-1.
[27]	U. Pyakurel, H. W. Hamacher and T. N. Dhamala, Generalized maximum dynamic contraflow on lossy network, International Journal of Operations Research Nepal, 3 (2014), 27-44.
[28]	U. Pyakurel, H. N. Nath, S. Dempe and T. N. Dhamala, Efficient dynamic flow algorithms for evacuation planning problems with partial lane reversal, Mathematics, 7 (2019), 993. doi: 10.3390/math7100993.
[29]	U. Pyakurel, H. N. Nath and T. N. Dhamala, Efficient contraflow algorithms for quickest evacuation planning, Science China Mathematics, 61 (2018), 2079-2100. doi: 10.1007/s11425-017-9264-3.
[30]	U. Pyakurel, H. N. Nath and T. N. Dhamala, Partial contraflow with path reversals for evacuation planning, Annals of Operations Research, 283 (2019), 591-612. doi: 10.1007/s10479-018-3031-8.
[31]	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-216. doi: 10.1007/s10878-008-9175-8.
[32]	B. Rupp, FlowLoc: Discrete Facility Locations in Flow Networks, Diploma thesis, University of Kaiserslautern, Germany, 2010.
[33]	S. Ruzika, H. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs, Networks, 57 (2011), 169-173. doi: 10.1002/net.20398.
[34]	M. Saho and M. Shigeno, Cancel-and-tighten algorithm for quickest flow problems, Network, 69 (2017), 179-188. doi: 10.1002/net.21726.
[35]	Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, Englewood Cliffs, 1985.
[36]	H. D. Sherali, T. B. Carter and A. G. Hobeika, A location-allocation model and algorithm for evacuation planning under hurricane/flood conditions, Transportation Research Part B: Methodological, 25 (1991), 439-452. doi: 10.1016/0191-2615(91)90037-J.
[37]	M. Skutella, An introduction to network flows over time,, in Research Trends in Combinatorial Optimization, (2009), 451–482. doi: 10.1007/978-3-540-76796-1_21.
[38]	E. Torres, Linearization of mixed-integer products, Mathematical Programming, 49 (1990), 427-428. doi: 10.1007/BF01588802.
[39]	C. Vogiatzis, J. L. Walteros and P. M. Pardalos, Evacuation through clustering techniques,, in Models, Algorithms, and Technologies for Network Analysis, Springer New York, 32 (2013), 185–198. doi: 10.1007/978-1-4614-5574-5_10.
[40]	C. Vogiatzis, R. Yoshida, I. Aviles-Spadoni, S. Imamoto and P. M. Pardalos, Livestock evacuation planning for natural and man-made emergencies, International Journal of Mass Emergencies and Disasters, 31 (2013), 25-37.