Search:
 

 
Examples:
 

 

Example - Travelling Salesman Problem (T.S.P.)

* The "\" symbol has been used at the end of lines to indicate that the line was too long for the display and has been
wrapped to the line below in order to fit within the width of the web page. These lines would need to be joined in the normal
program editor.

I. Introduction

This program illustrates a classic problem: a salesman (or woman!) must visit a certain number of towns, each once and only once, but in the shortest distance possible to avoid wasting fuel etc.

As an example, there are data in the program relating to 50 UK towns and cities, of which, each time the program is run, the computer randomly selects 10 (so we do not have to solve the same problem each time).

II. Mathematics Involved

Insertion Algorithm

It must be stressed that this algorithm does not necessarily come up with the best route possible; rather it comes up with a reasonably good one.

  1. Start with the first three towns on the list. Because of symmetry (l(ABC) = l(BCA) = l(CAB) = l(CBA) = l(BAC) = l(ACB), where l(ABC) is the length of the itinerary passing through towns A , B and C in that order) there is only one possible route for three towns, so it is bound to be the best.
  2. Generate the insertion costs for the next town on the list in various points in the itinerary. The insertion cost of putting town C in between town A and town B in the itinerary is given by d(A,C)+d(C,B)-d(A,B).
  3. Insert this town in the position where the insertion cost is smallest.

Repeat 2. and 3. until all 10 towns are in the itinerary.

( d(A,B) is the distance from A to B . This program uses the distance by road between the towns rather than the straight-line distance. Hence if you travel from Aberystwyth to Exeter you have to go past Bristol (although not necessarily through it).)

III. How the Program Works

1) Initialisation

The data are of the form commonly found on the back of road atlases, and are in a triangular shape. All the 1225 (=50*49/2) distances (along with the town's latitude and longitude for placing them on the map) are given at the beginning of the program. The relevant data (those for the 10 towns chosen) are stored in a distance matrix for ease of use.

After the random selection of the towns, the other half of the distance matrix needs to be filled in. As distances are symmetric: the distance from A to B is the same as the distance from B to A. We can therefore generate the complete matrix simply by adding the existing matrix and its transpose:

REM complete the gaps in the matrix REM by symmetry DIM TempMat AS Matrix TempMat . Copy ( distancemat ) TempMat . Transpose () distancemat . Add ( TempMat )

2) The haveago() Procedure

Now that the distances have been calculated, the user is invited to choose an order for the tour of towns, by clicking on the points or labels representing each. At each stage the cumulative distance is displayed on the taskbar. The final distance is displayed in a message box, and the user is asked whether to let the computer try to better the distance. 

   DIM totdist$,miles$,shallI$,sofar$,proceed$

   totdist$ = "Total distance for your route: "
   miles$ = " miles"
   shallI$ = "Shall I have a go?"
   sofar$ = "Distance so far = "
   proceed$ = "Click OK to proceed"

   WHILE linesdrawn%% < 9
     TSP.tag = ""
     WHILE TSP.tag = ""
       process()
     WEND 
     
     proposedtown%% = VAL (TSP.tag)
     flag% = 0
     FOR i%% = 1 TO linesdrawn%% + 1
       IF proposedtown%% = townlist%%(i%%) THEN 
         flag% = flag% + 1
       END IF 
     NEXT i%%
     IF flag% = 0 THEN 
       CALL linedraw (currenttown%%,proposedtown%%)
       TSP.refresh()
       cumdist% = cumdist% + distancemat.elements(currenttown%%,\
       proposedtown%%)
       Superbase.StatusText = sofar$ + STR$ (cumdist%,"99999") + miles$
       currenttown%% = proposedtown%%
       townlist%%(linesdrawn%% + 2) = currenttown%%
       linesdrawn%% = linesdrawn%% + 1
     END IF 
   WEND 
   CALL linedraw(currenttown%%,townlist%%(1))
   TSP.refresh()
   yourdist% = cumdist% + distancemat.elements(currenttown%%,townlist%%(1))
   Superbase.StatusText = proceed$
   REQUEST totdist$ + STR$ (yourdist%,"99999") + miles$,shallI$,1,decide%

3) The insert() Procedure

If desired, the computer then attempts to generate a better route by using the insertion algorithm. The ‘computer' distance is calculated using the Summation() method. 

SUB computer()
   DIM i%%,j%%,compdistance%
   DIM formula$,ican$,knowhow$
   ' computer tries using insertion algorithm nb not necessarily optimal
   'there are r different places to insert - the index refers to the city
   'immediately before the inserted one.
   
   FOR i%% = 1 TO 3
     stage%%(i%%) = i%%
   NEXT i%%
   FOR j%% = 3 TO 9
     CALL insert(j%%)
   NEXT j%%

   ican$ = "I can do it in "
   knowhow$ = "Do you want to know how I did it?"

   formula$ = "distancemat.elements(stage%%(i%%),stage%%(i%%+1))"
   compdistance% = Summation(formula$,"i%%",1,9) + distancemat.elements\
   (stage%%(10),stage%%(1))
   IF compdistance% < yourdist% THEN 
     REQUEST ican$ + STR$ (compdistance%,"9999") + " miles!",knowhow$,1\
     ,decide%
     IF decide% = 1 THEN 
       
       REM draw computer-generated route
       linecol%% = 4
       taga$ = "b"
       FOR i%% = 1 TO 9
         CALL linedraw(stage%%(i%%),stage%%(i%% + 1))
       NEXT i%%
       CALL linedraw(stage%%(10),stage%%(1))
       TSP.refresh()
     END IF 
   ELSE 
     IF compdistance% > yourdist% THEN REQUEST "OK, you win!","",0
     IF compdistance% = yourdist% THEN REQUEST "That's the best I can do\
     too!","",0
   END IF 
 END SUB

The computer's route can then be displayed if it is any better.