Travelling salesman problem is a grouped as a NP-hard problem. The problem involves identifying the shortest route that a sales man would follow to visit several cities. The travelling salesman problem model several problems of real life applications. There are approximations algorithms developed to solve the problem. However, an exact feasible solution to the general Travelling salesman problem has not been developed; although, the problem has been under research for more than half a decade. Small traveling salesman problems have been solved using exact algorithms developed through various methods, such as genetic algorithms.
It has been proved that the TSP cannot be approximated within any factor Unless P = NP. Also, the minimum spanning tree (MST) heuristic (TSP-MST) is an approximation algorithm. Moreover, the cycle shrinking algorithm is a for ATSP. These are some of the theorems brought forth in this paper.
The Application of the travelling salesman problem has wide application in modeling real-life applications. In this regard, the basic application is the sales man and the mail delivery route. The challenge is to identify the shortest route for the journey, so as to save cost and time of travel. Other applications include modeling machine schedules, robotic movements in cellular manufacturing, and frequency assignment in communications networks.
Earlier literature reveals that most research has concentrated on small TSP problems. Also, no exact feasible solutions to the general TSP problem have been found.
Travelling sales man problem deals with finding the shortest distance between cities. This involves finding the shortest distance upon which a sales man can visit each city once and return to the city of origin covering the shortest distance. It has been studied in the fields of computer science and operational research (Arora, 1996).
The problem arose around 1832 with no mathematical treatments. However, Hassler Whitney introduced the name “travelling sales man problem” at around 1930s. The problem gained significance in 1950s and 1960s when scientist from Europe and USA made contributions. Scientists such as George, Fulkerson, Johnson, and Santa defined the problem of travelling salesman problem as a linear program and developed cutting plane for its plane.
Undirected-weighted graph has been used to model the travelling salesman problem (TSP). Where cities are considered as the vertices of the graph, edges forms the paths, and the length of the edges form the path length. The problem involves optimization of the distance between the vertices through visiting each vertex once (Johnson, Gutin, Mcgeoch, Yeo, Zhang, & Zverovich, 2002).
There are two categories of travelling salesman problem, and this includes asymmetric and symmetric TSP (Sumant & Diptesh, 2008). In symmetric travelling sales man problem, the model of the problem forms an undirected graph where the distances between two cities are equal at opposite directions. In the asymmetric travelling sales man problem the paths in both directions of the cities may not exist; thus, forming a directed graph (Reinelt, 1994).
Given a group of cities and the travel costs from each city to the other, the TSP involves estimating the cheapest route for visiting all the cities and returning to the city of origin. The problem may seem simple if the travel cost is symmetric. However, the problem is a non-deterministic polynomial hard when the routes may not be directed in both directions and the travel costs are not symmetric. There has not yet an effective method for solving the travelling salesman problem, in spite of being studied most in computational mathematics (Johnson et al, 2002).
Travelling salesman problems in undirected graphs
Let G = (V, E) be an undirected graph, and the cost function for visiting each edge be C(e) > 0 for every edge e ϵE (Reinelt, 1994). The problem aims at finding the minimum cost of visiting each vertex V once; thus, it is referred as the Hamiltonian cycle.
Theorem 1 : “The TSP cannot be approximated within any factor Unless P = NP” (west, 2001).
Proof: let A be the approximation algorithm on TSP with an approximation ration K; then, the Hamiltonian can be solved in a polynomial time. Letting G = (V, E) be the given Hamiltonian. The graph H = (V, ) is generated with a cost of K(e) for every e ϵ E, if not so, then K(e) = D (Reinelt, 1994). Where D= nK +1 and n = . If G has a Hamiltonian cycle, the solution of the TSP solution gives an optimal cost (OPT) = n; otherwise, the optimal cost is n-1 +D = n(K+1) (Johnson et al, 2002).
The approximation ratio of A returns the TSP to H at a cost less than the optimal cost = Kn; otherwise, H does not have a TSP tour of a lesser costs than the optimal cost. However, the general traveling sales person problem cannot be solved, therefore, by contradiction the algorithm A with an approximation constant K may not exist.
Theorem 2: minimum spanning tree (MST) heuristic (TSP-MST) is an approximation algorithm)
Consider the MST based heuristic algorithm shown below
The graph G has Eulerian tour if v ϵ G has even degrees. Therefore, Eulerian graph can be obtained by doubling T (Reinelt, 1994).
We have c(T) = , where OPT is the optimal cost.
A tree can be obtained by eliminating an edge from the optimized Hamiltonian cycle. Therefore, c(H) = 2c(T) ≤ 2OPT(west, 2001).
Travelling salesman problem in directed graphs
In undirected travelling salesman problem the objective is establish the Hamiltonian cycle, while, in the directed TSP, the objective would be to establish the Hamiltonian walk. Let G = (V, A) be a directed graph with a cost of c(a) > 0 for every arc a ϵ A, solution would involve establishing a closed walk through all vertices (west, 2001). In this case, cycle shrinking algorithm is used. A minimum cycle cover is established through combining and shrinking of cycles. A cycle cover covers all vertices and can be found using a polynomial time. An approximation ration of is achieved by the algorithm used for shrinking of the cycles (Reinelt, 1994).
The cycle shrinking algorithm is given by G (V, A), C: A R+ . This algorithm transforms the graph G to satisfy the function C(uv) ≤ C(uw) + c(wv), for u, v, and w. this is achieved by setting C(uv) as the cost of the shortest route for a given pair u, v ϵ V. this is based on the assumption that G is strongly connected (Johnson et al, 2002).
The figure above shows a cycle shrinking algorithm. Where, three cycles are added, and the vertices (blue and pink) show the proxy nodes. New cycles are found on the proxy nodes.
Theorem 3: the cycle shrinking algorithm is a for ATSP
Let C = {C1, C2, . . . , Ck} be a set of cycle covers, and Ci be the ith cycle cover formulated by the algorithm. The theorem follows by showing that the C(ci) ≤ OPT and K ≤ in the following lemmas. Where, C(ci) is the cost of cycle ci (west, 2001).
Lemma: For each cycle ci, C(ci) ≤ OPT
Letting Vi to be the proxy nodes at a given state I; so that, Vi = V(ci).
If Gi = G (Vi) is the sub-graph generated on Vi. Then, OPT (Vi) ≤ OPT (G) observed when the optimal Hamiltonian tour of G is shortened to pass through Vi. Where, OPT (G) and OPT (Vi) is the optimal cost in Hamiltonian walk on G and Vi respectively (Johnson et al, 2002).
If Wi is the optimal Hamiltonian walk on Vi, Wi is transformed to cycle cover through short cutting. Short cutting on arcs uv and uw by visiting v many times; thus, Wi becomes a cycle cover. Therefore, this reduces the cost of the tour; Thus, C (ci) OPT (Vi). Also, C (ci) C(. Therefore, C(ci) ≤ OPT (west, 2001).
Lemma: The maximum number of cycle covers resulting from the shrinking algorithm is
If K is the cycle covers from shrinking algorithms, then K ≤ (west, 2001).
This is evident in that the shrinking algorithm can eliminate the vertices to at most half of the vertices. Therefore, the number of vertices appearing in the next stage is given by
Combing the proofs of the lemmas it is found that the cycle shrinking algorithm is a for ATSP (Johnson et al, 2002).
Applications of traveling salesman problem
The application of the TSP spans widely in many disciplines such as genetics, engineering, computer science, and electronics. Some of the applications include machine scheduling, frequency assignment, cellular manufacturing, salesman route, etc.
Salesman route
The basic application is to establish the shortest route for a salesman who wishes to visit several cities. The salesman must identify the shortest route so as to reduce the time spent during the journey. The predicament off the salesman is similar to that of a mail deliverer. The delivery has to be made such that the shortest distance is covered when delivering mails to all the cities; thus, reducing the costs of transport.
Machine scheduling problems
In case, there are n jobs (1, 2, 3 n) that are sequentially processed in a machine. Moreover, each of these jobs is to be processed at a fee. The cost of processing the ith job soon after the jth job is Cij. The machine is subjected to its initial conditions after processing all the jobs. The sequencing problem can be modeled and solved, such that the cheapest cost for processing all the jobs is minimized. The problem can be solved by a permutation π {1, 2, 3 . . . n} to minimizes the problem (Gutin & Punnen, 2002).
Cellular manufacturing
Family of cellular products are grouped and processed together in a specialized cell; thus, reducing costs and achieving efficiency. In this process, Robots are used to handle materials in order to improve the efficacy of the cell. The robots activities problem can be formulated in a travelling salesman problem. Let P1, P2 . . . Pn to be the parts to be produced. If part Pi is to be processed in two robots cell M1 and M2 in a sequence, M1 followed by M2. Also, let Di and Dj be the processing time in M1 and M2 respectively. The robot takes time (t) to cover the movement between the input and storage, and L time taken in either loading or unloading. Considering two robots movements with an intersection C1 and C2, the permutation {1, 2, 3 . . . n} gives the sequence in which parts are taken for processing. In the cycle (C1) time, for which the robot takes a part Pπ(i) and places it on M2 and after processing is taken to output storage, after which it takes part Pπ(I +1) (Gutin & Punnen, 2002).
The cycle is + bπ(i) + aπ(i+1).
In the next cycle (C2), the system takes part Pπ(i) loads to M2, takes Pπ(I +1) to M2, and lastly takes part Pπ(i) for output storage. The cycle in this case can be calculated by
+ w1 (i+1) + w2(i) (Gutin & Punnen, 2002). In this case, the w1 (i+1) and w2(i) is the waiting time for M1 and M2 respectively.
The time for processing in cycle C1 and C2 is given by:
= 2 (t+L) + Xi + Yi and
= 2 (t+L) + max { Xi + Yi, 6t +2l}
Where Xi= bi + 2(t +l) and Yi= ai + 2(t +l)
The robot makes a decision to make, if > cylce C1 is selected and vice versa. Considering the cost given by C = (Cij)nxn. The optimal TSP tour is solved (Gutin & Punnen, 2002).
Frequency assignment
The problem of modeling frequency assignment for several transmitters in a communication network are modeled as a TSP. A frequency is assigned to each of the transmitters (from a set of available frequency range) ensuring that they satisfy interference constraints (Arora, 1996).
If we let the constraints be represented by G = (V, E) and an arbitrary transmitter be represented by (i). If a weight Cij is given for each tolerance arc (i, j), and F = {0, 1,2,3,R) to be a set of possible frequencies.
The problem involves assigning a frequency f (i) ϵ F to I ϵV, such that
For cases where R is great, the assignment is feasible.
If is a complete graph from G obtained by adding zero weight edges, and obtained from is such that = +1.
The minimum cost in the Hamiltonian path in is given by (H*); thus, the TSP is applicable in computation of the lower-bound in frequency assignment (Applegate, Robert, Vasek, & Cook, 2006).
Literature review
The problem has caught the attention of researchers for over half a decade with no absolute solution given to the general TSP problem. The problem captures several aspects of real life situation from mail delivery to networking. The problem is a NP complete problem that demonstrates various aspects of combinatorial optimization (Applegate, et al, 2006). Fulkerson, Dantzig, and Johnson demonstrated a method for solving the TSP, and its effectiveness was shown solving TSP problem involving 49 cities (Arora, 1996). However, it was later found that the general TSP could not be subjected to linear programming techniques to solve it in polynomial time. Therefore, attempts to solve the TSP problems brought complexities. Therefore, difficult and solvable cases of the TSP are referred as NP- hard. However, solutions to small sized TPS problems have been developed. The TSP problem under special cases is referred to as NP- hard, while the general case of a TSP problem is regarded as NP complete (Huang, Wunsch, & Levine, 2008).
There are several methods of optimization that have been developed to tackle the TSP problem. These methods include the simulated annealing, artificial neutral networks, and evolutionary computation. Attempts have been made to solve the travelling sales man problem with genetic algorithms (a sub division of evolutionary algorithms), among others. The approach uses genetic crossover and mutations operators to solve the TSP problem (Larranaga, Kuijpers, Murga, Inza, & Dizdarevic, 1999). The genetic algorithms approach the problem from different representations, such as binary, path, adjacency, ordinal, and matrix representations. Binary representations proved successful for small TSP problems. However, large sized TSP problem developed complexities. Larranaga et al (1999) acknowledges that the results for other representations did not yield better results to solve large TSP problems. Sumanta & Diptesh (2008) found that most research has concentrated on small sized TSP problem of about 100 nodes.
Lawler et all (cited in Larranaga 1999) and Kirkpatrick et al (cited in Larranaga 1999) describes various heuristic algorithms for handling the travelling salesman problem. Also, they adopted the simulated annealing method to tackle the problem. Crowder & padberg (cited in Zambito 2006) argues that an exact solution was found for 318 cities. However, the feasible exact solutions found for the TSP problems are restricted to small sized TSP problems.
Conclusion
Practical travelling salesman problems are NP-hard problems. These problems span widely in combinatorial optimization research problems because of the applicability in many real life situations. In this regard, they are used to model cellular manufacturing problems, machine scheduling problems, and in networking problems, among others. Approximation algorithms have been developed to solve the problem. However, there is no feasible exact algorithm for solving the general case of the TSP problem. Although algorithms have been developed for small TSP problem, complexities arise in large TSP problem; thus, restricting the algorithms to lower bounds.
References:
Applegate,D., Robert, E., Vasek, C., & Cook, W. (2006). The travelling salesman problem: A computatioanal study .United Kingdom: Princeton university press.
Arora, S. (1996). Polynomial time approximation schemes for Euclidean travelling salesman and geometric problems. New Jersey: Princeton University.
Gutin, G. & Punnen, A. (2002). The travelling salesman problem and its variations. Netherlands: Kluler publishers.
Huang, D., Wunsch, D., & Levine, D. (2008). Advanced intelligent computing theories and applications: with aspects of artificial intelligence. Germany: Springer.
Johnson, D., Gutin, G., Mcgeoch, L., Yeo, A., Zhang, W., & Zverovich, A. (2002). The travelling salesman problem and its variations. Netherlands: Kluler academic publishers.
Larranaga, P., Kuijpers, C., Murga, R., Inza, I., & Dizdarevic, S., (1999). Genetic algorithms for the travelling salesman problem: review of representations and operators. Netherlands: Kluler publishers.
Reinelt, G. (1994). The travelling saleman: computational solutions for TSP applications. Berlin: Spring verlag.
Sumant, B. & Diptesh, G. (2008). A review of the tbu search literature on the travelling salesman problems. India: Indian institute of research and publications.
West, D. (2001). Introduction to graph theory. New York: Prentice hall.
Zambito, L. (2006). The travelling salesman problem: a comprehensive survey. Retrieved from http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf.
