Introduction to Evolutionary Algorithms

4. The Travelling Salesman Problem

4.1. The TSP

The travelling salesman problem (TSP) is a simple optimisation problem which is easy to solve using Evolutionary Algorithms. It's also fun to write code to solve the TSP, because it's easy to visualise and display - a simple way to get impressive results!

The TSP is basically this: A travelling salesman must visit a number of cities, distributed around a two dimensional map. He must do this in such a way that he travels the smallest possible distance, thus spending less time on the road and less money on petrol. We make the assumption that roads between cities are straight and that there aren't any problems with traffic (perhaps we could add the M25 to the problem later...).

Figures 5 and 6 show a typical set of cities. Figure 5 has an inefficient route while the route in figure 6 is optimum.

fig. 5: The Travelling Salesman Problem - inefficient route

fig. 6: The Travelling Salesman Problem - optimum route

So, when we attempt to solve the TSP we are aiming to find the best order in which to visit the cities. The best order is, in this case, the one which has the shortest distance.

The reason that the TSP is of such interest to those who study AI is that it has a feature called combinatorial explosion. This means that increasing the size of the problem space (adding a city) causes a drastic increase in the number of possible solutions. A TSP with n cities will have n! (n factorial) solutions. To illustrate this, here are the numbers of possible solutions for some problem sizes...

  1   =>  1
  2   =>  2
  3   =>  6
  4   =>  24
  ...
  10  =>  3,628,800
  ...
  20  =>  2,432,902,008,176,640,000
  ...
  500 =>  1.2201368259111 x 10^1134

4.2. TSP Implementation

In order to simulate the TSP in Delphi I created the class shown in Listing 1.

TTSPDisplay = class(TImage)
  private
    {  The array of 'cities' }
    FCities : array of TPoint;
    {  The number of 'cities' }
    FCityCount: Integer;
    {  Clear the map }
    procedure Clear;
    {  Show the cities }
    procedure DrawCities;
    {  Display a route  }
    procedure DrawRoute(Individual : TTSPIndividual);
    {  Getters... }
    function GetCity(I: Integer): TPoint;
    {  Setters... }
    procedure SetCityCount(const Value: Integer);
  public
    {  The constructor }
    constructor Create(Owner : TComponent); override;
    {  The destructor }
    destructor Destroy; override;
    {  Get the distance between two cities }
    function DistanceBetween(C1, C2 : Integer) : Double;
    {  Call this to draw the map }
    procedure DrawMap;
    {  Draw the map with a route  }
    procedure DrawMapWithRoute(Individual : TTSPIndividual);
    {  Places the cities at random points }
    procedure RandomCities;
    {  Access to the cities array }
    property Cities[I : Integer] : TPoint read GetCity;
  published
    {  Properties... }
    property CityCount : Integer read FCityCount write SetCityCount;
  end;

The TTSPDisplay class essentially maintains a list of cities. The class manages the creation and display of cities at random points on a map. Methods exist to calculate the distance between cities and to display routes between them. These are covered in more detail later. The TTSPDisplay class was used to create the images in figures 5 and 6.

	Back
	Contents
	Next