In this article we explain the formulations, concepts and algorithms to solve this problem called traveling salesman problem. This problems have application in various aspects of Management including Service Operations, Supply Chain Management and Logistics.
The Travelling Salesman Problem (TSP)
This is the most interesting and the most researched problem in the field of Operations Research.
This “easy to state” and “difficult to solve” problem has attracted the attention of both academicians and practitioners who have been attempting to solve and use the results in practice.
image:pixabay
The problem is stated as follows:
A salesman has to visit n cities and return to the starting point. How should he (she) visit the cities such that the total distance travelled is minimum?
It is assumed that the starting city is included in the n cities (or points) to be visited. Since the person comes back to the starting point, any of the n cities can be a starting point. Therefore for a given solution there are n1 other solutions that are same. The starting city is usually not specified at all. Any city can be the starting city. For a n city TSP, the person travels exactly n arcs (or n distances)
There is also a travelling salesman path problem where the start and end points are specified. Here the person travels n1 arcs and reaches the destination.
Usually in the TSP statement there is also a mention that the person visits each city once and only once and returns to the starting point. If the distance matrix is made of Euclidean distances, it satisfies triangle inequality (Given three points i, j, k, dik £ dij + djk), which would force the salesman to visit each city once and only once. If the distances do not satisfy triangle inequality or if we are considering cost or time instead of distances, these may not satisfy triangle inequality and we have to mention explicitly that the person visits each city once and only once.
Mathematical Programming Formulation of the Travelling Salesman Problem
Consider a n city TSP with a known distance matrix D. We consider a 5 city TSP for explaining the formulation, The distance matrix is given in Table
 10 
8 
9 
7 

10 
 
10 
5 
6 
8 
10 
 
8 
9 
9 
5 
8 
 6 

7 
6 
9 
6 
 





Let Xij = 1 if the salesman visits city j immediately after visiting city i. The formulation is
Minimize ∑∑ dij Xij
Subject to
∑ Xij = 1 ∀ i
∑ Xij = 1 ∀ j
Xij = 0, 1
Let us verify whether the formulation is adequate and satisfies all the requirements of a TSP. The objective function minimizes the total distance travelled. The constraints ensure that every city is visited only once. This formulation is clearly inadequate since it is the formulation of the assignment problem. For example a feasible solution to a 5x5 assignment problem can be
X12 = X23 = X31 = X45 = X54 = 1. This is not feasible to the TSP because this says that the person leaves city 1 goes to city 2 from there goes to city 3 and comes back to city 1. He also goes to city 4 (from 5?) and comes back from 5. This is infeasible to the TSP because this contains sub tours. For example
X12 = X23 = X31 = 1 is a subtour of cities 1231. It is also obvious that if there is a sub tour there is always one more in the solution. We have the other subtour given by X45 = X54 = 1 is another X12 = X24 = X45 = X53 = X31 = 1 represents the solution 124531 and is not a sub tour. It represents a full tour and is feasible to The TSP. The formulation should results in solutions not having sub tours. We need to add subtour elimination constraints.
For a 5 city TSP we can have subtours of length 1, 2, 3 or 4. For example, Xjj = 1 is a subtour of length 1. We indirectly eliminate subtours of length 1 by considering djj = ¥ (shown as a – in the distance matrix). Fixing djj = ¥ will not allow Xjj = 1. This will also indirectly not allow a 4 city subtour because if there is a 4 city subtour in a 5 city TSP, there has to be a 1 city sub tour.
A constraint of the form Xij + Xji £ 1 will eliminate all 2city subtours. This has to be added to the formulation. This will also eliminate all 3 city subtours because a 3city subtour should result in a 2city subtour in a 5 city TSP. Therefore addition of the 2city subtour elimination constraint will complete our formulation of the 5 city TSP.
The complete formulation is
Minimize ∑∑dij Xij
Subject to
∑ Xij = 1 ∀ i
∑ Xij = 1 ∀ j
Xij + Xji £ 1 1 ∀ i, j
Xij = 0, 1
If we consider a six city TSP, we have to add 2city subtour elimination constraints and also add a 3city subtour elimination constraint of the form
Xij + Xjk + X ki £ 1 1 ∀ i, j, k.
This increases the number of constraints significantly.
In general for a n city TSP, where n is odd we have to add subtour elimination constraints for eliminating subtours of length 2 to n1 and when n is even, we have to add subtour elimination constraints for eliminating subtours of length 2 to n.
For n =6, the number of 2city sub tour elimination constraints is ^{6}C2 = 15 and the number of 3city subtours is ^{6}C3 = 20.
Heuristic Algorithms for the TSP
We have seen that the TSP is an NP complete problem and that branch and bound algorithms (worst case enumerative algorithm) can be used to solve them optimally. We do not have polynomially bounded algorithms to get the optimal solutions. The branch and bound algorithms can solve the problem optimally up to a certain size. For large sized problems, we have to develop approximate algorithms or heuristic algorithms. In this section, we explain a few heuristic algorithms for the TSP.
Nearest Neighbourhood algorithm
In this algorithm, we start from a city and proceed towards the nearest city from there. If we start from city 1, we can go to the nearest city, which is city 5. From 5 we can reach city 2 (there is a tie between 2 and 4) and from 2 we can reach 4 from which we reach city 3. The solution is 152431 with Z = 34.
Starting from city 2 and moving to the nearest neighbour, we get the solution 245132 with Z = 36.
Starting with city 3, the solution is 315243 with Z = 34
Starting with city 4, the solution is 425134 with Z = 34
Starting with city 5, the solution is 524315 with Z = 34
The best solution is 152431 with Z = 34. This also happens to be the optimal solution.
The nearest neighborhood search heuristic is a “greedy” search heuristic where the last city to be added to the list is not optimized. Therefore this can give poor results. The worst case performance bound for the nearest neighborhood search is given by
Lh/Lo £ 1 + (log10 n)/2
This shows that in the worst case, the heuristic will be away from the optimum by a factor of 1 + log10 n. For a 100 city problem, the worst case bound is 2 indicating that the heuristic can be twice the optimum in the worst case.
Pairwise interchange heuristic
We start with a feasible solution and try to improve it by exchanging the cities pairwise. In an n city problem ^{n}C2 interchanges are possible and the best is chosen.
We can start with any sequence, say 12 345 1 with Z = 41. The sequence is represented by 1 2345 indicating that we will come back to the first from the last city. Interchanging positions 1 and 2 we get the sequence 21345 with Z = 38. This is better and we accept this solution.
We start the algorithm all over again with the starting solution 21345 with Z = 38. On interchanging 2 and 5 we get 51342 with Z = 34. Further exchanges do not improve the
Solution and the best solution after evaluating ^{n}C2 interchanges is 513425 with Z = 34.
The pair wise interchange heuristic evaluates ^{n}C2 interchanges and can take a considerable amount of CPU time. Sometimes we use an adjacent pairwise interchange where we exchange (n1) sequences, take the best and proceed till no more improvement is possible.
The article has been authored by Sumit Prakash, IIM Lucknow
Reference
i)Operation Research 9e By Hiller
ii)Lecture Notes
iii)Service Management by james fitzsimmons
Related Business Content
All Sections on MBASkool