00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015
00016 bool OnePointMove::search(class VRP *V, int j, int rules)
00017 {
00023
00024 VRPMove M;
00025 VRPMove BestM;
00026 M.savings=M.new_total_route_length=BestM.savings=BestM.new_total_route_length=VRP_INFINITY;
00027
00028 int i,k;
00029 int best_k=0;
00030 int accept_type;
00031
00032 i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00033 k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00034
00035
00036 if(V->route[V->route_num[j]].num_customers<=3)
00037 return false;
00038
00039 if( (rules & VRPH_FIXED_EDGES) )
00040 {
00041
00042 if( (V->fixed[i][j]) || (V->fixed[j][k]) )
00043 return false;
00044
00045 }
00046
00047
00048
00049 accept_type=VRPH_FIRST_ACCEPT;
00050
00051 if( rules & VRPH_FIRST_ACCEPT )
00052 accept_type=VRPH_FIRST_ACCEPT;
00053 if( rules & VRPH_BEST_ACCEPT )
00054 accept_type=VRPH_BEST_ACCEPT;
00055 if( rules & VRPH_LI_ACCEPT )
00056 accept_type=VRPH_LI_ACCEPT;
00057
00058
00059 V->create_search_neighborhood(j, rules);
00060
00061 int *old_sol=NULL;
00062 if(rules & VRPH_TABU)
00063 {
00064
00065 old_sol=new int[V->num_original_nodes+2];
00066 V->export_solution_buff(old_sol);
00067 }
00068
00069 for(i=0;i<V->search_size;i++)
00070 {
00071 k=V->search_space[i];
00072 if(evaluate(V,j,k,rules,&M)==true)
00073 {
00074
00075 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00076 {
00077 if(move(V, &M)==false)
00078 report_error("%s: move error 1\n",__FUNCTION__);
00079 else
00080 {
00081 if(!(rules & VRPH_TABU))
00082 return true;
00083 else
00084 {
00085
00086
00087 if(V->check_tabu_status(&M, old_sol))
00088 {
00089 delete [] old_sol;
00090 return true;
00091 }
00092
00093 }
00094 }
00095 }
00096
00097 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00098 {
00099
00100
00101 if(M.is_better(V, &BestM, rules))
00102 {
00103 best_k=k;
00104 BestM=M;
00105 }
00106 }
00107 }
00108 }
00109
00110
00111
00112 if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00113 {
00114
00115 if(old_sol)
00116 delete [] old_sol;
00117 return false;
00118 }
00119
00120
00121
00122
00123 if(move(V,&BestM)==true)
00124 {
00125 if(!(rules & VRPH_TABU))
00126 return true;
00127 }
00128
00129 if(rules & VRPH_TABU)
00130 {
00131
00132
00133 if(V->check_tabu_status(&BestM, old_sol))
00134 {
00135 delete [] old_sol;
00136 return true;
00137 }
00138 else
00139 {
00140 delete [] old_sol;
00141 return false;
00142 }
00143 }
00144
00145
00146 report_error("%s: move error 4\n",__FUNCTION__);
00147
00148 return false;
00149 }
00150
00151
00152 bool OnePointMove::route_search(class VRP *V, int r1, int r2, int rules)
00153 {
00158
00159
00160 if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0)
00161 report_error("%s: route_searches do not use neighbor list\n",__FUNCTION__);
00162
00163
00164
00165
00166 VRPMove M;
00167 VRPMove BestM;
00168 int k;
00169 double best_savings=VRP_INFINITY;
00170 int best_k=0;
00171 int accept_type;
00172
00173
00174
00175 accept_type=VRPH_FIRST_ACCEPT;
00176
00177 if( (rules & VRPH_FIRST_ACCEPT) > 0)
00178 accept_type=VRPH_FIRST_ACCEPT;
00179 if( (rules & VRPH_BEST_ACCEPT) > 0)
00180 accept_type=VRPH_BEST_ACCEPT;
00181 if( (rules & VRPH_LI_ACCEPT) > 0)
00182 accept_type=VRPH_LI_ACCEPT;
00183
00184
00185 int j;
00186 j= V->route[r1].start;
00187 while(j!=VRPH_DEPOT)
00188 {
00189
00190 k= V->route[r2].start;
00191 while(k!=VRPH_DEPOT)
00192 {
00193 if(evaluate(V,j,k,rules,&M)==true)
00194 {
00195
00196
00197 if(accept_type==VRPH_FIRST_ACCEPT)
00198 {
00199
00200
00201 if(move(V,&M)==true)
00202 return true;
00203 else
00204 report_error("%s: move is false?\n",__FUNCTION__);
00205
00206 }
00207
00208 if(accept_type==VRPH_BEST_ACCEPT)
00209 {
00210
00211
00212 if(M.savings<best_savings)
00213 {
00214 best_savings=M.savings;
00215 best_k=k;
00216 BestM=M;
00217 }
00218 }
00219
00220 if(accept_type==VRPH_LI_ACCEPT)
00221 {
00222
00223
00224 if(M.savings<-VRPH_EPSILON)
00225 {
00226
00227 if(move(V,&M)==true)
00228 return true;
00229 else
00230 report_error("%s: false 7\n",__FUNCTION__);
00231 }
00232
00233 if(M.savings<best_savings)
00234 {
00235 best_savings=M.savings;
00236 best_k=k;
00237 BestM=M;
00238 }
00239 }
00240 }
00241 k=VRPH_MAX(V->next_array[k],0);
00242 }
00243 j=VRPH_MAX(V->next_array[j],0);
00244 }
00245
00246 if(accept_type==VRPH_FIRST_ACCEPT)
00247 {
00248
00249 return false;
00250 }
00251
00252
00253 if(best_savings==VRP_INFINITY)
00254 return false;
00255
00256
00257 if(move(V,&BestM)==true)
00258 return true;
00259 else
00260 report_error("%s: false 8\n",__FUNCTION__);
00261
00262 return false;
00263
00264
00265 }
00266
00267
00268 bool OnePointMove::evaluate(class VRP *V, int j, int b, int rules, VRPMove *M)
00269 {
00275
00276 V->num_evaluations[ONE_POINT_MOVE_INDEX]++;
00277
00278 int a,c,i,k;
00279
00280 a = VRPH_MAX(V->pred_array[b],VRPH_DEPOT);
00281 c = VRPH_MAX(V->next_array[b],VRPH_DEPOT);
00282 k = VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00283 i = VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00284
00285
00286 if(rules & VRPH_FIXED_EDGES)
00287 {
00288
00289
00290 if( V->fixed[i][j]|| V->fixed[j][k] )
00291 return false;
00292
00293 if(b!=VRPH_DEPOT && (V->fixed[b][c] && V->fixed[a][b]) )
00294 return false;
00295 }
00296
00297 M->evaluated_savings=false;
00298
00299 if(b==j || V->routed[j]==false || V->routed[b]==false || j==VRPH_DEPOT)
00300 return false;
00301
00302 if(b!=VRPH_DEPOT)
00303 {
00304 if( (rules & VRPH_INTER_ROUTE_ONLY) && (V->route_num[j] ==V->route_num[b]) )
00305 return false;
00306
00307 if((rules & VRPH_INTRA_ROUTE_ONLY) && (V->route_num[j] !=V->route_num[b]) )
00308 return false;
00309
00310
00311 if(V->route_num[j] != V->route_num[b])
00312 {
00313 if( V->nodes[j].demand + V->route[V->route_num[b]].load > V->max_veh_capacity)
00314 return false;
00315 }
00316
00317
00318 }
00319
00320 double savings1, savings2, best_savings;
00321 Postsert postsert;
00322 Presert presert;
00323 best_savings=VRP_INFINITY;
00324 savings1=VRP_INFINITY;
00325 savings2=VRP_INFINITY;
00326
00327
00328
00329
00330 if(b==VRPH_DEPOT)
00331 {
00332 int current_start, current_end, current_route;
00333 current_start=abs(V->next_array[VRPH_DEPOT]);
00334 bool allowed, found_move;
00335 VRPMove CurrentM;
00336 found_move=false;
00337
00338 for(;;)
00339 {
00340
00341 int t=current_start;
00342 allowed=true;
00343
00344 if(j!=t)
00345 {
00346
00347 if((rules & VRPH_FIXED_EDGES) && V->fixed[VRPH_DEPOT][t])
00348 allowed=false;
00349
00350 if( (presert.evaluate(V,j,t,&CurrentM)==true)&&(V->check_move(&CurrentM,rules)==true) && allowed )
00351 {
00352
00353 if(CurrentM.is_better(V,M,rules))
00354 {
00355 found_move=true;
00356 *M=CurrentM;
00357 }
00358 }
00359 }
00360
00361
00362 current_route= V->route_num[current_start];
00363 current_end= V->route[current_route].end;
00364 t=current_end;
00365 allowed=true;
00366 if(j!=t)
00367 {
00368
00369 if((rules & VRPH_FIXED_EDGES) && V->fixed[t][VRPH_DEPOT])
00370 allowed=false;
00371
00372 if( (postsert.evaluate(V,j,t,&CurrentM)==true)&&(V->check_move(&CurrentM,rules)==true) && allowed )
00373 {
00374 if(CurrentM.is_better(V,M,rules))
00375 {
00376 found_move=true;
00377 *M=CurrentM;
00378 }
00379 }
00380
00381 }
00382
00383
00384 current_start=abs(V->next_array[current_end]);
00385 if(current_start==VRPH_DEPOT)
00386 break;
00387 }
00388
00389 return found_move;
00390
00391
00392 }
00393
00394
00395 if(c == j)
00396 {
00397
00398
00399 if(rules & VRPH_FIXED_EDGES)
00400 {
00401
00402
00403 if( V->fixed[a][b] )
00404 return false;
00405 }
00406
00407 if( (presert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true) )
00408 return true;
00409 else
00410 return false;
00411
00412 }
00413
00414
00415 if(a == j)
00416 {
00417
00418
00419 if(rules & VRPH_FIXED_EDGES)
00420 {
00421
00422
00423 if( V->fixed[b][c] )
00424 return false;
00425 }
00426
00427 if( (postsert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true) )
00428 return true;
00429 else
00430 return false;
00431
00432 }
00433
00434
00435
00436
00437
00438 savings1 = (V->d[a][j]+V->d[j][b]+V->d[i][k]) - (V->d[a][b]+V->d[i][j]+V->d[j][k]) ;
00439 savings2 = (V->d[i][k]+V->d[b][j]+V->d[j][c]) - (V->d[b][c]+V->d[i][j]+V->d[j][k]) ;
00440
00441 best_savings = VRPH_MIN(savings1, savings2);
00442
00443
00444 if( savings1 <= savings2 && (presert.evaluate(V,j,b,M)==true)
00445 &&(V->check_move(M,rules)==true) )
00446 {
00447
00448 if(rules & VRPH_FIXED_EDGES)
00449 {
00450
00451
00452 if( V->fixed[a][b] )
00453 return false;
00454 }
00455 return true;
00456 }
00457
00458
00459 if( savings2<savings1 && postsert.evaluate(V,j,b,M)==true &&
00460 (V->check_move(M,rules)==true) )
00461 {
00462
00463 if(rules & VRPH_FIXED_EDGES)
00464 {
00465
00466
00467 if( V->fixed[b][c] )
00468 return false;
00469 }
00470
00471 return true;
00472 }
00473
00474
00475
00476
00477 if( (presert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true))
00478 {
00479 if(rules & VRPH_FIXED_EDGES)
00480 {
00481
00482
00483 if( V->fixed[a][b] )
00484 return false;
00485 }
00486
00487 return true;
00488 }
00489
00490
00491
00492
00493 return false;
00494 }
00495
00496 bool OnePointMove::move(class VRP *V, VRPMove *M)
00497 {
00501
00502
00503 if(M->move_type==PRESERT)
00504 {
00505 Presert presert;
00506 if(presert.move(V,M->move_arguments[0],M->move_arguments[1]))
00507 {
00508 V->num_moves[ONE_POINT_MOVE_INDEX]++;
00509 V->capture_best_solution();
00510
00511 return true;
00512 }
00513 else
00514 report_error("%s: presert move is false\n",__FUNCTION__);
00515
00516
00517 }
00518 else
00519 {
00520 if(M->move_type==POSTSERT)
00521 {
00522 Postsert postsert;
00523 if(postsert.move(V,M->move_arguments[0],M->move_arguments[1]))
00524 {
00525 V->num_moves[ONE_POINT_MOVE_INDEX]++;
00526 V->capture_best_solution();
00527 return true;
00528 }
00529 else
00530 report_error("%s: postsert move is false\n",__FUNCTION__);
00531 }
00532 }
00533
00534 return false;
00535
00536 }