×

Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire. (English) Zbl 1487.90202

Summary: In case of fire, the supplying of the water requirements of the fire area is a vital issue. The water requirements must be satisfied as quickly as possible without encountering any obstacles. In the study, once a terrorist attack which will cause fire at certain area (node) is occurred, the situation in which the terrorists want to prevent the fire trucks’ transportation to this area via the shortest path is considered. The main logic of the study is determining the risky arc(s) that will interdict and presenting a relatively safety paths for the fire trucks. Terrorists wants to maximize the shortest path of fire trucks depending on limited interdiction budget. In this context, the problem is considered within the framework of the Network Interdiction Problem (NIP), where there are two opposite sides as leader (terrorist) and follower (fire truck). As a result, the bi-level model of the problem is presented first, and the model is applied on a numerical explanatory example.

MSC:

90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Israeli, E. and Wood, R.K., Shortest- path network interdiction. Networks, 40(2), (2002), 97-111. · Zbl 1027.90106
[2] Wollmer, R.D., Some methods for determining the most vital link in a railway network. RM-3321-ISA, The Rand Corporation, Santa Monica, California, 1963.
[3] Lubore, S.H. and Scilia, G.T., Determining the most vital link in a flow network, DTIC Document, 1971.
[4] Wollmer, R., Removing arcs from a network. Operations Research, 12(6), (1964), 934-940. · Zbl 0204.20102
[5] Ratliff, H.D., Sicilia, G.T. and Lubore, S.H., Finding the n most vital links in flow networks. Management Science, 21(5), (1975), 531-539. · Zbl 0311.90073
[6] Malik, K., Mittal, A.K. and Gupta, S.K., The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4), (1989), 223-227. · Zbl 0669.90090
[7] Ball, M.O., Golden, B.L. and Vohra, R. V., Finding the most vital arcs in a network. Operations Research Letters, 8(2), (1989), 73-76. · Zbl 0679.90086
[8] Lin, K.-C. and Chern, M.-S., The fuzzy shortest path problem and its most vital arcs. Fuzzy Sets and Systems, 58(3), (1993), 343-353. · Zbl 0804.90138
[9] Jiang, Y. and Hu, A., Finding the Most Vital Link with Respect to the Characteristic of Network Communication. Journal of Networks, (2011) 6(3).
[10] Wood, R.K., Deterministic network interdiction. Mathematical and Computer Modelling, 17(2), (1993), 1-18. · Zbl 0800.90772
[11] Cormican, K.J., Morton, D.P., Stochastic network interdiction, Operations Research, 46(2), (1998), 184-197. · Zbl 0987.90516
[12] Brown, G. et al., Defending critical infrastructure. Interfaces, 36(6), (2006), 530-544.
[13] Brown, G.G. et al., Interdicting a nuclear-weapons project. Operations Research, 57(4), (2009), 866-877. · Zbl 1226.90142
[14] Lim, C. and Smith, J.C., Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Transactions, 39(1), (2007), 15-26.
[15] Salmeron, J., Wood, K. and Baldick, R., Worst-case interdiction analysis of large-scale electric power grids. IEEE Transactions on power systems, 24(1), (2009), 96-104.
[16] Akgün, A., Tansel, B.A. and Wood, R.K., The multi-terminal maximum-flow network- interdiction problem. European Journal of Operational Research, 211(2), (2011), 241-251. · Zbl 1250.90021
[17] Kennedy, K.T. et al., Nodal interdiction. Mathematical and Computer Modelling, 54(11), (2011), 3116-3125. · Zbl 1235.90031
[18] Malaviya, A., Rainwater, C. and Sharkey, T., Multi-period network interdiction problems with applications to city-level drug enforcement. IIE Transactions, 44(5), (2012), 368-380.
[19] Granata, D., Steeger, G. and Rebennack, S., Network interdiction via a critical disruption path: branch-and-price algorithms. Computers and Operations Research, 40(11), (2013), 2689-2702. · Zbl 1348.90596
[20] Zenklusen, R., Network flow interdiction on planar graphs. Discrete Applied Mathematics, 158(13), (2010), 1441-1455. · Zbl 1209.05117
[21] Romich, A., Lan, G. and Smith, J.C., Algorithms for optimizing the placement of stationary monitors. IIE Transactions, 47(6), (2015), 556-576.
[22] McMasters, A.W. and Mustin, T.M., Optimal interdiction of a supply network. Naval Research Logistics Quarterly, 17(3), (1970), 261-268. · Zbl 0222.90017
[23] Chern, M.-S. and Lin, K.-C., Interdicting the activities of a linear program A parametric analysis. European Journal of Operational Research, 86(3), (1995), 580-591. · Zbl 0914.90247
[24] Washburn, A. and Wood, K., Two-Person Zero-Sum Games for Network Interdiction. Operations Research, 43(2), (1995), 243-251. · Zbl 0832.90124
[25] Bingöl, L., A Lagrangian heuristic for solving a network interdiction problem, Master Thesis, Naval Postgraduate School, Monterey, California, 2001.
[26] Burch, C., Carr, S., Krumke, M., Marathe, M., Phillips, C. and Sundberg, E. A., Decomposition-based approximation for network inhibition. In D. L. Woodruff (Eds.), Network Interdiction and Stochastic Integer Programming. Boston: Kluwer Academic Publishers, pp. 51-69, 2003. · Zbl 1051.90005
[27] Royset, J.O. and Wood, R.K., Solving the bi-objective maximum-flow network-interdiction problem. INFORMS Journal on Computing, 19(2), (2007), 175-184. · Zbl 1241.90139
[28] Rocco, C.M. and Ramirez-Marquez, J.E., Deterministic network interdiction optimization via an evolutionary approach. Reliability Engineering and System Safety, 94(2), (2009), 568-576.
[29] Altner, D.S., Ergun, A. and Uhan, N.A., The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability. Operations Research Letters, 38(1), (2010), 33-38. · Zbl 1182.90014
[30] Lunday, B.J. and Sherali, H.D., Minimizing the maximum network flow: models and algorithms with resource synergy considerations. Journal of the Operational Research Society, 63(12), (2012), 1693-1707.
[31] Rad, M.A. and Kakhki, H.T., Maximum dynamic network flow interdiction problem: new formulation and solution procedures. Computers and Industrial Engineering, 65(4), (2013), 531-536.
[32] Shirdel, G.H., A Note on the Integrality Gap in the Nodal Interdiction Problem. Journal of Sciences, Islamic Republic of Iran, 24(3), (2013), 269-273.
[33] Sullivan, K.M. and Cole Smith, J., Exact algorithms for solving a Euclidean maximum flow network interdiction problem. Networks, 64(2), (2014), 109-124. · Zbl 1387.90294
[34] Branch, K., Multi-Commodity Multi-Source-Sinks Network Flow. Journal of Engineering and Applied Sciences, 10(6), (2015), 118-122.
[35] Janjarassuk, U. and Nakrachata-Amon, T., A simulated annealing algorithm to the stochastic network interdiction problem. In Industrial Engineering and Engineering Management (IEEM), 2015 IEEE International Conference on. IEEE, (2015), 230-233.
[36] Afshari Rad, M. and Kakhki, H.T., Two extended formulations for cardinality maximum flow network interdiction problem. Networks, 69(4), (2017), 367-377. · Zbl 1386.90025
[37] Naoum-Sawaya, J. and Ghaddar, B., Cutting plane approach for the maximum flow interdiction problem. Journal of the Operational Research Society, (2017), 1-17.
[38] Fulkerson, D.R. and Harding, G.C., Maximizing the minimum source-sink path subject to a budget constraint. Mathematical Programming, 13(1), (1977), 116-118. · Zbl 0366.90115
[39] Golden, B., A problem in network interdiction. Naval Research Logistics Quarterly, 25(4), (1978), 711-713. · Zbl 0394.90038
[40] Corley, H.W. and David, Y.S., Most vital links and nodes in weighted networks. Operations Research Letters, 1(4), (1982), 157-160. · Zbl 0488.90069
[41] Wevley, C., The quickest path network interdiction problem. Master Thesis, Naval Postgraduate School, Monterey, California, 1999.
[42] Khachiyan, L., Gurvich, V. and Zhao, J., Extending dijkstraâ-algorithm to maximize the shortest path by node-wise limited arc interdiction. In International Computer Science Symposium in Russia. Springer, (2006). 221-234. · Zbl 1185.90198
[43] Khachiyan, L. et al., On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43(2), (2008), 204-233. · Zbl 1148.68036
[44] Bayrak, H. and Bailey, M.D., Shortest path network interdiction with asymmetric information. Networks, 52(3), (2008), 133-140. · Zbl 1171.90345
[45] Ramirez-Marquez, J.E. and Rocco, C.M., A bi-objective approach for shortest-path network interdiction. Computers and Industrial Engineering, 59(2), (2010), 232-240.
[46] Yates, J. and Lakshmanan, K., A constrained binary knapsack approximation for shortest path network interdiction. Computers and Industrial Engineering, 61(4), (2011), 981-992.
[47] Cappanera, P. and Scaparra, M.P., Optimal allocation of protective resources in shortest-path networks. Transportation Science, 45(1), (2011), 64-80.
[48] Yates, J. and Sanjeevi, S., A length-based, multiple-resource formulation for shortest path network interdiction problems in the transportation sector. International Journal of Critical Infrastructure Protection, 6(2), (2013), 107-119.
[49] Yates, J., Wang, X. and Chen, N., Assessing the effectiveness of k-shortest path sets in problems of network interdiction. Optimization and Engineering, 15(3), (2014), 721-749. · Zbl 1364.90068
[50] Yates, J. and Chen, N., A Spatial Segmentation Algorithm for Resource Allocation in an Integrated Spatial and Networked Environment. Applied Spatial Analysis and Policy, 7(4), (2014), 317-336.
[51] Xiao, K. et al., Stackelberg network interdiction game: nodal model and algorithm. In Game Theory for Networks (GAMENETS), 2014 5th International Conference on. IEEE, (2014), 1-5.
[52] Borrero, J.S., Prokopyev, O.A. and Saura, D., Sequential shortest path interdiction with incomplete information. Decision Analysis, 13(1), (2015), 68-98. · Zbl 1398.91165
[53] Song, Y. and Shen, S., Risk-Averse Shortest Path Interdiction. INFORMS Journal on Computing, 28(3), (2016), 527-539. · Zbl 1348.91077
[54] Casas, I., Delmelle, E. and Yates, J., Geographic characteristics of a network interdiction problem. GeoJournal, 81(1), (2016), 37-53.
[55] Borndörfer, R., Sagnol, G. and Schwartz, S., An Extended Network Interdiction Problem for Optimal Toll Control. Electronic Notes in Discrete Mathematics, 52, (2016), 301-308. · Zbl 1351.90113
[56] Sefair, J.A. and Smith, J.C., Dynamic shortest path interdiction. Networks, 68(4), (2016), 315-330. · Zbl 1390.90124
[57] Lozano, L. and Smith, J.C., A Backward Sampling Framework for Interdiction Problems with Fortification. INFORMS Journal on Computing, 29(1), (2016), 123-139. · Zbl 1414.91086
[58] Sadeghi, S., Seifi, A. and Azizi, E., Trilevel shortest path network interdiction with partial fortification. Computers and Industrial Engineering, 106, (2017), 400-411.
[59] Israeli, E., System Interdiction and Defense., DTIC Document, 1999.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.