Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire

Year 2019, Volume: 68 Issue: 1, 441 - 450, 01.02.2019

Ertuğrul Ayyıldız , Gökhan Özçelik , Cevriye Temel Gencer

https://doi.org/10.31801/cfsuasmas.425508

Cited By: 2

Abstract

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.

Keywords

Shortest path, network interdiction, mathematical modeling, terrorist actions

References

• Israeli, E. and Wood, R.K., Shortest- path network interdiction. Networks, 40(2), (2002), 97-111.
• 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.
• Lubore, S.H. and Scilia, G.T., Determining the most vital link in a flow network, DTIC Document, 1971.
• Wollmer, R., Removing arcs from a network. Operations Research, 12(6), (1964), 934-940.
• 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.
• 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.
• 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.
• 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.
• Jiang, Y. and Hu, A., Finding the Most Vital Link with Respect to the Characteristic of Network Communication. Journal of Networks, (2011) 6(3).
• Wood, R.K., Deterministic network interdiction. Mathematical and Computer Modelling, 17(2), (1993), 1-18.
• Cormican, K.J., Morton, D.P., Stochastic network interdiction, Operations Research, 46(2), (1998), 184--197.
• Brown, G. et al., Defending critical infrastructure. Interfaces, 36(6), (2006), 530-544.
• Brown, G.G. et al., Interdicting a nuclear-weapons project. Operations Research, 57(4), (2009), 866-877.
• Lim, C. and Smith, J.C., Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Transactions, 39(1), (2007), 15-26.
• 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.
• 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.
• Kennedy, K.T. et al., Nodal interdiction. Mathematical and Computer Modelling, 54(11), (2011), 3116-3125.
• 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.
• 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.
• Zenklusen, R., Network flow interdiction on planar graphs. Discrete Applied Mathematics, 158(13), (2010), 1441-1455.
• Romich, A., Lan, G. and Smith, J.C., Algorithms for optimizing the placement of stationary monitors. IIE Transactions, 47(6), (2015), 556-576.
• McMasters, A.W. and Mustin, T.M., Optimal interdiction of a supply network. Naval Research Logistics Quarterly, 17(3), (1970), 261-268.
• 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.
• Washburn, A. and Wood, K., Two-Person Zero-Sum Games for Network Interdiction. Operations Research, 43(2), (1995), 243-251.
• Bingöl, L., A Lagrangian heuristic for solving a network interdiction problem, Master Thesis, Naval Postgraduate School, Monterey, California, 2001.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• Sullivan, K.M. and Cole Smith, J., Exact algorithms for solving a Euclidean maximum flow network interdiction problem. Networks, 64(2), (2014), 109--124.
• Branch, K., Multi-Commodity Multi-Source-Sinks Network Flow. Journal of Engineering and Applied Sciences, 10(6), (2015), 118-122.
• 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.
• Afshari Rad, M. and Kakhki, H.T., Two extended formulations for cardinality maximum flow network interdiction problem. Networks, 69(4), (2017), 367-377.
• Naoum-Sawaya, J. and Ghaddar, B., Cutting plane approach for the maximum flow interdiction problem. Journal of the Operational Research Society, (2017), 1-17.
• 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.
• Golden, B., A problem in network interdiction. Naval Research Logistics Quarterly, 25(4), (1978), 711-713.
• Corley, H.W. and David, Y.S., Most vital links and nodes in weighted networks. Operations Research Letters, 1(4), (1982), 157-160.
• Wevley, C., The quickest path network interdiction problem. Master Thesis, Naval Postgraduate School, Monterey, California, 1999.
• 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.
• Khachiyan, L. et al., On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43(2), (2008), 204-233.
• Bayrak, H. and Bailey, M.D., Shortest path network interdiction with asymmetric information. Networks, 52(3), (2008), 133-140.
• 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.
• Yates, J. and Lakshmanan, K., A constrained binary knapsack approximation for shortest path network interdiction. Computers and Industrial Engineering, 61(4), (2011), 981--992.
• Cappanera, P. and Scaparra, M.P., Optimal allocation of protective resources in shortest-path networks. Transportation Science, 45(1), (2011), 64-80.
• 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.
• 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.
• 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.
• 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.
• Borrero, J.S., Prokopyev, O.A. and Saura, D., Sequential shortest path interdiction with incomplete information. Decision Analysis, 13(1), (2015), 68-98.
• Song, Y. and Shen, S., Risk-Averse Shortest Path Interdiction. INFORMS Journal on Computing, 28(3), (2016), 527-539.
• Casas, I., Delmelle, E. and Yates, J., Geographic characteristics of a network interdiction problem. GeoJournal, 81(1), (2016), 37-53.
• 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.
• Sefair, J.A. and Smith, J.C., Dynamic shortest path interdiction. Networks, 68(4), (2016), 315-330.
• Lozano, L. and Smith, J.C., A Backward Sampling Framework for Interdiction Problems with Fortification. INFORMS Journal on Computing, 29(1), (2016), 123-139.
• Sadeghi, S., Seifi, A. and Azizi, E., Trilevel shortest path network interdiction with partial fortification. Computers and Industrial Engineering, 106, (2017), 400--411.
• Israeli, E., System Interdiction and Defense., DTIC Document, 1999.