A new model to protect an important node against two threatening agents

Document Type : Research Paper


1 Department of Mathematics, Shiraz University of Technology, Shiraz, Iran

2 Department of Computer Engineering and Information Technology, Shiraz University of Technology, Shiraz, Iran


One of the main goals of network planners is the protection of important nodes in a network against natural disasters, security threats, attacks, and so on.
  Given the importance of this issue,  a new model is presented in this paper for protecting an important node  in a typical network based on a defensive location problem where the two  agents threaten  this node.  The protecting facilities location problem with two agents is formulated as a three-level programming problem.   The decision maker in the upper level is a network planner agent. The planner agent wants to find the best possible location of protecting facilities  to protect the important node against threatening agents. The second and third levels problems are stated as the shortest path problems in the network in which the edges are weighted with positive values. In this work, the genetic, variable neighborhood search, simulated annealing algorithms are used to solve the problem.  The performance of the used metaheuristic algorithms on this class of problems is investigated by a test problem that is generated randomly. Then,   t-test  are used to compare the performance of these algorithms. The best results are obtained by  the variable neighborhood search algorithm.


[1] J. Holland, Adaptation in natural and artifcial system, MIT Press, Cambridge, 1992.
[2] R. Khanduzi, M. R. Peyghami, H. R. Maleki, Solving continuous single-objective protecting location problem based on hybrid directed tabu search algorithm, International Journal of Advanced Manufacturing, 76 (2015), 295-310.
[3] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by simulated annealing, Science, 220(4598) (1983), 671- 680.
[4] H. R. Maleki, R. Khanduzi, R. Akbari, A novel hybrid algorithm for solving continuous single objective protecting location problem, Neural Computing and Applications, 28(11) (2016), 3323-3340.
[5] N. Mladenovic, P. Hansen, Variable neighborhood search, Computers and Operations Research, 24(11) (1997), 1097- 1100.
[6] M. Salehi, H. R. Maleki, S. Niroomand, Solving a new cost-oriented assembly line balancing problem by classical and hybrid meta-heuristic algorithms, Neural Computing and Applications, 32 (2020), 8217-8243.
[7] T. Uno, H. Katagiri, Single and multiobjective protecting location problems on a network, European Journal of Operational Research, 188 (2008), 76-84.