Traveling salesman problem in which all the vertices are assumed to be on a spherical surface is a special case of the conventional travelling salesman problem. There are exact and approximate algorithms for the travelling salesman problem. As the solution time is a performance parameter in most real-time applications, approximate algorithms always have an important area of research for both researchers and engineers. In this chapter, approximate algorithms based on heuristic methods are considered for the travelling salesman problem on the sphere. Firstly, 28 test instances were newly generated on the unit sphere. Then, using various heuristic methods such as genetic algorithms, ant colony optimization, and fluid genetic algorithms, the initial solutions for solving test instances of the traveling salesman problem are obtained in Matlab®. Then, the initial heuristic solutions are used as input for the 2-opt algorithm. The performances and time complexities of the applied methods are analyzed as a conclusion.
TopIntroduction
Describe the general perspective of the chapter. End by specifically stating the objectives of the chapter.
Although the origins of the Travelling Salesman Problem (TSP) are not exactly known, the early mathematical problems related to TSP have been put forward by W.R. Hamilton and T.P. Kirkman in the 1800s. In 1932, Menger (1932) made the mathematical definition of TSP and published it as the “messenger problem” (das boten problem) of finding an optimal delivery route. This problem was later called the TSP by Robinson (1949), and has become widespread in the literature with this term. Then, Dantzig et al. (1954) solved the TSP of 49 cities using linear programming methods. Also, Karp (1972) showed that problems involving the Hamilton tour were NP-class problems.
In TSP, one salesman needs to visit each of a list of n cities exactly once and then returns to the starting city. The importance of the TSP is that it represents a larger class of problems known as combinatorial optimization problems that has grown into a very mature field with strong links to various other disciplines like discrete mathematics (graph theory, combinatorics, etc.), computer science (complexity theory, data structures,etc.), probability theory, continuous optimization, and many other application areas. TSP also belongs to the class of such problems known as NP-complete. Thus, due to its nature, TSP is still attracting the attention of many researchers from various fields through clever combinations of ideas for finding an efficient algorithm in polynomial-time. It is known that the solution time in TSP extends exponentially as the problem size grows. Today, with the inventions and developments in the commercial and open-source software packages and hardware, combinatorial optimization problems are exactly solved. However, instead of all these improvements, it is still not possible to solve all large-scale combinatorial optimization problems and or to solve in reasonable time. Thus, the meta-heuristics are generally used to achieve reasonable solution times instead of exact solutions (Croes 1958; Holland 1975; Laporte 1992; Sureja 2012).
The Hamiltonian cycle problem is to decide whether a given graph has a Hamiltonian cycle in which each node is visited exactly once. In TSP, the problem is to find a minimum weight Hamiltonian Cycle. For a problem of n points, there are (n-1)!/2 Hamiltonian Tours if the distance matrix is symmetric, and n!/2, otherwise. The mathematical model of the TSP can be described as follows (Croes 1958). The objective function can be modeled as
(1) with the constraints
(2)(3)(4) where
dij is the distance from nodes of
i to
j,
n is the total number of nodes,
u is the artificial parameter for a guaranteed tour and the
Xij is the decision variable given as:
(5)