International Journal of Nonlinear Analysis and Applications

The distance-based critical node detection in the symmetric travelling salesman problem and its application to improve the approximate solutions

Document Type : Research Paper

Authors

1 Department of Mathematics and Computer Science, University of Bonab, Bonab, Iran

2 Department of Computer Engineering, University of Bonab, Bonab, Iran

Abstract

The travelling salesman problem is one of the well-known NP-hard problems, and there are various versions of the problem with respect to its different specifications of the constraints and assumptions. Especially, the symmetric travelling salesman problem has been considered in numerous routing models. The critical node detection problem has received increasing attention throughout the routing models. The critical node has the most important role in the routing problems, and if it is out of service then the optimal solution will be hit by a large undesirable cost. The critical node is defined as the node whose deletion from the network results in the largest decrease in the optimal cost. It is proved the critical node of the network is the critical node for the optimal tour, too. Thus, the critical node is considered to obtain a good approximate solution in a reasonable iteration. The 2-opt heuristic is applied by the critical node in the symmetric traveling salesman problem and the iterations are reduced significantly. Then, the pseudo-critical node is defined and detected in the approximate solution, whose removal results in the largest decrease of the approximate cost. So, the 2-opt heuristic is applied by the pseudo-critical node and the optimal or a nearby optimal solution is obtained.

Keywords

[1] G.U. Alozie, A. Arulselvan, K. Akartunalı and E.L. Pasiliao Jr, Efficient methods for the distance-based critical node detection problem in complex networks, Comput. Oper. Res. 131 (2021), 105254.
[2] R. Aringhieri, A. Grosso and P. Hosteins and R. Scatamacchia, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, Discrete Appl. Math. 253 (2019), 103–121.
[3] A. Arulselvan, C.W. Commander, L. Elefteriadou and P. M. Pardalos, Detecting critical nodes in sparse graphs, Comput. Oper. Res. 36 (2009), no. 7, 2193–2200.
[4] W. Chen, M. Jiang, C. Jiang and J. Zhang, Critical node detection problem for complex network in undirected weighted networks, Phys. A: Statist. Mech. Appl. 538 (2020), 122862.
[5] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Carnegie-Mellon University Pittsburgh Pa Management Sciences Research Group, 1976.
[6] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein Introduction to algorithms, 3rd ed., MIT Press, 2009.
[7] M. Di Summa, A. Grosso and M. Locatelli, Complexity of the critical node problem over trees, Comput. Oper. Res. 38 (2011), no. 12, 1766–1774.
[8] C. Jiang, Z. Liu, J. Wang, H. Yu and X. Guo, An optimal approach for the critical node problem using semidefinite programming, Phys. A: Statist. Mech. Appl. 471 (2017), 315–324.
[9] M. Held and R.M. Krap, The traveling salesman problem and minimum spanning trees, Oper. Res. 18 (1970), no. 6, 1138–1162.
[10] J.A. Hoogeveen, Analysis of Christofides’ heuristic: Some paths are more difficult than cycles, Oper. Res. Lett. 10 (1991), no. 5, 291–295.
[11] S. Hore, A. Chatterjee and A. Dewanji, Improving variable neighborhood search to solve the travelling salesman problem, Appl. Soft Comput. 68 (2018), 83–91.
[12] J. Li, P.M. Pardalos, B. Xin and J. Chen, The bi-objective critical node detection problem with minimum pairwise connectivity and cost: Theory and algorithms, Soft Comput. 23 (2019), no. 23, 12729–12744.
[13] J. Rezaei, F. Zare-Mirakabad, S.A. MirHassani and S.A. Marashi, EIA-CNDP: An exact iterative algorithm for critical node detection problem, Comput. Oper. Res. 127 (2021), 105138.
[14] S. Sahni and T. Gonzales, P-complete approximation problems, J. ACM 23 (1976), no. 3, 555–565.
[15] D. Santos, A. de Sousa and P. Monteiro, Compact models for critical node detection in telecommunication networks, Electronic Notes Discrete Math. 64 (2018), 325–334.
[16] G.H. Shirdel and M. Abdolhosseinzadeh, The critical node problem in stochastic networks with discrete-time Markov chain, Croatian Oper. Res. Rev. 7 (2016), no. 1, 33—46.
[17] S. Shukla, Reliable critical nodes detection for Internet of Things (IoT), Wireless Networks 27 (2021), no. 4, 2931–2946.
[18] A. Veremyev, K. Pavlikov, E. L. Pasiliao, M. T. Thai and V. Boginski, Critical nodes in interdependent networks with deterministic and probabilistic cascading failures, J. Glob. Optim. 74 (2019), no. 4, 803–838.
[19] Y. Zhou, Z. Wang, Y. Jin and Z.H. Fu, Late acceptance-based heuristic algorithms for identifying critical nodes of weighted graphs, Knowledge-Based Syst. 211 (2021), 106562.
International Journal of Nonlinear Analysis and Applications
Volume 14, Issue 8
August 2023
Pages 291-296
  • Receive Date: 02 March 2022
  • Revise Date: 20 May 2022
  • Accept Date: 05 September 2022