doi: 10.3934/jimo.2020102

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

Received  January 2019 Revised  January 2020 Published  June 2020

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.

Citation: Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020102
References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993.  Google Scholar

[2]

S. AnN. CuiX. 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.  Google Scholar

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

[4]

T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem on series-parallel graphs, International Journal of Operations Research, 10 (2013), 1-13.   Google Scholar

[5]

T. N. DhamalaU. 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.   Google Scholar

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

[7]

R. C. DhunganaU. Pyakurel and T. N. Dhamala, Abstract contraflow models and solution procedures for evacuation planning, Journal of Mathematics Research, 10 (2018), 89-100.   Google Scholar

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

[9]

M. GoerigkK. Deghdak and P. Heßler, A comprehensive evacuation planning model and genetic soution algorithm, Transportation Research, Part E, 71 (2014), 82-97.   Google Scholar

[10]

M. GoerigkB. 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.  Google Scholar

[11]

H. W. HamacherS. 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.  Google Scholar

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

[13]

H. JiaF. 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.  Google Scholar

[14]

S. KimS. Shekhar and M. Min, Contraflow transportation network reconfiguration for evacuation route planning, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1-15.   Google Scholar

[15]

S. KongsomsaksakulC. 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.   Google Scholar

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

[17]

A. KulshresthaY. 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.  Google Scholar

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

[19]

M. NgJ. 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.  Google Scholar

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

[21]

U. Pyakurel, Evacuation Planning Problem with Contraflow Approach, PhD thesis, IOST, Tribhuvan University, Nepal, 2016. Google Scholar

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

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

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

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

[26]

U. PyakurelT. 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.  Google Scholar

[27]

U. PyakurelH. W. Hamacher and T. N. Dhamala, Generalized maximum dynamic contraflow on lossy network, International Journal of Operations Research Nepal, 3 (2014), 27-44.   Google Scholar

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

[29]

U. PyakurelH. 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.  Google Scholar

[30]

U. PyakurelH. 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.  Google Scholar

[31]

S. RebennackA. ArulselvanL. 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.  Google Scholar

[32]

B. Rupp, FlowLoc: Discrete Facility Locations in Flow Networks, Diploma thesis, University of Kaiserslautern, Germany, 2010. Google Scholar

[33]

S. RuzikaH. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs, Networks, 57 (2011), 169-173.  doi: 10.1002/net.20398.  Google Scholar

[34]

M. Saho and M. Shigeno, Cancel-and-tighten algorithm for quickest flow problems, Network, 69 (2017), 179-188.  doi: 10.1002/net.21726.  Google Scholar

[35]

Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, Englewood Cliffs, 1985. Google Scholar

[36]

H. D. SheraliT. 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.  Google Scholar

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

[38]

E. Torres, Linearization of mixed-integer products, Mathematical Programming, 49 (1990), 427-428.  doi: 10.1007/BF01588802.  Google Scholar

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

[40]

C. VogiatzisR. YoshidaI. Aviles-SpadoniS. 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.   Google Scholar

show all references

References:
[1]

R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993.  Google Scholar

[2]

S. AnN. CuiX. 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.  Google Scholar

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

[4]

T. N. Dhamala and U. Pyakurel, Earliest arrival contraflow problem on series-parallel graphs, International Journal of Operations Research, 10 (2013), 1-13.   Google Scholar

[5]

T. N. DhamalaU. 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.   Google Scholar

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

[7]

R. C. DhunganaU. Pyakurel and T. N. Dhamala, Abstract contraflow models and solution procedures for evacuation planning, Journal of Mathematics Research, 10 (2018), 89-100.   Google Scholar

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

[9]

M. GoerigkK. Deghdak and P. Heßler, A comprehensive evacuation planning model and genetic soution algorithm, Transportation Research, Part E, 71 (2014), 82-97.   Google Scholar

[10]

M. GoerigkB. 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.  Google Scholar

[11]

H. W. HamacherS. 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.  Google Scholar

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

[13]

H. JiaF. 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.  Google Scholar

[14]

S. KimS. Shekhar and M. Min, Contraflow transportation network reconfiguration for evacuation route planning, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1-15.   Google Scholar

[15]

S. KongsomsaksakulC. 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.   Google Scholar

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

[17]

A. KulshresthaY. 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.  Google Scholar

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

[19]

M. NgJ. 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.  Google Scholar

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

[21]

U. Pyakurel, Evacuation Planning Problem with Contraflow Approach, PhD thesis, IOST, Tribhuvan University, Nepal, 2016. Google Scholar

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

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

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

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

[26]

U. PyakurelT. 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.  Google Scholar

[27]

U. PyakurelH. W. Hamacher and T. N. Dhamala, Generalized maximum dynamic contraflow on lossy network, International Journal of Operations Research Nepal, 3 (2014), 27-44.   Google Scholar

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

[29]

U. PyakurelH. 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.  Google Scholar

[30]

U. PyakurelH. 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.  Google Scholar

[31]

S. RebennackA. ArulselvanL. 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.  Google Scholar

[32]

B. Rupp, FlowLoc: Discrete Facility Locations in Flow Networks, Diploma thesis, University of Kaiserslautern, Germany, 2010. Google Scholar

[33]

S. RuzikaH. Sperber and M. Steiner, Earliest arrival flows on series-parallel graphs, Networks, 57 (2011), 169-173.  doi: 10.1002/net.20398.  Google Scholar

[34]

M. Saho and M. Shigeno, Cancel-and-tighten algorithm for quickest flow problems, Network, 69 (2017), 179-188.  doi: 10.1002/net.21726.  Google Scholar

[35]

Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, Englewood Cliffs, 1985. Google Scholar

[36]

H. D. SheraliT. 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.  Google Scholar

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

[38]

E. Torres, Linearization of mixed-integer products, Mathematical Programming, 49 (1990), 427-428.  doi: 10.1007/BF01588802.  Google Scholar

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

[40]

C. VogiatzisR. YoshidaI. Aviles-SpadoniS. 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.   Google Scholar

Figure 1.  Evacuation network $ N $ with arc labels (capacity, travel time)
Figure 3.  Auxiliary network $ \bar{N} $ of network $ N $ in Figure 1 with arc labels (capacity, travel time)
Table 1.  Maximum dynamic FlowLoc decisions (cf. Figure 1)
$ T $ maximum dynamic flow value when facility is placed on Location decision
(2, 3) (2, 4)
4 0 1 (2, 4)
5 4 5 (2, 4)
6 11 11 (2, 4) or (2, 3)
7 18 17 (2, 3)
$ T $ maximum dynamic flow value when facility is placed on Location decision
(2, 3) (2, 4)
4 0 1 (2, 4)
5 4 5 (2, 4)
6 11 11 (2, 4) or (2, 3)
7 18 17 (2, 3)
Table 2.  Quickest FlowLoc decisions (cf. Figure 1)
$ F $ quickest time when facility is placed on Location decision
(2, 3) (2, 4)
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)
$ F $ quickest time when facility is placed on Location decision
(2, 3) (2, 4)
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)
Table 4.  Computational results for some instances with $ F = 20000 $
$ |L| $ $ |P| $ Algorithm 4 Algorithm 5 MILP
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 - -
$ |L| $ $ |P| $ Algorithm 4 Algorithm 5 MILP
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 - -
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%
Algorithm 4 Algorithm 5
Maximum deviation 21.55% 5.31 %
Average deviation 3.48 % 0.18%
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) $
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) $
[1]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017

[2]

Shuxing Chen, Jianzhong Min, Yongqian Zhang. Weak shock solution in supersonic flow past a wedge. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 115-132. doi: 10.3934/dcds.2009.23.115

[3]

Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034

[4]

Shuang Liu, Yuan Lou. A functional approach towards eigenvalue problems associated with incompressible flow. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3715-3736. doi: 10.3934/dcds.2020028

[5]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020390

[6]

Joan Carles Tatjer, Arturo Vieiro. Dynamics of the QR-flow for upper Hessenberg real matrices. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1359-1403. doi: 10.3934/dcdsb.2020166

[7]

Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389

[8]

Gui-Qiang Chen, Beixiang Fang. Stability of transonic shock-fronts in three-dimensional conical steady potential flow past a perturbed cone. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 85-114. doi: 10.3934/dcds.2009.23.85

[9]

Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347

[10]

Kohei Nakamura. An application of interpolation inequalities between the deviation of curvature and the isoperimetric ratio to the length-preserving flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1093-1102. doi: 10.3934/dcdss.2020385

[11]

Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390

[12]

Imam Wijaya, Hirofumi Notsu. Stability estimates and a Lagrange-Galerkin scheme for a Navier-Stokes type model of flow in non-homogeneous porous media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1197-1212. doi: 10.3934/dcdss.2020234

[13]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[14]

Hongguang Ma, Xiang Li. Multi-period hazardous waste collection planning with consideration of risk stability. Journal of Industrial & Management Optimization, 2021, 17 (1) : 393-408. doi: 10.3934/jimo.2019117

[15]

Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020177

[16]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[17]

Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002

[18]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128

[19]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[20]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]