VRPH  1.0
src/ThreePointMove.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 bool ThreePointMove::search(VRP *V, int b, int rules)
00016 {
00022 
00023     VRPMove M;
00024     VRPMove BestM;
00025     BestM.savings=VRP_INFINITY;
00026     int h,i,ii,j;
00027     int accept_type;
00028     
00029     if(b==VRPH_DEPOT)        
00030         return false;
00031 
00032     if(rules & VRPH_FIXED_EDGES)
00033     {
00034         i=VRPH_MAX(V->pred_array[b],VRPH_DEPOT);
00035         j=VRPH_MAX(V->next_array[b],VRPH_DEPOT);
00036 
00037         // Make sure we aren't disturbing fixed edges
00038 
00039         if( V->fixed[i][b] || V->fixed[b][j] ) 
00040             return false;
00041     }
00042 
00043     accept_type=VRPH_FIRST_ACCEPT;//default
00044 
00045     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00046         accept_type=VRPH_FIRST_ACCEPT;
00047     if( (rules & VRPH_BEST_ACCEPT) > 0)
00048         accept_type=VRPH_BEST_ACCEPT;
00049     if( (rules & VRPH_LI_ACCEPT) > 0)
00050         accept_type=VRPH_LI_ACCEPT;
00051 
00052 
00053     // Create the search_space
00054     V->create_search_neighborhood(b, rules);
00055 
00056     int *old_sol=NULL;
00057     if(rules & VRPH_TABU)
00058     {
00059         // Remember the original solution 
00060         old_sol=new int[V->num_original_nodes+2];
00061         V->export_solution_buff(old_sol);
00062     }
00063         
00064     for(ii=0;ii<V->search_size;ii++)
00065     {
00066         // Get the edge i-j
00067         i=V->search_space[ii];
00068         j=VRPH_MAX(VRPH_DEPOT,V->next_array[i]);
00069         h=VRPH_MAX(VRPH_DEPOT,V->pred_array[i]);
00070 
00071         // Edge i-j
00072         if(i!=VRPH_DEPOT && j!=VRPH_DEPOT)
00073         {
00074             // We have the edge i-j to consider swapping with node b
00075 
00076             if(evaluate(V,b,i,j,rules,&M)==true)
00077             {
00078                 
00079                 if((accept_type==VRPH_FIRST_ACCEPT) || ((accept_type==VRPH_LI_ACCEPT)&&M.savings<=-VRPH_EPSILON))
00080                 {
00081                     // Make the move
00082                     if(move(V, &M)==false)
00083                         report_error("%s: move error 1\n",__FUNCTION__);
00084                     else
00085                     {
00086                         if(!(rules & VRPH_TABU))
00087                             return true;
00088                         else
00089                         {
00090                             // Check VRPH_TABU status of move - return true if its ok
00091                             // or revert to old_sol if not and continue to search.
00092                             if(V->check_tabu_status(&M, old_sol))
00093                             {
00094                                 delete [] old_sol;
00095                                 return true; // The move was ok
00096                             }
00097                             // else we reverted back - continue the search for a move
00098                         }
00099                     }
00100                 }
00101 
00102                 if(accept_type==VRPH_LI_ACCEPT || accept_type==VRPH_BEST_ACCEPT)
00103                 {
00104                     if(M.is_better(V, &BestM, rules))
00105                         BestM=M;
00106                 }
00107             }
00108         }
00109 
00110         // Edge h-i
00111         if(h!=VRPH_DEPOT && i!=VRPH_DEPOT)
00112         {
00113             // We have the edge h-i to consider swapping with node b
00114             if(evaluate(V,b,h,i,rules,&M)==true)
00115             {
00116                 if(accept_type==VRPH_FIRST_ACCEPT || ((accept_type==VRPH_LI_ACCEPT)&&M.savings<=-VRPH_EPSILON))
00117                 {
00118                     // Make the move
00119                     if(move(V, &M)==false)
00120                         report_error("%s: move error 2\n",__FUNCTION__);
00121                     else
00122                     {
00123                         if(!(rules & VRPH_TABU))
00124                             return true;
00125                         else
00126                         {
00127                             // Check VRPH_TABU status of move - return true if its ok
00128                             // or revert to old_sol if not and continue to search.
00129                             if(V->check_tabu_status(&M, old_sol))
00130                             {
00131                                 delete [] old_sol;
00132                                 return true; // The move was ok
00133                             }
00134                             // else we reverted back - continue the search for a move
00135                         }
00136                     }
00137                 }
00138 
00139                 if(accept_type==VRPH_LI_ACCEPT || accept_type==VRPH_BEST_ACCEPT)
00140                 {
00141                     if(M.is_better(V, &BestM, rules))
00142                         BestM=M;
00143                 }
00144             }
00145         }
00146     }
00147 
00148     if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00149     {
00150         if(rules&VRPH_TABU)
00151             delete [] old_sol;
00152         return false;        // No moves found
00153     }    
00154 
00155     if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00156     {
00157         if(move(V,&BestM)==false)
00158         {
00159             report_error("%s: best move evaluates to false\n",__FUNCTION__);
00160         }
00161         else
00162         {
00163             if(!(rules & VRPH_TABU))
00164                 return true;
00165             else
00166             {
00167                 // Check VRPH_TABU status of move - return true if its ok
00168                 // or revert to old_sol if not and continue to search.
00169                 if(V->check_tabu_status(&BestM, old_sol))
00170                 {
00171                     delete [] old_sol;
00172                     return true; // The move was ok
00173                 }
00174                 // else we reverted back - search over
00175                 delete [] old_sol;
00176                 return false;
00177 
00178             }
00179         }
00180     }
00181     report_error("%s: should have already returned\n",__FUNCTION__);
00182     return false;
00183 }
00184 
00185 bool ThreePointMove::route_search(VRP *V, int r1, int r2, int rules)
00186 {
00191 
00192     VRPMove M;
00193     VRPMove BestM;
00194     int j,k,l,m;
00195     int accept_type;
00196     
00197     BestM.savings=VRP_INFINITY;
00198 
00199     if(r1==r2)
00200     {
00201         fprintf(stderr,"ThreePM::%d==%d???\n",r1,r2);
00202         report_error("%s: search called with r1==r2\n",__FUNCTION__);
00203     }
00204 
00205     if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0)
00206         report_error("%s: route_search does not use neighbor_list\n",__FUNCTION__);
00207 
00208     accept_type=VRPH_FIRST_ACCEPT;//default
00209 
00210     if( (rules & VRPH_FIRST_ACCEPT) > 0)
00211         accept_type=VRPH_FIRST_ACCEPT;
00212     if( (rules & VRPH_BEST_ACCEPT) > 0)
00213         accept_type=VRPH_BEST_ACCEPT;
00214     if( (rules & VRPH_LI_ACCEPT) > 0)
00215         accept_type=VRPH_LI_ACCEPT;
00216 
00217 
00218     j= V->route[r1].start;
00219     k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00220 
00221     // We will try to move j-k from route r1 and exchange with l from route r2
00222     while(k!=VRPH_DEPOT)
00223     {
00224 
00225         l= V->route[r2].start;
00226         m= VRPH_MAX(V->next_array[l],VRPH_DEPOT);
00227 
00228         while(m!=VRPH_DEPOT)
00229         {
00230             // Try to swap j-k with node l
00231             if(evaluate(V,l,j,k,rules,&M)==true)
00232             {
00233                 // valid move found
00234                 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00235                 {
00236                     // make the move
00237                     if(move(V,&M)==false)
00238                         report_error("%s: first accept move is false!\n",__FUNCTION__);
00239                     else
00240                         return true;
00241                 }
00242 
00243                 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT) )
00244                 {
00245                     // See if it's the best so far...
00246                     if(M.is_better(V, &BestM, rules))
00247                         BestM=M;
00248                 }
00249 
00250             }
00251 
00252             // Try to swap l-m with node j
00253             if(evaluate(V,j,l,m,rules,&M)==true)
00254             {
00255                 // valid move found
00256                 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00257                 {
00258                     // make the move
00259                     if(move(V,&M)==false)
00260                         report_error("%s: first accept move is false!\n",__FUNCTION__);
00261                     else
00262                         return true;
00263                 }
00264 
00265                 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT) )
00266                 {
00267                     // See if it's the best so far...
00268                     if(M.is_better(V, &BestM, rules))
00269                         BestM=M;
00270                 }
00271 
00272             }
00273             // Advance the route r2 node
00274             l=m;
00275             m=VRPH_MAX(V->next_array[m],0);
00276         }
00277         // Advance the route r1 node
00278         j=k;
00279         k=VRPH_MAX(V->next_array[j],VRPH_DEPOT);
00280 
00281     }
00282 
00283 
00284     if(accept_type==VRPH_FIRST_ACCEPT)
00285         return false;    // No moves found
00286     if(BestM.savings == VRP_INFINITY)
00287         return false;
00288 
00289     if( (accept_type == VRPH_LI_ACCEPT) || (accept_type == VRPH_BEST_ACCEPT))
00290     {
00291 
00292         // We found a move -- make it...
00293         if(move(V,&BestM)==false)
00294             report_error("%s: best move is false!\n",__FUNCTION__);
00295         else
00296             return true;
00297 
00298     }
00299 
00300     report_error("%s: shouldn't be here...\n",__FUNCTION__);
00301 
00302     return false;
00303 
00304 
00305 
00306 
00307 }
00308 
00309 bool ThreePointMove::evaluate(VRP *V, int b, int i, int j, int rules, VRPMove *M)
00310 {
00311 
00317 
00318     V->num_evaluations[THREE_POINT_MOVE_INDEX]++;
00319 
00320     if(V->routed[b]==false|| V->routed[i]==false|| V->routed[j]==false)
00321         return false;
00322 
00323     M->evaluated_savings=false;
00324 
00325 
00326     if(b==i || b==j)//conflict
00327         return false;
00328 
00329     if(b==VRPH_DEPOT || i==VRPH_DEPOT || j==VRPH_DEPOT)
00330         return false;
00331 
00332     int a,c,h,k;
00333     int a_route, i_route;
00334 
00335     a_route=V->route_num[b];// this is b's former route
00336     i_route=V->route_num[i];
00337 
00338     // Don't do it if tiny routes
00339     if(V->route[a_route].num_customers<=1 || V->route[i_route].num_customers<=2)
00340         return false;    
00341 
00342     a=VRPH_MAX(V->pred_array[b],0);
00343     c=VRPH_MAX(V->next_array[b],0);
00344     h=VRPH_MAX(V->pred_array[i],0);
00345     k=VRPH_MAX(V->next_array[j],0);
00346 
00347     if(rules & VRPH_FIXED_EDGES)
00348     {
00349         // Make sure we aren't disturbing fixed edges
00350         if( V->fixed[a][b] || V->fixed[b][c] ) 
00351             return false;
00352 
00353         if( V->fixed[h][i] || V->fixed[j][k] ) 
00354             return false;
00355 
00356     }
00357 
00358     double savings=0;
00359 
00360     if(b==h)
00361     {
00362         // a-b/h-c/i-j-k --> a-c/i-j-b/h-k - postsert(b,j)
00363         savings = (V->d[a][i]+V->d[j][b]+V->d[b][k]) - 
00364             (V->d[a][b]+V->d[b][c]+V->d[j][k]);
00365     }
00366     
00367     if(b==k)
00368     {
00369         // h-i-j/a-b/k-c --> h-b/k-i-j/a-c - presert(b,i)
00370         savings = (V->d[h][b]+V->d[b][i]+V->d[j][c]) - 
00371             (V->d[h][i]+V->d[a][b]+V->d[b][c]);
00372 
00373     }
00374 
00375     // else no conflicts
00376 
00377     if(b!=h && b!=k)
00378     {
00379         // old:  a-b-c...h-i-j-k
00380         // new:  a-i-j-c...h-b-k
00381 
00382         // No conflicts
00383         // savings = new - old
00384         savings = (V->d[a][i]+V->d[j][c]+V->d[h][b]+V->d[b][k]) - 
00385             (V->d[a][b]+V->d[b][c]+V->d[h][i]+V->d[j][k]);
00386 
00387     }
00388 
00389     M->savings=savings;
00390     if(V->check_savings(M,rules)==false)
00391         return false;
00392 
00393     if(a_route==i_route)
00394     {
00395         // Same route - check length feasibility
00396         if(V->route[a_route].length+savings>V->max_route_length)
00397             return false;
00398         
00399         // Otherwise the move is feasible - record the move...
00400 
00401         M->num_arguments=3;
00402         M->move_arguments[0]=b;
00403         M->move_arguments[1]=i;
00404         M->move_arguments[2]=j;
00405         M->move_type=THREE_POINT_MOVE;
00406         M->new_total_route_length=V->total_route_length+savings;
00407         M->num_affected_routes=1;
00408         M->route_nums[0]=a_route;
00409         M->route_lens[0]=V->route[a_route].length+savings;
00410         M->route_custs[0]=V->route[a_route].num_customers;
00411         M->route_loads[0]=V->route[a_route].load;
00412         M->savings=savings;
00413         M->total_number_of_routes=V->total_number_of_routes;        
00414         // Now check the move
00415         if(V->check_move(M,rules)==true)
00416             return true;
00417         else
00418             return false;
00419 
00420 
00421     }
00422 
00423     // else diff. routes - can't have any overlaps in this case
00424     int new_a_load = V->route[a_route].load+V->nodes[i].demand + V->nodes[j].demand - V->nodes[b].demand;
00425     int new_i_load = V->route[i_route].load-V->nodes[i].demand - V->nodes[j].demand + V->nodes[b].demand;
00426 
00427     if(new_a_load>V->max_veh_capacity || new_i_load>V->max_veh_capacity)
00428         return false;
00429 
00430     double new_a_len = V->route[a_route].length + V->d[a][i]+V->d[i][j]+V->d[j][c]-V->d[a][b]-V->d[b][c];
00431     double new_i_len = V->route[i_route].length + V->d[h][b]+V->d[b][k]-V->d[h][i]-V->d[i][j]-V->d[j][k];
00432 
00433     if(new_a_len > V->max_route_length || new_i_len > V->max_route_length)
00434         return false;
00435 
00436     // else the move is feasible - record it.
00437 
00438     M->num_arguments=3;
00439     M->move_arguments[0]=b;
00440     M->move_arguments[1]=i;
00441     M->move_arguments[2]=j;
00442     M->move_type=THREE_POINT_MOVE;
00443     M->new_total_route_length=V->total_route_length+savings;
00444     M->num_affected_routes=2;
00445     M->route_nums[0]=a_route;
00446     M->route_nums[1]=i_route;
00447     M->route_lens[0]=new_a_len;
00448     M->route_lens[1]=new_i_len;
00449     M->route_custs[0]=V->route[a_route].num_customers+1;
00450     M->route_custs[1]=V->route[i_route].num_customers-1;
00451     M->route_loads[0]=new_a_load;
00452     M->route_loads[1]=new_i_load;
00453     M->savings=savings;
00454     M->total_number_of_routes=V->total_number_of_routes;        
00455 
00456 
00457     // Now check the move
00458     if(V->check_move(M,rules)==true)
00459         return true;
00460     else
00461         return false;
00462 }
00463 
00464 bool ThreePointMove::move(VRP *V, VRPMove *M)
00465 {
00469 
00470     V->num_moves[THREE_POINT_MOVE_INDEX]++;
00471 
00472 #if THREE_PM_VERIFY
00473     V->verify_routes("Before ThreePM\n");
00474 #endif
00475 
00476 
00477     // Easiest way to do this is by just post/preserting the nodes.
00478 
00479     int a,b,c,h,i,j,k;
00480 
00481     b=M->move_arguments[0];
00482     i=M->move_arguments[1];
00483     j=M->move_arguments[2];
00484 
00485     a=VRPH_MAX(V->pred_array[b],0);
00486     c=VRPH_MAX(V->next_array[b],0);
00487     h=VRPH_MAX(V->pred_array[i],0);
00488     k=VRPH_MAX(V->next_array[j],0);
00489 
00490     // First artificially inflate the constraints
00491     double orig_max_len=V->max_route_length;
00492     int orig_veh_cap=V->max_veh_capacity;
00493 
00494     V->max_route_length=VRP_INFINITY;
00495     V->max_veh_capacity=VRP_INFINITY;
00496 
00497     Postsert postsert;
00498     Presert presert;
00499 
00500 
00501     if(b==h)
00502     {
00503         // a-b/h-c/i-j-k --> a-c/i-j-b/h-k - postsert(b,j)
00504         if(postsert.move(V,b,j)==false)
00505             report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,b,j);
00506 
00507         V->max_route_length=orig_max_len;
00508         V->max_veh_capacity=orig_veh_cap;
00509         V->verify_routes("After ThreePM b==h\n");
00510     }
00511     
00512     if(b==k)
00513     {
00514         // h-i-j/a-b/k-c --> h-b/k-i-j/a-c - presert(b,i)
00515         if(presert.move(V,b,i)==false)
00516             report_error("%s: presert %d,%d is false\n",__FUNCTION__,b,i);
00517 
00518         V->max_route_length=orig_max_len;
00519         V->max_veh_capacity=orig_veh_cap;
00520         V->verify_routes("After ThreePM b==k\n");
00521 
00522     }
00523 
00524     if(b!=h && b!=k)
00525     {
00526         // First put b between h and i
00527         if(h!=VRPH_DEPOT)
00528         {
00529             if(postsert.move(V,b,h)==false)
00530                 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,b,h);
00531         }
00532         else
00533         {
00534             if(presert.move(V,b,i)==false)
00535                 report_error("%s: presert %d,%d is false!\n",__FUNCTION__,b,i);
00536         }
00537 
00538         // Now put i in between a and c
00539         if(a!=VRPH_DEPOT)
00540         {
00541             if(postsert.move(V,i,a)==false)
00542             {
00543                 fprintf(stderr,"postsert(%d,%d)\n",i,a);
00544                 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,i,a);
00545             }
00546         }
00547         else
00548         {
00549             if(presert.move(V,i,c)==false)
00550                 report_error("%s: presert %d,%d is false!\n",__FUNCTION__,i,c);
00551         }
00552 
00553         // Now put j after i
00554         if(postsert.move(V,j,i)==false)
00555             report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,j,i);
00556 
00557     }
00558     // Restore constraints
00559     V->max_route_length=orig_max_len;
00560     V->max_veh_capacity=orig_veh_cap;
00561 
00562     V->total_number_of_routes=M->total_number_of_routes;
00563 
00564     V->verify_routes("After ThreePM\n");
00565 
00566     V->capture_best_solution();
00567     return true;
00568 }
00569