Providing homeland security strategies against interdictions in the city transportation network: A case study in Turkey

Abstract

This study defines a capacitated multiple-source multiple-sink shortest path problem and introduces its extension, called the capacitated multiple-source multiple-sink shortest path network interdiction problem (CMSSNIP). CMSSNIP examines the actions of attackers who attempt to maximize the total shortest path of network users trying to reach the crime locations for the aid process after causing an incident in certain regions to provide strategic information for the defense systems of the government. In this context, the exact mathematical model is proposed to ensure useful information about safe routes to network users. In this manner, to the best knowledge of authors, the CMSSNIP consisting of multiple-source nodes and multiple-sink nodes and considering capacity-demand relations between security units and crime locations is studied for the first time. Consequently, a set of scenarios is considered based on the levels of the interdiction budget and the number of crime locations through a real case application to show the applicability of the model. Furthermore, computational experiments are performed to evaluate the performance of the model in networks of different sizes. It is realized that the model provides resilient strategies against interdictions in terms of obtaining the safe shortest paths at the operational level within seconds in the real case applications.

Keywords

• Shortest path problem
• Network interdiction
• Mixed integer programming
• Networks

References

1. [1] Zheng, K., Albert, L.A., "Interdiction models for delaying adversarial attacks against critical information technology infrastructure", Naval Research Logistics, 66(5): 411–429, (2019).
2. [2] Fang, Y., Sansavini, G., Zio, E., "An Optimization‐Based Framework for the Identification of Vulnerabilities in Electric Power Grids Exposed to Natural Hazards", Risk Analysis, 39(9): 1949–1969, (2019).
3. [3] Baycik, N.O., Sharkey, T.C., "Interdiction-Based Approaches to Identify Damage in Disrupted Critical Infrastructures with Dependencies", Journal of Infrastructure Systems, 25(2): 04019013, (2019).
4. [4] Ghorbani-Renani, N., González, A.D., Barker, K., Morshedlou, N., "Protection-interdiction-restoration: Tri-level optimization for enhancing interdependent network resilience", Reliability Engineering & System Safety, 199: 106907, (2020).
5. [5] Bhuiyan, T.H., Medal, H.R., Nandi, A.K., Halappanavar, M., "Risk-averse bi-level stochastic network interdiction model for cyber-security risk management", International Journal of Critical Infrastructure Protection, 32: 100408, (2021).
6. [6] Israeli E., Wood R.K., "Shortest‐path network interdiction", Networks, 40(2): 97–111, (2002).
7. [7] Xiang, Y., Wei, H., "Joint optimizing network interdiction and emergency facility location in terrorist attacks", Computers & Industrial Engineering, 144: 106480, (2020).
8. [8] Sefair, J.A., Smith, J.C., "Dynamic shortest‐path interdiction", Networks, 68(4): 315–330, (2016).

9. [9] Lubore, S.H., Ratliff, H.D., Sicilia, G.T., "Determining the most vital link in a flow network", Naval Research Logistics, 18(4): 497–502, (1971).
10. [10] Wollmer, R.D., "Some methods for determining the most vital link in a railway network", Rand Corporation, (1963).
11. [11] Ball, M.O., Golden, B.L., Vohra, R.V., "Finding the most vital arcs in a network", Operations Research Letters, 8(2): 73–76, (1989).
12. [12] Ratliff, H.D., Sicilia, G.T., Lubore, S.H., "Finding the n Most Vital Links in Flow Networks", Management Science, 21(5): 531–539, (1975).
13. [13] Wollmer, R., "Removing Arcs from a Network", Operations Research, 12(6): 934–940, (1964).
14. [14] Jiang, Y., Hu, A., "Finding the Most Vital Link with Respect to the Characteristic of Network Communication", Journal of Networks, 6(3): 462–469, (2011).
15. [15] Lin, K.C., Chern, M.S., "The fuzzy shortest path problem and its most vital arcs", Fuzzy Sets and Systems, 58(3): 343–353, (1993).
16. [16] Malik, K., Mittal, A.K., Gupta, S.K., "The k most vital arcs in the shortest path problem", Operations Research Letters, 8(4): 223–227, (1989).
17. [17] Wood, R.K., "Deterministic network interdiction", Mathematical and Computer Modelling, 17(2): 1–18, (1993).
18. [18] Brown, G., Carlyle, M., Salmerón, J., Wood, K., "Defending critical infrastructure", Interfaces (Providence), 36(6): 530–544, (2006).
19. [19] Yao, Y., Edmunds, T., Papageorgiou, D., Alvarez, R., "Trilevel optimization in power network defense", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 37(4): 712–718, (2007).
20. [20] Delkhosh, F., "A dynamic leader-follower model based on lack of central authority in emergency situations", International Journal of Data and Network Science, 4(1): 73–90, (2020).
21. [21] Johnson, M.P., Gutfraind, A., "Evader interdiction and collateral damage", In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, Berlin, Heidelberg, 86–100, (2012).
22. [22] Karabulut, E., Aras, N., Altınel, K., "Optimal sensor deployment to increase the security of the maximal breach path in border surveillance", European Journal of Operational Research, 259(1): 19–36, (2017).
23. [23] Pan, F., Charlton, W.S., Morton, D.P., "A stochastic program for interdicting smuggled nuclear material", Operations Research/Computer Science Interfaces Series, 22: 1–19, (2003).
24. [24] Morton, D.P., Pan, F., "Using Sensors to Interdict Nuclear Material Smuggling", In IIE Annual Conference. Proceedings, Institute of Industrial and Systems Engineers (IISE), (2005).
25. [25] Fulkerson, D.R., Harding, G.C., "Maximizing the minimum source-sink path subject to a budget constraint", Mathematical Programming, 13(1): 116–118, (1977).
26. [26] Golden, B., "A problem in network interdiction", Naval Research Logistics, 25(4): 711–713, (1978).
27. [27] Corley, H.W., David, Y.S., "Most vital links and nodes in weighted networks", Operations Research Letters, 1(4): 157–160, (1982).
28. [28] Dijkstra, E.W., "A note on two problems in connexion with graphs", Numerische Mathematik, 1(1): 269–271, (1959).
29. [29] Khachiyan, L., Gurvich, V., Zhao, J., "Extending Dijkstra’s algorithm to maximize the shortest path by node-wise limited arc interdiction", In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 221–234, (2006).
30. [30] Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V, Rudolf, G., Zhao, J., "On short paths interdiction problems: Total and node-wise limited interdiction", Theory of Computing Systems, 43(2): 204–233, (2008).
31. [31] Bayrak, H., Bailey, M.D., "Shortest path network interdiction with asymmetric information", Networks, 52(3): 133–140, (2008).
32. [32] Ramirez-Marquez, J.E., Rocco, C.M., "A bi-objective approach for shortest-path network interdiction", Computers & Industrial Engineering, 59(2): 232–240, (2010).
33. [33] Yates, J., 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): 107–119, (2013).
34. [34] Yates, J., Wang, X., Chen, N., "Assessing the effectiveness of k-shortest path sets in problems of network interdiction", Optimization and Engineering, 15(3): 721–749, (2014).
35. [35] Yates, J., Chen, N., "A Spatial Segmentation Algorithm for Resource Allocation in an Integrated Spatial and Networked Environment", Applied Spatial Analysis and Policy, 7(4): 317–336, (2014).
36. [36] Song, Y., Shen, S., "Risk-Averse Shortest Path Interdiction", INFORMS Journal on Computing, 28(3): 527–539, (2016).
37. [37] Casas, I., Delmelle, E., Yates, J., "Geographic characteristics of a network interdiction problem", Geo Journal, 81(1): 37–53, (2016).
38. [38] Borndörfer, R., Sagnol, G., Schwartz, S., "An Extended Network Interdiction Problem for Optimal Toll Control", Electronic Notes in Discrete Mathematics, 52: 301–308, (2016).
39. [39] Cappanera, P., Scaparra, M.P., "Optimal allocation of protective resources in shortest-path networks", Transportation Science, 45(1): 64–80, (2011).
40. [40] Sadeghi, S., Seifi, A., Azizi, E., "Trilevel shortest path network interdiction with partial fortification", Computers & Industrial Engineering, 106: 400–411, (2017).
41. [41] Lozano, L., Smith, J.C., "A backward sampling framework for interdiction problems with fortification", INFORMS Journal on Computing, 29(1): 123–139, (2017).
42. [42] Pay, B.S., Merrick, J.R.W., Song, Y., "Stochastic network interdiction with incomplete preference", Networks, 73(1): 3–22, (2019).
43. [43] Bidgoli, M.M., Kheirkhah, A.S., "An arc interdiction vehicle routing problem with information asymmetry", Computers & Industrial Engineering, 115: 520–531, (2018).
44. [44] Quadros, H., Costa Roboredo, M., Alves Pessoa, A., "A branch-and-cut algorithm for the multiple allocation r-hub interdiction median problem with fortification", Expert Systems with Applications, 110: 311–322, (2018).
45. [45] Ayyildiz, E., Özçelik, G., Demirci, E., "Multiple-Sink Shortest Path Network Interdiction Problem", Sigma Journal of Engineering and Natural Sciences, 9(4): 395–403, (2018).
46. [46] Wei, X., Xu, K., Jiao, P., Yin, Q., Zha, Y., "A Decomposition Approach for Stochastic Shortest-Path Network Interdiction with Goal Threshold", Symmetry (Basel), 11(2): 237, (2019).
47. [47] Baycik, N.O., Sullivan, K.M., "Robust location of hidden interdictions on a shortest path network", IISE Transactions, 51(12): 1332–1347, (2019).
48. [48] Ketkov, S.S., Prokopyev, O.A., "On greedy and strategic evaders in sequential interdiction settings with incomplete information", Omega (United Kingdom), 92: 102161, (2020).
49. [49] Yates, J., Lakshmanan, K., "A constrained binary knapsack approximation for shortest path network interdiction", Computers & Industrial Engineering, 61(4): 981–992, (2011).
50. [50] Borrero J.S., Prokopyev O.A., Sauré D., "Sequential Shortest Path Interdiction with Incomplete Information", Decision Analysis, 13(1): 68–98, (2016).
51. [51] Ayyildiz, E., Ozcelik, G., Temel Gencer, C., "Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire", Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics, 68(1): 441–450, (2019).
52. [52] Xu, K., Zeng, Y., Zhang, Q., Yin, Q., Sun, L., Xiao, K., "Online probabilistic goal recognition and its application in dynamic shortest-path local network interdiction", Engineering Applications of Artificial Intelligence, 85: 57–71, (2019).
53. [53] Zhang, J., Zhuang, J., Behlendorf, B., "Stochastic shortest path network interdiction with a case study of Arizona–Mexico border", Reliability Engineering & System Safety, 179: 62–73, (2018).
54. [54] Yates, J., Casas, I., "Role of Spatial Data in the Protection of Critical Infrastructure and Homeland Defense", Applied Spatial Analysis and Policy, 5(1): 1–23, (2012).
55. [55] Özçelik, G., Gencer, C., "A goal programming model that ensures efficient usage of limited interdiction budget in the procurement game", Croatian Operational Research Review, 9(1): 75–85, (2018).