The Travelling Salesman Problem-Formulation & Concepts

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 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 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 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 ⁶C2 = 15 and the number of 3-city subtours is ⁶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 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.

Pairwise interchange heuristic

We start with a feasible solution and try to improve it by exchanging the cities pairwise. In an n city problem ⁿC2 interchanges are possible and the best is chosen.

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 ⁿC2 interchanges is 5-1-3-4-2-5 with Z = 34.

The pair wise interchange heuristic evaluates ⁿC2 interchanges and can take a considerable amount of CPU time. Sometimes we use an adjacent pairwise interchange where we exchange (n-1) 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