00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015
00016
00017 bool TwoPointMove::search(class VRP *V, int j, int rules)
00018 {
00025
00026 VRPMove M;
00027 VRPMove BestM;
00028 BestM.savings=VRP_INFINITY;
00029 int i,k;
00030 int accept_type;
00031
00032 if(j==VRPH_DEPOT)
00033 return false;
00034
00035 if(rules & VRPH_FIXED_EDGES)
00036 {
00037 i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00038 k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00039
00040
00041
00042 if( V->fixed[i][j] || V->fixed[j][k] )
00043 return false;
00044 }
00045
00046 accept_type=VRPH_FIRST_ACCEPT;
00047
00048 if( (rules & VRPH_FIRST_ACCEPT) > 0)
00049 accept_type=VRPH_FIRST_ACCEPT;
00050 if( (rules & VRPH_BEST_ACCEPT) > 0)
00051 accept_type=VRPH_BEST_ACCEPT;
00052 if( (rules & VRPH_LI_ACCEPT) > 0)
00053 accept_type=VRPH_LI_ACCEPT;
00054
00055 int *old_sol=NULL;
00056 if(rules & VRPH_TABU)
00057 {
00058
00059 old_sol=new int[V->num_original_nodes+2];
00060 V->export_solution_buff(old_sol);
00061 }
00062
00063
00064 V->create_search_neighborhood(j, rules);
00065
00066 for(i=0;i<V->search_size;i++)
00067 {
00068 k=V->search_space[i];
00069
00070 if(k!=VRPH_DEPOT && k!=j)
00071 {
00072
00073
00074 if(evaluate(V,j,k,rules,&M)==true)
00075 {
00076
00077 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00078 {
00079
00080
00081 if(move(V, &M)==false)
00082 report_error("%s: move error 1\n",__FUNCTION__);
00083 else
00084 {
00085 if(!(rules & VRPH_TABU))
00086 return true;
00087 else
00088 {
00089
00090
00091 if(V->check_tabu_status(&M, old_sol))
00092 {
00093 delete [] old_sol;
00094 return true;
00095 }
00096
00097 }
00098 }
00099 }
00100
00101
00102
00103 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT )
00104 {
00105
00106 if(M.is_better(V, &BestM, rules))
00107 BestM=M;
00108
00109 }
00110
00111 }
00112 }
00113 }
00114
00115
00116
00117 if(accept_type==VRPH_FIRST_ACCEPT)
00118 {
00119 if(old_sol)
00120 delete [] old_sol;
00121 return false;
00122 }
00123
00124 if(BestM.savings==VRP_INFINITY)
00125 {
00126 if(old_sol)
00127 delete [] old_sol;
00128 return false;
00129 }
00130
00131
00132 if(move(V,&BestM)==true)
00133 {
00134 if(!(rules & VRPH_TABU))
00135 return true;
00136 }
00137
00138 if(rules & VRPH_TABU)
00139 {
00140
00141
00142 if(V->check_tabu_status(&M, old_sol))
00143 {
00144 delete [] old_sol;
00145 return true;
00146 }
00147 else
00148 {
00149 delete [] old_sol;
00150 return false;
00151 }
00152 }
00153
00154
00155 report_error("%s: best move false!\n",__FUNCTION__);
00156
00157
00158 return false;
00159 }
00160
00161
00162 bool TwoPointMove::route_search(class VRP *V, int r1, int r2, int rules)
00163 {
00168
00169
00170 VRPMove M;
00171 VRPMove BestM;
00172 int j,k;
00173 int accept_type;
00174
00175 BestM.savings=VRP_INFINITY;
00176
00177 if(r1==r2)
00178 {
00179 fprintf(stderr,"TPM::%d==%d???\n",r1,r2);
00180 report_error("%s: called with r1==r2\n",__FUNCTION__);
00181 }
00182
00183 if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0)
00184 report_error("%s: ROUTE_BASED search does not use neighbor_list\n",__FUNCTION__);
00185
00186 accept_type=VRPH_FIRST_ACCEPT;
00187
00188 if( (rules & VRPH_FIRST_ACCEPT) > 0)
00189 accept_type=VRPH_FIRST_ACCEPT;
00190 if( (rules & VRPH_BEST_ACCEPT) > 0)
00191 accept_type=VRPH_BEST_ACCEPT;
00192 if( (rules & VRPH_LI_ACCEPT) > 0)
00193 accept_type=VRPH_LI_ACCEPT;
00194
00195
00196 j= V->route[r1].start;
00197 while(j!=VRPH_DEPOT)
00198 {
00199
00200 k= V->route[r2].start;
00201 while(k!=VRPH_DEPOT)
00202 {
00203
00204 if(evaluate(V,j,k,rules,&M)==true)
00205 {
00206
00207 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00208 {
00209
00210 if(move(V,&M)==false)
00211 report_error("%s: first accept move is false!\n",__FUNCTION__);
00212 else
00213 return true;
00214 }
00215
00216 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT) )
00217 {
00218
00219
00220 if(M.is_better(V, &BestM, rules))
00221 BestM=M;
00222 }
00223
00224
00225 }
00226
00227 k=VRPH_MAX(V->next_array[k],0);
00228 }
00229
00230 j=VRPH_MAX(V->next_array[j],0);
00231 }
00232
00233
00234 if(accept_type==VRPH_FIRST_ACCEPT)
00235 return false;
00236 if(BestM.savings == VRP_INFINITY)
00237 return false;
00238
00239 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type == VRPH_BEST_ACCEPT))
00240 {
00241
00242
00243 if(move(V,&BestM)==false)
00244 report_error("%s: best move is false!\n",__FUNCTION__);
00245 else
00246 return true;
00247
00248 }
00249
00250 report_error("%s: shouldn't be here...\n",__FUNCTION__);
00251
00252 return false;
00253
00254 }
00255
00256 bool TwoPointMove::evaluate(class VRP *V, int j, int b, int rules, VRPMove *M)
00257 {
00264
00265 V->num_evaluations[TWO_POINT_MOVE_INDEX]++;
00266
00267 if(V->routed[j]==false || V->routed[b]==false || j==b)
00268 return false;
00269
00270 if(rules & VRPH_FIXED_EDGES)
00271 {
00272
00273 int i,k,a,c;
00274
00275 a=VRPH_MAX(V->pred_array[b],VRPH_DEPOT);
00276 c=VRPH_MAX(V->next_array[b],VRPH_DEPOT);
00277
00278 i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00279 k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00280
00281 if( V->fixed[a][b] || V->fixed[b][c] || V->fixed[i][j] || V->fixed[j][k] )
00282 return false;
00283 }
00284
00285 M->evaluated_savings=false;
00286
00287
00288 class Swap swap;
00289
00290 if(V->routed[j]==false || V->routed[b]==false)
00291 return false;
00292
00293 if(j==VRPH_DEPOT || b==VRPH_DEPOT || j==b)
00294 {
00295 fprintf(stderr,"TPM::j=%d, b=%d\n",j,b);
00296 report_error("%s: evaluate() called with bad arguments??\n",__FUNCTION__);
00297 }
00298
00299 if((rules & VRPH_INTER_ROUTE_ONLY) && (V->route_num[j]==V->route_num[b]) )
00300 return false;
00301
00302 if((rules & VRPH_INTRA_ROUTE_ONLY) && (V->route_num[j]!=V->route_num[b]) )
00303 return false;
00304
00305
00306 if( (swap.evaluate(V,j,b,M)==true) && (V->check_move(M, rules)==true))
00307 {
00308 return true;
00309
00310 }
00311 else
00312 {
00313
00314 return false;
00315 }
00316
00317 }
00318
00319
00320 bool TwoPointMove::move(class VRP *V, VRPMove *M)
00321 {
00322
00326
00327 if(M->move_type!=SWAP)
00328 report_error("%s: Unknown move type\n",__FUNCTION__);
00329
00330 class Swap swap;
00331
00332 if(swap.move(V,M->move_arguments[0], M->move_arguments[1])==false)
00333 {
00334
00335 report_error("%s: TPM::swap.move evaluates to false!!\n",__FUNCTION__);
00336
00337 }
00338
00339 V->capture_best_solution();
00340 V->num_moves[TWO_POINT_MOVE_INDEX]++;
00341
00342 return true;
00343
00344 }
00345