VRPH  1.0
src/OrOpt.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 bool OrOpt::search(class VRP *V, int a, int len, int rules)
00017 {
00022 
00023 
00024     VRPMove M, BestM;
00025     BestM.savings=VRP_INFINITY;
00026     int i,b,c,d;
00027     int string_end;
00028     int str[10];
00029         
00030     int accept_type;
00031 
00032     //default setting
00033     accept_type=VRPH_FIRST_ACCEPT;
00034 
00035     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00036         accept_type=VRPH_FIRST_ACCEPT;
00037     if( (rules & VRPH_BEST_ACCEPT) > 0)
00038         accept_type=VRPH_BEST_ACCEPT;
00039     if( (rules & VRPH_LI_ACCEPT) > 0)
00040         accept_type=VRPH_LI_ACCEPT;
00041     
00042     string_end = V->get_string_end(a,len);
00043 
00044     if(string_end==-1)
00045     {
00046         // We couldn't get a string of the right length
00047         return false;
00048     }
00049 
00050     if(rules & VRPH_FIXED_EDGES)
00051     {
00052         // Make sure we aren't disturbing fixed edges
00053         i=VRPH_MAX(V->pred_array[a],VRPH_DEPOT);
00054 
00055         if( V->fixed[i][a] ) 
00056             return false;
00057 
00058         i=VRPH_MAX(V->next_array[string_end],VRPH_DEPOT);
00059         if( V->fixed[string_end][i])
00060             return false;
00061     }
00062 
00063 
00064     // Load the string into the str array to look for the VRPH_DEPOT
00065     str[0]=a;
00066     for(i=1;i<len;i++)
00067     {
00068         str[i]= V->next_array[str[i-1]];
00069         if(str[i]<=VRPH_DEPOT)
00070             return false;
00071     }
00072 
00073     V->create_search_neighborhood(a, rules);
00074 
00075     int *old_sol=NULL;
00076     if(rules & VRPH_TABU)
00077     {
00078         // Remember the original solution 
00079         old_sol=new int[V->num_original_nodes+2];
00080         V->export_solution_buff(old_sol);
00081     }
00082         
00083     for(i=0;i<V->search_size;i++)
00084     {
00085         c=V->search_space[i];
00086     
00087         if(c!=VRPH_DEPOT)                
00088         {
00089             
00090             d=VRPH_MAX(V->next_array[c],0);
00091             b=VRPH_MAX(V->pred_array[c],0);
00092 
00093             int flag=0;
00094             if(d==VRPH_DEPOT)
00095                 flag=1;
00096 
00097             // Look for overlap
00098             
00099             for(int j=0;j<len;j++)
00100             {
00101                 if(str[j]==c || str[j]==d)
00102                     // Either c or d is already in the string that starts at a
00103                     flag=1;
00104             }
00105             if(flag==0)
00106             {
00107 
00108                 // Try the move
00109                 if(evaluate(V,a,len,c,d,rules, &M)==true)
00110                 {
00111                     // The move is good--make it
00112                     if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON))
00113                     {
00114                         if(move(V, &M)==false)
00115                             report_error("%s: move error 1\n",__FUNCTION__);
00116                         else
00117                         {
00118                             if(!(rules & VRPH_TABU))
00119                                 return true;
00120                             else
00121                             {
00122                                 // Check VRPH_TABU status of move - return true if its ok
00123                                 // or revert to old_sol if not and continue to search.
00124                                 if(V->check_tabu_status(&M, old_sol))
00125                                 {
00126                                     delete [] old_sol;
00127                                     return true; // The move was ok
00128                                 }
00129                                 // else we reverted back - continue the search for a move
00130                             }
00131                         }                        
00132                     }
00133 
00134                     if(accept_type == VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00135                     {
00136                         if(M.is_better(V, &BestM, rules))//if(M.savings<best_savings)
00137                             BestM=M;
00138                             
00139                     }
00140 
00141                     if(accept_type == VRPH_LI_ACCEPT)
00142                     {
00143                         // Move if downhill
00144                         if(M.savings<-VRPH_EPSILON)
00145                         {
00146                             if(move(V, &M)==false)
00147                                 report_error("%s: move error 2\n",__FUNCTION__);
00148                             else
00149                             {
00150                                 if(!(rules & VRPH_TABU))
00151                                     return true;
00152                                 else
00153                                 {
00154                                     // Check VRPH_TABU status of move - return true if its ok
00155                                     // or revert to old_sol if not and continue to search.
00156                                     if(V->check_tabu_status(&M, old_sol))
00157                                     {
00158                                         delete [] old_sol;
00159                                         return true; // The move was ok
00160                                     }
00161                                     // else we reverted back - continue the search for a move
00162                                 }
00163                             }                        
00164                         }
00165                         else
00166                         {
00167                             // Uphill move - see if it's the best so far
00168                             if(M.is_better(V, &BestM, rules))//if(M.savings<BestM.savings)
00169                                 BestM=M;
00170                         }
00171                     }
00172                 }
00173             }
00174         }
00175     }
00176 
00177     if(accept_type == VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00178     {
00179         if(old_sol)
00180             delete [] old_sol;
00181         return false ; // No moves found
00182     }
00183 
00184     if(move(V,&BestM)==true)
00185     {
00186         if(!(rules & VRPH_TABU))
00187             return true;                    
00188     }
00189     
00190     if(rules & VRPH_TABU)
00191     {    
00192         // Check VRPH_TABU status of move - return true if its ok
00193         // or revert to old_sol if not and return
00194         if(V->check_tabu_status(&BestM, old_sol))// was &M??
00195         {
00196             delete [] old_sol;
00197             return true; // The move was ok
00198         }
00199         else
00200         {
00201             delete [] old_sol;
00202             return false;
00203         }
00204     }
00205         
00206     // Should have already returned
00207     report_error("%s: move error\n",__FUNCTION__);
00208     return false;
00209 
00210 
00211 }
00212 
00213 bool OrOpt::route_search(VRP *V, int r1, int r2, int len, int rules)
00214 {
00220 
00221     VRPMove M, BestM;
00222     BestM.savings=VRP_INFINITY;
00223     int c,d;
00224     int accept_type;
00225 
00226     //default setting
00227     accept_type=VRPH_FIRST_ACCEPT;
00228 
00229     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00230         accept_type=VRPH_FIRST_ACCEPT;
00231     if( (rules & VRPH_BEST_ACCEPT) > 0)
00232         accept_type=VRPH_BEST_ACCEPT;
00233     if( (rules & VRPH_LI_ACCEPT) > 0)
00234         accept_type=VRPH_LI_ACCEPT;
00235 
00236     int j;
00237     j= V->route[r1].start;
00238     while(j!=VRPH_DEPOT)
00239     {
00240         // Loop through r1 and r2
00241         c= V->route[r2].start;
00242         while(c!=VRPH_DEPOT)
00243         {
00244             d=VRPH_MAX(V->next_array[c],0);
00245             if(evaluate(V,j,len,c,d,rules, &M)==true)
00246             {
00247                 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00248                 {    
00249                     // Make the move
00250                     if(move(V,&M)==false)
00251                         report_error("%s: first accept move returns false",__FUNCTION__);
00252                     else    
00253                         return true;
00254                 }
00255 
00256 
00257                 if(accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT)
00258                 {
00259                     if(M.is_better(V, &BestM, rules))
00260                         BestM=M;                
00261 
00262                 }
00263 
00264             }
00265 
00266             // Advance r2 node
00267             c=d;
00268         }
00269 
00270         // Advance r1 node
00271         j=VRPH_MAX(V->next_array[j],0);
00272     }
00273 
00274     if(accept_type==VRPH_FIRST_ACCEPT)
00275         return false; // No moves found
00276 
00277     if(BestM.savings==VRP_INFINITY)
00278         return false;
00279 
00280     if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00281     {
00282         
00283             // Make the move
00284             if(move(V,&BestM)==false)
00285                 report_error("%s: first accept move returns false\n",__FUNCTION__);
00286             else    
00287                 return true;
00288 
00289     }
00290 
00291     report_error("%s: shouldn't get here...\n",__FUNCTION__);
00292 
00293     return false;
00294 
00295 }
00296 
00297 bool OrOpt::evaluate(class VRP *V, int a, int len, int c, int d, int rules, VRPMove *M)
00298 {
00303 
00304     V->num_evaluations[OR_OPT_INDEX]++;
00305 
00306     M->evaluated_savings=false;
00307 
00308     if(rules & VRPH_FIXED_EDGES)
00309     {
00310         // Make sure we aren't disturbing fixed edges
00311         if( V->fixed[c][d] ) 
00312             return false;
00313     }    
00314 
00315     if(V->routed[a]==false || V->routed[c]==false  ||
00316         V->routed[d]==false )
00317         return false;
00318 
00319     int a_route, c_route;
00320 
00321     M->eval_arguments[0]=a;M->eval_arguments[1]=len;
00322     M->eval_arguments[2]=c;M->eval_arguments[3]=d;
00323 
00324     // First make sure the edge c-d exists
00325     if(c!=VRPH_DEPOT && VRPH_MAX(V->next_array[c],0)!=d )
00326         report_error("%s: c-d not an edge!\n",__FUNCTION__);
00327         
00328 
00329     if(c==VRPH_DEPOT && VRPH_MAX(V->pred_array[d],0)!=c)
00330         report_error("%s: c-d not an edge!\n",__FUNCTION__);
00331     
00332 
00333     a_route= V->route_num[a];
00334     if(c!=VRPH_DEPOT)
00335         c_route= V->route_num[c];
00336     else
00337         c_route= V->route_num[d];
00338 
00339     
00340     if( (rules & VRPH_INTER_ROUTE_ONLY) && (a_route ==c_route))
00341         return false;
00342 
00343     if((rules & VRPH_INTRA_ROUTE_ONLY) && a_route !=c_route)
00344         return false;
00345     
00346     // Construct the appropriate string;
00347 
00348     int string_end = V->get_string_end(a, len);
00349     if(string_end==-1)
00350         // The string of length len beginning at a is not contained in a single route
00351         return false;
00352 
00353     if(rules & VRPH_FIXED_EDGES)
00354     {
00355         // Make sure we aren't disturbing fixed edges
00356         int z,b;
00357 
00358         z=VRPH_MAX(V->pred_array[a],VRPH_DEPOT);
00359         b=VRPH_MAX(V->next_array[string_end],VRPH_DEPOT);
00360 
00361         if( V->fixed[z][a] || V->fixed[string_end][b] ) 
00362             return false;
00363         
00364         
00365     }
00366 
00367     // Now just use MoveString to evaluate
00368 
00369     MoveString MS;
00370 
00371     if(MS.evaluate(V,c,d,a,string_end, M)==true) 
00372     {
00373         if(V->check_move(M,rules)==true)
00374             return true;
00375         else
00376             return false;
00377         
00378     }
00379     
00380 
00381     return false;
00382 
00383 
00384 }
00385 
00386 
00387 
00388 bool OrOpt::move(class VRP *V, VRPMove *M)
00389 {
00394 
00395     int a,len,c,d;
00396 
00397     a=M->eval_arguments[0];
00398     len=M->eval_arguments[1];
00399     c=M->eval_arguments[2];
00400     d=M->eval_arguments[3];
00401 
00402     int string_end = V->get_string_end(a, len);
00403     if(string_end==-1)
00404     {
00405         report_error("%s: no string end in move??\n",__FUNCTION__);
00406         
00407     }
00408 
00409     MoveString MS;
00410 
00411     if(    MS.move(V,c,d,a,string_end)==false)
00412     {
00413         report_error("%s: MS.move is false!\n",__FUNCTION__);
00414         
00415     }
00416 
00417     V->num_moves[OR_OPT_INDEX]++;
00418     V->capture_best_solution();
00419     return true;
00420 }