VRPH  1.0
src/CrossExchange.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 CrossExchange::route_search(class VRP *V, int r1, int r2, int rules)
00017 {
00023 
00024     // Make sure we have two diff. routes!
00025     if(r1==r2)
00026         return false;
00027 
00028 #if CROSS_EXCHANGE_DEBUG > 1
00029     printf("Evaluating CE move b/w routes %d and %d\n",r1,r2);
00030 #endif
00031 
00032 
00033     int start_1, end_1, start_2, end_2;
00034     int i1, i2, k1, k2; // Route r1 nodes
00035     int j1, j2, l1, l2;    // Route r2 nodes
00036 
00037     VRPMove M, BestM;
00038 
00039     BestM.savings=VRP_INFINITY;
00040 
00041     int accept_type;
00042 
00043     // Default
00044     accept_type = VRPH_FIRST_ACCEPT;
00045 
00046     if( (rules & VRPH_LI_ACCEPT) == VRPH_LI_ACCEPT)
00047         accept_type = VRPH_LI_ACCEPT;
00048 
00049 
00050     if( (rules & VRPH_BEST_ACCEPT) == VRPH_BEST_ACCEPT)
00051         accept_type = VRPH_BEST_ACCEPT;
00052 
00053     // Use current_1a/b and next_1a/b for route r1 and current_2a/b and next_2a/b for route r2
00054     if(V->route[r1].num_customers < 4 || V->route[r2].num_customers < 4)
00055         // Not possible to find a CE move
00056         return false;
00057 
00058     int *old_sol=NULL;
00059     if(rules & VRPH_TABU)
00060     {
00061         // Remember the original solution 
00062         old_sol=new int[V->num_original_nodes+2];
00063         V->export_solution_buff(old_sol);
00064     }
00065 
00066     // Get route starts and ends
00067 
00068     start_1= V->route[r1].start;
00069     end_1= V->route[r1].end;
00070 
00071     int end_i=V->pred_array[end_1];
00072 
00073 
00074     start_2= V->route[r2].start;
00075     end_2= V->route[r2].end;
00076 
00077     int end_j=V->pred_array[end_2];
00078 
00079     i1 = start_1; // don't allow VRPH_DEPOT edges for now...
00080     i2 = V->next_array[i1];
00081 
00082     while(i2 != end_i)
00083     {
00084         // First edge in route 1 is i1-i2
00085 
00086         // Now find the second edge in route r1
00087         k1 = V->next_array[i2];
00088 
00089 
00090         if(k1==end_1)
00091             break;    // VRPH_DEPOT edge not allowed
00092 
00093         k2 = V->next_array[k1];
00094         while(k2 != end_1)
00095         {
00096             // Second edge in route 1 is k1-k2
00097 
00098             // Now find edges in the second route
00099 
00100             j1 = start_2; 
00101             j2 = V->next_array[j1];
00102 
00103             while(j2 != end_j)
00104             {
00105 
00106                 // First edge in route 2 is j1-j2
00107 
00108                 // Now find the second edge in route r2: l1-l2
00109                 l1 = V->next_array[j2];
00110 
00111                 if(l1==end_2)
00112                     break;
00113 
00114                 l2 = V->next_array[l1];
00115 
00116                 while(l2 != end_2)
00117                 {
00118                     // Now evaluate the cross exchange move involving
00119                     // i1-i2, k1-k2, and
00120                     // j1-j2, l1-l2
00121 
00122                     if(this->evaluate(V,i1,i2,k1,k2,j1,j2,l1,l2,rules,&M) == true)
00123                     {
00124 
00125                         // We have found a valid move.
00126                         if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00127                         {
00128                             // Make the move
00129 
00130                             if(move(V, &M)==false)
00131                                 report_error("%s: move error 1\n");
00132                             else
00133                             {
00134                                 if(!(rules & VRPH_TABU))
00135                                     return true;
00136                                 else
00137                                 {
00138                                     // Check VRPH_TABU status of move - return true if its ok
00139                                     // or revert to old_sol if not and continue to search.
00140                                     if(V->check_tabu_status(&M, old_sol))
00141                                     {
00142                                         delete [] old_sol;
00143                                         return true; // The move was ok
00144                                     }
00145                                     // else we reverted back - continue the search for a move
00146                                 }
00147                             }
00148                         }
00149 
00150 
00151                         if(accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT)
00152                         {
00153                             // Check for new best move
00154                             if(M.is_better(V, &BestM, rules))
00155                                 BestM=M;
00156 
00157                         }
00158 
00159                     }
00160 
00161                     // Now advance the second edge in route r2
00162 
00163                     l1 = l2;
00164                     l2 = V->next_array[l1];
00165 
00166                 }
00167                 // end route r2 edge 2 loop
00168 
00169                 // Now advance the first edge in route r2
00170 
00171                 j1 = j2;
00172                 j2= V->next_array[j1];
00173 
00174             }
00175             // end route r2 edge 1 loop
00176 
00177             // Now advance the second edge in route r1
00178             k1 = k2;
00179             k2 = V->next_array[k1];
00180 
00181         }
00182         // end route r1 edge 2 loop
00183 
00184         // Now advance the first edge in route r1
00185 
00186         i1 = i2;
00187         i2 = V->next_array[i1];
00188 
00189     }
00190 
00191 #if CROSS_EXCHANGE_DEBUG > 1
00192     printf("END OF LOOP: %f\n",BestM.savings);
00193 #endif
00194     if(BestM.savings == VRP_INFINITY || accept_type == VRPH_FIRST_ACCEPT)
00195         return false;
00196 
00197     if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY)
00198     {
00199         if(rules&VRPH_TABU)
00200             delete [] old_sol;
00201         return false;        // No moves found
00202     }    
00203 
00204     if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT)
00205     {
00206         if(move(V,&BestM)==false)
00207         {
00208             report_error("%s: best move evaluates to false\n");
00209         }
00210         else
00211         {
00212             if(!(rules & VRPH_TABU))
00213                 return true;
00214             else
00215             {
00216                 // Check VRPH_TABU status of move - return true if its ok
00217                 // or revert to old_sol if not and continue to search.
00218                 if(V->check_tabu_status(&BestM, old_sol))
00219                 {
00220                     delete [] old_sol;
00221                     return true; // The move was ok
00222                 }
00223                 // else we reverted back - search over
00224                 delete [] old_sol;
00225                 return false;
00226 
00227             }
00228         }
00229     }
00230 
00231     report_error("%s: should have returned already...\n",__FUNCTION__);
00232     return false;
00233 }
00234 
00235 
00236 
00237 // EVALUATE
00238 bool CrossExchange::evaluate(class VRP *V, int i1, int i2, int k1, int k2, int j1, int j2, int l1, int l2,
00239                              int rules, VRPMove *M)
00240 {
00245 
00246     V->num_evaluations[CROSS_EXCHANGE_INDEX]++;
00247 
00248 #if CROSS_EXCHANGE_DEBUG > 1
00249     printf("Evaluting CE move: %d-%d, %d-%d, %d-%d, %d-%d\n",i1,i2,k1,k2,j1,j2,l1,l2);
00250 #endif
00251     if(V->routed[i1]==false|| V->routed[i2]==false|| V->routed[k1]==false|| V->routed[k2]==false
00252         || V->routed[j1]==false|| V->routed[j2]==false|| V->routed[l1]==false|| V->routed[l2]==false)
00253         return false;
00254 
00255 
00256     M->evaluated_savings=false;
00257     double savings;
00258 
00259     // savings = new - old
00260 
00261     M->savings = savings = (V->d[i1][j2]+V->d[j1][i2]+V->d[k1][l2]+V->d[l1][k2]) - 
00262         (V->d[i1][i2]+V->d[j1][j2]+V->d[k1][k2]+V->d[l1][l2]);
00263 
00264     // Check the savings now
00265     if(V->check_savings(M,rules)==false)
00266         return false;
00267 
00268 
00269     // else the move has potential -- now check feasibility
00270     // Assume that edge i1-i2 is before k1-k2 in one route and that j1-j2 is before l1-l2 
00271     // in the second route - this is not checked!!
00272 
00273 
00274     // Move seems to make sense
00275     int i_route, j_route ;
00276 
00277     i_route= V->route_num[i2];
00278     j_route= V->route_num[j2];
00279 
00280     if(i_route==j_route)
00281     {
00282         fprintf(stderr,"i1=%d;i2=%d;k1=%d;k2=%d;j1=%d;j2=%d;l1=%d;l2=%d\n",i1,i2,k1,k2,j1,j2,l1,l2);
00283         fprintf(stderr,"i_route=%d; j_route=%d\n",i_route,j_route);
00284         V->show_route(i_route);
00285         report_error("%s: i_route==j_route!!\n",__FUNCTION__);
00286     }
00287 
00288     // Otherwise, the move appears to make sense
00289 
00290     double new_i_len, new_j_len;
00291 
00292     // savings = new_i_len + new_i_len - (old_i_len + old_j_len)
00293 
00294     //new_i_len=    route distance to (i1) + d(i1,j2)+ route distance between j2 and l1 
00295     //                + d(l1,k2) + route distance from (k2) to depot at end of route
00296 
00297     //new_j_len=    route distance to (j1) + d(j1,i2) + route distance between i2 and k1
00298     //                + d(k1,l2) + route distance from (l2) to depot at end of route
00299 
00300 
00301     VRPSegment S_0_i1, S_j2_l1, S_k2_0;
00302     V->get_segment_info(VRPH_DEPOT, i1, &S_0_i1);
00303     V->get_segment_info(j2, l1, &S_j2_l1);
00304     V->get_segment_info(k2, VRPH_DEPOT, &S_k2_0);
00305 
00306     new_i_len = S_0_i1.len + V->d[i1][j2] + S_j2_l1.len + V->d[l1][k2] + S_k2_0.len;
00307 
00308     if(new_i_len>V->max_route_length)
00309         return false;
00310 
00311     new_j_len =  savings + V->route[i_route].length + V->route[j_route].length - new_i_len;
00312 
00313     if(new_j_len>V->max_route_length)
00314         return false;
00315 
00316     int new_i_load, new_j_load;
00317 
00318     new_i_load = S_0_i1.load + S_j2_l1.load + S_k2_0.load;
00319 
00320     if(new_i_load>V->max_veh_capacity)
00321         return false;
00322 
00323 
00324     new_j_load = V->route[i_route].load + V->route[j_route].load - new_i_load;
00325 
00326 
00327     if(new_j_load > V->max_veh_capacity)
00328         return false;
00329 
00330     // The move is feasible - check the rules    
00331 
00332     M->savings=savings;
00333 
00334 #if CROSS_EXCHANGE_DEBUG>1
00335     printf("CROSS_EXCHANGE::savings is %f\n", savings);
00336 #endif
00337 
00338     M->num_affected_routes=2;
00339     M->route_nums[0] = i_route;
00340     M->route_nums[1] = j_route;
00341     M->route_custs[0]= S_0_i1.num_custs + S_j2_l1.num_custs +  S_k2_0.num_custs;
00342 
00343 #if CROSS_EXCHANGE_DEBUG > 1
00344     printf("%d + %d + %d = %d\n",S_0_i1.num_custs, S_j2_l1.num_custs,  S_k2_0.num_custs, 
00345         M->route_custs[0]);
00346 #endif
00347     M->route_custs[1]= V->route[i_route].num_customers + V->route[j_route].num_customers-
00348         M->route_custs[0];
00349     M->route_lens[0]=new_i_len;
00350     M->route_lens[1]=new_j_len;
00351     M->route_loads[0]=new_i_load;
00352     M->route_loads[1]=new_j_load;
00353     M->savings=savings;
00354     M->new_total_route_length= V->total_route_length+savings;
00355     M->num_arguments=9;
00356     M->move_arguments[0]=i1; M->move_arguments[1]=i2; M->move_arguments[2]=k1; M->move_arguments[3]=k2;
00357     M->move_arguments[4]=j1; M->move_arguments[5]=j2; M->move_arguments[6]=l1; M->move_arguments[7]=l2;
00358     M->move_arguments[8]=rules;
00359     M->total_number_of_routes = V->total_number_of_routes;
00360 
00361 #if CROSS_EXCHANGE_DEBUG > 1
00362     printf("CROSS_EXCHANGE::\nlengths: %f, %f\nloads: %d, %d\ncusts: %d, %d\n",M->route_lens[0],
00363         M->route_lens[1], M->route_loads[0], M->route_loads[1], M->route_custs[0], M->route_custs[1]);
00364 #endif
00365 
00366 
00367     if(V->check_move(M,rules)==true)
00368         return true;
00369     else
00370         return false;
00371 
00372 }
00373 
00374 
00375 bool CrossExchange::move(class VRP *V, VRPMove *M)
00376 {
00381 
00382     int i1, i2, k1, k2, j1, j2, l1, l2;
00383 
00384     i1=M->move_arguments[0];i2=M->move_arguments[1];k1=M->move_arguments[2];k2=M->move_arguments[3];
00385     j1=M->move_arguments[4];j2=M->move_arguments[5];l1=M->move_arguments[6];l2=M->move_arguments[7];
00386 
00387 
00388 #if CROSS_EXCHANGE_DEBUG
00389     printf("Routes before cross (%d-%d, %d-%d) (%d-%d, %d-%d)\n",i1,i2,k1,k2,j1,j2,l1,l2);
00390     V->show_route(V->route_num[i1]);
00391     V->show_route(V->route_num[j1]);
00392 #endif
00393 
00394     V->next_array[j1]=i2;
00395     V->pred_array[i2]=j1;
00396 
00397     V->next_array[k1]=l2;
00398     V->pred_array[l2]=k1;
00399 
00400     V->next_array[i1]=j2;
00401     V->pred_array[j2]=i1;
00402 
00403     V->next_array[l1]=k2;
00404     V->pred_array[k2]=l1;
00405 
00406 
00407 
00408     // Now update the route_num and the start and ends
00409     int current_node;
00410 
00411     current_node= V->route[M->route_nums[0]].start;
00412 
00413     while(current_node!=VRPH_DEPOT)
00414     {
00415         V->route[M->route_nums[0]].end=current_node;        
00416         V->route_num[current_node] = M->route_nums[0];
00417         current_node= VRPH_MAX(VRPH_DEPOT,V->next_array[current_node]);
00418     }
00419 
00420     current_node= V->route[M->route_nums[1]].start;
00421 
00422     while(current_node!=VRPH_DEPOT)
00423     {
00424         V->route[M->route_nums[1]].end=current_node;        
00425         V->route_num[current_node] = M->route_nums[1];
00426         current_node= VRPH_MAX(VRPH_DEPOT, V->next_array[current_node]);
00427     }
00428 
00429     V->update(M);
00430 
00431 
00432 #if CROSS_EXCHANGE_DEBUG
00433     printf("Routes after CrossExchange move (%d-%d, %d-%d), (%d-%d, %d-%d)\n",
00434         i1,i2,k1,k2, j1,j2,l1,l2);
00435     V->show_route(M->route_nums[0]);
00436     V->show_route(M->route_nums[1]);
00437 #endif
00438 
00439 #if CROSS_EXCHANGE_VERIFY
00440     V->verify_routes("After CrossExchange move\n");
00441 #endif
00442 
00443     V->num_moves[CROSS_EXCHANGE_INDEX]++;
00444 
00445     V->capture_best_solution();
00446 
00447     return true;
00448 
00449 }
00450