Article Preview
Top1. Introduction
Given a tourist map with a set of n cities and the distances dij (1≤i,j≤n and i≠j) between each pairs of them, find the shortest tour which visits each of the cities once and exactly once. Here n is a finite integer. This is the classic traveling salesman problem (TSP). A tour with each of the cities once is named as the Hamiltonian cycle (HC) or Hamiltonian tour. The objective of TSP is to detect the shortest HC, i.e., the best tour with length lmin=Min(l(HC)) and where l(HC) means the length of the HC. In graph theory, the TSP map is usually represented as a complete weighted graph. The weights on the edges note the distance, time or expense for various kinds of TSP. Therefore, a mathematical formulation of TSP is to find the HC with the minimum (or maximum) weights in a complete weighted graph. In this paper, we take the minimum HC as the best tour and the weight is also called the cost.
TSP is easy to describe but hard to resolve. It has been proven to be NP-complete. For the symmetrical TSP with n cities, the number of HCs reaches (n-1)!/2. It is a challenging work to design an efficient algorithm for TSP. The time complexity of the exact algorithms is generally an exponential function of the scale of TSP. Finding the best tour is our desired goal whereas the exact algorithms are time-consuming for large scale of TSP instances. In 1962, Held and Karp (1962) and Bellman (1962) used the dynamic programming method to detect the best tour in O(n22n) time. Till 2010, the time is reduced to O(1.657n) by Andreas (Andreas, 2010) with a Monte Carlo method. Please refer to the literatures (Woeginger, 2003; Matai, Prakash & Mittal, 2010; Applegate, Bixby, Chvatal & Cook, 2006) to acquire more information about the exact algorithms for TSP. Although some TSP with thousands of cities has been resolved by the exact algorithms, such as the improved cutting plane method (http://www.math.uwaterloo.ca/tsp/index.html), it is believed the exact algorithm does not exist unless NP=P. The experiments on exact algorithms show that they are feasible for TSP with less than 1,000 cities (Singh, & Oudheusden, 1997; Klerk & Dobre, 2011; Gouveia, Voβ, 1995; Perez, & Gonzalez, 2004). Once the scale of TSP becomes larger, the computation time will increase tremendously even the super computers are utilized (Levine, 2000; Ergan & Orlin, 2006).