00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015
00016 bool OrOpt::search(class VRP *V, int a, int len, int rules)
00017 {
00022
00023
00024 VRPMove M, BestM;
00025 BestM.savings=VRP_INFINITY;
00026 int i,b,c,d;
00027 int string_end;
00028 int str[10];
00029
00030 int accept_type;
00031
00032
00033 accept_type=VRPH_FIRST_ACCEPT;
00034
00035 if( (rules & VRPH_FIRST_ACCEPT) > 0)
00036 accept_type=VRPH_FIRST_ACCEPT;
00037 if( (rules & VRPH_BEST_ACCEPT) > 0)
00038 accept_type=VRPH_BEST_ACCEPT;
00039 if( (rules & VRPH_LI_ACCEPT) > 0)
00040 accept_type=VRPH_LI_ACCEPT;
00041
00042 string_end = V->get_string_end(a,len);
00043
00044 if(string_end==-1)
00045 {
00046
00047 return false;
00048 }
00049
00050 if(rules & VRPH_FIXED_EDGES)
00051 {
00052
00053 i=VRPH_MAX(V->pred_array[a],VRPH_DEPOT);
00054
00055 if( V->fixed[i][a] )
00056 return false;
00057
00058 i=VRPH_MAX(V->next_array[string_end],VRPH_DEPOT);
00059 if( V->fixed[string_end][i])
00060 return false;
00061 }
00062
00063
00064
00065 str[0]=a;
00066 for(i=1;i<len;i++)
00067 {
00068 str[i]= V->next_array[str[i-1]];
00069 if(str[i]<=VRPH_DEPOT)
00070 return false;
00071 }
00072
00073 V->create_search_neighborhood(a, rules);
00074
00075 int *old_sol=NULL;
00076 if(rules & VRPH_TABU)
00077 {
00078
00079 old_sol=new int[V->num_original_nodes+2];
00080 V->export_solution_buff(old_sol);
00081 }
00082
00083 for(i=0;i<V->search_size;i++)
00084 {
00085 c=V->search_space[i];
00086
00087 if(c!=VRPH_DEPOT)
00088 {
00089
00090 d=VRPH_MAX(V->next_array[c],0);
00091 b=VRPH_MAX(V->pred_array[c],0);
00092
00093 int flag=0;
00094 if(d==VRPH_DEPOT)
00095 flag=1;
00096
00097
00098
00099 for(int j=0;j<len;j++)
00100 {
00101 if(str[j]==c || str[j]==d)
00102
00103 flag=1;
00104 }
00105 if(flag==0)
00106 {
00107
00108
00109 if(evaluate(V,a,len,c,d,rules, &M)==true)
00110 {
00111
00112 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON))
00113 {
00114 if(move(V, &M)==false)
00115 report_error("%s: move error 1\n",__FUNCTION__);
00116 else
00117 {
00118 if(!(rules & VRPH_TABU))
00119 return true;
00120 else
00121 {
00122
00123
00124 if(V->check_tabu_status(&M, old_sol))
00125 {
00126 delete [] old_sol;
00127 return true;
00128 }
00129
00130 }
00131 }
00132 }
00133
00134 if(accept_type == VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00135 {
00136 if(M.is_better(V, &BestM, rules))
00137 BestM=M;
00138
00139 }
00140
00141 if(accept_type == VRPH_LI_ACCEPT)
00142 {
00143
00144 if(M.savings<-VRPH_EPSILON)
00145 {
00146 if(move(V, &M)==false)
00147 report_error("%s: move error 2\n",__FUNCTION__);
00148 else
00149 {
00150 if(!(rules & VRPH_TABU))
00151 return true;
00152 else
00153 {
00154
00155
00156 if(V->check_tabu_status(&M, old_sol))
00157 {
00158 delete [] old_sol;
00159 return true;
00160 }
00161
00162 }
00163 }
00164 }
00165 else
00166 {
00167
00168 if(M.is_better(V, &BestM, rules))
00169 BestM=M;
00170 }
00171 }
00172 }
00173 }
00174 }
00175 }
00176
00177 if(accept_type == VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00178 {
00179 if(old_sol)
00180 delete [] old_sol;
00181 return false ;
00182 }
00183
00184 if(move(V,&BestM)==true)
00185 {
00186 if(!(rules & VRPH_TABU))
00187 return true;
00188 }
00189
00190 if(rules & VRPH_TABU)
00191 {
00192
00193
00194 if(V->check_tabu_status(&BestM, old_sol))
00195 {
00196 delete [] old_sol;
00197 return true;
00198 }
00199 else
00200 {
00201 delete [] old_sol;
00202 return false;
00203 }
00204 }
00205
00206
00207 report_error("%s: move error\n",__FUNCTION__);
00208 return false;
00209
00210
00211 }
00212
00213 bool OrOpt::route_search(VRP *V, int r1, int r2, int len, int rules)
00214 {
00220
00221 VRPMove M, BestM;
00222 BestM.savings=VRP_INFINITY;
00223 int c,d;
00224 int accept_type;
00225
00226
00227 accept_type=VRPH_FIRST_ACCEPT;
00228
00229 if( (rules & VRPH_FIRST_ACCEPT) > 0)
00230 accept_type=VRPH_FIRST_ACCEPT;
00231 if( (rules & VRPH_BEST_ACCEPT) > 0)
00232 accept_type=VRPH_BEST_ACCEPT;
00233 if( (rules & VRPH_LI_ACCEPT) > 0)
00234 accept_type=VRPH_LI_ACCEPT;
00235
00236 int j;
00237 j= V->route[r1].start;
00238 while(j!=VRPH_DEPOT)
00239 {
00240
00241 c= V->route[r2].start;
00242 while(c!=VRPH_DEPOT)
00243 {
00244 d=VRPH_MAX(V->next_array[c],0);
00245 if(evaluate(V,j,len,c,d,rules, &M)==true)
00246 {
00247 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00248 {
00249
00250 if(move(V,&M)==false)
00251 report_error("%s: first accept move returns false",__FUNCTION__);
00252 else
00253 return true;
00254 }
00255
00256
00257 if(accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT)
00258 {
00259 if(M.is_better(V, &BestM, rules))
00260 BestM=M;
00261
00262 }
00263
00264 }
00265
00266
00267 c=d;
00268 }
00269
00270
00271 j=VRPH_MAX(V->next_array[j],0);
00272 }
00273
00274 if(accept_type==VRPH_FIRST_ACCEPT)
00275 return false;
00276
00277 if(BestM.savings==VRP_INFINITY)
00278 return false;
00279
00280 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00281 {
00282
00283
00284 if(move(V,&BestM)==false)
00285 report_error("%s: first accept move returns false\n",__FUNCTION__);
00286 else
00287 return true;
00288
00289 }
00290
00291 report_error("%s: shouldn't get here...\n",__FUNCTION__);
00292
00293 return false;
00294
00295 }
00296
00297 bool OrOpt::evaluate(class VRP *V, int a, int len, int c, int d, int rules, VRPMove *M)
00298 {
00303
00304 V->num_evaluations[OR_OPT_INDEX]++;
00305
00306 M->evaluated_savings=false;
00307
00308 if(rules & VRPH_FIXED_EDGES)
00309 {
00310
00311 if( V->fixed[c][d] )
00312 return false;
00313 }
00314
00315 if(V->routed[a]==false || V->routed[c]==false ||
00316 V->routed[d]==false )
00317 return false;
00318
00319 int a_route, c_route;
00320
00321 M->eval_arguments[0]=a;M->eval_arguments[1]=len;
00322 M->eval_arguments[2]=c;M->eval_arguments[3]=d;
00323
00324
00325 if(c!=VRPH_DEPOT && VRPH_MAX(V->next_array[c],0)!=d )
00326 report_error("%s: c-d not an edge!\n",__FUNCTION__);
00327
00328
00329 if(c==VRPH_DEPOT && VRPH_MAX(V->pred_array[d],0)!=c)
00330 report_error("%s: c-d not an edge!\n",__FUNCTION__);
00331
00332
00333 a_route= V->route_num[a];
00334 if(c!=VRPH_DEPOT)
00335 c_route= V->route_num[c];
00336 else
00337 c_route= V->route_num[d];
00338
00339
00340 if( (rules & VRPH_INTER_ROUTE_ONLY) && (a_route ==c_route))
00341 return false;
00342
00343 if((rules & VRPH_INTRA_ROUTE_ONLY) && a_route !=c_route)
00344 return false;
00345
00346
00347
00348 int string_end = V->get_string_end(a, len);
00349 if(string_end==-1)
00350
00351 return false;
00352
00353 if(rules & VRPH_FIXED_EDGES)
00354 {
00355
00356 int z,b;
00357
00358 z=VRPH_MAX(V->pred_array[a],VRPH_DEPOT);
00359 b=VRPH_MAX(V->next_array[string_end],VRPH_DEPOT);
00360
00361 if( V->fixed[z][a] || V->fixed[string_end][b] )
00362 return false;
00363
00364
00365 }
00366
00367
00368
00369 MoveString MS;
00370
00371 if(MS.evaluate(V,c,d,a,string_end, M)==true)
00372 {
00373 if(V->check_move(M,rules)==true)
00374 return true;
00375 else
00376 return false;
00377
00378 }
00379
00380
00381 return false;
00382
00383
00384 }
00385
00386
00387
00388 bool OrOpt::move(class VRP *V, VRPMove *M)
00389 {
00394
00395 int a,len,c,d;
00396
00397 a=M->eval_arguments[0];
00398 len=M->eval_arguments[1];
00399 c=M->eval_arguments[2];
00400 d=M->eval_arguments[3];
00401
00402 int string_end = V->get_string_end(a, len);
00403 if(string_end==-1)
00404 {
00405 report_error("%s: no string end in move??\n",__FUNCTION__);
00406
00407 }
00408
00409 MoveString MS;
00410
00411 if( MS.move(V,c,d,a,string_end)==false)
00412 {
00413 report_error("%s: MS.move is false!\n",__FUNCTION__);
00414
00415 }
00416
00417 V->num_moves[OR_OPT_INDEX]++;
00418 V->capture_best_solution();
00419 return true;
00420 }