VRPH
1.0
|
00001 00002 // // 00003 // This file is part of the VRPH software package for // 00004 // generating solutions to vehicle routing problems. // 00005 // VRPH was developed by Chris Groer (cgroer@gmail.com). // 00006 // // 00007 // (c) Copyright 2010 Chris Groer. // 00008 // All Rights Reserved. VRPH is licensed under the // 00009 // Common Public License. See LICENSE file for details. // 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 // Make sure we aren't disturbing fixed edges 00038 00039 if( V->fixed[i][b] || V->fixed[b][j] ) 00040 return false; 00041 } 00042 00043 accept_type=VRPH_FIRST_ACCEPT;//default 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 // Create the search_space 00054 V->create_search_neighborhood(b, rules); 00055 00056 int *old_sol=NULL; 00057 if(rules & VRPH_TABU) 00058 { 00059 // Remember the original solution 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 // Get the edge i-j 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 // Edge i-j 00072 if(i!=VRPH_DEPOT && j!=VRPH_DEPOT) 00073 { 00074 // We have the edge i-j to consider swapping with node b 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 // Make the move 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 // Check VRPH_TABU status of move - return true if its ok 00091 // or revert to old_sol if not and continue to search. 00092 if(V->check_tabu_status(&M, old_sol)) 00093 { 00094 delete [] old_sol; 00095 return true; // The move was ok 00096 } 00097 // else we reverted back - continue the search for a move 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 // Edge h-i 00111 if(h!=VRPH_DEPOT && i!=VRPH_DEPOT) 00112 { 00113 // We have the edge h-i to consider swapping with node b 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 // Make the move 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 // Check VRPH_TABU status of move - return true if its ok 00128 // or revert to old_sol if not and continue to search. 00129 if(V->check_tabu_status(&M, old_sol)) 00130 { 00131 delete [] old_sol; 00132 return true; // The move was ok 00133 } 00134 // else we reverted back - continue the search for a move 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; // No moves found 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 // Check VRPH_TABU status of move - return true if its ok 00168 // or revert to old_sol if not and continue to search. 00169 if(V->check_tabu_status(&BestM, old_sol)) 00170 { 00171 delete [] old_sol; 00172 return true; // The move was ok 00173 } 00174 // else we reverted back - search over 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;//default 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 // We will try to move j-k from route r1 and exchange with l from route r2 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 // Try to swap j-k with node l 00231 if(evaluate(V,l,j,k,rules,&M)==true) 00232 { 00233 // valid move found 00234 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00235 { 00236 // make the move 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 // See if it's the best so far... 00246 if(M.is_better(V, &BestM, rules)) 00247 BestM=M; 00248 } 00249 00250 } 00251 00252 // Try to swap l-m with node j 00253 if(evaluate(V,j,l,m,rules,&M)==true) 00254 { 00255 // valid move found 00256 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00257 { 00258 // make the move 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 // See if it's the best so far... 00268 if(M.is_better(V, &BestM, rules)) 00269 BestM=M; 00270 } 00271 00272 } 00273 // Advance the route r2 node 00274 l=m; 00275 m=VRPH_MAX(V->next_array[m],0); 00276 } 00277 // Advance the route r1 node 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; // No moves found 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 // We found a move -- make it... 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)//conflict 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];// this is b's former route 00336 i_route=V->route_num[i]; 00337 00338 // Don't do it if tiny routes 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 // Make sure we aren't disturbing fixed edges 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 // a-b/h-c/i-j-k --> a-c/i-j-b/h-k - postsert(b,j) 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 // h-i-j/a-b/k-c --> h-b/k-i-j/a-c - presert(b,i) 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 // else no conflicts 00376 00377 if(b!=h && b!=k) 00378 { 00379 // old: a-b-c...h-i-j-k 00380 // new: a-i-j-c...h-b-k 00381 00382 // No conflicts 00383 // savings = new - old 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 // Same route - check length feasibility 00396 if(V->route[a_route].length+savings>V->max_route_length) 00397 return false; 00398 00399 // Otherwise the move is feasible - record the move... 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 // Now check the move 00415 if(V->check_move(M,rules)==true) 00416 return true; 00417 else 00418 return false; 00419 00420 00421 } 00422 00423 // else diff. routes - can't have any overlaps in this case 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 // else the move is feasible - record it. 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 // Now check the move 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 // Easiest way to do this is by just post/preserting the nodes. 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 // First artificially inflate the constraints 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 // a-b/h-c/i-j-k --> a-c/i-j-b/h-k - postsert(b,j) 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 // h-i-j/a-b/k-c --> h-b/k-i-j/a-c - presert(b,i) 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 // First put b between h and i 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 // Now put i in between a and c 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 // Now put j after i 00554 if(postsert.move(V,j,i)==false) 00555 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,j,i); 00556 00557 } 00558 // Restore constraints 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