A Survey of Approximate Methods for the Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is a famous problem in the class of combinatorial optimization problems. Its special case is a symmetric TSP in which the matrix of the distances between each pair of cities is symmetric. Several approaches have been proposed up to date for solving the symmetric TSP, especially the approximate methods, which have made remarkable advances. This article aims to survey these techniques including the approximation algorithms, the neural network methods, and the metaheuristics. The hybridization schemes based on these manners are also reviewed.