00001
00002
00003
00004
00005
00006
00007
00008
00009
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
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
00070 VRP V(n);
00071
00072
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
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
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
00134 start=clock();
00135 lambda=.5+1.5*lcgrand(0);
00136
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
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
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
00172 V.import_solution_buff(ej_solbuff);
00173
00174 int r=VRPH_DEPOT;
00175 while(r==VRPH_DEPOT)
00176 r=(int)(lcgrand(11)*(n-1));
00177
00178
00179 V.eject_neighborhood(r,num_ejected,ejected_buff);
00180
00181 if(method==REGRET)
00182 {
00183
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
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
00212 stop=clock();
00213 ej_time+=(double)(stop-start)/CLOCKS_PER_SEC;
00214
00215
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
00226 V.import_solution_buff(best_solbuff);
00227
00228
00229
00230
00231
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
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 }