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 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 // Default values 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 // Get the input file name 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 // Now process the options 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 // Fill the array with random values 00157 printf("Creating %d random lambdas\n",num_lambdas); 00158 for(int j=0;j<num_lambdas;j++) 00159 { 00160 // Generate a random lambda in (0.5,2) 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; //default 00213 00214 00215 // Load the problem data 00216 V.read_TSPLIB_file(in); 00217 00218 // Create the neighbor_lists-we may use a smaller size depending on the parameter 00219 // but we have the largest possible here... 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 // Restore the best solution found 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 // Clean up the individual routes since the SA routine doesn't do this for us 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 // Print results to stdout 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