VRPH
1.0
|
00001 00002 // // 00003 // This file is part of the VRPH software package for // 00004 // generating solutions to vehicle routing problems. // 00005 // VRPH was developed by Chris Groer (cgroer@gmail.com). // 00006 // // 00007 // (c) Copyright 2010 Chris Groer. // 00008 // All Rights Reserved. VRPH is licensed under the // 00009 // Common Public License. See LICENSE file for details. // 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 // Default parameter settings 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 // Get the input file name 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 // Get # of non-VRPH_DEPOT nodes 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 // Allocate the buffer for the final solution 00150 final_sol=new int[n+2]; 00151 00152 // Parse command line 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 // Generate a random lambda 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 // Load the problem data 00272 V.read_TSPLIB_file(infile); 00273 // If we have more than one day, just run alg. on day 1 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 // Start processing the input options 00284 if(new_lambdas==false) 00285 { 00286 // Use .6, 1.4, 1.6 00287 num_lambdas=3; 00288 lambda_vals[0]=.6; 00289 lambda_vals[1]=1.4; 00290 lambda_vals[2]=1.6; 00291 } 00292 00293 // Start constructing the list of optional heuristics we will we use 00294 if(nlist_size==0) 00295 // No neighbor lists 00296 neighbor_lists=0; 00297 else 00298 neighbor_lists=VRPH_USE_NEIGHBOR_LIST; 00299 heuristics|=neighbor_lists; 00300 00301 if(has_heuristics==false) 00302 // Use default set of operators 00303 heuristics|=(ONE_POINT_MOVE|TWO_POINT_MOVE|TWO_OPT); 00304 00305 00306 // Add in Tabu Search if requested 00307 heuristics+=tabu; 00308 00309 // Declare a CW object of the right size 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 // No solution imported - start from scratch 00323 for(i=0;i<num_lambdas;i++) 00324 { 00325 // Empty the solution warehouse and set nodes to unrouted 00326 V.reset(); 00327 00328 // Construct a new Clarke Wright solution 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 // Run the record-to-record travel algorithm with the given parameters 00342 V.RTR_solve(heuristics, intensity, max_tries, num_perturbs, dev, nlist_size, 00343 perturb_type, accept_type, verbose); 00344 00345 // Check for a new global best solution - recall the best solution found 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 // Reset best 00358 V.set_best_total_route_length(VRP_INFINITY); 00359 } 00360 } 00361 else 00362 { 00363 // Import a solution from the file and call it the best so far 00364 V.read_solution_file(sol_file); 00365 printf("Read in solution:\n"); 00366 V.show_routes(); 00367 // CSG - is the line below necessary? 00368 //V.export_solution_buff(V.best_sol_buff); 00369 V.set_best_total_route_length(V.get_total_route_length()); 00370 00371 // Now improve it 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 // Restore the best solution found 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 // Print results to stdout 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