Learning ۲-opt Algorithm for the Euclidean Symmetric Traveling Salesman Problem

The traveling salesman problem (TSP) is known one of the NP-hard problems to find the optimal solution. However, in the case that arc costs satisfy the triangle inequality there are polynomial time approximation algorithms; ۲-opt algorithm is a heuristic method to obtain a good approximate solution for TSP. The proposed learning ۲-opt algorithm improves the classical ۲-opt algorithm to remove cross arcs and cross regions and provides a good approximate solution in a reasonable iteration. So, in the optimal solution for the Euclidean symmetric TSP (ES-TSP) there is neither cross arcs nor cross regions, and a learning phase determine the cross regions, and the ۲-opt heuristic algorithm removes the cross arcs. A Markov decision process is applied to determine the states of the learning process, and it is considered to reward function according to the improvement of the current state solution. The topology of the network and the order of nodes are learned by the proposed method, and the proper ۲-opt improvement policy is implemented during transitions in the Markov chain process.