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 // SEARCH 00016 bool TwoOpt::search(class VRP *V, int b, int rules) 00017 { 00024 00025 VRPMove M; 00026 VRPMove BestM; 00027 int i,ii,j,k,a,c; 00028 int best_edges[4]; 00029 int accept_type; 00030 00031 memset(best_edges,-1,4*sizeof(int)); 00032 accept_type=VRPH_FIRST_ACCEPT; //default 00033 00034 if( (rules & VRPH_FIRST_ACCEPT) == VRPH_FIRST_ACCEPT) 00035 accept_type=VRPH_FIRST_ACCEPT; 00036 if( (rules & VRPH_BEST_ACCEPT) == VRPH_BEST_ACCEPT ) 00037 accept_type=VRPH_BEST_ACCEPT; 00038 if( (rules & VRPH_LI_ACCEPT) == VRPH_LI_ACCEPT ) 00039 accept_type=VRPH_LI_ACCEPT; 00040 00041 int *old_sol=NULL; 00042 if(rules & VRPH_TABU) 00043 { 00044 // Remember the original solution 00045 old_sol=new int[V->num_original_nodes+2]; 00046 V->export_solution_buff(old_sol); 00047 } 00048 00049 // Create the search_space 00050 V->create_search_neighborhood(b, rules); 00051 00052 BestM.savings=VRP_INFINITY; 00053 00054 // Get the existing edges a-b and b-c 00055 a=VRPH_MAX(V->pred_array[b],0); 00056 c=VRPH_MAX(V->next_array[b],0); 00057 00058 if(rules & VRPH_FIXED_EDGES) 00059 { 00060 // If both edges a-b and b-c are fixed, then no 2 opt moves are possible 00061 if(V->fixed[a][b] && V->fixed[b][c]) 00062 return false; 00063 } 00064 00065 for(ii=0; ii<V->search_size; ii++) 00066 { 00067 j=V->search_space[ii]; 00068 if(V->routed[j]==false) 00069 { 00070 fprintf(stderr,"Unrouted node %d found in TO.search\n",j); 00071 report_error("%s: Error in routed array\n",__FUNCTION__); 00072 } 00073 00074 if(j!=b && j!=VRPH_DEPOT) 00075 { 00076 i=VRPH_MAX(V->pred_array[j],0); 00077 k=VRPH_MAX(V->next_array[j],0); 00078 00079 // Four edges: a-b, b-c, i-j, j-k 00080 // Now evaluate the 4 moves 00081 00082 M.savings=VRP_INFINITY ; 00083 00084 if(evaluate(V,a,b,i,j,rules, &M)==true) 00085 { 00086 00087 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00088 accept_type==VRPH_FIRST_ACCEPT ) 00089 { 00090 if(move(V, &M)==false) 00091 report_error("%s: move error 1\n",__FUNCTION__); 00092 else 00093 { 00094 if(!(rules & VRPH_TABU)) 00095 return true; 00096 else 00097 { 00098 // Check VRPH_TABU status of move - return true if its ok 00099 // or revert to old_sol if not and continue to search. 00100 if(V->check_tabu_status(&M, old_sol)) 00101 { 00102 delete [] old_sol; 00103 return true; // The move was ok 00104 } 00105 // else we reverted back - continue the search for a move 00106 00107 } 00108 } 00109 } 00110 00111 00112 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00113 { 00114 00115 if(M.is_better(V, &BestM, rules)) 00116 { 00117 BestM=M; 00118 best_edges[0]=a;best_edges[1]=b;best_edges[2]=i;best_edges[3]=j; 00119 } 00120 } 00121 00122 } 00123 00124 00125 if(evaluate(V,a,b,j,k,rules, &M)==true) 00126 { 00127 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00128 accept_type==VRPH_FIRST_ACCEPT ) 00129 { 00130 00131 if(move(V, &M)==false) 00132 report_error("%s: move error 2\n",__FUNCTION__); 00133 else 00134 { 00135 if(!(rules & VRPH_TABU)) 00136 return true; 00137 else 00138 { 00139 // Check VRPH_TABU status of move - return true if its ok 00140 // or revert to old_sol if not and continue to search. 00141 if(V->check_tabu_status(&M, old_sol)) 00142 { 00143 delete [] old_sol; 00144 return true; // The move was ok 00145 } 00146 // else we reverted back - continue the search for a move 00147 } 00148 } 00149 } 00150 00151 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00152 { 00153 if(M.is_better(V, &BestM, rules)) 00154 { 00155 BestM=M; 00156 best_edges[0]=a;best_edges[1]=b;best_edges[2]=j;best_edges[3]=k; 00157 } 00158 } 00159 00160 } 00161 00162 00163 if(evaluate(V,b,c,i,j,rules, &M)==true) 00164 { 00165 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00166 accept_type==VRPH_FIRST_ACCEPT ) 00167 { 00168 00169 if(move(V, &M)==false) 00170 report_error("%s: move error 3\n",__FUNCTION__); 00171 else 00172 { 00173 if(!(rules & VRPH_TABU)) 00174 return true; 00175 else 00176 { 00177 // Check VRPH_TABU status of move - return true if its ok 00178 // or revert to old_sol if not and continue to search. 00179 if(V->check_tabu_status(&M, old_sol)) 00180 { 00181 delete [] old_sol; 00182 return true; // The move was ok 00183 } 00184 // else we reverted back - continue the search for a move 00185 00186 } 00187 } 00188 } 00189 00190 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00191 { 00192 if(M.is_better(V, &BestM, rules)) 00193 { 00194 BestM=M; 00195 best_edges[0]=b;best_edges[1]=c;best_edges[2]=i;best_edges[3]=j; 00196 } 00197 } 00198 00199 } 00200 00201 00202 if(evaluate(V,b,c,j,k,rules, &M)==true) 00203 { 00204 00205 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00206 accept_type==VRPH_FIRST_ACCEPT ) 00207 { 00208 if(move(V, &M)==false) 00209 report_error("%s: move error 4\n",__FUNCTION__); 00210 else 00211 { 00212 if(!(rules & VRPH_TABU)) 00213 return true; 00214 else 00215 { 00216 // Check VRPH_TABU status of move - return true if its ok 00217 // or revert to old_sol if not and continue to search. 00218 if(V->check_tabu_status(&M, old_sol)) 00219 { 00220 delete [] old_sol; 00221 return true; // The move was ok 00222 } 00223 // else we reverted back - continue the search for a move 00224 } 00225 } 00226 } 00227 00228 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00229 { 00230 if(M.is_better(V, &BestM, rules)) 00231 { 00232 BestM=M; 00233 best_edges[0]=b;best_edges[1]=c;best_edges[2]=j;best_edges[3]=k; 00234 } 00235 } 00236 } 00237 00238 } 00239 // end if j!=VRPH_DEPOT && j!=b 00240 00241 00242 if(j==VRPH_DEPOT && j!=b) 00243 { 00244 // In this case we have many edges to consider 00245 // We will consider all edges of the form VRPH_DEPOT-t 00246 // and t-VRPH_DEPOT 00247 00248 int current_start, current_end, current_route; 00249 current_start=abs(V->next_array[VRPH_DEPOT]); 00250 00251 00252 for(;;) 00253 { 00254 // Consider the edge VRPH_DEPOT-current_start 00255 int t=current_start; 00256 00257 if(evaluate(V,a,b,VRPH_DEPOT,t,rules, &M)==true) 00258 { 00259 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00260 accept_type==VRPH_FIRST_ACCEPT ) 00261 { 00262 if(move(V, &M)==false) 00263 report_error("%s: VRPH_DEPOT move error 1\n",__FUNCTION__); 00264 else 00265 { 00266 if(!(rules & VRPH_TABU)) 00267 return true; 00268 else 00269 { 00270 // Check VRPH_TABU status of move - return true if its ok 00271 // or revert to old_sol if not and continue to search. 00272 if(V->check_tabu_status(&M, old_sol)) 00273 { 00274 delete [] old_sol; 00275 return true; // The move was ok 00276 } 00277 // else we reverted back - continue the search for a move 00278 00279 } 00280 } 00281 } 00282 00283 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00284 { 00285 00286 if(M.is_better(V, &BestM, rules)) 00287 { 00288 BestM=M; 00289 best_edges[0]=a;best_edges[1]=b;best_edges[2]=VRPH_DEPOT;best_edges[3]=t; 00290 } 00291 00292 } 00293 } 00294 00295 if(evaluate(V,b,c,VRPH_DEPOT,t,rules, &M)==true) 00296 { 00297 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00298 accept_type==VRPH_FIRST_ACCEPT ) 00299 { 00300 if(move(V, &M)==false) 00301 report_error("%s: VRPH_DEPOT move error 2\n",__FUNCTION__); 00302 else 00303 { 00304 if(!(rules & VRPH_TABU)) 00305 return true; 00306 else 00307 { 00308 // Check VRPH_TABU status of move - return true if its ok 00309 // or revert to old_sol if not and continue to search. 00310 if(V->check_tabu_status(&M, old_sol)) 00311 { 00312 delete [] old_sol; 00313 return true; // The move was ok 00314 } 00315 // else we reverted back - continue the search for a move 00316 00317 } 00318 } 00319 } 00320 00321 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00322 { 00323 00324 if(M.is_better(V, &BestM, rules)) 00325 { 00326 BestM=M; 00327 best_edges[0]=b;best_edges[1]=c;best_edges[2]=VRPH_DEPOT;best_edges[3]=t; 00328 } 00329 00330 } 00331 } 00332 00333 // Now try the t-VRPH_DEPOT edge 00334 current_route= V->route_num[current_start]; 00335 current_end= V->route[current_route].end; 00336 t=current_end; 00337 00338 if(evaluate(V,a,b,t,VRPH_DEPOT,rules, &M)==true) 00339 { 00340 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00341 accept_type==VRPH_FIRST_ACCEPT ) 00342 { 00343 if(move(V, &M)==false) 00344 report_error("%s: VRPH_DEPOT move error 3\n",__FUNCTION__); 00345 else 00346 { 00347 if(!(rules & VRPH_TABU)) 00348 return true; 00349 else 00350 { 00351 // Check VRPH_TABU status of move - return true if its ok 00352 // or revert to old_sol if not and continue to search. 00353 if(V->check_tabu_status(&M, old_sol)) 00354 { 00355 delete [] old_sol; 00356 return true; // The move was ok 00357 } 00358 // else we reverted back - continue the search for a move 00359 00360 } 00361 } 00362 } 00363 00364 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00365 { 00366 00367 if(M.is_better(V, &BestM, rules)) 00368 { 00369 BestM=M; 00370 best_edges[0]=a;best_edges[1]=b;best_edges[2]=t;best_edges[3]=VRPH_DEPOT; 00371 } 00372 00373 } 00374 } 00375 00376 if(evaluate(V,b,c,t,VRPH_DEPOT,rules, &M)==true) 00377 { 00378 if( ( (accept_type == VRPH_LI_ACCEPT) && ( M.savings<-VRPH_EPSILON )) || 00379 accept_type==VRPH_FIRST_ACCEPT ) 00380 { 00381 if(move(V, &M)==false) 00382 report_error("%s: VRPH_DEPOT move error 4\n",__FUNCTION__); 00383 else 00384 { 00385 if(!(rules & VRPH_TABU)) 00386 return true; 00387 else 00388 { 00389 // Check VRPH_TABU status of move - return true if its ok 00390 // or revert to old_sol if not and continue to search. 00391 if(V->check_tabu_status(&M, old_sol)) 00392 { 00393 delete [] old_sol; 00394 return true; // The move was ok 00395 } 00396 // else we reverted back - continue the search for a move 00397 00398 } 00399 } 00400 } 00401 00402 if( accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT ) 00403 { 00404 00405 if(M.is_better(V, &BestM, rules)) 00406 { 00407 BestM=M; 00408 best_edges[0]=b;best_edges[1]=c;best_edges[2]=t;best_edges[3]=VRPH_DEPOT; 00409 } 00410 00411 } 00412 } 00413 00414 // Now advance to the next node adjacent to the VRPH_DEPOT 00415 current_start=abs(V->next_array[current_end]); 00416 if(current_start==VRPH_DEPOT) // We're done 00417 break; 00418 } 00419 00420 // end VRPH_DEPOT loop 00421 00422 } 00423 // end j loop 00424 } 00425 // end ii loop 00426 00427 00428 if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY) 00429 { 00430 if(rules&VRPH_TABU) 00431 delete [] old_sol; 00432 return false; // No moves found 00433 } 00434 00435 00436 00437 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00438 { 00439 00440 if(move(V,&BestM)==false) 00441 { 00442 fprintf(stderr,"%f: (%d[%d]-%d[%d], %d[%d]-%d[%d])\n",BestM.savings, 00443 best_edges[0], 00444 V->route_num[best_edges[0]], 00445 best_edges[1],V->route_num[best_edges[1]], 00446 best_edges[2],V->route_num[best_edges[2]], 00447 best_edges[3],V->route_num[best_edges[3]]); 00448 V->show_routes(); 00449 report_error("%s: best move evaluates to false\n",__FUNCTION__); 00450 } 00451 else 00452 { 00453 if(!(rules & VRPH_TABU)) 00454 return true; 00455 else 00456 { 00457 // Check VRPH_TABU status of move - return true if its ok 00458 // or revert to old_sol if not and continue to search. 00459 if(V->check_tabu_status(&BestM, old_sol)) 00460 { 00461 delete [] old_sol; 00462 return true; // The move was ok 00463 } 00464 // else we reverted back - search over 00465 delete [] old_sol; 00466 return false; 00467 00468 } 00469 } 00470 } 00471 00472 report_error("%s: search shouldn't get here!\n",__FUNCTION__); 00473 00474 return false; 00475 00476 } 00477 00478 bool TwoOpt::route_search(class VRP *V, int r1, int r2, int rules) 00479 { 00480 00485 00486 00487 VRPMove M, BestM; 00488 int i,j,a,b; 00489 BestM.savings=VRP_INFINITY; 00490 int accept_type; 00491 00492 if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0) 00493 report_error("%s: route searches do not use neighbor_list\n",__FUNCTION__); 00494 00495 accept_type=VRPH_FIRST_ACCEPT; //default 00496 00497 if( (rules & VRPH_FIRST_ACCEPT) > 0) 00498 accept_type=VRPH_FIRST_ACCEPT; 00499 if( (rules & VRPH_BEST_ACCEPT) > 0) 00500 accept_type=VRPH_BEST_ACCEPT; 00501 if( (rules & VRPH_LI_ACCEPT) > 0) 00502 accept_type=VRPH_LI_ACCEPT; 00503 00504 double current_savings=VRP_INFINITY; 00505 00506 00507 a=VRPH_DEPOT; 00508 b= V->route[r1].start; 00509 00510 for(;;) 00511 { 00512 // Get the edge a-b from route r1 00513 00514 // Now get edges from route r2; 00515 00516 j= V->route[r2].start; 00517 i=VRPH_DEPOT; 00518 for(;;) 00519 { 00520 00521 // We now have the edges: a-b, b-c in route r1 00522 // i-j, j-k in route r2 00523 // Find the best of these 4 2 opt moves 00524 current_savings=VRP_INFINITY; 00525 00526 00527 // a-b, i-j 00528 if(evaluate(V,a,b,i,j,rules, &M)==true) 00529 { 00530 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00531 { 00532 if(move(V,&M)==false) 00533 report_error("%s: first accept move is false!\n",__FUNCTION__); 00534 else 00535 return true; 00536 00537 } 00538 00539 if(accept_type == VRPH_LI_ACCEPT || accept_type==VRPH_BEST_ACCEPT) 00540 { 00541 // See if it's the best so far 00542 00543 if(M.is_better(V, &BestM, rules)) 00544 BestM=M; 00545 } 00546 } 00547 00548 // Advance route r2 node 00549 i=j; 00550 if(i==VRPH_DEPOT) 00551 break; 00552 j=VRPH_MAX(V->next_array[j],0); 00553 } 00554 // Advance route r1 node 00555 a=b; 00556 if(a==VRPH_DEPOT) 00557 break; 00558 b=VRPH_MAX(V->next_array[b],0); 00559 } 00560 00561 if(accept_type == VRPH_FIRST_ACCEPT) 00562 return false; 00563 00564 if(BestM.savings==VRP_INFINITY) 00565 return false; // No move found 00566 00567 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT)) 00568 { 00569 // Make the best move 00570 00571 if(move(V, &BestM)==false) 00572 report_error("%s: best move is false\n",__FUNCTION__); 00573 else 00574 return true; 00575 } 00576 00577 return false; 00578 } 00579 00580 bool TwoOpt::evaluate(class VRP *V, int a, int b, int c, int d, int rules, VRPMove *M) 00581 { 00589 00590 V->num_evaluations[TWO_OPT_INDEX]++; 00591 00592 // Look for overlaps 00593 if( (b==c) || (a==c) || (a==d) || (b==d) || V->routed[a]==false || 00594 V->routed[b]==false || V->routed[c]==false || V->routed[d]==false ) 00595 { 00596 // Two Opt move doesn't make sense here... 00597 return false; 00598 } 00599 00600 // Check for fixed edges 00601 if(rules & VRPH_FIXED_EDGES) 00602 { 00603 if(V->fixed[a][b] || V->fixed[c][d]) 00604 return false; 00605 } 00606 00607 // Look for two edges involving the VRPH_DEPOT 00608 int num_depot_edges=0; 00609 if(a==VRPH_DEPOT) num_depot_edges++; 00610 if(b==VRPH_DEPOT) num_depot_edges++; 00611 if(c==VRPH_DEPOT) num_depot_edges++; 00612 if(d==VRPH_DEPOT) num_depot_edges++; 00613 if(num_depot_edges>1) 00614 return false; 00615 00616 M->eval_arguments[0]=a;M->eval_arguments[1]=b;M->eval_arguments[2]=c;M->eval_arguments[3]=d; 00617 M->evaluated_savings=false; 00618 00619 int a_route, c_route; 00620 00621 if(a!=VRPH_DEPOT) 00622 a_route= V->route_num[a]; 00623 else 00624 a_route= V->route_num[b]; 00625 00626 if(c!=VRPH_DEPOT) 00627 c_route= V->route_num[c]; 00628 else 00629 c_route= V->route_num[d]; 00630 00631 // Check for INTER/INTRA restrictions 00632 00633 if( ( rules & VRPH_INTER_ROUTE_ONLY) && (a_route==c_route) ) 00634 return false; 00635 00636 if( ( rules & VRPH_INTRA_ROUTE_ONLY) && (a_route!=c_route) ) 00637 return false; 00638 00639 #if 1 00640 // First, we can see if any of the possible moves passes the savings rules 00641 // before going into more expensive evaluations. 00642 00643 if(a_route==c_route) 00644 { 00645 M->num_affected_routes=1; 00646 M->savings = ( V->d[a][c]+V->d[b][d] -V->nodes[c].service_time) - 00647 ( V->d[a][b]+V->d[c][d]-V->nodes[b].service_time ); 00648 00649 // Can check feasibility 00650 if(M->savings+V->route[a_route].length > V->max_route_length) 00651 return false; 00652 00653 } 00654 else 00655 { 00656 M->num_affected_routes=2; 00657 M->savings = (V->d[a][d]+V->d[c][b]) - (V->d[a][b]+V->d[c][d]) ; 00658 00659 // Observation: if savings>0, then one route must increase its length 00660 // by at least savings/2 00661 // So if both increase their lengths by savings/2 and are both infeasible 00662 // then we can say for certain that the move is infeasible. 00663 00664 if(M->savings/2+V->route[a_route].length> V->max_route_length && 00665 M->savings/2+V->route[c_route].length> V->max_route_length) 00666 return false; 00667 } 00668 00669 M->evaluated_savings=false; 00670 if( (V->check_savings(M, rules))==false) 00671 return false; 00672 00673 00674 #endif 00675 00676 // Otherwise, the move is reasonable to consider further... 00677 00678 00679 if(a_route==c_route) 00680 { 00681 00682 // same route-- the 2opt move here corresponds to reversing the portion of 00683 // this route that is between a and c 00684 Flip flip; 00685 00686 // First the easy case - VRPH_DEPOT not involved 00687 00688 if(a!=VRPH_DEPOT && b!=VRPH_DEPOT && c!=VRPH_DEPOT && d!=VRPH_DEPOT) 00689 { 00690 00691 if(V->before(a,c)==true) 00692 { 00693 00694 00695 if( (flip.evaluate(V,a,d,M)==true)&&(V->check_move(M, rules)==true)) 00696 { 00697 00698 return true; 00699 } 00700 else 00701 { 00702 00703 return false; 00704 } 00705 } 00706 else 00707 { 00708 // a is after c 00709 if( (flip.evaluate(V,c,b,M)==true) &&(V->check_move(M, rules)==true)) 00710 { 00711 00712 return true; 00713 } 00714 else 00715 { 00716 00717 return false; 00718 } 00719 00720 } 00721 } 00722 else // VRPH_DEPOT involved 00723 { 00724 // Otherwise, we have a VRPH_DEPOT node 00725 // We'll need to use the dummy node 00726 int dummy= V->dummy_index; 00727 00728 if(a==VRPH_DEPOT) 00729 { 00730 // Put a dummy node between a and b and evaluate 00731 V->presert_dummy(b); 00732 if( (flip.evaluate(V,dummy,d,M)==true)&&(V->check_move(M, rules)==true)) 00733 { 00734 V->remove_dummy(); 00735 return true; 00736 } 00737 else 00738 { 00739 V->remove_dummy(); 00740 return false; 00741 } 00742 } 00743 00744 if(b==VRPH_DEPOT) 00745 { 00746 V->postsert_dummy(a); 00747 if( (flip.evaluate(V,c,dummy,M)==true)&&(V->check_move(M, rules)==true)) 00748 { 00749 V->remove_dummy(); 00750 return true; 00751 } 00752 else 00753 { 00754 V->remove_dummy(); 00755 return false; 00756 } 00757 } 00758 00759 if(c==VRPH_DEPOT) 00760 { 00761 00762 V->presert_dummy(d); 00763 if( (flip.evaluate(V,dummy,b,M)==true)&&(V->check_move(M, rules)==true)) 00764 { 00765 V->remove_dummy(); 00766 return true; 00767 } 00768 else 00769 { 00770 V->remove_dummy(); 00771 return false; 00772 } 00773 } 00774 00775 if(d==VRPH_DEPOT) 00776 { 00777 00778 V->postsert_dummy(c); 00779 00780 if( (flip.evaluate(V,a,dummy,M)==true)&&(V->check_move(M, rules)==true)) 00781 { 00782 V->remove_dummy(); 00783 return true; 00784 } 00785 else 00786 { 00787 V->remove_dummy(); 00788 return false; 00789 } 00790 } 00791 } 00792 } 00793 00794 // else the edges are in different routes 00795 00796 SwapEnds swap_ends; 00797 00798 // First the easy case - VRPH_DEPOT not involved 00799 00800 if(a!=VRPH_DEPOT && b!=VRPH_DEPOT && c!=VRPH_DEPOT && d!=VRPH_DEPOT) 00801 { 00802 if( (swap_ends.evaluate(V,a,c,M)==true)&&(V->check_move(M, rules)==true)) 00803 return true; 00804 else 00805 return false; 00806 } 00807 // else we have some VRPH_DEPOT nodes to deal with 00808 00809 int dummy= V->dummy_index; 00810 00811 // Case 2: a is the VRPH_DEPOT 00812 if(a==VRPH_DEPOT && b!=VRPH_DEPOT && c!=VRPH_DEPOT && d!=VRPH_DEPOT) 00813 { 00814 V->presert_dummy(b); 00815 if( (swap_ends.evaluate(V,dummy,c,M)==true)&&(V->check_move(M, rules)==true)) 00816 { 00817 V->remove_dummy(); 00818 return true; 00819 } 00820 else 00821 { 00822 V->remove_dummy(); 00823 return false; 00824 } 00825 00826 00827 00828 } 00829 00830 // Case 3: d is the VRPH_DEPOT 00831 if(d==VRPH_DEPOT && b!=VRPH_DEPOT && c!=VRPH_DEPOT && a!=VRPH_DEPOT) 00832 { 00833 V->postsert_dummy(c); 00834 if( (swap_ends.evaluate(V,a,c,M)==true)&&(V->check_move(M, rules)==true)) 00835 { 00836 V->remove_dummy(); 00837 return true; 00838 } 00839 else 00840 { 00841 V->remove_dummy(); 00842 return false; 00843 } 00844 00845 00846 } 00847 00848 // Case 4: c is the VRPH_DEPOT 00849 if(a!=VRPH_DEPOT && b!=VRPH_DEPOT && c==VRPH_DEPOT && d!=VRPH_DEPOT) 00850 { 00851 00852 V->presert_dummy(d); 00853 if( (swap_ends.evaluate(V,dummy,a,M)==true)&&(V->check_move(M, rules)==true)) 00854 { 00855 V->remove_dummy(); 00856 return true; 00857 } 00858 else 00859 { 00860 V->remove_dummy(); 00861 return false; 00862 } 00863 } 00864 00865 // Case 5: b is the VRPH_DEPOT 00866 if(a!=VRPH_DEPOT && b==VRPH_DEPOT && c!=VRPH_DEPOT && d!=VRPH_DEPOT) 00867 { 00868 00869 V->postsert_dummy(a); 00870 if( (swap_ends.evaluate(V,c,a,M)==true)&&(V->check_move(M, rules)==true)) 00871 { 00872 V->remove_dummy(); 00873 return true; 00874 } 00875 else 00876 { 00877 V->remove_dummy(); 00878 return false; 00879 } 00880 00881 } 00882 00883 // Should never get here! 00884 00885 report_error("%s: should never get here!\n",__FUNCTION__); 00886 return false; 00887 00888 } 00889 00890 bool TwoOpt::move(class VRP *V, VRPMove *M) 00891 { 00897 int a,b,c,d; 00898 00899 a=M->eval_arguments[0];b=M->eval_arguments[1];c=M->eval_arguments[2];d=M->eval_arguments[3]; 00900 00901 V->num_moves[TWO_OPT_INDEX]++; 00902 00903 if(M->move_type==FLIP && M->move_type==SWAP_ENDS) 00904 report_error("%s: unknown move type\n",__FUNCTION__); 00905 00906 bool uses_dummy=false; 00907 00908 // We have at most one VRPH_DEPOT node 00909 if(a==VRPH_DEPOT) 00910 { 00911 uses_dummy=true; 00912 V->presert_dummy(b); 00913 } 00914 00915 if(b==VRPH_DEPOT) 00916 { 00917 uses_dummy=true; 00918 V->postsert_dummy(a); 00919 } 00920 00921 if(c==VRPH_DEPOT) 00922 { 00923 uses_dummy=true; 00924 V->presert_dummy(d); 00925 } 00926 00927 if(d==VRPH_DEPOT) 00928 { 00929 uses_dummy=true; 00930 V->postsert_dummy(c); 00931 } 00932 00933 if(M->move_type==FLIP) 00934 { 00935 Flip flip; 00936 00937 if(flip.move(V, M->move_arguments[0], M->move_arguments[1])==true) 00938 { 00939 00940 if(uses_dummy) 00941 V->remove_dummy(); 00942 00943 V->capture_best_solution(); 00944 return true; 00945 } 00946 else 00947 { 00948 fprintf(stderr,"flip.move(%d,%d) is false\n",M->move_arguments[0],M->move_arguments[1]); 00949 report_error("%s: Flip error 1\n",__FUNCTION__); 00950 } 00951 } 00952 00953 // SWAP_ENDS otherwise 00954 SwapEnds swap_ends; 00955 00956 if(swap_ends.move(V,M->move_arguments[0],M->move_arguments[1])==true) 00957 { 00958 if(uses_dummy) 00959 V->remove_dummy(); 00960 00961 V->capture_best_solution(); 00962 00963 return true; 00964 } 00965 else 00966 report_error("%s: SwapEnds error 1\n",__FUNCTION__); 00967 00968 00969 return false; 00970 00971 } 00972