00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014 #include <time.h>
00015
00016 int main(int argc, char *argv[])
00017 {
00023
00024 VRPH_version();
00025
00026 char out[VRPH_STRING_SIZE];
00027 char plot_file[VRPH_STRING_SIZE];
00028 char sol_file[VRPH_STRING_SIZE];
00029 char fixed_edges_file[VRPH_STRING_SIZE];
00030 int i,n;
00031 clock_t start, stop;
00032 double elapsed;
00033
00034
00035 bool verbose=false;
00036 int intensity =30;
00037 int max_tries=5;
00038 int num_lambdas=3;
00039 int num_perturbs=1;
00040 int nlist_size=40;
00041 int perturb_type=VRPH_LI_PERTURB ;
00042 int accept_type=VRPH_FIRST_ACCEPT;
00043 int neighbor_lists=VRPH_USE_NEIGHBOR_LIST;
00044 int tabu=0;
00045 int tabu_list_size=0;
00046
00047
00048 double lambda_vals[VRPH_MAX_NUM_LAMBDAS];
00049 bool new_lambdas=false;
00050 bool has_heuristics=false;
00051 bool has_outfile=false;
00052 bool has_plot_file=false;
00053 bool has_sol_file=false;
00054 bool has_fixed_edges_file=false;
00055 int heuristics=0;
00056 double dev=.01;
00057 int *final_sol;
00058 double final_obj=VRP_INFINITY;
00059 bool do_pdf=false;
00060 int *my_sol_buff;
00061
00062
00063 if(argc<2 || (strncmp(argv[1],"-help",5)==0)||(strncmp(argv[1],"--help",6)==0)||(strncmp(argv[1],"-h",2)==0))
00064 {
00065 fprintf(stderr,"Usage: %s -f <vrp_input_file> [options]\n",argv[0]);
00066 fprintf(stderr,"Options:\n");
00067
00068 fprintf(stderr,"\t-help prints this help message\n");
00069
00070 fprintf(stderr,"\t-a <accept_type> 0 for VRPH_FIRST_ACCEPT or 1 for VRPH_BEST_ACCEPT\n\t\t(default is VRPH_FIRST_ACCEPT)\n");
00071
00072 fprintf(stderr,"\t-d <deviation> runs the RTR search with given deviation\n");
00073 fprintf(stderr,"\t\t default is dev=.01\n");
00074
00075 fprintf(stderr,"\t-fix <fixed_edge_file> will fix all of the edges in the provided file\n");
00076
00077 fprintf(stderr,"\t-h <heuristic> applies the specified heuristics (can be repeated)\n");
00078 fprintf(stderr,"\t\t default is ONE_POINT_MOVE, TWO_POINT_MOVE, and TWO_OPT\n");
00079 fprintf(stderr,"\t\t others available are OR_OPT, THREE_OPT, and CROSS_EXCHANGE\n");
00080 fprintf(stderr,"\t\t Example: -h OR_OPT -h THREE_OPT -h TWO_OPT -h ONE_POINT_MOVE\n");
00081 fprintf(stderr,"\t\t Setting -h KITCHEN_SINK applies all heuristics in the \n");
00082 fprintf(stderr,"\t\t improvement phase\n");
00083
00084 fprintf(stderr,"\t-sol <sol_file> begins with an existing solution contained\n");
00085 fprintf(stderr,"\t\t in sol_file\n");
00086
00087 fprintf(stderr,"\t-v prints verbose output to stdout\n");
00088
00089 fprintf(stderr,"\t-k <intensity> runs the RTR search with the provided intensity\n\t\t(default is 30)\n");
00090
00091 fprintf(stderr,"\t-L <num_lambdas> runs the RTR procedure from num_lambdas\n");
00092 fprintf(stderr,"\t\t different initial solutions using a random lambda chosen\n");
00093 fprintf(stderr,"\t\t from (0.5,2.0)\n");
00094 fprintf(stderr,"\t\t default is to use lambda in {.6, 1.4, 1.6}.\n");
00095
00096 fprintf(stderr,"\t-m <max_tries> gives up after not beating a local minimum after\n");
00097 fprintf(stderr,"\t\t max_tries consecutive attempts (default is 5)\n");
00098
00099 fprintf(stderr,"\t-N <nlist_size> uses the nlist_size nearest neighbors in the search\n");
00100 fprintf(stderr,"\t\t default is 25. Using -N 0 will not use neighbor lists at all\n");
00101
00102 fprintf(stderr,"\t-P <num_perturbs> perturbs the current solution num_perturbs times\n\t\t(default is 1)\n");
00103
00104 fprintf(stderr,"\t-p <perturb_type> 0 for VRPH_LI_PERTURB or 1 for VRPH_OSMAN_PERTURB\n");
00105
00106 fprintf(stderr,"\t-plot <plot_file> plots the best solution to the provided file.\n");
00107 fprintf(stderr,"\t\t This requires a working PLPlot installation\n");
00108
00109 fprintf(stderr,"\t-pdf will create a .pdf from the .ps file created by -plot\n");
00110
00111 fprintf(stderr,"\t-r will search the neighborhood in a random fashion\n");
00112
00113 fprintf(stderr,"\t-t <tabu_list_size> will use a primitive Tabu Search in the uphill phase\n");
00114
00115 fprintf(stderr,"\t-out <out_file> writes the solution to the provided file\n");
00116
00117
00118
00119 exit(-1);
00120 }
00121
00122 bool has_filename=false;
00123 char *infile=NULL;
00124 for(i=1;i<argc;i++)
00125 {
00126 if(strcmp(argv[i],"-f")==0)
00127 {
00128
00129 has_filename=true;
00130 infile=argv[i+1];
00131 }
00132 }
00133 if(has_filename==false)
00134 {
00135 fprintf(stderr,"No input file given\nUsage: %s -f <filename> [options]\n",argv[0]);
00136 exit(-1);
00137 }
00138
00139
00140 n=VRPGetDimension(infile);
00141 int num_days=VRPGetNumDays(infile);
00142 my_sol_buff=new int[n+2];
00143
00144
00145 VRP V(n,num_days);
00146
00147
00148
00149
00150 final_sol=new int[n+2];
00151
00152
00153 for(i=2;i<argc;i++)
00154 {
00155 if(strcmp(argv[i],"-a")==0)
00156 {
00157 accept_type=atoi(argv[i+1]);
00158 if( (accept_type!=0) && (accept_type !=1))
00159 report_error("%s: %s: accept_type must be 0 or 1\n");
00160
00161 if(accept_type==1)
00162 accept_type=VRPH_BEST_ACCEPT;
00163 else
00164 accept_type=VRPH_FIRST_ACCEPT;
00165 }
00166
00167 if(strcmp(argv[i],"-d")==0)
00168 dev=atof(argv[i+1]);
00169
00170 if(strcmp(argv[i],"-D")==0)
00171 intensity=atoi(argv[i+1]);
00172
00173 if(strcmp(argv[i],"-fix")==0)
00174 {
00175 has_fixed_edges_file=true;
00176 strcpy(fixed_edges_file,argv[i+1]);
00177 }
00178
00179 if(strcmp(argv[i],"-h")==0)
00180 {
00181 has_heuristics=true;
00182 if(strcmp(argv[i+1],"ONE_POINT_MOVE")==0)
00183 heuristics|=ONE_POINT_MOVE;
00184 if(strcmp(argv[i+1],"TWO_POINT_MOVE")==0)
00185 heuristics|=TWO_POINT_MOVE;
00186 if(strcmp(argv[i+1],"TWO_OPT")==0)
00187 heuristics|=TWO_OPT;
00188 if(strcmp(argv[i+1],"OR_OPT")==0)
00189 heuristics|=OR_OPT;
00190 if(strcmp(argv[i+1],"THREE_OPT")==0)
00191 heuristics|=THREE_OPT;
00192 if(strcmp(argv[i+1],"CROSS_EXCHANGE")==0)
00193 heuristics|=CROSS_EXCHANGE;
00194 if(strcmp(argv[i+1],"THREE_POINT_MOVE")==0)
00195 heuristics|=THREE_POINT_MOVE;
00196 if(strcmp(argv[i+1],"KITCHEN_SINK")==0)
00197 heuristics|=KITCHEN_SINK;
00198 }
00199
00200 if(strcmp(argv[i],"-k")==0)
00201 max_tries=atoi(argv[i+1]);
00202
00203 if(strcmp(argv[i],"-L")==0)
00204 {
00205 new_lambdas=true;
00206 num_lambdas = atoi(argv[i+1]);
00207
00208 if(num_lambdas>VRPH_MAX_NUM_LAMBDAS)
00209 {
00210 fprintf(stderr,"%d>VRPH_MAX_NUM_LAMBDAS\n",num_lambdas);
00211 exit(-1);
00212 }
00213
00214 for(int j=0;j<num_lambdas;j++)
00215 {
00216
00217 lambda_vals[j] = 0.5 + 1.5*((double)lcgrand(1));
00218 }
00219 }
00220
00221 if(strcmp(argv[i],"-N")==0)
00222 nlist_size=atoi(argv[i+1]);
00223
00224 if(strcmp(argv[i],"-out")==0)
00225 {
00226 has_outfile=true;
00227 strcpy(out,argv[i+1]);
00228 }
00229
00230 if(strcmp(argv[i],"-plot")==0)
00231 {
00232 has_plot_file=true;
00233 strcpy(plot_file,argv[i+1]);
00234 }
00235
00236 if(strcmp(argv[i],"-p")==0)
00237 {
00238 perturb_type=atoi(argv[i+1]);
00239 if(perturb_type!=0 && perturb_type!=1)
00240 {
00241 fprintf(stderr,"Perturb type must be 0 or 1!\n");
00242 exit(-1);
00243 }
00244 }
00245
00246 if(strcmp(argv[i],"-P")==0)
00247 num_perturbs=atoi(argv[i+1]);
00248
00249 if(strcmp(argv[i],"-pdf")==0)
00250 do_pdf=true;
00251
00252
00253
00254 if(strcmp(argv[i],"-sol")==0)
00255 {
00256 has_sol_file=true;
00257 strcpy(sol_file,argv[i+1]);
00258 }
00259
00260 if(strcmp(argv[i],"-t")==0)
00261 {
00262 tabu=VRPH_TABU;
00263 tabu_list_size=atoi(argv[i+1]);
00264 }
00265
00266 if(strcmp(argv[i],"-v")==0)
00267 verbose=true;
00268
00269 }
00270
00271
00272 V.read_TSPLIB_file(infile);
00273
00274 if(num_days>1)
00275 {
00276 printf("Multi-day problem loaded (%d days). Will run only on day 1\n",
00277 num_days);
00278 V.set_daily_demands(1);
00279 V.set_daily_service_times(1);
00280 }
00281
00282
00283
00284 if(new_lambdas==false)
00285 {
00286
00287 num_lambdas=3;
00288 lambda_vals[0]=.6;
00289 lambda_vals[1]=1.4;
00290 lambda_vals[2]=1.6;
00291 }
00292
00293
00294 if(nlist_size==0)
00295
00296 neighbor_lists=0;
00297 else
00298 neighbor_lists=VRPH_USE_NEIGHBOR_LIST;
00299 heuristics|=neighbor_lists;
00300
00301 if(has_heuristics==false)
00302
00303 heuristics|=(ONE_POINT_MOVE|TWO_POINT_MOVE|TWO_OPT);
00304
00305
00306
00307 heuristics+=tabu;
00308
00309
00310 ClarkeWright CW(n);
00311
00312 if(has_fixed_edges_file)
00313 {
00314 V.read_fixed_edges(fixed_edges_file);
00315 if(has_fixed_edges_file)
00316 heuristics |= VRPH_FIXED_EDGES;
00317 }
00318
00319 start=clock();
00320 if(!has_sol_file)
00321 {
00322
00323 for(i=0;i<num_lambdas;i++)
00324 {
00325
00326 V.reset();
00327
00328
00329 CW.Construct(&V,lambda_vals[i], false);
00330 CW.has_savings_matrix=false;
00331
00332 if(V.get_total_route_length()-V.get_total_service_time() < final_obj)
00333 {
00334 final_obj=V.get_total_route_length()-V.get_total_service_time();
00335 V.export_canonical_solution_buff(final_sol);
00336 }
00337
00338 if(verbose)
00339 printf("CW solution %d[L=%1.4f]: %5.4f\n",i,lambda_vals[i], V.get_total_route_length());
00340
00341
00342 V.RTR_solve(heuristics, intensity, max_tries, num_perturbs, dev, nlist_size,
00343 perturb_type, accept_type, verbose);
00344
00345
00346 V.get_best_sol_buff(my_sol_buff);
00347 V.import_solution_buff(my_sol_buff);
00348 if(V.get_total_route_length()-V.get_total_service_time() < final_obj)
00349 {
00350 final_obj = V.get_total_route_length()-V.get_total_service_time();
00351 V.export_canonical_solution_buff(final_sol);
00352 }
00353
00354 if(verbose)
00355 printf("%5.2f\n",V.get_best_total_route_length()-V.get_total_service_time());
00356
00357
00358 V.set_best_total_route_length(VRP_INFINITY);
00359 }
00360 }
00361 else
00362 {
00363
00364 V.read_solution_file(sol_file);
00365 printf("Read in solution:\n");
00366 V.show_routes();
00367
00368
00369 V.set_best_total_route_length(V.get_total_route_length());
00370
00371
00372 V.RTR_solve(heuristics, intensity, max_tries, num_perturbs, dev, nlist_size,
00373 perturb_type, accept_type,verbose);
00374
00375 V.export_canonical_solution_buff(final_sol);
00376 }
00377
00378 stop=clock();
00379
00380
00381 V.import_solution_buff(final_sol);
00382
00383 elapsed=(double)(stop-start)/CLOCKS_PER_SEC;
00384
00385 if(verbose)
00386 {
00387 V.summary();
00388 V.show_routes();
00389 V.print_stats();
00390 printf("\n");
00391 }
00392
00393 if(has_outfile)
00394 V.write_solution_file(out);
00395
00396 if(has_plot_file)
00397 {
00398 #if !HAS_PLPLOT
00399 fprintf(stderr,"Need PLPLOT to plot solution\n");
00400 exit(-1);
00401 #endif
00402
00403 bool plot_success=V.plot(plot_file);
00404 if(plot_success && do_pdf)
00405 {
00406 char pdf_string[VRPH_STRING_SIZE];
00407 sprintf(pdf_string,"%s %s",VRPH_EPS_EXE,plot_file);
00408 system(pdf_string);
00409 }
00410 }
00411
00412
00413 printf("%d %5.3f %5.2f",V.get_total_number_of_routes(),
00414 V.get_total_route_length()-V.get_total_service_time(),
00415 elapsed);
00416 if(V.get_best_known()>0 && V.get_best_known()<VRP_INFINITY)
00417 printf(" %1.3f\n",(V.get_total_route_length()-V.get_total_service_time())/V.get_best_known());
00418 else
00419 printf("\n");
00420
00421 delete [] my_sol_buff;
00422 delete [] final_sol;
00423
00424 return 0;
00425
00426
00427
00428 }
00429
00430