'**************************************************************** '* THE SALESMAN'S PROBLEM: FIND THE BEST ITINERARY TO VISIT NV * '* TOWNS WITH THE MINIMAL TOTAL DISTANCE USING THE "SIMULATED * '* ANNEALING METHOD". THE MAXIMUM NUMBER OF TOWNS IS HERE SET * '* TO FIFTY. * '* ------------------------------------------------------------ * '* LISTE OF MAIN VARIABLES: * '* NV : NUMBER OF TOWNS TO VISIT * '* CH\$(NV,4) : TABLE OF TOWN NAMES * '* V\$(NV,4) : SHORTEST ITINERARY * '* D(NV,NV) : MATRIX OF DISTANCES IN KM (OPTION 2) * '* ICO(NV,2) : GEOGRAPHICAL COORDINATES OF TOWNS (OPTION 1) * '* IT1 ET LL : INDICES OF STEPS OF RESOLUTION * '* ------------------------------------------------------------ * '* SAMPLE RUN: * '* (Find shortest itinerary to visit 38 French towns: * '* AMIENS, ANGOULEME, AUXERRE, BAYONNE, BORDEAUX, BOURGES, * '* BREST, CAEN, CALAIS, CHERBOURG, CLERMONT-FERRAND, DIJON, * '* GRENOBLE, LE HAVRE, LE MANS, LILLE, LIMOGES, LYON, * '* MARSEILLE, METZ, MONTPELLIER, MULHOUSE, NANCY, NANTES, NICE,* '* ORLEANS, PARIS, PAU, PERIGUEUX, POITIERS, REIMS, RENNES, * '* ROUEN, SAINT-ETIENNE, STRASBOURG, TOULOUSE, TOURS, TROYES). * '* * '* Input file "Villes.dat" contains the names and geographical * '* coordinates in km of the 38 towns (The origin is an arbitra- * '* ry point 30 km west of Brest and at the latitude of Calais): * '* * '* AMIENS, 525, 115 * '* ANGOULEME, 365, 585 * '* AUXERRE, 620, 340 * '* BAYONNE, 228, 830 * '* BORDEAUX, 305, 675 * '* BOURGES, 535, 425 * '* BREST, 030, 260 * '* CAEN, 333, 190 * '* CALAIS, 497, 0 * '* CHERBOURG, 250, 140 * '* CLERMONT-FERRAND,590, 565 * '* DIJON, 730, 395 * '* GRENOBLE, 795, 630 * '* LE_HAVRE, 370, 157 * '* LE_MANS, 370, 325 * '* LILLE, 578, 034 * '* LIMOGES, 450, 565 * '* LYON, 725, 570 * '* MARSEILLE, 775, 835 * '* METZ, 810, 195 * '* MONTPELLIER, 655, 805 * '* MULHOUSE, 910, 340 * '* NANCY, 810, 245 * '* NANTES, 235, 405 * '* NICE, 920, 780 * '* ORLEANS, 495, 330 * '* PARIS, 530, 228 * '* PAU, 316, 844 * '* PERIGUEUX, 410, 630 * '* POITIERS, 380, 480 * '* REIMS, 655, 185 * '* RENNES, 233, 305 * '* ROUEN, 440, 165 * '* SAINT-ETIENNE, 690, 605 * '* STRASBOURG, 925, 245 * '* TOULOUSE, 460, 810 * '* TOURS, 410, 390 * '* TROYES, 657, 286 * '* * '* Distances between towns (km): * '* 1 : as the crow flies * '* 2 : by road * '* Your choice (1 or 2): 2 * '* * '* Starting number of iterations: 10 * '* Maximum number of iterations : 2000 * '* Increment value of iterations: 10 * '* * '* See results in file Villes.lst. * '* * '* NOTE: Since this program depends on random numbers, you are * '* never sure to really have the shortest itinerary in * '* one pass. With above data, the output file contains: * '* * '* Shortest Itinerary Found: * '* * '* BORDEAUX --> ANGOULEME --> * '* PERIGUEUX --> LIMOGES --> * '* POITIERS --> TOURS --> * '* LE_MANS --> NANTES --> * '* BREST --> RENNES --> * '* CHERBOURG --> CAEN --> * '* LE_HAVRE --> ROUEN --> * '* CALAIS --> LILLE --> * '* AMIENS --> PARIS --> * '* REIMS --> METZ --> * '* NANCY --> STRASBOURG --> * '* MULHOUSE --> DIJON --> * '* TROYES --> AUXERRE --> * '* ORLEANS --> BOURGES --> * '* CLERMONT-FERRAND --> SAINT-ETIENNE --> * '* LYON --> GRENOBLE --> * '* NICE --> MARSEILLE --> * '* MONTPELLIER --> TOULOUSE --> * '* PAU --> BAYONNE --> * '* * '* NITER= 1200 DMIN= 5536 KM. * '* * '* This is probably one of the best itineraries possible, but * '* other solutions may exist. * '* Note: with option 1 (by air), total distance is of course * '* shorter. * '* ------------------------------------------------------------ * '* * '* Basic Release By J-P Moreau, Paris. * '* (www.jpmoreau.fr) * '**************************************************************** 'NOTE: With F90: NBITER=1085 DMIN=5599 (see tanneal.f90) ' With C++: NBITER=1450 DMIN=5630 (see tanneal.cpp) ' With TPW: NBITER= 490 DMIN=5509 (see tanneal.pas) '---------------------------------------------------------------- 'Program TANNEAL DEFDBL A-H, O-Z DEFINT I-N NV = 38 'Number of towns to visit DIM CH(NV) AS STRING DIM Vs(NV) AS STRING DIM V1s(NV) AS STRING DIM ICO(NV, 2) DIM D(NV, NV) DIM L(NV) AS DOUBLE DIM C(NV) DIM ID(NV, NV) 'indices of towns (used bv subroutines 2000 and 2001 'IAmiens,IAngouleme,IAuxerre,IBayonne,IBordeaux,IBourges 'IBrest,ICaen,ICalais,ICherbourg,IClermont,IDijon,IGrenoble 'LeHavre,LeMans,Lille,Limoges,Lyon,Marseille,Metz, 'Montpellier,Mulhouse,Nancy,Nantes,Nice 'IOrleans,IParis,IPau,IPerigueux,IPoitiers,IReims,IRennes 'IRouen,IStEtienne,IStrasbourg,IToulouse,ITours,ITroyes CLS PRINT PRINT " Distances between towns (km):" PRINT " 1 : as the crow flies" PRINT " 2 : by road" INPUT " Your choice ( 1 or 2 ): ", ichoice PRINT INPUT " Starting number of iterations: ", nbiter INPUT " Maximum number of iterations : ", nmax INPUT " Increment value of iterations: ", iditer 'open I/O text files OPEN "villes.dat" FOR INPUT AS #1 OPEN "villes.lst" FOR OUTPUT AS #2 IF ichoice = 1 THEN 'By air PRINT #2, PRINT #2, " SALESMAN'S PROBLEM" PRINT #2, PRINT #2, " NO TOWN COORDINATES (KM)" PRINT #2, " EAST SOUTH" PRINT #2, END IF 'read names of cities and coordinates from input file FOR i = 1 TO NV INPUT #1, CH(i), ICO(i, 1), ICO(i, 2) IF ichoice = 1 THEN PRINT #2, i; " "; CH(i); " "; ICO(i, 1); " "; ICO(i, 2) END IF NEXT i CLOSE #1 'Init distances by air FOR i = 1 TO NV - 1 FOR J = i + 1 TO NV X = ICO(i, 1) - ICO(J, 1) Y = ICO(i, 2) - ICO(J, 2) D(i, J) = SQR(X * X + Y * Y) ID(i, J) = INT(D(i, J)) D(J, i) = D(i, J) ID(J, i) = INT(D(i, J)) NEXT J NEXT i IF ichoice = 1 THEN 'By air PRINT #2, PRINT #2, " MATRIX OF DISTANCES (KM)" FOR i = 1 TO NV FOR J = 1 TO NV PRINT #2, " "; ID(i, J); NEXT J PRINT #2, NEXT i END IF IF ichoice = 2 THEN GOSUB 2000 'Init distances by road GOSUB 2001 END IF ' Main loop DDMIN = 35000# 10 GOSUB 500 'call TIME ' aff_L(0) GOSUB 1000 'call ANNEAL(nbiter, itmin) nbiter = nbiter + iditer IF nbiter <= nmax THEN GOTO 10 ' print results PRINT #2, PRINT #2, " Shortest Itinerary Found:" PRINT #2, i = 1 20 PRINT #2, " "; Vs(L(i)); " --> "; Vs(L(i + 1)); " -->" i = i + 2 IF i < NV THEN GOTO 20 GOSUB 600 'call DELTAT (Total distance) PRINT #2, PRINT #2, " NITER= "; itmin; " DMIN= "; T; " KM." CLOSE #2 PRINT PRINT PRINT " See Results in file Villes.lst." PRINT END 'of main program ' GENERATE A RANDOM TIME 500 'Subroutine TIME ' Labels: 515, 520, 525 FOR i5 = 1 TO NV L(i5) = 0 C(i5) = 0# NEXT i5 n5 = NV 515 it = INT(1 + RND * n5) k5 = 0: j5 = 1 516 IF C(j5) = 0# THEN k5 = k5 + 1 IF k5 <> it THEN GOTO 520 k5 = j5 GOTO 525 520 j5 = j5 + 1 IF j5 <= NV THEN GOTO 516 525 L(n5) = k5 n5 = n5 - 1 C(k5) = 1# IF n5 > 0 THEN GOTO 515 RETURN ' Calculate total distance, T 600 'Subroutine DELTAT T = 0# FOR i6 = 1 TO NV - 1 T = T + D(L(i6), L(i6 + 1)) NEXT i6 RETURN ' Debug only 800 'Subroutine aff_L(jj) PRINT #2, PRINT #2, "("; jj; ")": n = 0 FOR i = 1 TO NV n = n + 1 PRINT #2, " "; L(i); IF n = 20 THEN PRINT #2, : n = 0 END IF NEXT i RETURN ' Simulated Annealing Method 1000 'Subroutine ANNEAL(nbiter,itmin) ' Labels: 1010, 1020, 1025 GOSUB 600: DT = T DMIN = 35000# TP = 110# FOR IT1 = 1 TO 40 FOR LL = 1 TO nbiter i = INT(1 + RND * NV) IF i < 1 THEN i = 1 1005 J = INT(1 + RND * NV) IF J < 1 THEN J = 1 IF J = i THEN GOTO 1005 IF J < i THEN II = i i = J J = II END IF I1 = i - 1 IF I1 < 1 THEN I1 = I1 + NV I2 = i + 1 J1 = J - 1 R = RND IF R > .5 THEN GOTO 1010 J2 = J + 1 IF J2 > NV THEN J2 = J2 - NV 1025 K = INT(1 + RND * NV) K2 = K + 1 IF K2 > NV THEN K2 = 1 IF K = i THEN GOTO 1025 IF K = J THEN GOTO 1025 IF K <= i THEN II = K K = i i = II II = K2 K2 = I2 I2 = II END IF IF K <= J THEN II = K K = J J = II II = K2 K2 = J2 J2 = II END IF DD = D(L(i), L(J2)) + D(L(K), L(I2)) + D(L(J), L(K2)) DD = DD - (D(L(i), L(I2)) + D(L(J), L(J2)) + D(L(K), L(K2))) R1 = RND 'Guard against underflow or overflow in Exp IF DD / TP > 60# THEN EX = 0# ELSEIF DD / TP < -60 THEN EX = 1# ELSE EX = EXP(-DD / TP) END IF IF R1 > EX THEN GOTO 1020 FOR M = 1 TO i C(M) = 1# * L(M) NEXT M M = i + 1 FOR M1 = J2 TO K C(M) = 1# * L(M1) M = M + 1 NEXT M1 FOR M1 = I2 TO J C(M) = 1# * L(M1) M = M + 1 NEXT M1 IF K2 <> 1 THEN FOR M1 = K2 TO NV C(M) = 1# * L(M1) M = M + 1 NEXT M1 END IF FOR M1 = 1 TO NV L(M1) = INT(C(M1)) NEXT M1 ' aff_L(1) GOTO 1020 1010 IF i = J1 THEN GOTO 1020 DD = D(L(I1), L(J1)) + D(L(i), L(J)) - (D(L(I1), L(i)) + D(L(J1), L(J))) R1 = RND 'Guard against underflow or overflow in Exp IF DD / TP > 60 THEN EX = 0# ELSEIF DD / TP < -60 THEN EX = 1# ELSE EX = EXP(-DD / TP) END IF IF R1 <= EX THEN ' aff_L(2) KF = i + INT(.5 + ((J1 - i) / 2)) FOR K = i TO KF II = L(K) L(K) = L(J1 + i - K) L(J1 + i - K) = II NEXT K ' aff_L(3) END IF 1020 NEXT LL TP = TP * .9 'lower temperature GOSUB 600: DT = T DMAX = DT IF DT < DMIN THEN DMIN = DT FOR i9 = 1 TO NV V1s(L(i9)) = CH(L(i9)) NEXT i9 END IF NEXT IT1 IF DMIN < DDMIN THEN itmin = nbiter DDMIN = DMIN FOR i9 = 1 TO NV Vs(i9) = V1s(i9) NEXT i9 END IF RETURN ' Initialize road distances (according to Michelin France Map) 2000 'Subroutine InitDist {part 1} ' initialize town indices IAmiens = 1 IAngouleme = 2 IAuxerre = 3 IBayonne = 4 IBordeaux = 5 IBourges = 6 IBrest = 7 ICaen = 8 ICalais = 9 ICherbourg = 10 IClermont = 11 IDijon = 12 IGrenoble = 13 LeHavre = 14 LeMans = 15 Lille = 16 Limoges = 17 Lyon = 18 Marseille = 19 Metz = 20 Montpellier = 21 Mulhouse = 22 Nancy = 23 Nantes = 24 Nice = 25 IOrleans = 26 IParis = 27 IPau = 28 IPerigueux = 29 IPoitiers = 30 IReims = 31 IRennes = 32 IRouen = 33 IStEtienne = 34 IStrasbourg = 35 IToulouse = 36 ITours = 37 ITroyes = 38 ' distances between Amiens and other towns D(IAmiens, IAngouleme) = 588# D(IAmiens, IAuxerre) = 302# D(IAmiens, IBayonne) = 888# D(IAmiens, IBordeaux) = 711# D(IAmiens, IBourges) = 357# D(IAmiens, IBrest) = 617# D(IAmiens, ICaen) = 246# D(IAmiens, ICalais) = 154# D(IAmiens, ICherbourg) = 366# D(IAmiens, IClermont) = 520# D(IAmiens, IDijon) = 444# D(IAmiens, IGrenoble) = 696# D(IAmiens, LeHavre) = 178# D(IAmiens, LeMans) = 317# D(IAmiens, Lille) = 110# D(IAmiens, Limoges) = 586# D(IAmiens, Lyon) = 592# D(IAmiens, Marseille) = 907# D(IAmiens, Metz) = 342# D(IAmiens, Montpellier) = 981# D(IAmiens, Mulhouse) = 512# D(IAmiens, Nancy) = 353# D(IAmiens, Nantes) = 475# D(IAmiens, Nice) = 1063# D(IAmiens, IOrleans) = 262# D(IAmiens, IParis) = 132# D(IAmiens, IPau) = 910# D(IAmiens, IPerigueux) = 674# D(IAmiens, IPoitiers) = 478# D(IAmiens, IReims) = 154# D(IAmiens, IRennes) = 422# D(IAmiens, IRouen) = 122# D(IAmiens, IStEtienne) = 648# D(IAmiens, IStrasbourg) = 505# D(IAmiens, IToulouse) = 837# D(IAmiens, ITours) = 366# D(IAmiens, ITroyes) = 284# ' distances between Angouleme and other towns D(IAngouleme, IAuxerre) = 439# D(IAngouleme, IBayonne) = 295# D(IAngouleme, IBordeaux) = 118# D(IAngouleme, IBourges) = 295# D(IAngouleme, IBrest) = 536# D(IAngouleme, ICaen) = 460# D(IAngouleme, ICalais) = 751# D(IAngouleme, ICherbourg) = 559# D(IAngouleme, IClermont) = 283# D(IAngouleme, IDijon) = 530# D(IAngouleme, IGrenoble) = 569# D(IAngouleme, LeHavre) = 532# D(IAngouleme, LeMans) = 334# D(IAngouleme, Lille) = 678# D(IAngouleme, Limoges) = 103# D(IAngouleme, Lyon) = 460# D(IAngouleme, Marseille) = 740# D(IAngouleme, Metz) = 794# D(IAngouleme, Montpellier) = 640# D(IAngouleme, Mulhouse) = 759# D(IAngouleme, Nancy) = 692# D(IAngouleme, Nantes) = 240# D(IAngouleme, Nice) = 927# D(IAngouleme, IOrleans) = 339# D(IAngouleme, IParis) = 461# D(IAngouleme, IPau) = 317# D(IAngouleme, IPerigueux) = 86# D(IAngouleme, IPoitiers) = 110# D(IAngouleme, IReims) = 630# D(IAngouleme, IRennes) = 347# D(IAngouleme, IRouen) = 504# D(IAngouleme, IStEtienne) = 397# D(IAngouleme, IStrasbourg) = 865# D(IAngouleme, IToulouse) = 334# D(IAngouleme, ITours) = 227# D(IAngouleme, ITroyes) = 510# ' distances between Auxerre and other towns D(IAuxerre, IBayonne) = 707# D(IAuxerre, IBordeaux) = 530# D(IAuxerre, IBourges) = 144# D(IAuxerre, IBrest) = 695# D(IAuxerre, ICaen) = 407# D(IAuxerre, ICalais) = 454# D(IAuxerre, ICherbourg) = 537# D(IAuxerre, IClermont) = 240# D(IAuxerre, IDijon) = 150# D(IAuxerre, IGrenoble) = 445# D(IAuxerre, LeHavre) = 366# D(IAuxerre, LeMans) = 288# D(IAuxerre, Lille) = 501# D(IAuxerre, Limoges) = 331# D(IAuxerre, Lyon) = 298# D(IAuxerre, Marseille) = 614# D(IAuxerre, Metz) = 314# D(IAuxerre, Montpellier) = 596# D(IAuxerre, Mulhouse) = 379# D(IAuxerre, Nancy) = 258# D(IAuxerre, Nantes) = 450# D(IAuxerre, Nice) = 768# D(IAuxerre, IOrleans) = 150# D(IAuxerre, IParis) = 162# D(IAuxerre, IPau) = 794# D(IAuxerre, IPerigueux) = 433# D(IAuxerre, IPoitiers) = 331# D(IAuxerre, IReims) = 202# D(IAuxerre, IRennes) = 447# D(IAuxerre, IRouen) = 301# D(IAuxerre, IStEtienne) = 361# D(IAuxerre, IStrasbourg) = 410# D(IAuxerre, IToulouse) = 621# D(IAuxerre, ITours) = 262# D(IAuxerre, ITroyes) = 81# ' distances between Bayonne and other towns D(IBayonne, IBordeaux) = 177# D(IBayonne, IBourges) = 590# D(IBayonne, IBrest) = 798# D(IBayonne, ICaen) = 755# D(IBayonne, ICalais) = 1046# D(IBayonne, ICherbourg) = 854# D(IBayonne, IClermont) = 545# D(IBayonne, IDijon) = 811# D(IBayonne, IGrenoble) = 812# D(IBayonne, LeHavre) = 827# D(IBayonne, LeMans) = 602# D(IBayonne, Lille) = 973# D(IBayonne, Limoges) = 398# D(IBayonne, Lyon) = 722# D(IBayonne, Marseille) = 680# D(IBayonne, Metz) = 1079# D(IBayonne, Montpellier) = 516# D(IBayonne, Mulhouse) = 1097# D(IBayonne, Nancy) = 965# D(IBayonne, Nantes) = 502# D(IBayonne, Nice) = 835# D(IBayonne, IOrleans) = 634# D(IBayonne, IParis) = 756# D(IBayonne, IPau) = 103# D(IBayonne, IPerigueux) = 298# D(IBayonne, IPoitiers) = 405# D(IBayonne, IReims) = 891# D(IBayonne, IRennes) = 609# D(IBayonne, IRouen) = 799# D(IBayonne, IStEtienne) = 691# D(IBayonne, IStrasbourg) = 1237# D(IBayonne, IToulouse) = 276# D(IBayonne, ITours) = 522# D(IBayonne, ITroyes) = 805# ' distances between Bordeaux and other towns D(IBordeaux, IBourges) = 413# D(IBordeaux, IBrest) = 621# D(IBordeaux, ICaen) = 578# D(IBordeaux, ICalais) = 869# D(IBordeaux, ICherbourg) = 677# D(IBordeaux, IClermont) = 368# D(IBordeaux, IDijon) = 634# D(IBordeaux, IGrenoble) = 654# D(IBordeaux, LeHavre) = 650# D(IBordeaux, LeMans) = 425# D(IBordeaux, Lille) = 796# D(IBordeaux, Limoges) = 221# D(IBordeaux, Lyon) = 545# D(IBordeaux, Marseille) = 648# D(IBordeaux, Metz) = 902# D(IBordeaux, Montpellier) = 484# D(IBordeaux, Mulhouse) = 816# D(IBordeaux, Nancy) = 788# D(IBordeaux, Nantes) = 325# D(IBordeaux, Nice) = 803# D(IBordeaux, IOrleans) = 457# D(IBordeaux, IParis) = 579# D(IBordeaux, IPau) = 199# D(IBordeaux, IPerigueux) = 121# D(IBordeaux, IPoitiers) = 228# D(IBordeaux, IReims) = 714# D(IBordeaux, IRennes) = 432# D(IBordeaux, IRouen) = 622# D(IBordeaux, IStEtienne) = 514# D(IBordeaux, IStrasbourg) = 1060# D(IBordeaux, IToulouse) = 244# D(IBordeaux, ITours) = 345# D(IBordeaux, ITroyes) = 628# ' distances between Bourges and other towns D(IBourges, IBrest) = 634# D(IBourges, ICaen) = 363# D(IBourges, ICalais) = 526# D(IBourges, ICherbourg) = 493# D(IBourges, IClermont) = 180# D(IBourges, IDijon) = 259# D(IBourges, IGrenoble) = 466# D(IBourges, LeHavre) = 508# D(IBourges, LeMans) = 230# D(IBourges, Lille) = 455# D(IBourges, Limoges) = 187# D(IBourges, Lyon) = 357# D(IBourges, Marseille) = 637# D(IBourges, Metz) = 458# D(IBourges, Montpellier) = 540# D(IBourges, Mulhouse) = 488# D(IBourges, Nancy) = 402# D(IBourges, Nantes) = 347# D(IBourges, Nice) = 792# D(IBourges, IOrleans) = 106# D(IBourges, IParis) = 236# D(IBourges, IPau) = 734# D(IBourges, IPerigueux) = 289# D(IBourges, IPoitiers) = 187# D(IBourges, IReims) = 346# D(IBourges, IRennes) = 506# D(IBourges, IRouen) = 323# D(IBourges, IStEtienne) = 326# D(IBourges, IStrasbourg) = 554# D(IBourges, IToulouse) = 561# D(IBourges, ITours) = 150# D(IBourges, ITroyes) = 225# ' distances between Brest and other towns D(IBrest, ICaen) = 371# D(IBrest, ICalais) = 713# D(IBrest, ICherbourg) = 415# D(IBrest, IClermont) = 750# D(IBrest, IDijon) = 854# D(IBrest, IGrenoble) = 1106# D(IBrest, LeHavre) = 479# D(IBrest, LeMans) = 402# D(IBrest, Lille) = 814# D(IBrest, Limoges) = 606# D(IBrest, Lyon) = 1002# D(IBrest, Marseille) = 1317# D(IBrest, Metz) = 920# D(IBrest, Montpellier) = 1105# D(IBrest, Mulhouse) = 1081# D(IBrest, Nancy) = 915# D(IBrest, Nantes) = 296# D(IBrest, Nice) = 1472# D(IBrest, IOrleans) = 545# D(IBrest, IParis) = 596# D(IBrest, IPau) = 820# D(IBrest, IPerigueux) = 622# D(IBrest, IPoitiers) = 485# D(IBrest, IReims) = 731# D(IBrest, IRennes) = 245# D(IBrest, IRouen) = 495# D(IBrest, IStEtienne) = 896# D(IBrest, IStrasbourg) = 1077# D(IBrest, IToulouse) = 865# D(IBrest, ITours) = 484# D(IBrest, ITroyes) = 733# ' distances between Caen and other towns D(ICaen, ICalais) = 342# D(ICaen, ICherbourg) = 120# D(ICaen, IClermont) = 617# D(ICaen, IDijon) = 542# D(ICaen, IGrenoble) = 794# D(ICaen, LeHavre) = 108# D(ICaen, LeMans) = 156# D(ICaen, Lille) = 342# D(ICaen, Limoges) = 469# D(ICaen, Lyon) = 690# D(ICaen, Marseille) = 1005# D(ICaen, Metz) = 567# D(ICaen, Montpellier) = 988# D(ICaen, Mulhouse) = 769# D(ICaen, Nancy) = 540# D(ICaen, Nantes) = 283# D(ICaen, Nice) = 1160# D(ICaen, IOrleans) = 257# D(ICaen, IParis) = 240# D(ICaen, IPau) = 777# D(ICaen, IPerigueux) = 606# D(ICaen, IPoitiers) = 410# D(ICaen, IReims) = 379# D(ICaen, IRennes) = 176# D(ICaen, IRouen) = 124# D(ICaen, IStEtienne) = 745# D(ICaen, IStrasbourg) = 725# D(ICaen, IToulouse) = 768# D(ICaen, ITours) = 233# D(ICaen, ITroyes) = 418# ' distances between Calais and other towns D(ICalais, ICherbourg) = 462# D(ICalais, IClermont) = 678# D(ICalais, IDijon) = 603# D(ICalais, IGrenoble) = 855# D(ICalais, LeHavre) = 284# D(ICalais, LeMans) = 418# D(ICalais, Lille) = 112# D(ICalais, Limoges) = 746# D(ICalais, Lyon) = 751# D(ICalais, Marseille) = 1066# D(ICalais, Metz) = 467# D(ICalais, Montpellier) = 1049# D(ICalais, Mulhouse) = 636# D(ICalais, Nancy) = 523# D(ICalais, Nantes) = 668# D(ICalais, Nice) = 1221# D(ICalais, IOrleans) = 420# D(ICalais, IParis) = 292# D(ICalais, IPau) = 1059# D(ICalais, IPerigueux) = 828# D(ICalais, IPoitiers) = 630# D(ICalais, IReims) = 278# D(ICalais, IRennes) = 518# D(ICalais, IRouen) = 218# D(ICalais, IStEtienne) = 806# D(ICalais, IStrasbourg) = 624# D(ICalais, IToulouse) = 995# D(ICalais, ITours) = 524# D(ICalais, ITroyes) = 399# ' distances between Cherbourg and other towns D(ICherbourg, IClermont) = 663# D(ICherbourg, IDijon) = 684# D(ICherbourg, IGrenoble) = 936# D(ICherbourg, LeHavre) = 228# D(ICherbourg, LeMans) = 276# D(ICherbourg, Lille) = 462# D(ICherbourg, Limoges) = 589# D(ICherbourg, Lyon) = 810# D(ICherbourg, Marseille) = 1125# D(ICherbourg, Metz) = 687# D(ICherbourg, Montpellier) = 1108# D(ICherbourg, Mulhouse) = 889# D(ICherbourg, Nancy) = 660# D(ICherbourg, Nantes) = 319# D(ICherbourg, Nice) = 1280# D(ICherbourg, IOrleans) = 507# D(ICherbourg, IParis) = 360# D(ICherbourg, IPau) = 876# D(ICherbourg, IPerigueux) = 645# D(ICherbourg, IPoitiers) = 450# D(ICherbourg, IReims) = 499# D(ICherbourg, IRennes) = 212# D(ICherbourg, IRouen) = 244# D(ICherbourg, IStEtienne) = 865# D(ICherbourg, IStrasbourg) = 845# D(ICherbourg, IToulouse) = 893# D(ICherbourg, ITours) = 356# D(ICherbourg, ITroyes) = 399# ' distances between Clermont-Ferrand and other towns D(IClermont, IDijon) = 282# D(IClermont, IGrenoble) = 286# D(IClermont, LeHavre) = 581# D(IClermont, LeMans) = 507# D(IClermont, Lille) = 605# D(IClermont, Limoges) = 178# D(IClermont, Lyon) = 177# D(IClermont, Marseille) = 457# D(IClermont, Metz) = 546# D(IClermont, Montpellier) = 360# D(IClermont, Mulhouse) = 463# D(IClermont, Nancy) = 490# D(IClermont, Nantes) = 460# D(IClermont, Nice) = 612# D(IClermont, IOrleans) = 289# D(IClermont, IParis) = 508# D(IClermont, IPau) = 554# D(IClermont, IPerigueux) = 250# D(IClermont, IPoitiers) = 285# D(IClermont, IReims) = 487# D(IClermont, IRennes) = 528# D(IClermont, IRouen) = 516# D(IClermont, IStEtienne) = 146# D(IClermont, IStrasbourg) = 569# D(IClermont, IToulouse) = 501# D(IClermont, ITours) = 307# D(IClermont, ITroyes) = 321# ' distances between Dijon and other towns D(IDijon, IGrenoble) = 295# D(IDijon, LeHavre) = 506# D(IDijon, LeMans) = 435# D(IDijon, Lille) = 530# D(IDijon, Limoges) = 425# D(IDijon, Lyon) = 191# D(IDijon, Marseille) = 507# D(IDijon, Metz) = 264# D(IDijon, Montpellier) = 490# D(IDijon, Mulhouse) = 229# D(IDijon, Nancy) = 210# D(IDijon, Nantes) = 597# D(IDijon, Nice) = 662# D(IDijon, IOrleans) = 297# D(IDijon, IParis) = 312# D(IDijon, IPau) = 836# D(IDijon, IPerigueux) = 520# D(IDijon, IPoitiers) = 446# D(IDijon, IReims) = 286# D(IDijon, IRennes) = 605# D(IDijon, IRouen) = 441# D(IDijon, IStEtienne) = 247# D(IDijon, IStrasbourg) = 335# D(IDijon, IToulouse) = 726# D(IDijon, ITours) = 409# D(IDijon, ITroyes) = 152# ' distances between Grenoble and other towns D(IGrenoble, LeHavre) = 758# D(IGrenoble, LeMans) = 613# D(IGrenoble, Lille) = 782# D(IGrenoble, Limoges) = 464# D(IGrenoble, Lyon) = 104# D(IGrenoble, Marseille) = 281# D(IGrenoble, Metz) = 560# D(IGrenoble, Montpellier) = 300# D(IGrenoble, Mulhouse) = 450# D(IGrenoble, Nancy) = 505# D(IGrenoble, Nantes) = 730# D(IGrenoble, Nice) = 334# D(IGrenoble, IOrleans) = 549# D(IGrenoble, IParis) = 564# D(IGrenoble, IPau) = 709# D(IGrenoble, IPerigueux) = 544# D(IGrenoble, IPoitiers) = 585# D(IGrenoble, IReims) = 581# D(IGrenoble, IRennes) = 857# D(IGrenoble, IRouen) = 693# D(IGrenoble, IStEtienne) = 143# D(IGrenoble, IStrasbourg) = 548# D(IGrenoble, IToulouse) = 536# D(IGrenoble, ITours) = 533# D(IGrenoble, ITroyes) = 447# ' distances between Le Havre and other towns D(LeHavre, LeMans) = 264# D(LeHavre, Lille) = 284# D(LeHavre, Limoges) = 577# D(LeHavre, Lyon) = 654# D(LeHavre, Marseille) = 969# D(LeHavre, Metz) = 531# D(LeHavre, Montpellier) = 952# D(LeHavre, Mulhouse) = 733# D(LeHavre, Nancy) = 504# D(LeHavre, Nantes) = 500# D(LeHavre, Nice) = 1124# D(LeHavre, IOrleans) = 282# D(LeHavre, IParis) = 204# D(LeHavre, IPau) = 876# D(LeHavre, IPerigueux) = 645# D(LeHavre, IPoitiers) = 450# D(LeHavre, IReims) = 343# D(LeHavre, IRennes) = 284# D(LeHavre, IRouen) = 88# D(LeHavre, IStEtienne) = 709# D(LeHavre, IStrasbourg) = 689# D(LeHavre, IToulouse) = 840# D(LeHavre, ITours) = 305# D(LeHavre, ITroyes) = 502# ' distances between Le Mans and other towns D(LeMans, Lille) = 418# D(LeMans, Limoges) = 313# D(LeMans, Lyon) = 509# D(LeMans, Marseille) = 816# D(LeMans, Metz) = 534# D(LeMans, Montpellier) = 716# D(LeMans, Mulhouse) = 662# D(LeMans, Nancy) = 503# D(LeMans, Nantes) = 181# D(LeMans, Nice) = 971# D(LeMans, IOrleans) = 150# D(LeMans, IParis) = 203# D(LeMans, IPau) = 651# D(LeMans, IPerigueux) = 420# D(LeMans, IPoitiers) = 224# D(LeMans, IReims) = 345# D(LeMans, IRennes) = 157# D(LeMans, IRouen) = 200# D(LeMans, IStEtienne) = 504# D(LeMans, IStrasbourg) = 749# D(LeMans, IToulouse) = 615# D(LeMans, ITours) = 80# D(LeMans, ITroyes) = 326# ' distances between Lille and other towns D(Lille, Limoges) = 673# D(Lille, Lyon) = 678# D(Lille, Marseille) = 993# D(Lille, Metz) = 349# D(Lille, Montpellier) = 976# D(Lille, Mulhouse) = 563# D(Lille, Nancy) = 405# D(Lille, Nantes) = 595# D(Lille, Nice) = 1148# D(Lille, IOrleans) = 347# D(Lille, IParis) = 219# D(Lille, IPau) = 995# D(Lille, IPerigueux) = 784# D(Lille, IPoitiers) = 588# D(Lille, IReims) = 205# D(Lille, IRennes) = 565# D(Lille, IRouen) = 218# D(Lille, IStEtienne) = 733# D(Lille, IStrasbourg) = 505# D(Lille, IToulouse) = 922# D(Lille, ITours) = 451# D(Lille, ITroyes) = 326# ' distances between Limoges and other towns D(Limoges, Lyon) = 355# D(Limoges, Marseille) = 635# D(Limoges, Metz) = 645# D(Limoges, Montpellier) = 550# D(Limoges, Mulhouse) = 654# D(Limoges, Nancy) = 589# D(Limoges, Nantes) = 310# D(Limoges, Nice) = 790# D(Limoges, IOrleans) = 324# D(Limoges, IParis) = 454# D(Limoges, IPau) = 363# D(Limoges, IPerigueux) = 102# D(Limoges, IPoitiers) = 121# D(Limoges, IReims) = 533# D(Limoges, IRennes) = 500# D(Limoges, IRouen) = 541# D(Limoges, IStEtienne) = 324# D(Limoges, IStrasbourg) = 760# D(Limoges, IToulouse) = 315# D(Limoges, ITours) = 225# D(Limoges, ITroyes) = 412# ' distances between Lyon and other towns D(Lyon, Marseille) = 315# D(Lyon, Metz) = 456# D(Lyon, Montpellier) = 298# D(Lyon, Mulhouse) = 375# D(Lyon, Nancy) = 401# D(Lyon, Nantes) = 626# D(Lyon, Nice) = 470# D(Lyon, IOrleans) = 445# D(Lyon, IParis) = 460# D(Lyon, IPau) = 731# D(Lyon, IPerigueux) = 415# D(Lyon, IPoitiers) = 462# D(Lyon, IReims) = 477# D(Lyon, IRennes) = 753# D(Lyon, IRouen) = 589# D(Lyon, IStEtienne) = 63# D(Lyon, IStrasbourg) = 480# D(Lyon, IToulouse) = 534# D(Lyon, ITours) = 429# D(Lyon, ITroyes) = 343# ' distances between Marseille and other towns D(Marseille, Metz) = 771# D(Marseille, Montpellier) = 168# D(Marseille, Mulhouse) = 690# D(Marseille, Nancy) = 716# D(Marseille, Nantes) = 973# D(Marseille, Nice) = 187# D(Marseille, IOrleans) = 760# D(Marseille, IParis) = 776# D(Marseille, IPau) = 577# D(Marseille, IPerigueux) = 654# D(Marseille, IPoitiers) = 742# D(Marseille, IReims) = 793# D(Marseille, IRennes) = 1069# D(Marseille, IRouen) = 904# D(Marseille, IStEtienne) = 308# D(Marseille, IStrasbourg) = 796# D(Marseille, IToulouse) = 404# D(Marseille, ITours) = 736# D(Marseille, ITroyes) = 658# ' distances between Metz and other towns D(Metz, Montpellier) = 754# D(Metz, Mulhouse) = 227# D(Metz, Nancy) = 56# D(Metz, Nantes) = 701# D(Metz, Nice) = 926# D(Metz, IOrleans) = 453# D(Metz, IParis) = 331# D(Metz, IPau) = 1192# D(Metz, IPerigueux) = 747# D(Metz, IPoitiers) = 645# D(Metz, IReims) = 188# D(Metz, IRennes) = 671# D(Metz, IRouen) = 419# D(Metz, IStEtienne) = 511# D(Metz, IStrasbourg) = 163# D(Metz, IToulouse) = 990# D(Metz, ITours) = 557# D(Metz, ITroyes) = 208# RETURN 2001 'Subroutine InitDist {part 2} ' distances between Montpellier and other towns D(Montpellier, Mulhouse) = 673# D(Montpellier, Nancy) = 700# D(Montpellier, Nantes) = 809# D(Montpellier, Nice) = 323# D(Montpellier, IOrleans) = 743# D(Montpellier, IParis) = 759# D(Montpellier, IPau) = 413# D(Montpellier, IPerigueux) = 490# D(Montpellier, IPoitiers) = 659# D(Montpellier, IReims) = 776# D(Montpellier, IRennes) = 916# D(Montpellier, IRouen) = 887# D(Montpellier, IStEtienne) = 291# D(Montpellier, IStrasbourg) = 779# D(Montpellier, IToulouse) = 240# D(Montpellier, ITours) = 636# D(Montpellier, ITroyes) = 642# ' distances between Mulhouse and other towns D(Mulhouse, Nancy) = 171# D(Mulhouse, Nantes) = 824# D(Mulhouse, Nice) = 698# D(Mulhouse, IOrleans) = 524# D(Mulhouse, IParis) = 539# D(Mulhouse, IPau) = 1106# D(Mulhouse, IPerigueux) = 701# D(Mulhouse, IPoitiers) = 675# D(Mulhouse, IReims) = 358# D(Mulhouse, IRennes) = 832# D(Mulhouse, IRouen) = 668# D(Mulhouse, IStEtienne) = 430# D(Mulhouse, IStrasbourg) = 113# D(Mulhouse, IToulouse) = 909# D(Mulhouse, ITours) = 636# D(Mulhouse, ITroyes) = 274# ' distances between Nancy and other towns D(Nancy, Nantes) = 708# D(Nancy, Nice) = 872# D(Nancy, IOrleans) = 365# D(Nancy, IParis) = 300# D(Nancy, IPau) = 1046# D(Nancy, IPerigueux) = 728# D(Nancy, IPoitiers) = 589# D(Nancy, IReims) = 244# D(Nancy, IRennes) = 662# D(Nancy, IRouen) = 439# D(Nancy, IStEtienne) = 457# D(Nancy, IStrasbourg) = 188# D(Nancy, IToulouse) = 871# D(Nancy, ITours) = 477# D(Nancy, ITroyes) = 177# ' distances between Nantes and other towns D(Nantes, Nice) = 1128# D(Nantes, IOrleans) = 300# D(Nantes, IParis) = 378# D(Nantes, IPau) = 524# D(Nantes, IPerigueux) = 326# D(Nantes, IPoitiers) = 189# D(Nantes, IReims) = 513# D(Nantes, IRennes) = 107# D(Nantes, IRouen) = 353# D(Nantes, IStEtienne) = 606# D(Nantes, IStrasbourg) = 859# D(Nantes, IToulouse) = 569# D(Nantes, ITours) = 197# D(Nantes, ITroyes) = 488# ' distances between Nice and other towns D(Nice, IOrleans) = 915# D(Nice, IParis) = 931# D(Nice, IPau) = 732# D(Nice, IPerigueux) = 809# D(Nice, IPoitiers) = 775# D(Nice, IReims) = 948# D(Nice, IRennes) = 1224# D(Nice, IRouen) = 1059# D(Nice, IStEtienne) = 463# D(Nice, IStrasbourg) = 808# D(Nice, IToulouse) = 559# D(Nice, ITours) = 891# D(Nice, ITroyes) = 813# ' distances between Orleans and other towns D(IOrleans, IParis) = 130# D(IOrleans, IPau) = 656# D(IOrleans, IPerigueux) = 426# D(IOrleans, IPoitiers) = 256# D(IOrleans, IReims) = 265# D(IOrleans, IRennes) = 297# D(IOrleans, IRouen) = 217# D(IOrleans, IStEtienne) = 503# D(IOrleans, IStrasbourg) = 611# D(IOrleans, IToulouse) = 574# D(IOrleans, ITours) = 112# D(IOrleans, ITroyes) = 188# ' distances between Paris and other towns D(IParis, IPau) = 778# D(IParis, IPerigueux) = 556# D(IParis, IPoitiers) = 506# D(IParis, IReims) = 142# D(IParis, IRennes) = 348# D(IParis, IRouen) = 139# D(IParis, IStEtienne) = 516# D(IParis, IStrasbourg) = 488# D(IParis, IToulouse) = 705# D(IParis, ITours) = 234# D(IParis, ITroyes) = 178# ' distances between Pau and other towns D(IPau, IPerigueux) = 261# D(IPau, IPoitiers) = 427# D(IPau, IReims) = 920# D(IPau, IRennes) = 631# D(IPau, IRouen) = 848# D(IPau, IStEtienne) = 700# D(IPau, IStrasbourg) = 1171# D(IPau, IToulouse) = 173# D(IPau, ITours) = 544# D(IPau, ITroyes) = 959# ' distances between Perigueux and other towns D(IPerigueux, IPoitiers) = 196# D(IPerigueux, IReims) = 635# D(IPerigueux, IRennes) = 433# D(IPerigueux, IRouen) = 617# D(IPerigueux, IStEtienne) = 504# D(IPerigueux, IStrasbourg) = 807# D(IPerigueux, IToulouse) = 248# D(IPerigueux, ITours) = 340# D(IPerigueux, ITroyes) = 514# ' distances between Poitiers and other towns D(IPoitiers, IReims) = 521# D(IPoitiers, IRennes) = 259# D(IPoitiers, IRouen) = 424# D(IPoitiers, IStEtienne) = 431# D(IPoitiers, IStrasbourg) = 741# D(IPoitiers, IToulouse) = 436# D(IPoitiers, ITours) = 104# D(IPoitiers, ITroyes) = 444# ' distances between Reims and other towns D(IReims, IRennes) = 483# D(IReims, IRouen) = 230# D(IReims, IStEtienne) = 533# D(IReims, IStrasbourg) = 346# D(IReims, IToulouse) = 840# D(IReims, ITours) = 369# D(IReims, ITroyes) = 123# ' distances between Rennes and other towns D(IRennes, IRouen) = 300# D(IRennes, IStEtienne) = 660# D(IRennes, IStrasbourg) = 829# D(IRennes, IToulouse) = 676# D(IRennes, ITours) = 236# D(IRennes, ITroyes) = 485# ' distances between Rouen and other towns D(IRouen, IStEtienne) = 644# D(IRouen, IStrasbourg) = 576# D(IRouen, IToulouse) = 792# D(IRouen, ITours) = 277# D(IRouen, ITroyes) = 317# ' distances between Saint-Etienne and other towns D(IStEtienne, IStrasbourg) = 536# D(IStEtienne, IToulouse) = 527# D(IStEtienne, ITours) = 424# D(IStEtienne, ITroyes) = 399# ' distances between Strasbourg and other towns D(IStrasbourg, IToulouse) = 1015# D(IStrasbourg, ITours) = 715# D(IStrasbourg, ITroyes) = 365# ' distance between Toulouse et ITours, ITroyes D(IToulouse, ITours) = 535# D(IToulouse, ITroyes) = 786# ' distance Tours-Troyes } D(ITours, ITroyes) = 300# ' end by symmetry D(1, 1) = 0# FOR i = 2 TO NV FOR J = 1 TO i - 1 D(i, J) = D(J, i) NEXT J D(i, i) = 0# NEXT i RETURN 'End of file tanneal.bas