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