/*************************************************************** * 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 number of towns, the * * names and geographical coordinates in km of the 38 towns (The* * origin is an arbitrary 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: 5 * * * * 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: * * * * BREST --> NANTES --> * * RENNES --> CHERBOURG --> * * CAEN --> LE_MANS --> * * TOURS --> ORLEANS --> * * BOURGES --> LIMOGES --> * * POITIERS --> ANGOULEME --> * * PERIGUEUX --> BORDEAUX --> * * BAYONNE --> PAU --> * * TOULOUSE --> MONTPELLIER --> * * MARSEILLE --> NICE --> * * GRENOBLE --> LYON --> * * SAINT-ETIENNE --> CLERMONT-FERRAND --> * * AUXERRE --> TROYES --> * * DIJON --> MULHOUSE --> * * STRASBOURG --> NANCY --> * * METZ --> REIMS --> * * PARIS --> LE_HAVRE --> * * ROUEN --> CALAIS --> * * LILLE --> AMIENS --> * * * * NITER=1450 DMIN= 5630.00 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. * * ------------------------------------------------------------ * * * * C++ Release By J-P Moreau, Paris. * * (www.jpmoreau.fr) * ***************************************************************/ #include #include #include #include #define NBRVILLES 39 // index 0 not used #define MAXRAND 32767 typedef char NomVille[17]; NomVille CH[NBRVILLES], Vs[NBRVILLES]; int ICO[NBRVILLES][3]; // indices 0 non utilisé double D[NBRVILLES][NBRVILLES]; int L[NBRVILLES]; double C[NBRVILLES]; int ID[NBRVILLES][NBRVILLES]; int i,j, NV=38; int choice,diter,itermin,nbreiter,nmax; double DDMIN,DMAX,DMIN,DT,TP,X,Y; FILE *fp, *fp1; // I/O Text Files void TIME(); double DELTAT(); void ANNEAL(int,int *); void aff_L(int); void InitDist(); void main() { printf("\n Distances between towns (km):\n"); printf(" 1 : as the crow flies\n"); printf(" 2 : by road\n"); printf(" Your choice ( 1 or 2 ): "); scanf("%d", &choice); printf("\n Starting number of iterations: "); scanf("%d", &nbreiter); printf("\n Maximum number of iterations : "); scanf("%d", &nmax); printf("\n Increment value of iterations: "); scanf("%d", &diter); fp1 = fopen("villes.lst","w"); if (choice==1) { fprintf(fp1,"\n\n SALESMAN'S PROBLEM\n\n"); fprintf(fp1," NO TOWN COORDINATES (KM)\n"); fprintf(fp1," EAST SOUTH\n\n"); } // NV= Number of towns fp=fopen("villes.dat","r"); for (i=1; i<=NV; i++) { fscanf(fp,"%16s %d %d\n",CH[i],&ICO[i][1],&ICO[i][2]); if (choice==1) { fprintf(fp1,"%4d %16s %4d %4d\n",i,CH[i],ICO[i][1],ICO[i][2]); } } fclose(fp); for (i=1; i %s -->\n",Vs[L[i]],Vs[L[i+1]]); i=i+2; } fprintf(fp1,"\n NITER=%d DMIN= %8.2f Km.\n",itermin, DELTAT()); fclose(fp1); printf("\n\n Results in file villes.lst\n\n"); } //main() // GENERATE A RANDOM TIME void TIME() { int i5,it,j5,k5,n5; double r; for (i5=1; i50) goto a15; } // TIME() // Calculate total distance, DT double DELTAT() { double T; int i6; T=0.0; for (i6=1; i616000) goto a; J2=J+1; if (J2>NV) J2=J2-NV; a25: R=rand()/(1.0*MAXRAND); K=(int) (1 + floor(NV*R)); K2=K+1; if (K2>NV) K2=1; if(K==I) goto a25; if(K==J) goto a25; if(K<=I) { II=K; K=I; I=II; II=K2; K2=I2; I2=II; } if(K<=J) { II=K; K=J; J=II; II=K2; K2=J2; J2=II; } 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=rand()/(1.0*MAXRAND); if (DD/TP<=0.0) { if (DD/TP<-60) EX=1.0; else EX=exp(-DD/TP); } else { if (DD/TP>=60.0) EX=0.0; else EX=1.0/exp(DD/TP); } if (R1>EX) goto b; for (M=1; M<=I; M++) C[M]=L[M]; M=I+1; for (M1=J2; M1<=K; M1++) { C[M]=L[M1]; M++; } for (M1=I2; M1=60.0) EX=0.0; else EX=1.0/exp(DD/TP); } if(R1<=EX) { // aff_L(2); KF=(int) (I+floor(0.5+((J1-I)/2.0))); for(K=I; K<=KF; K++) { II=L[K]; L[K]=L[J1+I-K]; L[J1+I-K]=II; } // aff_L(3); } b: ;} // for LL TP=TP*0.9; DT=DELTAT(); DMAX=DT; if (DT