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

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 ۲-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 ۲-opt heuristic is applied by the pseudo-critical node and the optimal or a nearby optimal solution is obtained.

کلیدواژه ها:

Critical node ، Travelling salesman problem ، Approximation Algorithm ، ۲-opt algorithm ، Approximate Solution