00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015 int main(int argc, char *argv[])
00016 {
00021
00022 VRPH_version();
00023
00024 char in[VRPH_STRING_SIZE];
00025 char out[VRPH_STRING_SIZE];
00026 char plotfile[VRPH_STRING_SIZE];
00027 char solfile[VRPH_STRING_SIZE];
00028 int i;
00029 int n;
00030
00031
00032 bool verbose=false;
00033 double starting_temperature = 2;
00034 double cooling_ratio = .99;
00035 int num_loops=200;
00036 int num_lambdas=3;
00037 int iters_per_loop=2;
00038 int nlist_size=10;
00039 int perturb_type=VRPH_LI_PERTURB ;
00040
00041 double lambda_vals[VRPH_MAX_NUM_LAMBDAS];
00042 bool new_lambdas=false;
00043 bool has_heuristics=false;
00044 bool has_outfile=false;
00045 bool has_plotfile=false;
00046 bool has_solfile=false;
00047 int heuristics=0;
00048
00049 if(argc<2 || (strncmp(argv[1],"-help",5)==0)||(strncmp(argv[1],"--help",6)==0)||(strncmp(argv[1],"-h",2)==0))
00050 {
00051 fprintf(stderr,"Usage: %s -f <vrp_input_file> [options]\n",argv[0]);
00052 fprintf(stderr,"Options:\n");
00053
00054 fprintf(stderr,"\t-help prints this help message\n");
00055
00056 fprintf(stderr,"\t-sol <solfile> begins with an existing solution contained\n");
00057 fprintf(stderr,"\t\t in solfile.\n");
00058
00059 fprintf(stderr,"\t-v prints verbose output to stdout\n");
00060
00061 fprintf(stderr,"\t-i <num_iters> runs the SA procedure for num_iters iterations\n");
00062 fprintf(stderr,"\t\t before cooling\n");
00063
00064 fprintf(stderr,"\t-n <num_loops> runs the SA procedure a total of num_loops times\n");
00065
00066 fprintf(stderr,"\t-t <starting_temperature> runs the SA procedure starting at\n");
00067 fprintf(stderr,"\t\t this temperature\n");
00068
00069 fprintf(stderr,"\t-c <cooling_ratio> runs the SA by decreasing the temperature by a\n");
00070 fprintf(stderr,"\t\t multiplicative factor of cooling_ratio every num_iters moves\n");
00071
00072 fprintf(stderr,"\t-h <heuristic> applies the specified heuristics (can be repeated)\n");
00073 fprintf(stderr,"\t\t default is ONE_POINT_MOVE, TWO_POINT_MOVE, and TWO_OPT\n");
00074 fprintf(stderr,"\t\t others available are OR_OPT, THREE_OPT, and CROSS_EXCHANGE\n");
00075 fprintf(stderr,"\t\t Example: -h OR_OPT -h THREE_OPT -h TWO_OPT\n");
00076
00077 fprintf(stderr,"\t-l <num_lambdas> runs the SA procedure from num_lambdas\n");
00078 fprintf(stderr,"\t\t different initial CW solutions using a random lambda chosen\n");
00079 fprintf(stderr,"\t\t from (0.5,2.0)\n");
00080 fprintf(stderr,"\t\t default is to use lambda in (.6, 1.4, 1.6).\n");
00081
00082 fprintf(stderr,"\t-s <nlist_size> uses the nlist_size nearest neighbors in the search\n");
00083 fprintf(stderr,"\t\t (default is 40).\n");
00084
00085 fprintf(stderr,"\t-o <out_file> writes the solution to the provided file\n");
00086 fprintf(stderr,"\t-plot <plot_file> plots the best solution to the provided file\n");
00087 exit(-1);
00088 }
00089
00090
00091 bool has_filename=false;
00092 for(i=1;i<argc;i++)
00093 {
00094 if(strcmp(argv[i],"-f")==0)
00095 {
00096
00097 strncpy(in,argv[i+1],strlen(argv[i+1]));
00098 in[strlen(argv[i+1])]='\0';
00099 has_filename=true;
00100 }
00101 }
00102 if(has_filename==false)
00103 {
00104 fprintf(stderr,"No input file given\nUsage: %s -f <filename> [options]\n",argv[0]);
00105 exit(-1);
00106 }
00107
00108 n=VRPGetDimension(in);
00109 VRP V(n);
00110
00111
00112 for(i=1;i<argc;i++)
00113 {
00114 if(strcmp(argv[i],"-v")==0)
00115 verbose=true;
00116
00117 if(strcmp(argv[i],"-t")==0)
00118 starting_temperature=(double)(atof(argv[i+1]));
00119
00120 if(strcmp(argv[i],"-i")==0)
00121 iters_per_loop=atoi(argv[i+1]);
00122
00123 if(strcmp(argv[i],"-n")==0)
00124 num_loops=atoi(argv[i+1]);
00125
00126 if(strcmp(argv[i],"-h")==0)
00127 {
00128 has_heuristics=true;
00129 if(strcmp(argv[i+1],"ONE_POINT_MOVE")==0)
00130 heuristics+=ONE_POINT_MOVE;
00131 if(strcmp(argv[i+1],"TWO_POINT_MOVE")==0)
00132 heuristics+=TWO_POINT_MOVE;
00133 if(strcmp(argv[i+1],"TWO_OPT")==0)
00134 heuristics+=TWO_OPT;
00135 if(strcmp(argv[i+1],"OR_OPT")==0)
00136 heuristics+=OR_OPT;
00137 if(strcmp(argv[i+1],"THREE_OPT")==0)
00138 heuristics+=THREE_OPT;
00139 if(strcmp(argv[i+1],"CROSS_EXCHANGE")==0)
00140 heuristics+=CROSS_EXCHANGE;
00141 if(strcmp(argv[i+1],"THREE_POINT_MOVE")==0)
00142 heuristics+=THREE_POINT_MOVE;
00143 }
00144
00145 if(strcmp(argv[i],"-l")==0)
00146 {
00147 new_lambdas=true;
00148 num_lambdas = atoi(argv[i+1]);
00149
00150 if(num_lambdas>VRPH_MAX_NUM_LAMBDAS)
00151 {
00152 fprintf(stderr,"%d>VRPH_MAX_NUM_LAMBDAS\n",num_lambdas);
00153 exit(-1);
00154 }
00155
00156
00157 printf("Creating %d random lambdas\n",num_lambdas);
00158 for(int j=0;j<num_lambdas;j++)
00159 {
00160
00161 lambda_vals[j] = 0.5 + 1.5*((double)lcgrand(0));
00162 }
00163 }
00164
00165 if(strcmp(argv[i],"-sol")==0)
00166 {
00167 has_solfile=true;
00168 strcpy(solfile,argv[i+1]);
00169 }
00170
00171 if(strcmp(argv[i],"-c")==0)
00172 cooling_ratio=(double)(atof(argv[i+1]));
00173
00174 if(strcmp(argv[i],"-s")==0)
00175 nlist_size=atoi(argv[i+1]);
00176
00177 if(strcmp(argv[i],"-p")==0)
00178 {
00179 perturb_type=atoi(argv[i+1]);
00180 if(perturb_type!=0 && perturb_type!=1)
00181 {
00182 fprintf(stderr,"Perturb type must be 0 or 1!\n");
00183 exit(-1);
00184 }
00185 }
00186
00187 if(strcmp(argv[i],"-o")==0)
00188 {
00189 has_outfile=true;
00190 strcpy(out,argv[i+1]);
00191
00192 }
00193
00194 if(strcmp(argv[i],"-plot")==0)
00195 {
00196 has_plotfile=true;
00197 strcpy(plotfile,argv[i+1]);
00198
00199 }
00200
00201 }
00202
00203 if(new_lambdas==false)
00204 {
00205 num_lambdas=3;
00206 lambda_vals[0]=.6;
00207 lambda_vals[1]=1.4;
00208 lambda_vals[2]=1.6;
00209 }
00210
00211 if(has_heuristics==false)
00212 heuristics=ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT;
00213
00214
00215
00216 V.read_TSPLIB_file(in);
00217
00218
00219
00220 V.create_neighbor_lists(VRPH_MIN(MAX_NEIGHBORLIST_SIZE,n));
00221 ClarkeWright CW(n);
00222
00223 double best_obj=VRP_INFINITY;
00224 double this_obj, start_obj;
00225 int *best_sol=new int[n+2];
00226
00227 time_t start=clock();
00228 if(has_solfile == false)
00229 {
00230 for(i=0;i<num_lambdas;i++)
00231 {
00232 CW.Construct(&V,lambda_vals[i], false);
00233
00234 if(verbose)
00235 printf("CW[%f] solution: %f\n",lambda_vals[i], V.get_total_route_length());
00236
00237 this_obj = V.SA_solve(heuristics, starting_temperature, cooling_ratio, iters_per_loop,
00238 num_loops, nlist_size, verbose);
00239
00240 if(V.get_best_total_route_length()<best_obj)
00241 {
00242 best_obj=V.get_best_total_route_length();
00243 V.export_canonical_solution_buff(best_sol);
00244 }
00245
00246 if(verbose)
00247 printf("Improved solution: %f\n",this_obj);
00248
00249 }
00250 }
00251 else
00252 {
00253 V.read_solution_file(solfile);
00254 start_obj=V.get_total_route_length();
00255 this_obj = V.SA_solve(heuristics, starting_temperature, cooling_ratio, iters_per_loop,
00256 num_loops, nlist_size, verbose);
00257 if(V.get_best_total_route_length()<best_obj)
00258 {
00259 best_obj=V.get_best_total_route_length();
00260 V.export_canonical_solution_buff(best_sol);
00261 }
00262 if(verbose)
00263 printf("Improved solution: %f\n",this_obj);
00264
00265 }
00266
00267
00268 V.import_solution_buff(best_sol);
00269
00270 delete [] best_sol;
00271
00272 if(has_outfile)
00273 V.write_solution_file(out);
00274 best_obj=this_obj;
00275
00276 if(verbose)
00277 printf("Solution before cleaning individual routes: %5.3f\n",V.get_total_route_length()-
00278 V.get_total_service_time());
00279
00280 for(i=1;i<=V.get_total_number_of_routes();i++)
00281 V.clean_route(i,ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT+THREE_OPT+THREE_POINT_MOVE);
00282 if(verbose)
00283 {
00284 printf("Solution after cleaning individual routes: %5.3f\n",V.get_total_route_length()-
00285 V.get_total_service_time());
00286 V.summary();
00287 V.print_stats();
00288 }
00289
00290 if(has_plotfile)
00291 {
00292 #if !HAS_PLPLOT
00293 fprintf(stderr,"Need PLPLOT to plot solution\n");
00294 exit(-1);
00295 #endif
00296
00297 V.plot(plotfile);
00298
00299 }
00300
00301 time_t stop=clock();
00302 double elapsed=(double)(stop-start)/CLOCKS_PER_SEC;
00303
00304 printf("%d %5.3f %5.2f",V.get_total_number_of_routes(),
00305 V.get_total_route_length()-V.get_total_service_time(),
00306 elapsed);
00307 if(V.get_best_known()>0 && V.get_best_known()<VRP_INFINITY)
00308 printf(" %1.3f\n",(V.get_total_route_length()-V.get_total_service_time())/V.get_best_known());
00309 else
00310 printf("\n");
00311
00312 return 0;
00313 }
00314
00315