A bi-level programming model for protecting an important node in a network. (English) Zbl 1482.90123
Summary: Protecting important nodes in a network against natural disasters, security threats, attacks and so on is one of the main goals of network planners. In this paper, a new model is presented for protecting an important node (NMPN) in a typical network based on defensive location problem where the threatening agent (t-agent) has the ability to reinforce its power at some nodes. The NMPN is a bi-level programming problem. At the upper level, the planner agent (p-agent) try to find the best locations for protecting resources in order to protect the important node. The lower level problem is represented as the shortest path problem in the network in which the edges are weighted with positive values and sometimes negative values. Thus, Bellman-Ford algorithm is applied to solve the lower level problem. The NMPN is an NP-hard problem. In this work, the genetic, ant colony optimization, binary artificial bee colony with differential evolution, artificial bee colony algorithms and a modified tabu search (MTS) algorithm are used to solve the problem. A test problem is randomly generated to investigate the performance of the used metaheuristic algorithms in this paper. Parameters of the metaheuristic algorithms are tuned by the Taguchi method for solving the test problem. Also, the ANOVA and Tukey tests are used to compare the performance of metaheuristic algorithms. The best results are obtained by the MTS algorithm.
MSC:
| 90C10 | Integer programming |
| 90B80 | Discrete location and assignment |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | J. Antony and M. Kaye, Experimental Quality: A Strategic Approach to Achieve and Improve Quality, Kluwer Academic, Norwell (1999). |
| [2] | C. O. Astorquiza, I. Contreras and G. Laporte, Multi-level facility location problem, European Journal of Operational Research, 267 (2018), 791-805. · Zbl 1403.90484 |
| [3] | O. Berman, T. Drezner, Z. Drezner and G. O. Wesolowsky, A pro-tecting maximal covering problem on a network, International Trans-actions in Operational Research, 16 (2009), 69-86. · Zbl 1153.90332 |
| [4] | J. Cao, B. Yin, Y. Lu, X. Kang and A. Chen, Modified artificial bee colony approach for the 0-1 knapsack problem, Applied Intelligence, 48 (2017), 1582-1595. |
| [5] | T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, Massachusetts (1990). · Zbl 1158.68538 |
| [6] | S. Dempe, Foundations of Bilevel Programming, Kluwer Academic, Dordrecht (2002). · Zbl 1038.90097 |
| [7] | M. Dorigo, Optimization, Learning and Natural Algorithms, Ph.D. thesis, Politecnico di Milano, Italy (1992). |
| [8] | Z. Drezner, Competitive location strategies for two facilities, Re-gional Science and Urban Economics, 12 (1982), 485-493. |
| [9] | B. C. Eaton and R. G. Lipsey, The principle of minimum differenti-ation reconsidered: Some new developments in the theory of spatial competition, The Review of Economic Studies, 42 (1975), 27-49. · Zbl 0294.90003 |
| [10] | F. Ferdowsi, H. R. Maleki and S. Rivaz, Air refueling tanker alloca-tion based on a multi-objective zero-one integer programming model, Operational Research, 20 (2018), 1913-1938. |
| [11] | F. Ferdowsi , H. R. Maleki and S. Rivaz, A bi-objective formulation for refueling stations selection problem, Journal of Mathematical Ex-tension, 13 (2019), 71-85. · Zbl 1461.90077 |
| [12] | S. L. Hakimi, On locating new facilities in a competitive environ-ment, European Journal of Operational Research, 12 (1983), 29-35. · Zbl 0499.90026 |
| [13] | M. A. HashemiNezhad and M. Abbasi, Stochastic capacitated p-median problem with normal distribution, Journal of Mathematical Extension, 13 (2019), 1-21. · Zbl 1461.90066 |
| [14] | J. Holland, Adaptation in Natural and Artificial System, MIT Press, Cambridge (1992). |
| [15] | H. Hotelling, Stability in competition, The Economic Journal, 30 (1929), 41-57. |
| [16] | C. Hu, X. Liu and j. Lu, A bi-objective two-stage robust location model for waste-to-energy facilities under uncertainty, Decision Sup-port Systems, 99 (2017), 37-50. |
| [17] | D. Karaboga, An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Kayseri (2005). |
| [18] | K. Karkazis, Facilities location in a competitive environment, Eu-ropean Journal of Operational Research, 42 (1989), 294-304. · Zbl 0688.90018 |
| [19] | R. Khandouzi, M. R. Peyghami and H. R. Maleki, Solving con-tinuous single-objective defensive location problem based on hybrid directed tabu search algorithm, International Journal of Advanced Manufacturing Technology, 76 (2015), 295-310. |
| [20] | D. Kress and E. Pesch, Sequential competitive location on networks, European Journal of Operational Research, 217 (2012), 483-499. · Zbl 1244.90128 |
| [21] | H. R. Maleki , R. khanduzi and R. Akbari, A novel hybrid algorithm for solving continuous single objective protecting location problem, Neural Computing and Applications, 28 (2016), 3323-3340. |
| [22] | C. S. ReVelle and H. A. Eiselt, Location analysis: A synthesis and survey, European Journal of Operational Research, 165 (2005), 1-19. · Zbl 1112.90362 |
| [23] | M. Sakawa, K. Kato and T. Shibano, An interactive Fuzzy satisfic-ing method for multiobjective multidimensional 0-1 knapsack prob-lems through genetic algorithms, Proceedings of IEEE International Conference on Evolutionary Computation, (1996), 243-246. |
| [24] | R. Storn and K . Price, Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11(1997), 341-359. · Zbl 0888.90135 |
| [25] | G. Taguchi, Introduction to Quality Engineering, Asian Productiv-ity Organization/UNIPUB, White Plains, (1986). |
| [26] | E. G. Talbi, Metaheuristics: From Design to Implementation, John Wiley and Sons, Hoboken, (2009). · Zbl 1190.90293 |
| [27] | C. Teye , G. H. Bell and C. J. Bliemer, Entropy maximizing facility location model for port city intermodal terminals, Transportation Research Part E: Logistics and Transportation Review, 100 (2017), 1-16. |
| [28] | T. Uno and H. Katagiri, Single and multi-objective protecting lo-cation problems on a network, European Journal of Operational Re-search, 188 (2008), 76-84. · Zbl 1135.90022 |
| [29] | T. Uno and K. Kato, An interactive fuzzy satisficing method for multiobjective stochastic protecting location problems, IEEE Inter-national Conference on Fuzzy Systems, (2011), 879-883. |
| [30] | A. Weber, Reine Theory des Standorts, Verlag des Mohr, Tubingen, (1909). |
| [31] | R. Zanjirani and M. Hekmatfar, Facility Location: Concepts, Models, Algorithms and Case Studies, Physica-Verlag, Heidelberg, (2009). |
| [32] | R. Zanjirani, S. Fallah, R. Ruise, S. Hosseini and N. Asgari, OR models in urban service facility location: A critical review of appli-cations and future developments, European Journal of Operational Research, 726 (2018), 1-27. |
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.
