VRPH  1.0
src/TwoPointMove.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 
00016 // SEARCH
00017 bool TwoPointMove::search(class VRP *V, int j, int rules)
00018 {
00025 
00026     VRPMove M;
00027     VRPMove BestM;
00028     BestM.savings=VRP_INFINITY;
00029     int i,k;
00030     int accept_type;
00031 
00032     if(j==VRPH_DEPOT)        
00033         return false;
00034 
00035     if(rules & VRPH_FIXED_EDGES)
00036     {
00037         i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00038         k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00039 
00040         // Make sure we aren't disturbing fixed edges
00041 
00042         if( V->fixed[i][j] || V->fixed[j][k] ) 
00043             return false;
00044     }
00045 
00046     accept_type=VRPH_FIRST_ACCEPT;//default
00047 
00048     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00049         accept_type=VRPH_FIRST_ACCEPT;
00050     if( (rules & VRPH_BEST_ACCEPT) > 0)
00051         accept_type=VRPH_BEST_ACCEPT;
00052     if( (rules & VRPH_LI_ACCEPT) > 0)
00053         accept_type=VRPH_LI_ACCEPT;
00054 
00055     int *old_sol=NULL;
00056     if(rules & VRPH_TABU)
00057     {
00058         // Remember the original solution 
00059         old_sol=new int[V->num_original_nodes+2];
00060         V->export_solution_buff(old_sol);
00061     }
00062 
00063     // Create the search_space
00064     V->create_search_neighborhood(j, rules);
00065 
00066     for(i=0;i<V->search_size;i++)
00067     {
00068         k=V->search_space[i];
00069 
00070         if(k!=VRPH_DEPOT && k!=j)
00071         {
00072             // VRPH_DEPOT not allowed in TwoPointMove
00073 
00074             if(evaluate(V,j,k,rules,&M)==true)
00075             {
00076                 // Feasible move found
00077                 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00078                 {
00079                     // make the move
00080 
00081                     if(move(V, &M)==false)
00082                         report_error("%s: move error 1\n",__FUNCTION__);
00083                     else
00084                     {
00085                         if(!(rules & VRPH_TABU))
00086                             return true;
00087                         else
00088                         {
00089                             // Check VRPH_TABU status of move - return true if its ok
00090                             // or revert to old_sol if not and continue to search.
00091                             if(V->check_tabu_status(&M, old_sol))
00092                             {
00093                                 delete [] old_sol;
00094                                 return true; // The move was ok
00095                             }
00096 
00097                         }
00098                     }
00099                 }
00100 
00101 
00102 
00103                 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT )
00104                 {
00105                     // compare to best move so far
00106                     if(M.is_better(V, &BestM, rules))
00107                         BestM=M;
00108 
00109                 }
00110 
00111             }
00112         }
00113     }
00114 
00115 
00116 
00117     if(accept_type==VRPH_FIRST_ACCEPT)
00118     {
00119         if(old_sol)
00120             delete [] old_sol;
00121         return false;
00122     }
00123 
00124     if(BestM.savings==VRP_INFINITY)
00125     {
00126         if(old_sol)
00127             delete [] old_sol;
00128         return false;
00129     }
00130     // else we found a move - make it
00131 
00132     if(move(V,&BestM)==true)
00133     {
00134         if(!(rules & VRPH_TABU))
00135             return true;                    
00136     }
00137 
00138     if(rules & VRPH_TABU)
00139     {    
00140         // Check VRPH_TABU status of move - return true if its ok
00141         // or revert to old_sol if not and return
00142         if(V->check_tabu_status(&M, old_sol))
00143         {
00144             delete [] old_sol;
00145             return true; // The move was ok
00146         }
00147         else
00148         {
00149             delete [] old_sol;
00150             return false;
00151         }
00152     }
00153 
00154 
00155     report_error("%s: best move false!\n",__FUNCTION__);
00156 
00157 
00158     return false;
00159 }
00160 
00161 
00162 bool TwoPointMove::route_search(class VRP *V, int r1, int r2, int rules)
00163 {
00168 
00169 
00170     VRPMove M;
00171     VRPMove BestM;
00172     int j,k;
00173     int accept_type;
00174 
00175     BestM.savings=VRP_INFINITY;
00176 
00177     if(r1==r2)
00178     {
00179         fprintf(stderr,"TPM::%d==%d???\n",r1,r2);
00180         report_error("%s: called with r1==r2\n",__FUNCTION__);
00181     }
00182 
00183     if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0)
00184         report_error("%s: ROUTE_BASED search does not use neighbor_list\n",__FUNCTION__);
00185 
00186     accept_type=VRPH_FIRST_ACCEPT;//default
00187 
00188     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00189         accept_type=VRPH_FIRST_ACCEPT;
00190     if( (rules & VRPH_BEST_ACCEPT) > 0)
00191         accept_type=VRPH_BEST_ACCEPT;
00192     if( (rules & VRPH_LI_ACCEPT) > 0)
00193         accept_type=VRPH_LI_ACCEPT;
00194 
00195 
00196     j= V->route[r1].start;
00197     while(j!=VRPH_DEPOT)
00198     {
00199 
00200         k= V->route[r2].start;
00201         while(k!=VRPH_DEPOT)
00202         {
00203             // Try to swap nodes j and k
00204             if(evaluate(V,j,k,rules,&M)==true)
00205             {
00206                 // valid move found
00207                 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00208                 {
00209                     // make the move
00210                     if(move(V,&M)==false)
00211                         report_error("%s: first accept move is false!\n",__FUNCTION__);
00212                     else
00213                         return true;
00214                 }
00215 
00216                 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT) )
00217                 {
00218 
00219                     // See if it's the best so far...
00220                     if(M.is_better(V, &BestM, rules))
00221                         BestM=M;
00222                 }
00223 
00224 
00225             }
00226             // Advance the route r2 node
00227             k=VRPH_MAX(V->next_array[k],0);
00228         }
00229         // Advance the route r1 node
00230         j=VRPH_MAX(V->next_array[j],0);
00231     }
00232 
00233 
00234     if(accept_type==VRPH_FIRST_ACCEPT)
00235         return false;    // No moves found
00236     if(BestM.savings == VRP_INFINITY)
00237         return false;
00238 
00239     if( (accept_type == VRPH_LI_ACCEPT) || (accept_type == VRPH_BEST_ACCEPT))
00240     {
00241 
00242         // We found a move -- make it...
00243         if(move(V,&BestM)==false)
00244             report_error("%s: best move is false!\n",__FUNCTION__);
00245         else
00246             return true;
00247 
00248     }
00249 
00250     report_error("%s: shouldn't be here...\n",__FUNCTION__);
00251 
00252     return false;
00253 
00254 }
00255 
00256 bool TwoPointMove::evaluate(class VRP *V, int j, int b, int rules, VRPMove *M)
00257 {
00264 
00265     V->num_evaluations[TWO_POINT_MOVE_INDEX]++;    
00266 
00267     if(V->routed[j]==false || V->routed[b]==false || j==b)
00268         return false;
00269 
00270     if(rules & VRPH_FIXED_EDGES)
00271     {
00272         // Make sure we aren't disturbing fixed edges
00273         int i,k,a,c;
00274 
00275         a=VRPH_MAX(V->pred_array[b],VRPH_DEPOT);
00276         c=VRPH_MAX(V->next_array[b],VRPH_DEPOT);
00277 
00278         i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00279         k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00280 
00281         if( V->fixed[a][b] || V->fixed[b][c] || V->fixed[i][j] || V->fixed[j][k] ) 
00282             return false;
00283     }
00284 
00285     M->evaluated_savings=false;// false until we check
00286 
00287 
00288     class Swap swap;
00289 
00290     if(V->routed[j]==false || V->routed[b]==false)
00291         return false;
00292 
00293     if(j==VRPH_DEPOT || b==VRPH_DEPOT || j==b)
00294     {
00295         fprintf(stderr,"TPM::j=%d, b=%d\n",j,b);
00296         report_error("%s: evaluate() called with bad arguments??\n",__FUNCTION__);
00297     }
00298 
00299     if((rules & VRPH_INTER_ROUTE_ONLY) && (V->route_num[j]==V->route_num[b]) )
00300         return false;
00301 
00302     if((rules & VRPH_INTRA_ROUTE_ONLY) && (V->route_num[j]!=V->route_num[b]) )
00303         return false;
00304 
00305 
00306     if( (swap.evaluate(V,j,b,M)==true) && (V->check_move(M, rules)==true))
00307     {
00308         return true;
00309         // The move is good
00310     }
00311     else
00312     {
00313         // Not allowed
00314         return false;
00315     }
00316 
00317 }
00318 
00319 
00320 bool TwoPointMove::move(class VRP *V, VRPMove *M)
00321 {
00322 
00326 
00327     if(M->move_type!=SWAP)
00328         report_error("%s: Unknown move type\n",__FUNCTION__);
00329 
00330     class Swap swap;
00331 
00332     if(swap.move(V,M->move_arguments[0], M->move_arguments[1])==false)
00333     {
00334         // This is an error
00335         report_error("%s: TPM::swap.move evaluates to false!!\n",__FUNCTION__);
00336 
00337     }
00338 
00339     V->capture_best_solution();
00340     V->num_moves[TWO_POINT_MOVE_INDEX]++;
00341 
00342     return true;
00343 
00344 }
00345