VRPH  1.0
src/OnePointMove.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 OnePointMove::search(class VRP *V, int j, int rules)
00017 {
00023     
00024     VRPMove M;
00025     VRPMove BestM;
00026     M.savings=M.new_total_route_length=BestM.savings=BestM.new_total_route_length=VRP_INFINITY;
00027 
00028     int i,k;
00029     int best_k=0;
00030     int accept_type;
00031 
00032     i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00033     k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00034 
00035     // Return false if there are two or fewer nodes in i's route
00036     if(V->route[V->route_num[j]].num_customers<=3)
00037         return false;
00038 
00039     if( (rules & VRPH_FIXED_EDGES)  )
00040     {
00041         // Make sure we aren't disturbing fixed edges
00042         if( (V->fixed[i][j]) || (V->fixed[j][k]) )
00043             return false;
00044 
00045     }    
00046 
00047     // Determine acceptance type
00048     //default setting
00049     accept_type=VRPH_FIRST_ACCEPT;
00050 
00051     if( rules & VRPH_FIRST_ACCEPT )
00052         accept_type=VRPH_FIRST_ACCEPT;
00053     if( rules & VRPH_BEST_ACCEPT )
00054         accept_type=VRPH_BEST_ACCEPT;
00055     if( rules & VRPH_LI_ACCEPT )
00056         accept_type=VRPH_LI_ACCEPT;
00057 
00058     // Create the search_space
00059     V->create_search_neighborhood(j, rules);    
00060 
00061     int *old_sol=NULL;
00062     if(rules & VRPH_TABU)
00063     {
00064         // Remember the original solution 
00065         old_sol=new int[V->num_original_nodes+2];
00066         V->export_solution_buff(old_sol);
00067     }
00068         
00069     for(i=0;i<V->search_size;i++)
00070     {            
00071         k=V->search_space[i];
00072         if(evaluate(V,j,k,rules,&M)==true)
00073         {
00074             // Feasible move found
00075             if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00076             {
00077                 if(move(V, &M)==false)
00078                     report_error("%s: move error 1\n",__FUNCTION__);
00079                 else
00080                 {
00081                     if(!(rules & VRPH_TABU))
00082                         return true;
00083                     else
00084                     {
00085                         // Check VRPH_TABU status of move - return true if its ok
00086                         // or revert to old_sol if not and continue to search.
00087                         if(V->check_tabu_status(&M, old_sol))
00088                         {
00089                             delete [] old_sol;
00090                             return true; // The move was ok
00091                         }
00092                         // else we reverted back - continue the search for a move
00093                     }
00094                 }
00095             }
00096 
00097             if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00098             {
00099                 // store the move
00100 
00101                 if(M.is_better(V, &BestM, rules))
00102                 {
00103                     best_k=k;
00104                     BestM=M;
00105                 }
00106             }                
00107         }
00108     }        
00109 
00110 
00111     // We've considered all the possibilities now...
00112     if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00113     {
00114         // No moves found
00115         if(old_sol)
00116             delete [] old_sol;
00117         return false;
00118     }
00119 
00120     // else we found a move - try to make it
00121 
00122 
00123     if(move(V,&BestM)==true)
00124     {
00125         if(!(rules & VRPH_TABU))
00126             return true;                    
00127     }
00128     
00129     if(rules & VRPH_TABU)
00130     {    
00131         // Check VRPH_TABU status of move - return true if its ok
00132         // or revert to old_sol if not and return
00133         if(V->check_tabu_status(&BestM, old_sol))// was &M??
00134         {
00135             delete [] old_sol;
00136             return true; // The move was ok
00137         }
00138         else
00139         {
00140             delete [] old_sol;
00141             return false;
00142         }
00143     }
00144         
00145     // Should have already returned
00146     report_error("%s: move error 4\n",__FUNCTION__);    
00147 
00148     return false;
00149 }
00150 
00151 
00152 bool OnePointMove::route_search(class VRP *V, int r1, int r2, int rules)
00153 {
00158 
00159     // So search is now ROUTE_BASED - no neighbor_lists
00160     if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0)
00161         report_error("%s: route_searches do not use neighbor list\n",__FUNCTION__);
00162 
00163     // Otherwise, we have a route search - look for all moves involving 
00164     // route r1 and route r2
00165 
00166     VRPMove M;
00167     VRPMove BestM;
00168     int k;
00169     double best_savings=VRP_INFINITY;
00170     int best_k=0;
00171     int accept_type;
00172 
00173 
00174     //default setting
00175     accept_type=VRPH_FIRST_ACCEPT;
00176 
00177     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00178         accept_type=VRPH_FIRST_ACCEPT;
00179     if( (rules & VRPH_BEST_ACCEPT) > 0)
00180         accept_type=VRPH_BEST_ACCEPT;
00181     if( (rules & VRPH_LI_ACCEPT) > 0)
00182         accept_type=VRPH_LI_ACCEPT;
00183         
00184 
00185     int j;
00186     j= V->route[r1].start;
00187     while(j!=VRPH_DEPOT)
00188     {
00189         // Loop through r1 and r2
00190         k= V->route[r2].start;
00191         while(k!=VRPH_DEPOT)
00192         {
00193             if(evaluate(V,j,k,rules,&M)==true)
00194             {
00195 
00196                 // Feasible move found
00197                 if(accept_type==VRPH_FIRST_ACCEPT)
00198                 {
00199                     // This is the first move found -- make it and return if VRPH_FIRST_ACCEPT
00200                     
00201                     if(move(V,&M)==true)
00202                         return true;
00203                     else
00204                         report_error("%s: move is false?\n",__FUNCTION__);
00205                                 
00206                 }
00207 
00208                 if(accept_type==VRPH_BEST_ACCEPT)
00209                 {
00210                     // VRPH_BEST_ACCEPT - store the move
00211 
00212                     if(M.savings<best_savings)
00213                     {
00214                         best_savings=M.savings;
00215                         best_k=k;
00216                         BestM=M;
00217                     }
00218                 }
00219 
00220                 if(accept_type==VRPH_LI_ACCEPT)
00221                 {
00222                     // move if downhill, store otherwise.
00223                     
00224                     if(M.savings<-VRPH_EPSILON)
00225                     {
00226                         // it's downhill, so make it.
00227                         if(move(V,&M)==true)
00228                             return true;
00229                         else
00230                             report_error("%s: false 7\n",__FUNCTION__);
00231                     }
00232 
00233                     if(M.savings<best_savings)
00234                     {
00235                         best_savings=M.savings;
00236                         best_k=k;
00237                         BestM=M;
00238                     }
00239                 }
00240             }
00241             k=VRPH_MAX(V->next_array[k],0);
00242         }
00243         j=VRPH_MAX(V->next_array[j],0);
00244     }
00245 
00246     if(accept_type==VRPH_FIRST_ACCEPT)
00247     {
00248         // No moves found
00249         return false;
00250     }
00251 
00252     // Otherwise we will make the best move found
00253     if(best_savings==VRP_INFINITY)
00254         return false;
00255 
00256     // else we found a move - make it
00257     if(move(V,&BestM)==true)
00258         return true;
00259     else
00260         report_error("%s: false 8\n",__FUNCTION__);
00261     
00262     return false;
00263     
00264 
00265 }
00266 
00267 // EVALUATE
00268 bool OnePointMove::evaluate(class VRP *V, int j, int b, int rules, VRPMove *M)
00269 {
00275 
00276     V->num_evaluations[ONE_POINT_MOVE_INDEX]++;
00277 
00278     int a,c,i,k;
00279 
00280     a = VRPH_MAX(V->pred_array[b],VRPH_DEPOT);
00281     c = VRPH_MAX(V->next_array[b],VRPH_DEPOT);
00282     k = VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00283     i = VRPH_MAX(V->pred_array[j],VRPH_DEPOT);
00284 
00285 
00286     if(rules & VRPH_FIXED_EDGES)
00287     {        
00288         // Make sure we aren't disturbing fixed edges
00289 
00290         if( V->fixed[i][j]|| V->fixed[j][k] )
00291             return false;
00292 
00293         if(b!=VRPH_DEPOT &&  (V->fixed[b][c] && V->fixed[a][b]) )
00294             return false;
00295     }
00296 
00297     M->evaluated_savings=false;
00298 
00299     if(b==j || V->routed[j]==false || V->routed[b]==false || j==VRPH_DEPOT) 
00300         return false;
00301 
00302     if(b!=VRPH_DEPOT)
00303     {
00304         if( (rules & VRPH_INTER_ROUTE_ONLY) && (V->route_num[j] ==V->route_num[b]) )
00305             return false;
00306 
00307         if((rules & VRPH_INTRA_ROUTE_ONLY) && (V->route_num[j] !=V->route_num[b]) )
00308             return false;
00309 
00310         // Can quickly check veh capacity: j added to V->route_num[b]
00311         if(V->route_num[j] != V->route_num[b])
00312         {
00313             if( V->nodes[j].demand + V->route[V->route_num[b]].load > V->max_veh_capacity)
00314                 return false;
00315         }
00316 
00317 
00318     }
00319     
00320     double savings1, savings2, best_savings;
00321     Postsert postsert;
00322     Presert presert;
00323     best_savings=VRP_INFINITY;
00324     savings1=VRP_INFINITY;
00325     savings2=VRP_INFINITY;
00326 
00327     // First consider the complicated case where b is the VRPH_DEPOT.
00328     // We have 2*r edges to consider where r is the # of routes
00329     // In this case we will find the best possible insertion
00330     if(b==VRPH_DEPOT)
00331     {
00332         int current_start, current_end, current_route;
00333         current_start=abs(V->next_array[VRPH_DEPOT]);
00334         bool allowed, found_move;
00335         VRPMove CurrentM;
00336         found_move=false;
00337         
00338         for(;;)
00339         {
00340             // Consider the edge VRPH_DEPOT-current_start
00341             int t=current_start;
00342             allowed=true;
00343 
00344             if(j!=t)
00345             {
00346                 // Check for fixed edges
00347                 if((rules & VRPH_FIXED_EDGES) && V->fixed[VRPH_DEPOT][t])
00348                     allowed=false;
00349 
00350                 if( (presert.evaluate(V,j,t,&CurrentM)==true)&&(V->check_move(&CurrentM,rules)==true) && allowed )
00351                 {
00352                     
00353                     if(CurrentM.is_better(V,M,rules))
00354                     {
00355                         found_move=true;
00356                         *M=CurrentM;
00357                     }
00358                 }
00359             }
00360 
00361             // Now try the t-VRPH_DEPOT edge                
00362             current_route= V->route_num[current_start];
00363             current_end= V->route[current_route].end;
00364             t=current_end;
00365             allowed=true;
00366             if(j!=t)
00367             {
00368                 // Check for fixed edges
00369                 if((rules & VRPH_FIXED_EDGES) && V->fixed[t][VRPH_DEPOT])
00370                     allowed=false;
00371 
00372                 if( (postsert.evaluate(V,j,t,&CurrentM)==true)&&(V->check_move(&CurrentM,rules)==true) && allowed )
00373                 {
00374                     if(CurrentM.is_better(V,M,rules))
00375                     {
00376                         found_move=true;
00377                         *M=CurrentM;
00378                     }
00379                 }
00380                 
00381             }
00382 
00383             // Now advance to the next node adjacent to the VRPH_DEPOT
00384             current_start=abs(V->next_array[current_end]);
00385             if(current_start==VRPH_DEPOT)    // We're done
00386                 break;
00387         }
00388 
00389         return found_move;
00390 
00391         
00392     }
00393     
00394     // Special Case
00395     if(c == j)
00396     {
00397         // Only option is to insert j between a and b (b is not VRPH_DEPOT)
00398 
00399         if(rules & VRPH_FIXED_EDGES)
00400         {
00401             // Make sure we aren't disturbing fixed edges
00402 
00403             if( V->fixed[a][b] )//|| V->fixed[b][c])
00404                 return false;
00405         }
00406         
00407         if( (presert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true) )
00408             return true;
00409         else
00410             return false;
00411         
00412     }
00413 
00414 
00415     if(a == j)
00416     {
00417         // Only option is to insert j between b and c.  b is not VRPH_DEPOT
00418 
00419         if(rules & VRPH_FIXED_EDGES)
00420         {
00421             // Make sure we aren't disturbing fixed edges
00422 
00423             if( V->fixed[b][c] )//|| V->fixed[a][b] ) 
00424                 return false;
00425         }
00426 
00427         if( (postsert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true) )
00428             return true;
00429         else
00430             return false;
00431         
00432     }
00433     
00434     // No conflicts o/w    - can insert j either before or after b 
00435     // We will choose the better move always!
00436 
00437     // savings = new-old
00438     savings1 = (V->d[a][j]+V->d[j][b]+V->d[i][k]) - (V->d[a][b]+V->d[i][j]+V->d[j][k])  ;
00439     savings2 = (V->d[i][k]+V->d[b][j]+V->d[j][c]) - (V->d[b][c]+V->d[i][j]+V->d[j][k])  ;
00440 
00441     best_savings = VRPH_MIN(savings1, savings2);
00442 
00443     
00444     if( savings1 <= savings2 &&  (presert.evaluate(V,j,b,M)==true)
00445         &&(V->check_move(M,rules)==true) )
00446     {
00447 
00448         if(rules & VRPH_FIXED_EDGES)
00449         {
00450             // Make sure we aren't disturbing fixed edges
00451 
00452             if( V->fixed[a][b] )//|| V->fixed[b][c] ) 
00453                 return false;
00454         }
00455         return true;
00456     }
00457     
00458     // Now check savings2
00459     if( savings2<savings1 && postsert.evaluate(V,j,b,M)==true &&
00460         (V->check_move(M,rules)==true) )
00461     {
00462 
00463         if(rules & VRPH_FIXED_EDGES)
00464         {
00465             // Make sure we aren't disturbing fixed edges
00466 
00467             if( V->fixed[b][c] )//|| V->fixed[a][b] ) 
00468                 return false;
00469         }
00470 
00471         return true;
00472     }
00473 
00474     // Need to check savings1 again in the event that savings2 was better, but the move
00475     // itself was infeasible--not sure if this ever happens...
00476 
00477     if( (presert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true))
00478     {
00479         if(rules & VRPH_FIXED_EDGES)
00480         {
00481             // Make sure we aren't disturbing fixed edges
00482 
00483             if( V->fixed[a][b] )//|| V->fixed[b][c]) 
00484                 return false;
00485         }
00486 
00487         return true;
00488     }
00489     
00490 
00491     
00492     // ELSE no feasible moves found
00493     return false;
00494 }
00495 
00496 bool OnePointMove::move(class VRP *V, VRPMove *M)
00497 {
00501     
00502         
00503     if(M->move_type==PRESERT)
00504     {
00505         Presert presert;
00506         if(presert.move(V,M->move_arguments[0],M->move_arguments[1]))
00507         {
00508             V->num_moves[ONE_POINT_MOVE_INDEX]++;
00509             V->capture_best_solution();
00510 
00511             return true;
00512         }
00513         else
00514             report_error("%s: presert move is false\n",__FUNCTION__);
00515 
00516 
00517     }
00518     else
00519     {
00520         if(M->move_type==POSTSERT)
00521         {
00522             Postsert postsert;
00523             if(postsert.move(V,M->move_arguments[0],M->move_arguments[1]))
00524             {
00525                 V->num_moves[ONE_POINT_MOVE_INDEX]++;
00526                 V->capture_best_solution();
00527                 return true;
00528             }
00529             else
00530                 report_error("%s: postsert move is false\n",__FUNCTION__);
00531         }
00532     }
00533     
00534     return false;
00535     
00536 }