VRPH  1.0
src/TwoOpt.cpp
Go to the documentation of this file.
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