VRPH  1.0
src/ThreeOpt.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 ThreeOpt::route_search(class VRP *V, int r, int rules)
00017 {
00023 
00024     VRPMove M, BestM;
00025     int ii,a,b,c,d,e,f;
00026 
00027     BestM.savings=VRP_INFINITY;
00028 
00029     int e11, e12, e21, e22, e31, e32;
00030     // The edges involved in the move: e1, e2, e3
00031     
00032 
00033     int accept_type=VRPH_FIRST_ACCEPT;
00034 
00035     // Initialize to null edges
00036     e11=e12=e21=e22=e31=e32=0;    
00037 
00038     if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0)
00039         report_error("%s: neighbor_list not used in 3OPT search--searches all nodes in route\n",__FUNCTION__);
00040 
00041     accept_type = VRPH_FIRST_ACCEPT;    //default
00042 
00043     if( (rules & VRPH_LI_ACCEPT) == VRPH_LI_ACCEPT)
00044         accept_type=VRPH_LI_ACCEPT;
00045 
00046     if( (rules & VRPH_BEST_ACCEPT) == VRPH_BEST_ACCEPT)
00047         accept_type=VRPH_BEST_ACCEPT;
00048 
00049     ii=0;
00050 
00051     b= V->route[r].start;
00052     a=VRPH_MAX(V->pred_array[b],0);
00053     // edge 1 is a-b
00054     c=VRPH_MAX(V->next_array[b],0);    
00055     if(c==VRPH_DEPOT)
00056         return false;
00057     d=VRPH_MAX(V->next_array[c],0);
00058     if(d==VRPH_DEPOT)
00059         return false;
00060     e=VRPH_MAX(V->next_array[d],0);
00061     if(e==VRPH_DEPOT)
00062         return false;
00063     f=VRPH_MAX(V->next_array[e],0);
00064     if(f==VRPH_DEPOT)
00065         return false;
00066 
00067     int a_end, c_end, e_end;
00068     // Set the a_end to 3 hops back from the route's end since
00069     // we will have searched all possible moves by this point.
00070     // This is ugly...
00071     a_end = VRPH_MAX(VRPH_DEPOT,V->pred_array[VRPH_MAX(VRPH_DEPOT,V->pred_array[VRPH_MAX(VRPH_DEPOT, V->pred_array[V->route[r].end])])]);
00072     c_end = VRPH_MAX(VRPH_DEPOT, V->pred_array[V->route[r].end]);
00073     e_end = V->route[r].end;
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 
00084 
00085     // Evaluate the first move and then enter the loop
00086     // We begin with the edges a-b, c-d, and e-f
00087     if(evaluate(V,a,b,c,d,e,f,rules,&M)==true)
00088     {
00089         if(accept_type==VRPH_FIRST_ACCEPT || ((accept_type==VRPH_LI_ACCEPT)&&M.savings<-VRPH_EPSILON))
00090         {
00091             // Make the move
00092             if(move(V, &M)==false)
00093                 report_error("%s: move error 1\n",__FUNCTION__);
00094             else
00095             {
00096                 if(!(rules & VRPH_TABU))
00097                     return true;
00098                 else
00099                 {
00100                     // Check VRPH_TABU status of move - return true if its ok
00101                     // or revert to old_sol if not and continue to search.
00102                     if(V->check_tabu_status(&M, old_sol))
00103                     {
00104                         delete [] old_sol;
00105                         return true; // The move was ok
00106                     }
00107                     // else we reverted back - continue the search for a move
00108                 }
00109             }
00110         }
00111 
00112         if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00113         {
00114             if(M.is_better(V, &BestM, rules))//if(M.savings<BestM.savings)
00115                 BestM=M;
00116         }
00117     }
00118 
00119     a=b;
00120 
00121 
00122     while(a!=a_end)
00123     {
00124         b=VRPH_MAX(V->next_array[a],0);
00125         c=VRPH_MAX(V->next_array[b],0);
00126         while(c!=c_end)
00127         {
00128             d=VRPH_MAX(V->next_array[c],0);
00129             e=VRPH_MAX(V->next_array[d],0);
00130             while(e!=e_end)
00131             {    
00132                 f=VRPH_MAX(V->next_array[e],0);
00133 
00134                 // Evaluate the move!
00135                 if(evaluate(V,a,b,c,d,e,f,rules,&M)==true)
00136                 {
00137                     if(accept_type==VRPH_FIRST_ACCEPT || ((accept_type==VRPH_LI_ACCEPT)&&M.savings<-VRPH_EPSILON))
00138                     {
00139                         // Make the move
00140                         if(move(V, &M)==false)
00141                             report_error("%s: move error 1\n",__FUNCTION__);
00142                         else
00143                         {
00144                             if(!(rules & VRPH_TABU))
00145                                 return true;
00146                             else
00147                             {
00148                                 // Check VRPH_TABU status of move - return true if its ok
00149                                 // or revert to old_sol if not and continue to search.
00150                                 if(V->check_tabu_status(&M, old_sol))
00151                                 {
00152                                     delete [] old_sol;
00153                                     return true; // The move was ok
00154                                 }
00155                                 // else we reverted back - continue the search for a move
00156                             }
00157                         }
00158                     }
00159 
00160                     if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00161                     {
00162                         if(M.is_better(V, &BestM, rules))
00163                             BestM=M;
00164 
00165                     }
00166                 }
00167                 e=f;
00168             }
00169             c=d;
00170         }
00171         a=b;
00172     }
00173 
00174 
00175     if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00176         return false;
00177 
00178     if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00179     {
00180         if(move(V,&BestM)==false)
00181         {
00182             report_error("%s: best move evaluates to false\n",__FUNCTION__);
00183         }
00184         else
00185         {
00186             if(!(rules & VRPH_TABU))
00187                 return true;
00188             else
00189             {
00190                 // Check VRPH_TABU status of move - return true if its ok
00191                 // or revert to old_sol if not and continue to search.
00192                 if(V->check_tabu_status(&BestM, old_sol))
00193                 {
00194                     delete [] old_sol;
00195                     return true; // The move was ok
00196                 }
00197                 // else we reverted back - search over
00198                 delete [] old_sol;
00199                 return false;
00200 
00201             }
00202         }
00203     }
00204 
00205     if(move(V,&BestM)==false)//best_e11,best_e12,best_e21,best_e22, best_e31, best_e32,rules)==false)
00206         report_error("%s: first move is false!\n",__FUNCTION__);
00207     else
00208         return true;
00209 
00210 
00211     return false;
00212 }
00213 
00214 bool ThreeOpt::evaluate(class VRP *V, int a, int b, int c, int d, int e, int f,
00215                         int rules, VRPMove *M)
00216 {
00224 
00225     V->num_evaluations[THREE_OPT_INDEX]++;
00226     M->evaluated_savings=false;
00227 
00228     if(V->routed[a]==false || V->routed[b]==false || V->routed[c]==false
00229         || V->routed[d]==false|| V->routed[e]==false|| V->routed[f]==false)
00230         return false;
00231 
00232     if(rules & VRPH_FIXED_EDGES)
00233     {
00234         // Make sure we aren't disturbing fixed edges
00235         if( V->fixed[a][b] || V->fixed[c][d] || V->fixed[e][f]) 
00236             return false;
00237 
00238     }
00239 
00240     int a_route;
00241 
00242     if(a!=VRPH_DEPOT)
00243         a_route = V->route_num[a];
00244     else
00245         a_route = V->route_num[b];
00246 
00247     M->eval_arguments[0]=a;M->eval_arguments[1]=b;M->eval_arguments[2]=c;
00248     M->eval_arguments[3]=d;M->eval_arguments[4]=e;M->eval_arguments[5]=f;
00249 
00250     // IMPORTANT!! Assume that edges are in order and have no conflicts
00251 
00252     double s1, s2, s3, s4, s5, s6, s7, old;
00253 
00254 
00255     // savings = new-old
00256     double minval=VRP_INFINITY;
00257     int type=0;
00258     old= V->d[a][b]+V->d[c][d]+V->d[e][f];
00259     s1=(V->d[a][b]+V->d[c][e]+V->d[d][f])-old;    // 2-opt move
00260     minval=s1; type=1;
00261     s2=(V->d[a][c]+V->d[b][d]+V->d[e][f])-old;    // 2-opt move
00262     if(s2<minval){ minval=s2; type=2;}
00263     s3=(V->d[a][c]+V->d[b][e]+V->d[d][f])-old;    // 3-opt move
00264     if(s3<minval){ minval=s3; type=3;}
00265     s4=(V->d[a][d]+V->d[b][e]+V->d[c][f])-old;    // 3-opt move
00266     if(s4<minval){ minval=s4; type=4;}
00267     s5=(V->d[a][d]+V->d[c][e]+V->d[b][f])-old;    // 3-opt move
00268     if(s5<minval){ minval=s5; type=5;}
00269     s6=(V->d[a][e]+V->d[b][d]+V->d[c][f])-old;    // 3-opt move
00270     if(s6<minval){ minval=s6; type=6;}
00271     s7=(V->d[a][e]+V->d[c][d]+V->d[b][f])-old;    // 2-opt move
00272     if(s7<minval){ minval=s7; type=7;}
00273 
00274     // No need to check load here since it's INTRA only
00275 
00276     // Now check route feasibility of the best savings
00277     if(minval + V->route[a_route].length > V->max_route_length )
00278         // The move is infeasible
00279         return false;
00280 
00281     // else the move is feasible - store the results in the move struct
00282 
00283     M->savings=minval;
00284     M->num_affected_routes=1;
00285     M->route_lens[0]=minval+V->route[a_route].length;
00286     M->route_nums[0]=a_route;
00287     M->route_custs[0]=V->route[a_route].num_customers;
00288     M->route_loads[0]=V->route[a_route].load;
00289     M->total_number_of_routes=V->total_number_of_routes;
00290     M->new_total_route_length=V->total_route_length+M->savings;
00291     M->eval_arguments[0]=a;M->eval_arguments[1]=b;M->eval_arguments[2]=c;
00292     M->eval_arguments[3]=d;M->eval_arguments[4]=e;M->eval_arguments[5]=f;
00293     M->move_type=type;
00294 
00295     // Now check the move
00296     if(V->check_move(M,rules)==true)
00297     {
00298         return true;
00299     }
00300     else
00301         return false;
00302 
00303 }
00304 
00305 bool ThreeOpt::move(class VRP *V, VRPMove *M)// int a, int b, int c, int d, int e, int f, int rules)
00306 {
00311 
00312     int a,b,c,d,e,f;
00313     a=M->eval_arguments[0];b=M->eval_arguments[1];c=M->eval_arguments[2];
00314     d=M->eval_arguments[3];e=M->eval_arguments[4];f=M->eval_arguments[5];
00315 
00316     // Two cases:  1) all in one route;  2) 3 different routes (not considered!)
00317 
00318     int a_route,c_route,e_route;
00319 
00320     if(a!=VRPH_DEPOT)
00321         a_route= V->route_num[a];
00322     else
00323         a_route= V->route_num[b];
00324 
00325     if(c!=VRPH_DEPOT)
00326         c_route= V->route_num[c];
00327     else
00328         c_route= V->route_num[d];
00329 
00330     if(e!=VRPH_DEPOT) 
00331         e_route= V->route_num[e];
00332     else
00333         e_route= V->route_num[f];
00334 
00335 
00336 
00337     // INTRAROUTE CASE:
00338     if(a_route==c_route && c_route==e_route)
00339     {
00340         int type = M->move_type;
00341 
00342 
00344 
00345         //
00346         double oldlen, oldobj;
00347         double temp_maxlen;
00348         int temp_vehcap, a_route;
00349 
00350         // Remember the actual maximums as we may need to artificially inflate them.
00351         temp_maxlen= V->max_route_length;
00352         temp_vehcap= V->max_veh_capacity;
00353 
00354         Flip flip;
00355 
00356         a_route= V->route_num[b];// b is not VRPH_DEPOT
00357 
00358         oldlen= V->route[a_route].length;
00359         oldobj= V->total_route_length;
00360 
00361         if(type==1)
00362         {
00363 
00364             if(f==VRPH_DEPOT)
00365             {
00366                 V->postsert_dummy(e);
00367                 flip.move(V,c,V->dummy_index);
00368                 V->remove_dummy();
00369             }
00370             else
00371                 flip.move(V,c,f);
00372 
00373 
00374             V->num_moves[THREE_OPT_INDEX]++;
00375             V->capture_best_solution();
00376             return true;
00377 
00378         }
00379 
00380         if(type==2)
00381         {
00382 
00383 
00384             if(a==VRPH_DEPOT)
00385             {
00386 
00387                 V->presert_dummy(b);
00388                 flip.move(V,V->dummy_index,d);
00389                 V->remove_dummy();
00390             }
00391             else
00392                 flip.move(V,a,d);
00393 
00394             V->num_moves[THREE_OPT_INDEX]++;
00395             V->capture_best_solution();
00396             return true;
00397         }
00398 
00399         if(type==3)
00400         {
00401             V->max_route_length=VRP_INFINITY;    
00402             V->max_veh_capacity=VRP_INFINITY;
00403 
00404             if(a==VRPH_DEPOT)
00405             {
00406 
00407                 V->presert_dummy(b);
00408                 flip.move(V,V->dummy_index,d);
00409                 V->remove_dummy();
00410             }
00411             else
00412                 flip.move(V,a,d);
00413 
00414             if(f==VRPH_DEPOT)
00415             {
00416 
00417                 V->postsert_dummy(e);
00418                 flip.move(V,b,V->dummy_index);
00419                 V->remove_dummy();
00420 
00421             }
00422             else
00423                 flip.move(V,b,f);
00424 
00425             V->max_route_length=temp_maxlen;
00426             V->max_veh_capacity=temp_vehcap;
00427 
00428             V->num_moves[THREE_OPT_INDEX]++;
00429             V->capture_best_solution();
00430             return true;
00431         }
00432 
00433 
00434         if(type==4)
00435         {
00436             a_route= V->route_num[b]; // b not VRPH_DEPOT!
00437 
00438             if(a!=VRPH_DEPOT && f!=VRPH_DEPOT)
00439             {
00440                 V->next_array[a]=d;
00441                 V->pred_array[d]=a;
00442 
00443                 V->next_array[e]=b;
00444                 V->pred_array[b]=e;
00445 
00446                 V->next_array[c]=f;
00447                 V->pred_array[f]=c;
00448             }
00449 
00450             if(a==VRPH_DEPOT && f!=VRPH_DEPOT)
00451             {
00452                 int prev_end=VRPH_ABS(V->pred_array[b]);
00453                 V->next_array[prev_end] = -d;
00454                 V->pred_array[d] = -prev_end;
00455 
00456                 V->next_array[e]=b;
00457                 V->pred_array[b]=e;
00458 
00459                 V->next_array[c]=f;
00460                 V->pred_array[f]=c;
00461 
00462                 V->route[a_route].start=d;
00463             }
00464 
00465             if(a!=VRPH_DEPOT && f==VRPH_DEPOT)
00466             {
00467                 int prev_start=VRPH_ABS(V->next_array[e]);
00468                 V->pred_array[prev_start] = -c;
00469                 V->next_array[c] = -prev_start;
00470 
00471                 V->next_array[e]=b;
00472                 V->pred_array[b]=e;
00473 
00474                 V->next_array[a]=d;
00475                 V->pred_array[d]=a;
00476             }
00477 
00478             if(a==VRPH_DEPOT && f==VRPH_DEPOT)
00479             {
00480                 int prev_end=VRPH_ABS(V->pred_array[b]);
00481                 int prev_start=VRPH_ABS(V->next_array[e]);
00482 
00483 
00484                 V->next_array[prev_end]=-b;
00485                 V->pred_array[b]=-prev_end;
00486 
00487                 V->next_array[e]=b;
00488                 V->pred_array[b]=e;
00489 
00490                 V->next_array[c]=-prev_start;
00491                 V->pred_array[prev_start]=-c;
00492 
00493                 V->route[a_route].start=d;
00494 
00495 
00496             }
00497 
00498             //Now manually adjust the route_len and obj. value
00499 
00500 
00501             V->route[a_route].length=oldlen+M->savings;//s4;
00502             V->total_route_length=oldobj+M->savings;//s4;
00503 
00504             V->num_moves[THREE_OPT_INDEX]++;
00505             V->capture_best_solution();
00506             return true;
00507 
00508 
00509         }
00510 
00511         if(type==5)
00512         {
00513             V->max_route_length=VRP_INFINITY;    
00514             V->max_veh_capacity=VRP_INFINITY;
00515 
00516             int prev_end=-1;
00517 
00518             // Remember:  flip changes the obj. value!!!!
00519             if(a==VRPH_DEPOT)
00520             {
00521                 prev_end=VRPH_ABS(V->pred_array[b]);
00522                 V->presert_dummy(b);
00523                 flip.move(V,V->dummy_index,d);
00524                 V->remove_dummy();
00525 
00526             }
00527             else
00528                 flip.move(V,a,d);
00529 
00530             if(a==VRPH_DEPOT)
00531             {
00532 
00533                 V->next_array[prev_end]=-d;
00534                 V->pred_array[d]=-prev_end;
00535                 V->route[a_route].start=d; 
00536             }
00537             else
00538             {
00539                 V->next_array[a]=d;
00540                 V->pred_array[d]=a;
00541             }
00542 
00543             if(f==VRPH_DEPOT)
00544             {
00545                 int prev_start=VRPH_ABS(V->next_array[e]);
00546                 V->next_array[b]=-prev_start;
00547                 V->pred_array[prev_start]=-b;
00548 
00549             }
00550             else
00551             {
00552                 V->next_array[b]=f;
00553                 V->pred_array[f]=b;
00554             }
00555 
00556             V->next_array[e]=c;
00557             V->pred_array[c]=e;
00558 
00559 
00560 
00561             //Now manually adjust the route_len and obj. value
00562 
00563             V->max_route_length=temp_maxlen;
00564             V->max_veh_capacity=temp_vehcap;
00565 
00566 
00567             a_route= V->route_num[b];
00568 
00569             V->route[a_route].length=oldlen+M->savings;//s5;
00570             V->total_route_length=oldobj+M->savings;//s5;
00571 
00572             V->num_moves[THREE_OPT_INDEX]++;
00573             V->capture_best_solution();
00574             return true;
00575         }
00576 
00577         if(type==6)
00578         {
00579             V->max_route_length=VRP_INFINITY;    
00580             V->max_veh_capacity=VRP_INFINITY;
00581 
00582             int prev_end=VRPH_ABS(V->pred_array[b]);
00583 
00584             if(f==VRPH_DEPOT)
00585             {
00586                 V->postsert_dummy(e);
00587                 flip.move(V,c,V->dummy_index);
00588                 V->remove_dummy();
00589             }
00590             else
00591                 flip.move(V,c,f);
00592 
00593 
00594             if(a==VRPH_DEPOT)
00595             {
00596 
00597                 V->next_array[prev_end]=-e;
00598                 V->pred_array[e]=-prev_end;
00599                 V->route[V->route_num[b]].start=e;
00600             }
00601             else
00602             {
00603                 V->next_array[a]=e;
00604                 V->pred_array[e]=a;
00605             }
00606 
00607             V->next_array[d]=b;
00608             V->pred_array[b]=d;
00609 
00610             if(f==VRPH_DEPOT)
00611             {
00612                 int prev_start=VRPH_ABS(V->next_array[e]);
00613                 V->next_array[c]=-prev_start;
00614                 V->pred_array[prev_start]=-c;
00615 
00616             }
00617             else
00618             {
00619                 V->next_array[c]=f;
00620                 V->pred_array[f]=c;
00621             }
00622 
00623             //Now manually adjust the route_len and obj. value
00624 
00625             a_route= V->route_num[b];
00626             V->route[a_route].length=oldlen+M->savings;//s6;
00627             V->total_route_length=oldobj+M->savings;//s6;
00628 
00629             V->max_route_length=temp_maxlen;
00630             V->max_veh_capacity=temp_vehcap;
00631 
00632             V->num_moves[THREE_OPT_INDEX]++;
00633             V->capture_best_solution();
00634             return true;
00635 
00636         }
00637 
00638         if(type==7)
00639         {
00640 
00641             //ae,dc,bf
00642             if(a==VRPH_DEPOT && f==VRPH_DEPOT)
00643             {
00644                 // This is just a route reversal - should have no savings!!
00645                 report_error("%s: route reversal??\n",__FUNCTION__);
00646             }
00647 
00648             if(a==VRPH_DEPOT)
00649             {
00650                 V->presert_dummy(b);
00651                 flip.move(V,V->dummy_index,f);
00652                 V->remove_dummy();
00653             }
00654             else
00655             {
00656                 if(f==VRPH_DEPOT)
00657                 {
00658                     V->postsert_dummy(e);
00659                     flip.move(V,a,V->dummy_index);
00660                     V->remove_dummy();
00661                 }
00662                 else
00663                     flip.move(V,a,f);
00664 
00665             }
00666 
00667             V->num_moves[THREE_OPT_INDEX]++;
00668             V->capture_best_solution();
00669             return true;
00670 
00671 
00672         }
00673 
00674     }
00675 
00676 
00677     return false;
00678 
00679 }
00680 
00681