Travelling Salesman Problem

This code requires the Simulated Annealing package.

% Finds a route through all of the 25 towns in the table below.
% The optimal path has a length equal to 1989.
alltowns:-
  Towns=[aberdeen, aberystwyth, brighton, birmingham, bristol, cambridge,
         cardiff, carlisle, dover, edinburgh, exeter, glasgow, hull, leeds,
         liverpool, manchester, newcastle, nottingham, oxford, penzance,
         portsmouth, sheffield, swansea, york, london],
  towns(Towns).

% e.g. towns([leeds,dover,aberystwyth,london,cardiff,hull]).
towns(Towns):-
  retractall(town(_, _)),
  retractall(e(_, _, _)),
  towns_integers(Towns, 1),
  forall((member(Town1, Towns), member(Town2, Towns), d(Town1, Town2, D)), 
         (town(Town1, I), town(Town2, J), assert(e(I, J, D)))),
  length(Towns, NumberOfTowns),
  retractall(size(_)),
  asserta(size(NumberOfTowns)),
  anneal.

% e.g. towns_integers([leeds,bristol,york,london,hull], 1). 
towns_integers([], _).
towns_integers([Town|Towns], I):-
  assert(town(Town, I)),
  I1 is I + 1,
  towns_integers(Towns, I1).

% Towns are not ordered in e/3
dist(X, Y, D):-e(X, Y, D), !.
dist(X, Y, D):-e(Y, X, D), !.

% Called from anneal.pl
perturb(Xs, As):-
  rand_int(0, 3, R),
  /* Do a "reverse" three times more often than a "move" */
  R = 0, !,
  /* MOVE:                                                                 */
  /* The list As is the same as the list Xs except that two pseudo-        */
  /*   randomly chosen adjacent sublists are swapped.                      */
  /* N.B. L+M=Size rotates the whole list, which, for TSP, is redundant.   */
  /*      Choose random X in 1..Size-1, random K in 0..X-1 and random Y in */
  /*      X+1..Size.  Then L=X-K and M=Y-X.                                */
  /*      L is the length of the first sublist and K is its offset         */
  /*      (base-0) from the start of the list.  M is the length of the     */
  /*      second sublist, and it immediately follows the first sublist.    */
  size(Size),
  Size1 is Size - 1,
  rand_int(1, Size1, X),
  X1 is X - 1,
  rand_int(0, X1, K),
  X2 is X + 1,
  rand_int(X2, Size, Y),
  L is X - K,
  M is Y - X,
  split([K,L,M], Xs,[], [As,Cs, Bs,Ds, Cs,Bs, Ds,[]]).
perturb(Xs, As):-
  /* REVERSE:                                                              */
  /* The list As is the same as the list Xs except that a pseudo-randomly  */
  /*   chosen sublist is reversed.                                         */
  /* N.B. Avoid L=0 and L=1, which would reverse nothing.                  */
  /*      K=0, L=Size reverses the whole list, which, for TSP, is          */
  /*      redundant.                                                       */
  /*      Choose random K,X in 0..Size such that K < X-1. Then L=X-K.      */
  /*      L is the length of the sublist to reverse and K is its offset    */
  /*      (base-0) from the start of the list.                             */
  size(Size),
  repeat,
    rand_int(0, Size, K),
    rand_int(0, Size, X),
  K < X - 1, !,
  L is X - K,
  split([K,L], Xs,[], [As,Bs, Es,_, Cs,[]]),
  rev(L, Es, Bs,Cs).

/* rand_int(I, J, K) is true if K is a pseudo-random integer in the range  */
/*   I..J.                                                                 */
rand_int(I, J, K):-K is int(rand(J - I + 1)) + I.

/* rev(N, Xs, Ys,Zs) is true if the difference list Ys,Zs is the result of */
/*   reversing the first N elements of the list Xs.                        */
/* e.g. rev(3, [1,2,3,4,5], [3,2,1,5,6], [5,6]).                           */
rev(0, _, Ys,Ys):-!.
rev(N, [X|Xs], YsZs,Zs):-
  N1 is N - 1,
  rev(N1, Xs, YsZs,[X|Zs]).

/* split(Ns, Xs,Ys, Zss) splits the difference list Xs,Ys into a list of   */
/*   difference lists Zss according to the lengths given in Ns.            */
/* e.g. split([2,2,1], [1,2,3,4,5,6,7],[], [[1,2,3,4,5,6,7],[3,4,5,6,7],   */
/*                                          [3,4,5,6,7],[5,6,7],           */
/*                                          [5,6,7],[6,7],                 */
/*                                          [6,7],[]]).                    */
split([], Xs,As, [Xs,As]).
split([N|Ns], Xs,As, [Ys,Bs|Yss]):-
  split_1(N, Xs,As, Ys,Bs, Zs,Cs),
  split(Ns, Zs,Cs, Yss).

% e.g. split_1(2, [1,2,3,4,5],[], [1,2,3,4,5],[3,4,5], [3,4,5],[]).
split_1(0, Xs,As, Ys,Ys, Xs,As):-!.
split_1(N, [X|Xs],As, [X|Ys],Bs, Zs,Cs):-
  N1 is N - 1,
  split_1(N1, Xs,As, Ys,Bs, Zs,Cs).

% Called from anneal.pl
energy(List, Energy):-distance(List, Energy).
 
/* distance(Towns, Length) is true if Length is the length, as defined by  */
/*   dist/3, of the route going through all the Towns (including returning */
/*   to the first town from the last town).                                */
distance([Start|Towns], Length):-  
  distance_1(Towns, Start, Start, 0, Length).

distance_1([], End, Start, Length0, Length):-
  dist(End, Start, Length1),
  Length is Length0 + Length1.
distance_1([Town|Towns], Town0, Start, Length0, Length):-
  dist(Town0, Town, Length1),
  Length2 is Length0 + Length1,
  distance_1(Towns, Town, Start, Length2, Length).

% Called from anneal.pl
output(_, Xs, Energy):-
  integers_towns(Xs, Path),
  write(`Path: `), write(Path), nl,
  write(`Length: `), write(Energy), nl.

% e.g. integers_towns([3,1,5,2,4], Towns).
integers_towns([], []).
integers_towns([I|Is], [Town|Towns]):-
  town(Town, I), !,
  integers_towns(Is, Towns).

/* length(Xs, L) is true if L is the number of elements in the list Xs.    */
% length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of      */
/*   elements in the list Xs.                                              */
% length_1([], L, L).
% length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).
  
% This is the data from LPA Win-Prolog Examples\Salesman.pl
d( aberdeen,    aberystwyth, 427 ).
d( aberdeen,    birmingham,  403 ).
d( aberdeen,    brighton,    547 ).
d( aberdeen,    bristol,     480 ).
d( aberdeen,    cambridge,   443 ).
d( aberdeen,    cardiff,     484 ).
d( aberdeen,    carlisle,    206 ).
d( aberdeen,    dover,       573 ).
d( aberdeen,    edinburgh,   115 ).
d( aberdeen,    exeter,      555 ).
d( aberdeen,    glasgow,     142 ).
d( aberdeen,    hull,        336 ).
d( aberdeen,    leeds,       306 ).
d( aberdeen,    liverpool,   327 ).
d( aberdeen,    manchester,  326 ).
d( aberdeen,    newcastle,   221 ).
d( aberdeen,    nottingham,  370 ).
d( aberdeen,    oxford,      464 ).
d( aberdeen,    penzance,    663 ).
d( aberdeen,    portsmouth,  550 ).
d( aberdeen,    sheffield,   338 ).
d( aberdeen,    swansea,     502 ).
d( aberdeen,    york,        299 ).
d( aberdeen,    london,      488 ).
d( aberystwyth, birmingham,  114 ).
d( aberystwyth, brighton,    249 ).
d( aberystwyth, bristol,     121 ).
d( aberystwyth, cambridge,   211 ).
d( aberystwyth, cardiff,     108 ).
d( aberystwyth, carlisle,    219 ).
d( aberystwyth, dover,       284 ).
d( aberystwyth, edinburgh,   312 ).
d( aberystwyth, exeter,      196 ).
d( aberystwyth, glasgow,     313 ).
d( aberystwyth, hull,        216 ).
d( aberystwyth, leeds,       166 ).
d( aberystwyth, liverpool,   100 ).
d( aberystwyth, manchester,  126 ).
d( aberystwyth, newcastle,   254 ).
d( aberystwyth, nottingham,  154 ).
d( aberystwyth, oxford,      156 ).
d( aberystwyth, penzance,    304 ).
d( aberystwyth, portsmouth,  218 ).
d( aberystwyth, sheffield,   154 ).
d( aberystwyth, swansea,      75 ).
d( aberystwyth, york,        190 ).
d( aberystwyth, london,      212 ).
d( birmingham,  brighton,    159 ).
d( birmingham,  bristol,      86 ).
d( birmingham,  cambridge,    97 ).
d( birmingham,  cardiff,     100 ).
d( birmingham,  carlisle,    198 ).
d( birmingham,  dover,       181 ).
d( birmingham,  edinburgh,   291 ).
d( birmingham,  exeter,      162 ).
d( birmingham,  glasgow,     292 ).
d( birmingham,  hull,        122 ).
d( birmingham,  leeds,       109 ).
d( birmingham,  liverpool,    99 ).
d( birmingham,  manchester,   80 ).
d( birmingham,  newcastle,   198 ).
d( birmingham,  nottingham,   48 ).
d( birmingham,  oxford,       63 ).
d( birmingham,  penzance,    271 ).
d( birmingham,  portsmouth,  141 ).
d( birmingham,  sheffield,    75 ).
d( birmingham,  swansea,     125 ).
d( birmingham,  york,        125 ).
d( birmingham,  london,      110 ).
d( brighton,    bristol,     136 ).
d( brighton,    cambridge,   106 ).
d( brighton,    cardiff,     183 ).
d( brighton,    carlisle,    354 ).
d( brighton,    dover,        81 ).
d( brighton,    edinburgh,   432 ).
d( brighton,    exeter,      165 ).
d( brighton,    glasgow,     448 ).
d( brighton,    hull,        224 ).
d( brighton,    leeds,       250 ).
d( brighton,    liverpool,   250 ).
d( brighton,    manchester,  240 ).
d( brighton,    newcastle,   328 ).
d( brighton,    nottingham,  178 ).
d( brighton,    oxford,       96 ).
d( brighton,    penzance,    277 ).
d( brighton,    portsmouth,   49 ).
d( brighton,    sheffield,   216 ).
d( brighton,    swansea,     236 ).
d( brighton,    york,        250 ).
d( brighton,    london,       52 ).
d( bristol,     cambridge,   151 ).
d( bristol,     cardiff,      44 ).
d( bristol,     carlisle,    276 ).
d( bristol,     dover,       187 ).
d( bristol,     edinburgh,   369 ).
d( bristol,     exeter,       76 ).
d( bristol,     glasgow,     370 ).
d( bristol,     hull,        206 ).
d( bristol,     leeds,       195 ).
d( bristol,     liverpool,   163 ).
d( bristol,     manchester,  161 ).
d( bristol,     newcastle,   284 ).
d( bristol,     nottingham,  141 ).
d( bristol,     oxford,       71 ).
d( bristol,     penzance,    184 ).
d( bristol,     portsmouth,   97 ).
d( bristol,     sheffield,   161 ).
d( bristol,     swansea,      89 ).
d( bristol,     york,        211 ).
d( bristol,     london,      116 ).
d( cambridge,   cardiff,     177 ).
d( cambridge,   carlisle,    260 ).
d( cambridge,   dover,       125 ).
d( cambridge,   edinburgh,   330 ).
d( cambridge,   exeter,      216 ).
d( cambridge,   glasgow,     354 ).
d( cambridge,   hull,        124 ).
d( cambridge,   leeds,       143 ).
d( cambridge,   liverpool,   185 ).
d( cambridge,   manchester,  159 ).
d( cambridge,   newcastle,   226 ).
d( cambridge,   nottingham,   82 ).
d( cambridge,   oxford,       80 ).
d( cambridge,   penzance,    329 ).
d( cambridge,   portsmouth,  126 ).
d( cambridge,   sheffield,   116 ).
d( cambridge,   swansea,     216 ).
d( cambridge,   york,        149 ).
d( cambridge,   london,       54 ).
d( cardiff,     carlisle,    277 ).
d( cardiff,     dover,       232 ).
d( cardiff,     edinburgh,   370 ).
d( cardiff,     exeter,      119 ).
d( cardiff,     glasgow,     371 ).
d( cardiff,     hull,        227 ).
d( cardiff,     leeds,       209 ).
d( cardiff,     liverpool,   164 ).
d( cardiff,     manchester,  176 ).
d( cardiff,     newcastle,   298 ).
d( cardiff,     nottingham,  162 ).
d( cardiff,     oxford,      106 ).
d( cardiff,     penzance,    227 ).
d( cardiff,     portsmouth,  141 ).
d( cardiff,     sheffield,   175 ).
d( cardiff,     swansea,      45 ).
d( cardiff,     york,        232 ).
d( cardiff,     london,      161 ).
d( carlisle,    dover,       373 ).
d( carlisle,    edinburgh,    93 ).
d( carlisle,    exeter,      352 ).
d( carlisle,    glasgow,      94 ).
d( carlisle,    hull,        149 ).
d( carlisle,    leeds,       117 ).
d( carlisle,    liverpool,   118 ).
d( carlisle,    manchester,  120 ).
d( carlisle,    newcastle,    58 ).
d( carlisle,    nottingham,  187 ).
d( carlisle,    oxford,      260 ).
d( carlisle,    penzance,    455 ).
d( carlisle,    portsmouth,  338 ).
d( carlisle,    sheffield,   148 ).
d( carlisle,    swansea,     284 ).
d( carlisle,    york,        112 ).
d( carlisle,    london,      302 ).
d( dover,       edinburgh,   451 ).
d( dover,       exeter,      246 ).
d( dover,       glasgow,     467 ).
d( dover,       hull,        243 ).
d( dover,       leeds,       269 ).
d( dover,       liverpool,   269 ).
d( dover,       manchester,  260 ).
d( dover,       newcastle,   347 ).
d( dover,       nottingham,  197 ).
d( dover,       oxford,      128 ).
d( dover,       penzance,    355 ).
d( dover,       portsmouth,  130 ).
d( dover,       sheffield,   235 ).
d( dover,       swansea,     271 ).
d( dover,       york,        269 ).
d( dover,       london,       71 ).
d( edinburgh,   exeter,      445 ).
d( edinburgh,   glasgow,      44 ).
d( edinburgh,   hull,        221 ).
d( edinburgh,   leeds,       195 ).
d( edinburgh,   liverpool,   211 ).
d( edinburgh,   manchester,  213 ).
d( edinburgh,   newcastle,   104 ).
d( edinburgh,   nottingham,  258 ).
d( edinburgh,   oxford,      357 ).
d( edinburgh,   penzance,    548 ).
d( edinburgh,   portsmouth,  435 ).
d( edinburgh,   sheffield,   229 ).
d( edinburgh,   swansea,     377 ).
d( edinburgh,   york,        184 ).
d( edinburgh,   london,      380 ).
d( exeter,      glasgow,     446 ).
d( exeter,      hull,        282 ).
d( exeter,      leeds,       271 ).
d( exeter,      liverpool,   239 ).
d( exeter,      manchester,  237 ).
d( exeter,      newcastle,   360 ).
d( exeter,      nottingham,  217 ).
d( exeter,      oxford,      136 ).
d( exeter,      penzance,    112 ).
d( exeter,      portsmouth,  126 ).
d( exeter,      sheffield,   237 ).
d( exeter,      swansea,     165 ).
d( exeter,      york,        287 ).
d( exeter,      london,      172 ).
d( glasgow,     hull,        243 ).
d( glasgow,     leeds,       211 ).
d( glasgow,     liverpool,   212 ).
d( glasgow,     manchester,  214 ).
d( glasgow,     newcastle,   148 ).
d( glasgow,     nottingham,  281 ).
d( glasgow,     oxford,      355 ).
d( glasgow,     penzance,    549 ).
d( glasgow,     portsmouth,  433 ).
d( glasgow,     sheffield,   242 ).
d( glasgow,     swansea,     378 ).
d( glasgow,     york,        206 ).
d( glasgow,     london,      396 ).
d( hull,        leeds,        58 ).
d( hull,        liverpool,   122 ).
d( hull,        manchester,   90 ).
d( hull,        newcastle,   117 ).
d( hull,        nottingham,   90 ).
d( hull,        oxford,      164 ).
d( hull,        penzance,    396 ).
d( hull,        portsmouth,  242 ).
d( hull,        sheffield,    65 ).
d( hull,        swansea,     266 ).
d( hull,        york,         37 ).
d( hull,        london,      172 ).
d( leeds,       liverpool,    73 ).
d( leeds,       manchester,   41 ).
d( leeds,       newcastle,    89 ).
d( leeds,       nottingham,   72 ).
d( leeds,       oxford,      170 ).
d( leeds,       penzance,    378 ).
d( leeds,       portsmouth,  248 ).
d( leeds,       sheffield,    34 ).
d( leeds,       swansea,     229 ).
d( leeds,       york,         23 ).
d( leeds,       london,      198 ).
d( liverpool,   manchester,   35 ).
d( liverpool,   newcastle,   162 ).
d( liverpool,   nottingham,  100 ).
d( liverpool,   oxford,      165 ).
d( liverpool,   penzance,    343 ).
d( liverpool,   portsmouth,  243 ).
d( liverpool,   sheffield,    70 ).
d( liverpool,   swansea,     166 ).
d( liverpool,   york,         96 ).
d( liverpool,   london,      198 ).
d( manchester,  newcastle,   130 ).
d( manchester,  nottingham,   71 ).
d( manchester,  oxford,      143 ).
d( manchester,  penzance,    344 ).
d( manchester,  portsmouth,  221 ).
d( manchester,  sheffield,    38 ).
d( manchester,  swansea,     188 ).
d( manchester,  york,         64 ).
d( manchester,  london,      189 ).
d( newcastle,   nottingham,  155 ).
d( newcastle,   oxford,      253 ).
d( newcastle,   penzance,    468 ).
d( newcastle,   portsmouth,  331 ).
d( newcastle,   sheffield,   123 ).
d( newcastle,   swansea,     318 ).
d( newcastle,   york,         80 ).
d( newcastle,   london,      276 ).
d( nottingham,  oxford,       98 ).
d( nottingham,  penzance,    322 ).
d( nottingham,  portsmouth,  176 ).
d( nottingham,  sheffield,    38 ).
d( nottingham,  swansea,     173 ).
d( nottingham,  york,         80 ).
d( nottingham,  london,      126 ).
d( oxford,      penzance,    250 ).
d( oxford,      portsmouth,   78 ).
d( oxford,      sheffield,   136 ).
d( oxford,      swansea,     145 ).
d( oxford,      york,        178 ).
d( oxford,      london,       57 ).
d( penzance,    portsmouth,  242 ).
d( penzance,    sheffield,   348 ).
d( penzance,    swansea,     273 ).
d( penzance,    york,        398 ).
d( penzance,    london,      281 ).
d( portsmouth,  sheffield,   214 ).
d( portsmouth,  swansea,     186 ).
d( portsmouth,  york,        256 ).
d( portsmouth,  london,       72 ).
d( sheffield,   swansea,     196 ).
d( sheffield,   york,         52 ).
d( sheffield,   london,      164 ).
d( swansea,     york,        248 ).
d( swansea,     london,      200 ).
d( york,        london,      198 ).
% End of list of distances

LPA Index     Home Page

Valid HTML 4.01 Strict