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.
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.
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 1030 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.
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.
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 applets on this website appear at the bottom of each heuristic description page. For each applet,
simply enter the number of cities desired for the animation (a whole number between 4 and 100),
in the Total Cities field, and the animation will then begin.
The speed of the animation can be adjusted by dragging the slider meter at the bottom.
For any comments regarding these pages, please contact the author via e-mail.
to Top Next