VRPH  1.0
src/SwapEnds.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 SwapEnds::evaluate(class VRP *V, int a, int v, VRPMove *M)
00016 {
00017 
00025 
00026     
00027     int load_after_a, load_after_v, new_a_load, new_v_load, added_to_a, added_to_v, n, b, w;
00028     double new_a_len, new_v_len ;
00029     double savings;
00030     VRPSegment Sa, Sv;
00031 
00032 
00033     if(a==VRPH_DEPOT || v==VRPH_DEPOT)
00034         report_error("%s: Swap ends called with depot; Move doesn't make sense\n",__FUNCTION__);
00035 
00036     n = V->num_nodes;
00037     
00038 
00039     if(V->route_num[a] == V->route_num[v])
00040     {
00041         fprintf(stderr,"a=%d; v=%d; %d==%d!!\n",a,v,V->route_num[a], V->route_num[v]);
00042         report_error("%s: swap ends called with a and v in same route!\n",__FUNCTION__);
00043     }
00044     
00045     w = VRPH_MAX(V->next_array[v],0);
00046     b = VRPH_MAX(V->next_array[a],0);
00047     
00048     savings = ((V->d[a][w] + V->d[v][b]) - (V->d[a][b] + V->d[v][w]));
00049     
00050     V->get_segment_info(VRPH_DEPOT, a, &Sa);
00051     added_to_v= V->route[V->route_num[a]].num_customers-Sa.num_custs;
00052 
00053     load_after_a = V->route[V->route_num[a]].load - Sa.load;
00054 
00055     V->get_segment_info(VRPH_DEPOT, v, &Sv);
00056     added_to_a=V->route[V->route_num[v]].num_customers-Sv.num_custs;
00057 
00058     load_after_v = V->route[V->route_num[v]].load - Sv.load;
00059     
00060     
00063 
00064     new_a_len = Sa.len + V->route[V->route_num[v]].length - Sv.len + V->d[a][w]-V->d[v][w];
00065     new_a_load = Sa.load + load_after_v;
00066     new_v_len = Sv.len + V->route[V->route_num[a]].length - Sa.len  + V->d[v][b]-V->d[a][b];
00067     new_v_load = Sv.load + load_after_a;
00068 
00069     if(new_a_len > V->max_route_length || new_v_len > V->max_route_length 
00070         || new_a_load > V->max_veh_capacity || new_v_load > V->max_veh_capacity )
00071         // We violate some capacity constraint & the move is infeasible
00072         return false;
00073 
00074 
00075     // else the move is feasible and meets rules - record the move;
00076 
00077     M->num_affected_routes=2;
00078     M->route_nums[0]=V->route_num[a];
00079     M->route_nums[1]=V->route_num[v];
00080     M->savings=savings;
00081     M->route_lens[0]=new_a_len;
00082     M->route_lens[1]=new_v_len;
00083     M->route_loads[0]=new_a_load;
00084     M->route_loads[1]=new_v_load;
00085     M->route_custs[0]=V->route[V->route_num[a]].num_customers-added_to_v+added_to_a;
00086     M->route_custs[1]=V->route[V->route_num[v]].num_customers-added_to_a+added_to_v;
00087     M->new_total_route_length= V->total_route_length+M->savings;
00088     M->total_number_of_routes=V->total_number_of_routes;//none destroyed here
00089     M->move_type=SWAP_ENDS;
00090     M->num_arguments=2;
00091     M->move_arguments[0]=a;
00092     M->move_arguments[1]=v;
00093     
00094 
00095     return true;    
00096     
00097 }
00098 
00099 bool SwapEnds::move(VRP *V, int a, int v)
00100 {
00110     
00111 
00112     VRPMove M;
00113 
00114     if(evaluate(V,a,v,&M)==false)
00115         return false;    // move is infeasible
00116 
00117     int current_node, a_start, a_end, v_start, v_end;
00118     int route_after_a, route_before_a, route_before_v, route_after_v;
00119     int  n, u, b;
00120 
00121 
00122 #if SWAP_ENDS_DEBUG>0
00123         printf("Calling swap ends(%d,%d)\n",a,v);
00124 #endif
00125     
00126 
00127     if(a==VRPH_DEPOT || v==VRPH_DEPOT)
00128         report_error("%s: Swap ends called with depot; Move doesn't make sense\n",__FUNCTION__);
00129     
00130 
00131     n = V->num_nodes;
00132 
00133     if(V->route_num[a] == V->route_num[v])
00134         report_error("%s: swap ends called with a and v in same route!\n",__FUNCTION__);
00135 
00136 #if SWAP_VERIFY
00137     V->verify_routes("SWAP_ENDS::prior to move\n");
00138 #endif
00139 
00140     V->update(&M);
00141 
00142     a_end = V->route[V->route_num[a]].end;
00143     a_start = V->route[V->route_num[a]].start;
00144     
00145     route_after_a = V->route_num[-V->next_array[a_end]];
00146     route_before_a = V->route_num[-V->pred_array[a_start]];
00147 
00148     v_end = V->route[V->route_num[v]].end;
00149     v_start = V->route[V->route_num[v]].start;
00150     
00151     route_after_v = V->route_num[-V->next_array[v_end]];
00152     route_before_v = V->route_num[-V->pred_array[v_start]];
00153     
00154     u = V->next_array[v];
00155     b = V->next_array[a];
00156 
00157     if(u==VRPH_DEPOT || b==VRPH_DEPOT)
00158     {
00159         report_error("%s: u=0 or b=0 in swap_ends\n",__FUNCTION__);
00160 
00161     }
00162 
00163     if(u>0 && b>0)
00164     {
00165         V->next_array[a]=u;
00166         V->pred_array[u]=a;
00167         V->next_array[v]=b;
00168         V->pred_array[b]=v;
00169     }
00170     else
00171     {
00172         if(u>0 && b<0)
00173         {
00174             V->next_array[a]=u;
00175             V->pred_array[u]=a;
00176             V->next_array[v]=b;
00177             V->pred_array[-b]=-v;
00178         }
00179         else
00180         {
00181 
00182             if(u<0 && b>0)
00183             {
00184                 V->next_array[a]=u;
00185                 V->pred_array[-u]=-a;
00186                 V->next_array[v]=-b;
00187                 V->pred_array[b]=v;
00188             }
00189             else
00190                 report_error("%s: Reached strange place...\n",__FUNCTION__);
00191         }
00192     }
00193 
00194     
00195 
00196     // Now update the start, end, length, and load info for V->route_num[a] and V->route_num[v]
00197 
00198     
00199     V->route[V->route_num[a]].start = a_start;
00200     V->route[V->route_num[a]].end = v_end;
00201 
00202     
00203     V->route[V->route_num[v]].start = v_start;
00204     V->route[V->route_num[v]].end = a_end;
00205 
00206     // Now update the route_num-looping...
00207     
00208     current_node = a;
00209     while(current_node > 0)
00210     {
00211         V->route_num[current_node] = V->route_num[a];
00212         current_node = V->next_array[current_node];
00213         
00214     }
00215 
00216     current_node = v;
00217     while(current_node > 0)
00218     {
00219         V->route_num[current_node] = V->route_num[v];
00220         current_node = V->next_array[current_node];
00221 
00222     }
00223 
00224     // Now we have to update the routes following the modified a and v routes
00225 
00226     // Get the new start and end values 
00227     a_start = V->route[V->route_num[a]].start;
00228     v_start = V->route[V->route_num[v]].start;
00229     a_end = V->route[V->route_num[a]].end;
00230     v_end = V->route[V->route_num[v]].end;
00231 
00232 
00233     if(route_after_a != V->route_num[v] && route_after_v != V->route_num[a])
00234     {
00235         
00236 
00237         // Simple case - just switch the two
00238         if(route_after_a != 0 && route_after_v!=0)
00239         {
00240             
00241             V->next_array[a_end] = -V->route[route_after_a].start;
00242             V->pred_array[V->route[route_after_a].start] = -a_end;
00243 
00244             V->next_array[v_end] = -V->route[route_after_v].start;
00245             V->pred_array[V->route[route_after_v].start] = -v_end;
00246 
00247             return true;
00248         }
00249 
00250         if(route_after_a == 0)
00251         {
00252             V->next_array[a_end] = VRPH_DEPOT;
00253             V->pred_array[VRPH_DEPOT] = -a_end;
00254 
00255             V->next_array[v_end] = -V->route[route_after_v].start;
00256             V->pred_array[V->route[route_after_v].start] = -v_end;
00257 
00258 
00259             return true;
00260         }
00261 
00262         if(route_after_v == 0)
00263         {
00264             
00265             V->next_array[v_end] = VRPH_DEPOT;
00266             V->pred_array[VRPH_DEPOT] = -v_end;
00267 
00268             V->next_array[a_end] = -V->route[route_after_a].start;
00269         
00270             V->pred_array[V->route[route_after_a].start] = -a_end;
00271 
00272             return true;
00273         }
00274     }
00275 
00276     
00277     if(route_after_a == V->route_num[v] && route_after_v == V->route_num[a])
00278     {
00279         // If we don't change anything here, then the new V->route_num[v] will point to itself!
00280         // To fix this, make the new_v_route point 
00281         
00282         V->next_array[a_end] = -v_start;
00283         V->pred_array[v_start] = -a_end;
00284 
00285         V->next_array[v_end] = -a_start;
00286         V->pred_array[a_start] = -v_end;
00287 
00288         return true;
00289 
00290         
00291     }
00292 
00293     
00294     if(route_after_a == V->route_num[v])
00295     {
00296         
00297         // If we don't change anything here, then the new V->route_num[v] will point to itself!
00298         
00299         V->next_array[a_end] = -v_start;
00300         V->pred_array[v_start] = -a_end;
00301 
00302         if(route_after_v != VRPH_DEPOT)
00303         {
00304             V->next_array[v_end] = -V->route[route_after_v].start;
00305             V->pred_array[V->route[route_after_v].start] = -v_end;
00306         }
00307         else
00308         {
00309             V->next_array[v_end] = VRPH_DEPOT;
00310             V->pred_array[VRPH_DEPOT] = -v_end;
00311         }
00312 
00313 #if SWAP_ENDS_VERIFY
00314         V->verify_routes("SwapEnds 5\n");
00315 #endif
00316 
00317         return true;
00318 
00319         
00320     }
00321 
00322     if(route_after_v == V->route_num[a])
00323     {        
00324             
00325         // If we don't change anything here, then the new V->route_num[a] will point to itself!
00326         
00327         V->next_array[v_end] = -a_start;
00328         V->pred_array[a_start] = -v_end;
00329 
00330         if(route_after_a!=VRPH_DEPOT)
00331         {
00332             V->next_array[a_end] = -V->route[route_after_a].start;
00333             V->pred_array[V->route[route_after_a].start] = -a_end;
00334         }
00335         else
00336         {
00337             V->next_array[a_end] = VRPH_DEPOT;
00338             V->pred_array[VRPH_DEPOT] = -a_end;
00339         }
00340 
00341 
00342 
00343         return true;
00344 
00345 
00346     }
00347 
00348     report_error("%s: should never be here\n",__FUNCTION__);
00349 
00350     return false;
00351 
00352 
00353 }