00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015
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;
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
00045 old_sol=new int[V->num_original_nodes+2];
00046 V->export_solution_buff(old_sol);
00047 }
00048
00049
00050 V->create_search_neighborhood(b, rules);
00051
00052 BestM.savings=VRP_INFINITY;
00053
00054
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
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
00080
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
00099
00100 if(V->check_tabu_status(&M, old_sol))
00101 {
00102 delete [] old_sol;
00103 return true;
00104 }
00105
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
00140
00141 if(V->check_tabu_status(&M, old_sol))
00142 {
00143 delete [] old_sol;
00144 return true;
00145 }
00146
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
00178
00179 if(V->check_tabu_status(&M, old_sol))
00180 {
00181 delete [] old_sol;
00182 return true;
00183 }
00184
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
00217
00218 if(V->check_tabu_status(&M, old_sol))
00219 {
00220 delete [] old_sol;
00221 return true;
00222 }
00223
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
00240
00241
00242 if(j==VRPH_DEPOT && j!=b)
00243 {
00244
00245
00246
00247
00248 int current_start, current_end, current_route;
00249 current_start=abs(V->next_array[VRPH_DEPOT]);
00250
00251
00252 for(;;)
00253 {
00254
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
00271
00272 if(V->check_tabu_status(&M, old_sol))
00273 {
00274 delete [] old_sol;
00275 return true;
00276 }
00277
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
00309
00310 if(V->check_tabu_status(&M, old_sol))
00311 {
00312 delete [] old_sol;
00313 return true;
00314 }
00315
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
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
00352
00353 if(V->check_tabu_status(&M, old_sol))
00354 {
00355 delete [] old_sol;
00356 return true;
00357 }
00358
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
00390
00391 if(V->check_tabu_status(&M, old_sol))
00392 {
00393 delete [] old_sol;
00394 return true;
00395 }
00396
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
00415 current_start=abs(V->next_array[current_end]);
00416 if(current_start==VRPH_DEPOT)
00417 break;
00418 }
00419
00420
00421
00422 }
00423
00424 }
00425
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;
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
00458
00459 if(V->check_tabu_status(&BestM, old_sol))
00460 {
00461 delete [] old_sol;
00462 return true;
00463 }
00464
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;
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
00513
00514
00515
00516 j= V->route[r2].start;
00517 i=VRPH_DEPOT;
00518 for(;;)
00519 {
00520
00521
00522
00523
00524 current_savings=VRP_INFINITY;
00525
00526
00527
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
00542
00543 if(M.is_better(V, &BestM, rules))
00544 BestM=M;
00545 }
00546 }
00547
00548
00549 i=j;
00550 if(i==VRPH_DEPOT)
00551 break;
00552 j=VRPH_MAX(V->next_array[j],0);
00553 }
00554
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;
00566
00567 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT))
00568 {
00569
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
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
00597 return false;
00598 }
00599
00600
00601 if(rules & VRPH_FIXED_EDGES)
00602 {
00603 if(V->fixed[a][b] || V->fixed[c][d])
00604 return false;
00605 }
00606
00607
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
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
00641
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
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
00660
00661
00662
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
00677
00678
00679 if(a_route==c_route)
00680 {
00681
00682
00683
00684 Flip flip;
00685
00686
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
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
00723 {
00724
00725
00726 int dummy= V->dummy_index;
00727
00728 if(a==VRPH_DEPOT)
00729 {
00730
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
00795
00796 SwapEnds swap_ends;
00797
00798
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
00808
00809 int dummy= V->dummy_index;
00810
00811
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
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
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
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
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
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
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