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 #define RANDOM 0 00016 #define REGRET 1 00017 00018 int main(int argc, char *argv[]) 00019 { 00025 00026 VRPH_version(); 00027 00028 char infile[VRPH_STRING_SIZE]; 00029 char solfile[VRPH_STRING_SIZE]; 00030 char outfile[VRPH_STRING_SIZE]; 00031 bool has_outfile=false, has_solfile=false; 00032 int i,j,n,num_ejected, num_trials, num_heur_sols, num_improvements; 00033 int *ejected_buff, *heur_solbuff, *ej_solbuff, *best_solbuff; 00034 int method=-1; 00035 clock_t start, stop; 00036 00037 // Default values 00038 bool verbose=false; 00039 00040 if(argc < 7 || (strncmp(argv[1],"-help",5)==0 || strcmp(argv[1],"-h")==0 || strcmp(argv[1],"--h")==0)) 00041 { 00042 fprintf(stderr,"Usage: %s -f vrp_file -j num_ejected -t num_trials -m method [-s sol_file -out out_file -n num_heur_sols -v]\n",argv[0]); 00043 fprintf(stderr, 00044 "\t num_ejected should be something less than 20 or so\n" 00045 "\t num_trials can be fairly large as the procedure is fast (say 1000)\n" 00046 "\t method must be 0 (RANDOM search), 1 (REGRET search)\n" 00047 "\t Options:\n" 00048 "\t Can start with a solution in sol_file or it will generate an initial\n" 00049 "\t solution for you\n" 00050 "\t Can write the final best solution discovered to out_file\n" 00051 "\t Adding -v will print verbose output\n"); 00052 exit(-1); 00053 } 00054 00055 bool has_filename=false; 00056 for(i=1;i<argc;i++) 00057 { 00058 if(strcmp(argv[i],"-f")==0) 00059 { 00060 strcpy(infile,argv[i+1]); 00061 has_filename=true; 00062 } 00063 } 00064 00065 if(has_filename==false) 00066 report_error("No input file given\n"); 00067 00068 n=VRPGetDimension(infile); 00069 // Get # of non-VRPH_DEPOT nodes 00070 VRP V(n); 00071 00072 // Declare some buffers for solutions, nodes to eject, etc. 00073 ejected_buff=new int[n+2]; 00074 heur_solbuff=new int[n+2]; 00075 ej_solbuff=new int[n+2]; 00076 best_solbuff=new int[n+2]; 00077 num_ejected=num_trials=0; 00078 num_heur_sols=1; 00079 00080 // Now process the options 00081 for(i=1;i<argc;i++) 00082 { 00083 if(strcmp(argv[i],"-v")==0) 00084 verbose=true; 00085 00086 if(strcmp(argv[i],"-j")==0) 00087 num_ejected=atoi(argv[i+1]); 00088 00089 if(strcmp(argv[i],"-n")==0) 00090 num_heur_sols=atoi(argv[i+1]); 00091 00092 if(strcmp(argv[i],"-s")==0) 00093 { 00094 has_solfile=true; 00095 num_heur_sols=0; 00096 strcpy(solfile,argv[i+1]); 00097 } 00098 00099 if(strcmp(argv[i],"-t")==0) 00100 num_trials=atoi(argv[i+1]); 00101 00102 if(strcmp(argv[i],"-out")==0) 00103 { 00104 has_outfile=true; 00105 strcpy(outfile,argv[i+1]); 00106 } 00107 00108 if(strcmp(argv[i],"-m")==0) 00109 { 00110 method=atoi(argv[i+1]); 00111 if(method!=RANDOM && method!=REGRET) 00112 { 00113 fprintf(stderr,"Method must be either 0 (RANDOM search) or 1 (REGRET search)\n"); 00114 exit(-1); 00115 } 00116 } 00117 } 00118 00119 00120 // Load the problem data 00121 V.read_TSPLIB_file(infile); 00122 ClarkeWright CW(n); 00123 double heur1; 00124 double best_heur_sol=VRP_INFINITY; 00125 double best_final_sol=VRP_INFINITY; 00126 double heur_time=0,ej_time=0; 00127 double lambda; 00128 double *heur_sols=new double[num_heur_sols]; 00129 double *final_sols=new double[num_heur_sols]; 00130 00131 for(i=0;i<num_heur_sols;i++) 00132 { 00133 // Generate a solution w/ RTR that should be a good starting point for the search 00134 start=clock(); 00135 lambda=.5+1.5*lcgrand(0); 00136 // Start with a clean VRP object 00137 V.reset(); 00138 CW.Construct(&V, lambda, false); 00139 if(verbose) 00140 printf("CW solution %d[%5.3f]: %f\n",i,lambda,V.get_total_route_length()-V.get_total_service_time()); 00141 V.RTR_solve(ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT+VRPH_USE_NEIGHBOR_LIST,30,5,2,.01,30,VRPH_LI_PERTURB, 00142 VRPH_FIRST_ACCEPT,false); 00143 stop=clock(); 00144 heur_time+=((double)(stop-start))/CLOCKS_PER_SEC; 00145 heur_sols[i]=V.get_total_route_length()-V.get_total_service_time(); 00146 if(verbose) 00147 printf("RTR solution %d: %f\n",i,V.get_total_route_length()-V.get_total_service_time()); 00148 00149 // Record the value of the first solution 00150 if(i==0) 00151 heur1=V.get_total_route_length()-V.get_total_service_time(); 00152 00153 if(i==0 || V.get_total_route_length()-V.get_total_service_time() <= best_heur_sol) 00154 { 00155 best_heur_sol = V.get_total_route_length()-V.get_total_service_time(); 00156 if(verbose) 00157 printf("Found best sol: %f\n",V.get_total_route_length()-V.get_total_service_time()); 00158 } 00159 // Export this solution to ej_solbuff 00160 V.export_solution_buff(ej_solbuff); 00161 00162 double heur_obj=V.get_total_route_length()-V.get_total_service_time(); 00163 if(verbose) 00164 printf("Starting ejection routines with solution %f\n",heur_obj); 00165 00166 num_improvements=0; 00167 double orig_obj=heur_obj; 00168 start=clock(); 00169 for(j=0;j<num_trials;j++) 00170 { 00171 // Start with the best solution derived from this RTR run 00172 V.import_solution_buff(ej_solbuff); 00173 // Now pick random nodes to eject - start by finding a random non-VRPH_DEPOT node 00174 int r=VRPH_DEPOT; 00175 while(r==VRPH_DEPOT) 00176 r=(int)(lcgrand(11)*(n-1)); 00177 00178 // Eject a set of random nodes near node r 00179 V.eject_neighborhood(r,num_ejected,ejected_buff); 00180 00181 if(method==REGRET) 00182 { 00183 // Inject them using "cheapest insertion with regret" 00184 V.inject_set(num_ejected, ejected_buff,VRPH_REGRET_SEARCH, 50); 00185 double regret_obj=V.get_total_route_length()-V.get_total_service_time(); 00186 if(regret_obj<orig_obj) 00187 { 00188 if(verbose) 00189 printf("Attempt %04d: REGRET improved original: %f<%f\n",j, regret_obj,orig_obj); 00190 V.export_solution_buff(ej_solbuff); 00191 orig_obj=regret_obj; 00192 num_improvements++; 00193 } 00194 } 00195 00196 if(method==RANDOM) 00197 { 00198 // Inject them again using a random order and cheapest insertion 00199 V.inject_set(num_ejected, ejected_buff,VRPH_RANDOM_SEARCH, 50); 00200 double random_obj=V.get_total_route_length(); 00201 if(random_obj<orig_obj) 00202 { 00203 if(verbose) 00204 printf("Attempt %04d: RANDOM improved original: %f<%f\n",j, random_obj,orig_obj); 00205 V.export_solution_buff(ej_solbuff); 00206 orig_obj=random_obj; 00207 num_improvements++; 00208 } 00209 } 00210 } 00211 // end j loop 00212 stop=clock(); 00213 ej_time+=(double)(stop-start)/CLOCKS_PER_SEC; 00214 00215 // Import the best solution we found 00216 V.import_solution_buff(ej_solbuff); 00217 if(V.get_total_route_length()-V.get_total_service_time()<best_final_sol) 00218 { 00219 best_final_sol=V.get_total_route_length()-V.get_total_service_time(); 00220 V.export_solution_buff(best_solbuff); 00221 } 00222 final_sols[i]=V.get_total_route_length()-V.get_total_service_time(); 00223 } 00224 00225 // Restore the best solution found 00226 V.import_solution_buff(best_solbuff); 00227 00228 00229 // Output is 00230 // heur[i] ej[i] 00231 // best_heur best_ej heur_time ej_time 00232 for(i=0;i<num_heur_sols;i++) 00233 printf("%5.3f %5.3f\n",heur_sols[i], final_sols[i]); 00234 printf("%5.3f %5.3f %5.3f %5.3f\n",best_heur_sol, 00235 V.get_total_route_length()-V.get_total_service_time(),heur_time,ej_time); 00236 00237 if(has_outfile) 00238 V.write_solution_file(outfile); 00239 00240 00241 // Clean up 00242 delete [] ejected_buff; 00243 delete [] heur_solbuff; 00244 delete [] ej_solbuff; 00245 delete [] best_solbuff; 00246 delete [] heur_sols; 00247 delete [] final_sols; 00248 00249 return 0; 00250 }