The Travelling Salesman Problem: An Introduction

What is the Travelling Salesman Problem?

The idea behind the Travelling Salesman Problem (TSP) is as follows: A salesman has a given tour of a specified number of cities. Starting from any one of these cities, he must make a tour, visiting each of the other cities on the tour only once, with his final destination being his city of departure. This task should be achieved in such a way as to minimise the total distance travelled on the tour.

Everyday Usage

Of course the Problem's most obvious application in everyday life is for that of our travelling salesman, who seeks the best route around a number of places where he has appointments. By finding an efficient route, in theory, he saves time and lowers the costs of his journey. Other everyday applications of this problem is in electrics, where an electrician might need to consider the best way of wiring a large house, or where producers of circuit boards need to work out the most efficient circuiting arrangements on the board.

Symmetrical and Non-symmetrical tours

Tours can be symmetrical or non-symmetrical. A symmetrical tour considers that the distance from city 'a' to city 'b' is the same as that from 'b' to 'a'. A non-symmetrical tour considers that these distances are not the same (think of one-way systems which mean that going from town 'a' to town 'b' is not the exact opposite of going from 'b' to 'a'). For this project, we will consider that the tours are symmetrical - going from Liverpool to Manchester to Glasgow to Liverpool is considered the same as going from Liverpool to Glasgow to Manchester to Liverpool. The shape of these to two tours are basically the same.

Exact Methods

The formula to calculate the number of distinct tour paths for n cities is (n-1)!/2. A four city tour has six possible routes (3 x 2 x 1)/2=3, whilst a five city tour has 12 possible distinct tours (4 x 3 x 2 x 1)/2=12. A problem whose possibilities increase at such a rate rapidly becomes complex. As it would require 60 distinct drawings to represent a six city problem, humans are understandably turning toward the superior calculating speed of the computer to help with the problem. The optimum tour can be found by calculating the total length of each possible route around the cities and choosing the shortest of those. But even the computer begins to struggle at a relatively low number to consider all possible solutions. Finding the optimal route for a thirty city tour would require the calculation of distance of 4.42 x 10³⁰ different possible tours.

Tour Construction Heuristics

The difficulties associated with finding an optimal tour force us to find alternatives. A heuristic is a 'rule-of-thumb', applying a general idea to a specific problem. Although this is unlikely to provide us with the optimal solution, it tends to provide a near-optimal solution and is constructed far more quickly. The heuristics dealt with in this project are: 

Nearest Neighbour - Keep finding the nearest unvisited city to the present city, until all the cities have been visited. 
 The Nearest Neighbour Algorithm works as follows:

1. Choose any city as a starting point. Call this city 'a'.
2. Visit the nearest city to city 'a', which we shall call city 'b'. City 'b' becomes the 'current city'.
3. Visit the nearest city to city 'b' which has not yet been visited - city 'c'. City 'c' is now the 'current city'.
4. As per point 3, repeatedly visit the nearest unvisited city to the current city until all cities have been visited once.
5. Once all cities have been visited once, return from the last city to have been visited to the starting city - city 'a'.

Choose your starting city (shown in green). This will also be the final destination.	Find the closest city to your starting city (red).
Draw a line between the two. Now locate the nearest unvisited city to the newly incorporated city of the previous step.	Once again,draw a line between the two, then locate the nearest unvisited city to the newly incorporated city of the previous step.
Repeat Step 3/4...	...until only one city remains unvisited...
...and once this is incorporated...	..the only option is to return to the starting city.

Multi-Fragment - Keep adjoining the cities closest together, where neither are already connected to 2 other cities and where adjoining them will not result in a closed mini-tour. Repeat until all cities are directly connected to two other cities. 
 The Multi-Fragment Algorithm works as follows:

1. Consider a distance matrix (such as the type at the back of a road atlas of Britain), containing all the distances between all cities on the tour.
2. Find the shortest distance and link these two cities together.
3. Then, find the second shortest distance, and link these two cities.
4. Now, find the next smallest edge whose cities conform to the following criteria:
a) Both must have an edge degree ratio <=1 (i.e. neither can already be linked to more than one other city)
b) Adding an edge between the cities must not result in a closed tour, which does not already include all the cities on the tour.
5. Repeat until all cities end up being connected to two other cities.

Identify the two closest cities (shown in red).	Join the closest cities together. They now have one edge each (signified by grey colouring). Now find the next two closest cities (red).
Join them together. Now find the two closest cities, where joining them will not result in a closed tour, and where each has an edge degree of either one (denoted by grey shading) or zero (transparent circles).	If a city has an edge degree of two (shown in black), it cannot be connected to any further cities. Repeat the previous step...
...until there only remain two cities with an edge degree less than two...	...and these are joined to complete the tour...

Farthest Insertion - After joining the two farthest cities, to make a mini-tour, keep adding the farthest unvisited city from the tour, to make a new mini-tour. Repeat until all cities have been visited. There is also a guide to the Nearest Insertion algorithm, which works in the opposite fashion, adjoining the two closest cities, and repeatedly adding the nearest to the tour. 
 The Farthest Insertion Algorithm works as follows:

1. Find the two cities farthest apart. Let's call them city 'a' and city 'b'. Join them together.
2. City 'c' is the farthest city from the edge between city 'a' and city 'b'. This is incorporated into the tour by creating an edge between city 'c' and each of cities 'a' and 'b', thus creating a triangular mini-tour.
3. The remaining cities are incorporated as follows:
a) Find the farthest city yet to be incorporated, from any point on the mini-tour (city 'd').
b) Note the edge to which this city is closest.
c) Erase this edge, and create two new edges, between city 'd' each of the cities at the ends of the erased closest edge.

Identify the two farthest cities.	Join them together to form a mini-tour, then find the farthest city from any point of this mini-tour.
Incorporate this city by drawing a line between it and each of the two cities already on the mini-tour to form a new, three city mini-tour. Now find the farthest city from the new mini-tour. Identify the edge on the mini-tour to which the city is closest (shown in green).	Incorporate this city by erasing the closest edge to the city, and creating new edges between each of the cities at the ends of the former closest line, and the nearest city. Once again find the farthest city from this new mini-tour
Repeat the previous step...	...throughout the tour...
...until there remains only one city to be incorporated, and the only option...	...is to incorporate it to complete the tour.