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.
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. The problem is stated as follows:
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 n-1 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 n-1 arcs and reaches the destination. Usually in the TSP statement there is also a mention that the person visits each city
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
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 1-2-3-1. 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 1-2-4-5-3-1 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 2-city subtours. This has to be added to the formulation. This will also eliminate all 3 city subtours because a 3-city subtour should result in a 2-city subtour in a 5 city TSP. Therefore addition of the 2-city 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 2-city subtour elimination constraints and also add a 3-city 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 n-1 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 2-city sub tour elimination constraints is
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.
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 1-5-2-4-3-1 with Z = 34. Starting from city 2 and moving to the nearest neighbour, we get the solution 2-4-5-1-3-2 with Z = 36. Starting with city 3, the solution is 3-1-5-2-4-3 with Z = 34 Starting with city 4, the solution is 4-2-5-1-3-4 with Z = 34 Starting with city 5, the solution is 5-2-4-3-1-5 with Z = 34 The best solution is 1-5-2-4-3-1 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.
We start with a feasible solution and try to improve it by exchanging the cities pairwise. In an n city problem We can start with any sequence, say 1-2 -3-4-5 -1 with Z = 41. The sequence is represented by 1 -2-3-4-5 indicating that we will come back to the first from the last city. Interchanging positions 1 and 2 we get the sequence 2-1-3-4-5 with Z = 38. This is better and we accept this solution. We start the algorithm all over again with the starting solution 2-1-3-4-5 with Z = 38. On interchanging 2 and 5 we get 5-1-3-4-2 with Z = 34. Further exchanges do not improve the Solution and the best solution after evaluating The pair wise interchange heuristic evaluates
i)Operation Research 9e By Hiller ii)Lecture Notes iii)Service Management by james fitzsimmons |