An Algorithm for Solving the Traveling Salesman Problem
M.M. Hamed · Journal of King Abdulaziz University-Engineering Sciences · 1992
ABSTRACT. The main objective of the paper is to present an algorithm for finding a solution to the traveling salesman problem. The solution found by the algorithm being an optimal one or not, depends on the values ofthe ele-ments of the cost matrix. The algorithm is described and its time complexity is calculated and compared to other algorithms in the literature. It is shown that the proposed algorithm is efficient as it finds the solution in shoner time if compared to other algorithms. I. Introductioo The ordinary traveling salesman problem (TSP) is formulated in the literature[J1 as: "Finding the tour with minimum cost for passing through each of n cities exactly once, starting from and ending at an arbitrary city". This problem is classified as being NP-complete[2l. Actually, there are several variations of the TSP, e.g., time-dependent TSPfJAJ, and stochastic TSPI5J. Each variation lead to a rather different problem. Our main concern here is the ordinary TSP. Exhausti\\'t: search for an optimal solution by trying all possible permutations is a method which is not referred to any specific author. The time of such an approach is o (n!) since we must consider (n- I)! different permutations, and each permutation takes 0 (n) time to evaluate. Another algorithm due to Held and Karpl6! gives the op-timal solution in time O(n2 2n). This algorithm uses dynamic programming techniques. Other algorithms in the literature do not give an optimal solution, but rather they give a "good " solution based on heuristics. Examples of such heuristics are found in KruskalPI and Lin & Kernighan l8J. When comparing different al-