Abstract
It is paramount to enhance the resilience of many facilities that are known to be critical for modern societies and threatened by intentional attacks. For this purpose, it is important to not only protect them before disruptions, but also recover them after disruptions. To deal with this problem, this paper proposes a tri-level model explicitly integrating the decision making on recovery strategies of disrupted facilities with the decision making on protecting facilities from intentional attacks. The facilities studied in this research are assumed to be capacitated and a recovery strategy is considered to include repairing a subset of disrupted facilities and expanding the capacities of a subset of non-interdicted facilities. We are concerned with the defender’s objective of maximizing the resilience of the given set of facilities making profit within a prescribed time interval. To deal with the complexity of solving the proposed tri-level model, the ant colony system algorithm is employed with necessary adaptations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Abbreviations
- N :
-
Set of customers
- F :
-
Set of facilities
- i :
-
Index of customers
- j :
-
Index of facilities
- n :
-
The number of customers
- p :
-
The number of original facilities
- q :
-
The number of protected facilities
- \(r_{{\textit{num}}}\) :
-
The number of interdicted facilities
- T :
-
The length of concerned time interval
- \(t_{{\textit{re}}}\) :
-
Time required to repair a disrupted facility
- B :
-
Amount of budget
- \(c_{{\textit{trans}}}\) :
-
Transportation cost per distance
- \(c_{r}\) :
-
Cost required to repair each disrupted facility
- \(c_{e}\) :
-
Capacity expansion cost per demand unit
- \(\mu \) :
-
Maximal incremental value by which a facility’s capacity can be expanded
- \(p_{r}\) :
-
Revenue earned by satisfying each unit of customer demand
- \(c_{l}\) :
-
Penalty cost paid for each unit of unmet demand per unit of time
- \(a_{i}\) :
-
Total demand of customer i
- \(d_{ij}\) :
-
Distance between facility j and customer i
- \(t_{s}\) :
-
Length of a supply cycle
- k :
-
Number of ants
- \(q^{*}\) :
-
A random number uniformly distributed in [0,1]
- \(\eta _{j}\) :
-
Heuristic value of choosing facility j
- \(\alpha ,\beta \) :
-
Indexes reflecting the importance of pheromone and heuristic value
- \(\rho \) :
-
Pheromone evaporating rate
- m :
-
Stage of decision making, with \(m = 0\) indicates the first (i.e., protection) stage, and \(m = 1\) indicates the second (i.e., interdiction) stage
- \(\tau _{{\textit{mj}}}\) :
-
Pheromone amount on facility j in stage m
- \(p_{{\textit{mj}}}\) :
-
Probability of choosing facility j in stage m
References
Aksen, D., Akca, S. S., & Aras, N. (2014). A bilevel partial interdiction problem with capacitated facilities and demand outsourcing. Computers & Operations Research, 41, 346–358. https://doi.org/10.1016/j.cor.2012.08.013.
Aksen, D., Piyade, N., & Aras, N. (2010). The budget constrained r-interdiction median problem with capacity expansion. Central European Journal of Operations Research, 18(3), 269–291. https://doi.org/10.1007/s10100-009-0110-6.
Arab, A., Khodaei, A., Khator, S. K., Ding, K., Emesih, V. A., & Han, Z. (2015). Stochastic pre-hurricane restoration planning for electric power systems infrastructure. IEEE Transactions on Smart Grid, 6(2), 1046–1054. https://doi.org/10.1109/tsg.2015.2388736.
Azad, N., Saharidis, G. K. D., Davoudpour, H., Malekly, H., & Yektamaram, S. A. (2013). Strategies for protecting supply chain networks against facility and transportation disruptions: An improved Benders decomposition approach. Annals of Operations Research, 210(1), 125–163. https://doi.org/10.1007/s10479-012-1146-x.
Baykasoglu, A., Dereli, T., & Sabuncu, I. (2006). An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems. Omega-International Journal of Management Science, 34(4), 385–396. https://doi.org/10.1016/j.omega.2004.12.001.
Berman, O., Drezner, T., Drezner, Z., & Wesolowsky, G. O. (2009). A defensive maximal covering problem on a network. International Transactions in Operational Research, 16(1), 69–86.
Calvete, H. I., Gale, C., & Oliveros, M. J. (2011). Bilevel model for production-distribution planning solved by using ant colony optimization. Computers & Operations Research, 38(1), 320–327. https://doi.org/10.1016/j.cor.2010.05.007.
Cavdaroglu, B., Hammel, E., Mitchell, J. E., Sharkey, T. C., & Wallace, W. A. (2013). Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems. Annals of Operations Research, 203(1), 279–294. https://doi.org/10.1007/s10479-011-0959-3.
Chu, J. C., & Chen, Y.-J. (2012). Optimal threshold-based network-level transportation infrastructure life-cycle management with heterogeneous maintenance actions. Transportation Research Part B: Methodological, 46(9), 1123–1143. https://doi.org/10.1016/j.trb.2012.05.002.
Church, R. L., & ReVelle, C. S. (1974). The maximal covering location problem. Papers of the Regional Science Association, 32, 101–118.
Church, R. L., & Scaparra, M. P. (2007). Protecting critical assets: The r-interdiction median problem with fortification. Geographical Analysis, 39(2), 129–146.
Church, R. L., Scaparra, M. P., & Middleton, R. S. (2004). Identifying critical infrastructure: The median and covering facility interdiction problems. Annals of the Association of American Geographers, 94(3), 491–502. https://doi.org/10.1111/j.1467-8306.2004.00410.x.
Dorigo, M., & Stutzle, T. (2004). Ant colony optimization. London: The MIT Press.
Hakimi, S. L. (1964). Optimal location of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459.
Henry, D., & Ramirez-Marquez, J. E. (2012). Generic metrics and quantitative approaches for system resilience as a function of time. Reliability Engineering & System Safety, 99, 114–122. https://doi.org/10.1016/j.ress.2011.09.002.
Hernandez, I., Ramirez-Marquez, J. E., Rainwater, C., Pohl, E., & Medal, H. (2014). Robust facility location: Hedging against failures. Reliability Engineering & System Safety, 123, 73–80. https://doi.org/10.1016/j.ress.2013.10.006.
Hy, R. J., & Waugh, W. L. (1990). Handbook of emergency management: Programs and policies dealing with major hazards and disasters. New York: Greenwood Press.
Jenelius, E., Westin, J., & Holmgren, A. J. (2010). Critical infrastructure protection under imperfect attacker perception. International Journal of Critical Infrastructure Protection, 3(1), 16–26. https://doi.org/10.1016/j.ijcip.2009.10.002.
Liberatore, F., Scaparra, M. P., & Daskin, M. S. (2011). Analysis of facility protection strategies against an uncertain number of attacks: The stochastic R-interdiction median problem with fortification. Computers & Operations Research, 38(1), 357–366. https://doi.org/10.1016/j.cor.2010.06.002.
Liberatore, F., Scaparra, M. P., & Daskin, M. S. (2012). Hedging against disruptions with ripple effects in location analysis. Omega, 40(1), 21–30. https://doi.org/10.1016/j.omega.2011.03.003.
Losada, C., Scaparra, M. P., Church, R. L., & Daskin, M. S. (2012). The stochastic interdiction median problem with disruption intensity levels. Annals of Operations Research, 201(1), 345–365. https://doi.org/10.1007/s10479-012-1170-x.
Losada, C., Scaparra, M. P., & O’Hanley, J. R. (2012). Optimizing system resilience: A facility protection model with recovery time. European Journal of Operational Research, 217(3), 519–530. https://doi.org/10.1016/j.ejor.2011.09.044.
Nurre, S. G., Cavdaroglu, B., Mitchell, J. E., Sharkey, T. C., & Wallace, W. A. (2012). Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem. European Journal of Operational Research, 223(3), 794–806. https://doi.org/10.1016/j.ejor.2012.07.010.
O’Hanley, J. R., & Church, R. L. (2011). Designing robust coverage networks to hedge against worst-case facility losses. European Journal of Operational Research, 209(1), 23–36. https://doi.org/10.1016/j.ejor.2010.08.030.
O’Hanley, J. R., Church, R. L., & Gilless, J. K. (2007). Locating and protecting critical reserve sites to minimize expected and worst-case losses. Biological Conservation, 34(1), 130–141.
Ouyang, M., Dueñas-Osorio, L., & Min, X. (2012). A three-stage resilience analysis framework for urban infrastructure systems. Structural Safety, 36–37, 23–31. https://doi.org/10.1016/j.strusafe.2011.12.004.
Ouyang, M., & Fang, Y. P. (2017). A mathematical framework to optimize critical infrastructure resilience against intentional attacks. Computer-Aided Civil and Infrastructure Engineering. https://doi.org/10.1111/mice.12252.
Ouyang, M., & Wang, Z. (2015). Resilience assessment of interdependent infrastructure systems: With a focus on joint restoration modeling and analysis. Reliability Engineering & System Safety, 141, 74–82. https://doi.org/10.1016/j.ress.2015.03.011.
ReVelle, C. S., & Swain, R. W. (1970). Centrirl facilities location. Geographical Analysis, 2(1), 30–42.
Scaparra, M. P., & Church, R. L. (2008a). A bilevel mixed-integer program for critical infrastructure protection planning. Computers & Operations Research, 35(6), 1905–1923.
Scaparra, M. P., & Church, R. L. (2008b). An exact solution approach for the interdiction median problem with fortification. European Journal of Operational Research, 189(1), 76–92. https://doi.org/10.1016/j.ejor.2007.05.027.
Simic, Z., Lugaric, L., & Krajcar, S. (2009). Integrated approach to energy security and critical infrastructure in Croatia. Paper presented at the 6th international conference on the European Energy Market, EEM 2009, Leuven, Belgium.
Stützle, T. (2009). Ant colony optimization. In M. Ehrgott, C. M. Fonseca, X. Gandibleux, J.-K. Hao & M. Sevaux (Eds.), Evolutionary multi-criterion optimization: 5th international conference, EMO 2009. Proceedings, Nantes, France, April 7–10, 2009 (p. 2). Berlin, Heidelberg: Springer.
Swain, R. W. (1971). A decomposition algorithm for a class of facility location problems. Ph.D. thesis, Cornell University, Ithaca, New York, USA.
Usberti, F. L., Lyra, C., Cavellucci, C., & González, J. F. V. (2012). Hierarchical multiple criteria optimization of maintenance activities on power distribution networks. Annals of Operations Research, 224(1), 171–192. https://doi.org/10.1007/s10479-012-1182-6.
Wang, K. J., & Lee, C. H. (2015). A revised ant algorithm for solving location-allocation problem with risky demand in a multi-echelon supply chain network. Applied Soft Computing, 32, 311–321. https://doi.org/10.1016/j.asoc.2015.03.046.
Waters, N. M. (1977). Methodology for servicing the geography of urban fire: An exploration with special reference to London, Ontario. Unpublished doctoral dissertation, University of Western Ontario.
Yueni, Z., Zheng, Z., Xiaoyi, Z., & Kaiyuan, C. (2013). The r-interdiction median problem with probabilistic protection and its solution algorithm. Computers & Operations Research, 40(1), 451–462. https://doi.org/10.1016/j.cor.2012.07.017.
Zhang, C., & Ramirez-Marquez, J. E. (2013). Protecting critical infrastructures against intentional attacks: A two-stage game with incomplete information. IIE Transactions, 45(3), 244–258. https://doi.org/10.1080/0740817X.2012.676749.
Zhang, C., Ramirez-Marquez, J. E., & Li, Q. (2018). Locating and protecting facilities from intentional attacks using secrecy. Reliability Engineering & System Safety, 169(1), 51–62.
Zhang, C., Ramirez-Marquez, J. E., & Wang, J. (2015). Critical infrastructure protection using secrecy—A discrete simultaneous game. European Journal of Operational Research, 242(1), 212–221. https://doi.org/10.1016/j.ejor.2014.10.001.
Acknowledgements
The authors gratefully acknowledge the support from the National Natural Science Foundation of China under Grants 71301085, 71332005, 71671074 and 71731008, and the Fundamental Research Funds for the Central Universities (Grant Number HUST: 2017KFYXJJ178).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bao, S., Zhang, C., Ouyang, M. et al. An integrated tri-level model for enhancing the resilience of facilities against intentional attacks. Ann Oper Res 283, 87–117 (2019). https://doi.org/10.1007/s10479-017-2705-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-017-2705-y