Abstract Of Work Undertaken:

This term paper contains information about the travelling salesman problem, its history, application and theory. The TSP has received considerable attention over the last two decades. The travelling salesman problem (TSP) is a well known and important combinatorial optimization problem. The goal of TSP is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. Its definitely intriguing that a problem so easy to state can be so difficult to solve.

Table of Content
Contents
1. Introduction 2. History 3. Application 4. Theory a. As a graph b. Asymmetric and symmetric c. Related problems 5. Computing a solution A. Exact algorithms B. Heuristic and approximation algorithms i. ii. iii. Constructive heuristics Iterative improvement Randomised improvement

Page No.
5 5-6 6 6-7 6 7 7 8-12 8 8-11 9 9-10 10-11 11 11 11 11 12 12 12 12

C. Special cases i. ii. iii. Metric TSP Euclidean TSP Asymmetric TSP

D. Benchmarks 6. Human performance on TSP 7. Conclusion 8. References

Topic: Issues in travelling salesman problem

INTRODUCTION:

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. The structure should be simple enough that one can effectively process the data when necessary and rich enough to mirror the actual relationships of the data in the real world. Data structures are used in almost every program or software system. Data structure provides a means to manage huge amounts of data efficiently. Usually, efficient data structures are a key to designing efficient algorithms. The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations. The Travelling Salesman Problem is one of the most intensively studied problems in computational mathematics. The travelling salesman problem (TSP) is an NP-hard problem in combinational optimization studied in operations research and theoretical computer science. This term paper is devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point. In the theory of computational complexity, TSP (where, given a length L, the task is to decide whether any tour is shorter than L) belongs to a class of problems called NP-complete. These problems have no known efficient algorithms for solving them. Thus, it is likely that the worst case running time for any algorithm for the TSP increases exponentially with the number of cities. The TSP has received considerable attention over the last two decades and various approaches are proposed to solve the problem, such as branch-and-bound, cutting planes, 2opt, simulated annealing, neural network, and tabu search. Some of these methods are exact algorithms, while the others are near-optimal or approximate algorithms. The exact algorithms include the integer linear programming approaches with additional linear constraints to eliminate infeasible sub tours. On the other hand, network models yield appropriate methods that are flexible enough to include the precedence constraints. More recently, genetic algorithm approaches are successfully implemented to the TSP.
2.

HISTORY:

The origins of the travelling salesman problem are unclear. The travelling salesman problem was defined in the 1800s by the Irish mathematician W.R. Hamilton and by the British mathematician Thomas Kirkman. The general form of the TSP appears to have been first studied

by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic. The name travelling salesman problem was introduced soon after by Hassler Whitney at Princeton University. In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the USA. In the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences. Richard M. Karp showed in 1972 that the Hamilton cycle problem was NP-Complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours. Great progress was made in the late 1970s and 1980, when Grtschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2392 cities, using cutting planes and branch-and-bound. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2005, Cook and others computed an optimal tour through a 33,810-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 1% of an optimal tour.
3.

APPLICATION:

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. Other application of TSP are robotic travel problems like soldering or drilling operations on printed circuit boards, sequencing local genome maps to produce a global map, planning the order in which a satellite interferometer studies a sequence of stars. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder. Perhaps as important as the direct applications, TSP provides a base for academic research on discrete optimization problems.

4.

THEORY:

That refers to the problem of visiting a number of points (which may be cities), while keeping the total distance travelled as low as possible. In this section, some aspects of the TSP which are important for the implementation of the TSP are summarized briefly. a. As a graph problem: TSP can be modelled as an undirected weighted graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's length. A TSP tour becomes a Hamilton cycle, i.e., a cycle which visits each node in the graph exactly once, with the least weight in the graph, if and only if every edge has the same distance. Often, the model is a complete graph (i.e., an edge connects each pair of vertices). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour. Asymmetric and symmetric: It has to be noted that in this paper, following the origin of the TSP, the term distance is used. Distance is used here interchangeably with dissimilarity or cost and, unless explicitly stated, no restrictions to measures which obey the triangle inequality are made. An important distinction can be made between the symmetric TSP and the more general asymmetric TSP. In the symmetric TSP, the distance between two cities is the same in each opposite direction, forming an undirected graph. This symmetry halves the number of possible solutions. In the asymmetric TSP, paths may not exist in both directions or the distances might be different, forming a directed graph. Traffic collisions, one-way streets, and airfares for cities with different departure and arrival fees are examples of how this symmetry could break down.

Fig: Symmetric TSP with four cities

Fig: Asymmetric TSP

b. Related problems: The requirement of returning to the starting city does not change the computational complexity of the problem. The sequential ordering problem deals with the problem of visiting a set of cities where precedence relations between the

cities exist. The travelling purchaser problem deals with a purchaser who is charged with purchasing a set of products. He can purchase these products in several cities, but at different prices and not all cities offer the same products. The objective is to find a route between a subset of the cities, which minimizes total cost (travel cost + purchasing cost) and which enables the purchase of all required products.

5.

COMPUTING A SOLUTION:

Computational complexity The problem has been shown to be NP-hard and the decision problem version is NPcomplete. The bottleneck travelling salesman problem is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases. Removing the condition of visiting each city "only once" does not remove the NP-hardness, since it is easily seen that in the planar case there is an optimal tour that visits each city only. Complexity of approximation In the general case, finding a shortest travelling salesman tour is NPO-complete. If the distance measure is a metric and symmetric, the problem becomes APX-complete. If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 7/6. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio 0.814 log n; it is an open question if a constant factor approximation exists. The corresponding maximization problem of finding the longest travelling salesman tour is approximable within 63/38. If the distance function is symmetric, the longest tour can be approximated within 4/3 by a deterministic algorithm and within by a randomised algorithm. The traditional lines of attack for the NP-hard problems are the following: i. ii. iii. Devising algorithms for finding exact solutions (they will work reasonably fast only for small problem sizes). Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or probably good solutions, but which could not be proved to be optimal. Finding special cases for the problem ("sub problems") for which either better or exact heuristics are possible. A. Exact algorithms Finding the exact solution to a TSP with n cities requires checking (n-1)! possible tours. The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest. The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is the Held-Karp algorithm that solves the problem in time O(n22n). The dynamic programming solution requires exponential space. Using inclusion-exclusion, the problem can be solved in time within a polynomial factor of 2n and polynomial space. Improving these time bounds seems

to be difficult. For example, it has not been determined whether an exact algorithm for TSP that runs in time O(1.9999n) exists.
B. Heuristic and approximation algorithms

The NP-completeness of the TSP already makes it more time sufficient for small-tomedium size TSP instances to rely on heuristics in case a good but not necessarily optimal solution is sufficient. TSP heuristics typically fall into two groups, tour construction heuristics which create tours from scratch and tour improvement heuristics which use simple local search heuristics to improve existing tours. Various heuristics and approximation algorithms, which quickly yield good solutions have been devised. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 23% away from the optimal solution. Several categories of heuristics are recognized. Constructive heuristics Nearest neighbour algorithm: The nearest neighbour algorithm follows a very simple greedy procedure: The algorithm starts with a tour containing a randomly chosen city and then always adds to the last city in the tour the nearest not yet visited city. The algorithm stops when all cities are on the tour. An extension to this algorithm is to repeat it with each city as the starting point and then return the best tour found. This heuristic is called repetitive nearest neighbour. Insertion algorithms: All insertion algorithms start with a tour consisting of an arbitrary city and then choose in each step a city k not yet on the tour. This city is inserted into the existing tour between two consecutive cities i and j, such that the insertion cost (i.e., the increase in the tour's length) d(i,k) + d(k,j) - d(i,j) is minimized. The algorithms stop when all cities are on the tour. The insertion algorithms differ in the way the city to be inserted next is chosen. The following variations are implemented: Nearest insertion: The city k is chosen in each step as the city which is nearest to a city on the tour. Farthest insertion: The city k is chosen in each step as the city which is farthest from any of the cities on the tour. Cheapest insertion: The city k is chosen in each step such that the cost of inserting the new city is minimal. Arbitrary insertion: The city k is chosen randomly from all cities not yet on the tour. The nearest and cheapest insertion algorithms correspond to the minimum spanning tree algorithm. Adding a city to a partial tour corresponds to adding an edge to a partial spanning tree. For TSPs with distances obeying the triangular inequality, the equality to minimum spanning trees provides a theoretical upper bound for the two algorithms of twice the optimal tour length. The idea behind the farthest insertion algorithm is to link cities far outside into the tour first to establish an outline of the whole tour early. With this change, the algorithm cannot be directly related to generating a minimum spanning tree and thus the upper bound stated above cannot be guaranteed. However, it can was shown that the algorithm generates tours which approach 2=3 times the optimal tour length.

Iterative improvement: Tour improvement heuristics are simple local search heuristics which try to improve an initial tour.
a. Pairwise exchange or Lin-Kernighan heuristics: The pairwise exchange or 2-

opt technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. This is a special case of the k-opt method. Note that the label Lin Kernighan is an often heard misnomer for 2-opt. LinKernighan is actually a more general method. b. k-opt heuristic: The idea is to define a neighbourhood structure on the set of all admissible tours. Take a given tour and delete k mutually disjoint edges. Reassemble the remaining fragments into a tour, leaving no disjoint sub tours. This in effect simplifies the TSP under consideration into a much simpler problem. Each fragment endpoint can be connected to 2k 2 other possibilities: of 2k total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2k-city TSP can then be solved with brute force methods to find the least-cost recombination of the original fragments. The k-opt technique is a special case of the V-opt or variable-opt technique. The most popular of the k-opt methods are 3-opt, and these were introduced by Shen Lin of Bell Labs in 1965. There is a special case of 3-opt where the edges are not disjoint (two of the edges are adjacent to one another). In practice, it is often possible to achieve substantial improvement over 2-opt without the combinatorial cost of the general 3-opt by restricting the 3-changes to this special subset where two of the removed edges are adjacent. This so-called two-and-a-half-opt typically falls roughly midway between 2-opt and 3-opt, both in terms of the quality of tours achieved and the time required to achieve those tours. c. V-opt heuristic: The variable-opt method is related to, and a generalization of the kopt method. Whereas the k-opt methods remove a fixed number (k) of edges from the original tour, the variable-opt methods do not fix the size of the edge set to remove. Instead they grow the set as the search process continues. The best known method in this family is the LinKernighan method.
Randomised improvement:

Optimized Markov chain algorithms which use local searching heuristic subalgorithms can find a route extremely close to the optimal route for 700 to 800 cities. TSP is a touchstone for many general heuristics devised for combinatorial optimization such as genetic algorithms, simulated annealing, Tabu search, ant colony optimization, river formation dynamics and the cross entropy method.

Ant colony optimization: Artificial intelligence researcher Marco Dorigo described in 1997 a method of heuristically generating "good solutions" to the TSP using a simulation of an ant colony called ACS (Ant Colony System). It models behaviour observed in real ants to find short paths between food sources and their nest, an emergent behaviour resulting from each ant's preference to follow trail pheromones deposited by other ants. ACS sends out a large number of virtual ant agents to explore many possible routes on the map. Each ant probabilistically chooses the next city to visit based on a heuristic combining the distance to the city and the amount of virtual pheromone deposited on the edge to the city. The ants explore, depositing pheromone on each edge that they cross, until they have all completed a tour. At this point the ant which completed the shortest tour deposits virtual pheromone along its complete tour route. The amount of pheromone deposited is inversely proportional to the tour length: the shorter the tour, the more it deposits. Special cases: Metric TSP: In the metric TSP, also known as delta-TSP or -TSP, the intercity distances satisfy the triangle inequality. A very natural restriction of the TSP is to require that the distances between cities form a metric, i.e., they satisfy the triangle inequality. This can be understood as the absence of "shortcuts", in the sense that the direct connection from A to B is never longer than the route via intermediate C: The edge lengths then form a metric on the set of vertices. When the cities are viewed as points in the plane, many natural distance functions are metrics, and so many natural instances of TSP satisfy this constraint. a. Euclidean TSP: The Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. The Euclidean TSP is a particular case of the metric TSP, since distances in a plane obey the triangle inequality. Like the general TSP, the Euclidean TSP (and therefore the general metric TSP) is NP-complete. However, in some respects it seems to be easier than the general metric TSP. For example, the minimum spanning tree of the graph associated with an instance of the Euclidean TSP is a Euclidean minimum spanning tree, and so can be computed in expected O(n logn) time for n points. This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly.

In general, for any c > 0, where d is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP in b. Asymmetric TSP: In most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance from A to B is not equal to the distance from B to A is called asymmetric TSP. A practical application of an asymmetric TSP is route optimisation using street-level routing (which is made asymmetric by one-way streets, slip-roads, motorways, etc). time.

Benchmarks: For benchmarking of TSP algorithms, TSLIB is a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual printed circuits.
6.

Human performance on TSP:

The TSP, in particular the Euclidean variant of the problem, has attracted the attention of researchers in cognitive psychology. It is observed that humans are able to produce good quality solutions quickly. The first issue of the Journal of Problem Solving is devoted to the topic of human performance on TSP.
7.

CONCLUSION:

The travelling salesman problem is a well known and important combinatorial optimization problem. The TSP has received considerable attention over the last two decades. The goal of TSP is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. Solving TSPs is an important part of applications in many areas including vehicle routing, computer wiring, machine sequencing and scheduling, frequency assignment in communication networks. Its intriguing that a problem so easy to state can be so difficult to solve. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.
8.

REFERENCES:
i. ii. iii. iv. v.

http://mathworld.wolfram.com/TravelingSalesmanProblem.html http://ai-depot.com/Articles/51/TSP.html\ http://cran.r-project.org/web/packages/TSP/vignettes/TSP.pdf http://CRAN.R-project.org/doc/Rnews/ Applegate, D. L.; Bixby, R. M.; Chvtal, V.; Cook, W. J. (2006), The Traveling Salesman Problem

Dantzig G, Fulkerson D, Johnson S (1954). \Solution of a Large-scale Traveling Salesman Problem." vii. Croes GA (1958). \A Method for Solving Traveling-Salesman Problems.".
vi.