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 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.

Applets

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.

Comments?

For any comments regarding these pages, please contact the author via e-mail.

Previous Back to Top Next