VRPH  1.0
src/Presert.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 Presert::evaluate(class VRP *V, int u, int i, VRPMove *M)
00016 {
00024 
00025     int start_u,end_u, start_i, end_i;
00026     int t,v,h,demand_change, i_load, u_load, i_route, u_route;
00027     double tu, uv, tv, ui, hu, hi, u_loss, i_gain, i_change, i_length, u_length, savings;
00028 
00029     if(V->routed[u]==false || V->routed[i]==false)
00030         return false;
00031 
00032     if(i==u)
00033         report_error("%s: PRESERT::called with u=i\n",__FUNCTION__);
00034 
00035     i_route = V->route_num[i];
00036     u_route = V->route_num[u];
00037 
00038     if(V->next_array[u]==i)
00039     {
00040         // Nothing to do -
00041         return false;
00042     }
00043 
00044     // Can check load feasibility easily
00045     if(u_route != i_route)
00046     {
00047         if(V->route[i_route].load+V->nodes[u].demand>V->max_veh_capacity)
00048             return false;
00049     }
00050 
00051 
00052 
00053     // First, calculate the relevant nodes and distances
00054     // Original situation: ...-h-i-..., ...-t-u-v-....
00055     // New situation:  ...-h-u-i-..., ...-t-v-...
00056     t=VRPH_MAX(V->pred_array[u],0);
00057     v=VRPH_MAX(V->next_array[u],0);
00058     h=VRPH_MAX(V->pred_array[i],0);
00059 
00060     tu= V->d[t][u];
00061     uv= V->d[u][v];
00062     tv= V->d[t][v];
00063     ui= V->d[u][i];
00064     hu= V->d[h][u];
00065     hi= V->d[h][i];
00066     
00067     u_loss = tu+uv-tv;
00068     i_gain = ui+hu-hi;
00069 
00070     //savings = new - old;
00071     savings = (tv + hu + ui) - (tu + uv + hi);
00072     
00073     start_u= V->route[u_route].start;
00074     start_i= V->route[i_route].start;
00075     end_u= V->route[u_route].end;
00076     end_i= V->route[i_route].end;
00077 
00078     
00079     if(start_u==start_i)
00080     {
00081         // u and i were in the same route originally
00082         // No overall change in the load here - we just shifted u around
00083         demand_change = 0;
00084         // The total length of route i is now old_length + (i_gain - u_loss)
00085         i_change = i_gain - u_loss;
00086         i_length = V->route[i_route].length + i_change;
00087         i_load = V->route[i_route].load + demand_change;
00088         u_length = i_length;
00089         u_load = i_load;
00090     }
00091     else
00092     {
00093         // Different routes
00094         i_change = i_gain;
00095         demand_change = V->nodes[u].demand; 
00096         i_length = V->route[i_route].length + i_change;
00097         i_load = V->route[i_route].load + demand_change;
00098         u_length = V->route[u_route].length - u_loss;
00099         u_load = V->route[u_route].load - demand_change;
00100     }
00101 
00102     // Check feasibility 
00103 
00104     if( (i_length > V->max_route_length) || (u_length > V->max_route_length) || 
00105         (i_load > V->max_veh_capacity) || (u_load > V->max_veh_capacity) )
00106     {
00107         return false;
00108     }
00109 
00110     // else it's feasible - record the move 
00111 
00112 
00113     // Figure out if we reduce the # of routes here
00114     if(start_u==end_u)
00115         M->total_number_of_routes = V->total_number_of_routes-1;
00116     else
00117         M->total_number_of_routes = V->total_number_of_routes;
00118 
00119     if(u_route==i_route)
00120     {
00121 
00122         M->num_affected_routes=1;
00123         M->savings=i_gain-u_loss;
00124         M->route_nums[0]=u_route;
00125         M->route_lens[0]=u_length;
00126         M->route_loads[0]=u_load;
00127         M->route_custs[0]= V->route[u_route].num_customers; // no change
00128         M->new_total_route_length= V->total_route_length+M->savings;
00129         M->move_type=PRESERT;
00130         M->num_arguments=2;
00131         M->move_arguments[0]=u;
00132         M->move_arguments[1]=i;
00133     }
00134     else
00135     {
00136         // Different routes
00137         M->num_affected_routes=2;
00138         M->savings=i_gain-u_loss;
00139         M->route_nums[0]=u_route;
00140         M->route_nums[1]=i_route;
00141         M->route_lens[0]=u_length;
00142         M->route_lens[1]=i_length;
00143         M->route_loads[0]=u_load;
00144         M->route_loads[1]=i_load;
00145         if(u!= V->dummy_index)
00146         {
00147             M->route_custs[0] = V->route[u_route].num_customers-1;
00148             M->route_custs[1]=  V->route[i_route].num_customers+1;
00149         }
00150         else
00151         {
00152             M->route_custs[0] = V->route[u_route].num_customers;
00153             M->route_custs[1]=  V->route[i_route].num_customers;
00154         }
00155 
00156         M->new_total_route_length= V->total_route_length+M->savings;
00157         M->move_type=PRESERT;
00158         M->num_arguments=2;
00159         M->move_arguments[0]=u;
00160         M->move_arguments[1]=i;
00161 
00162     }
00163 
00164     return true;
00165 
00166 }
00167 bool Presert::move(VRP *V, int u, int i)
00168 {
00169 
00175 
00176     int pre_i, post_i, pre_u, post_u;
00177     int start_u,end_u, start_i, end_i;
00178     int i_route, u_route;
00179     int new_u_start, new_u_end, new_i_start, new_i_end;
00180     VRPMove M;
00181 
00182     if(V->next_array[u]==i)
00183     {
00184         // nothing to do
00185         return true;
00186     }
00187 
00188     if(evaluate(V,u,i, &M)==false)
00189         return false;    //infeasible
00190 
00191 #if PRESERT_VERIFY
00192     V->verify_routes("Before presert move\n");
00193 #endif
00194 
00195 
00196     // Otherwise, the move is feasible, so make it
00197 
00198     
00199     // Update the solution information
00200     V->update(&M);
00201 
00202     // Now modify the ordering
00203 
00204     i_route= V->route_num[i];
00205     u_route= V->route_num[u];
00206 
00207     // pre_i is what used to be before i
00208     pre_i= V->pred_array[i];
00209     // post_i is what used to be after i
00210     post_i= V->next_array[i];
00211     // pre_u is what used to be before u
00212     pre_u= V->pred_array[u];
00213     // post_u is what used to be after u
00214     post_u= V->next_array[u];
00215 
00216         
00217     // Get the start and end of the original route.
00218     start_i= V->route[i_route].start;
00219     end_i= V->route[i_route].end;
00220 
00221     start_u= V->route[u_route].start;
00222     end_u= V->route[u_route].end;
00223 
00224     
00225     if(start_i==i)
00226         // u is now before i
00227         new_i_start=u;
00228     else
00229     {
00230         if(start_i==u)
00231             new_i_start=post_u;
00232         else
00233             new_i_start=start_i;
00234     }
00235 
00236     if(end_i == u)
00237         // pre_u is the new end of this route since u is moving
00238         new_i_end=pre_u;
00239     else
00240         new_i_end=end_i;
00241 
00242     if(start_u==u)
00243         // post_ is the new start since u is moving
00244         new_u_start=post_u;
00245     else
00246         new_u_start=start_u;
00247 
00248     if(end_u==u)
00249         new_u_end=pre_u;
00250     else
00251         new_u_end=end_u;
00252     
00253     
00254     
00255     // Special case
00256     
00257     if(pre_i==-u)
00258     {
00259         // We have    1-...t-v-u-1
00260         //            1-i-a-...
00261         // and we form the routes
00262         //            1-...-t-v-1
00263         //            1-u-i-a-...
00264 
00265         V->next_array[u]=i;
00266         V->pred_array[i]=u;
00267 
00268         V->next_array[VRPH_ABS(pre_u)]=-u;
00269         V->pred_array[u]=-VRPH_ABS(pre_u);
00270 
00271         // Update i_route information
00272         V->route_num[u]=i_route;
00273         V->route[i_route].end=new_i_end;
00274         V->route[i_route].start=new_i_start;
00275 
00276         // Now update u's former route
00277 
00278         // Make sure we didn't have VRPH_DEPOT-u-VRPH_DEPOT route
00279         if(start_u==end_u)
00280             return true;//??
00281         
00282 
00283         // Update u_route information
00284         V->route[u_route].end=new_u_end;
00285         V->route[u_route].start=new_u_start;
00286 
00287         return true;
00288     }
00289 
00290     // Added Special case - u is the first node in the route following i's route
00291     if(V->next_array[end_i] == -u)
00292     {
00293         V->next_array[end_i] = -VRPH_ABS(post_u);//temp1;
00294         V->pred_array[VRPH_ABS(post_u)] = -end_i;
00295         V->next_array[u]=i;
00296         V->pred_array[i]=u;
00297         V->pred_array[u]=pre_i;
00298 
00299         if(pre_i>0)    // was >=!!
00300             V->next_array[pre_i]=u;
00301         else
00302             // post_i 
00303             V->next_array[VRPH_ABS(pre_i)]=-u;
00304 
00305         // Update i_route information
00306         V->route_num[u]=i_route;
00307         V->route[i_route].end=new_i_end;
00308         V->route[i_route].start=new_i_start;
00309 
00310         
00311         // Check for VRPH_DEPOT-u-VRPH_DEPOT route
00312         if(start_u==end_u)
00313             return true;
00314         
00315 
00316         // start_u is now next[u] since u used to be at the start
00317         start_u= V->next_array[u];
00318 
00319         // Update u_route information
00320         V->route[u_route].end=new_u_end;
00321         V->route[u_route].start=new_u_start;
00322 
00323         return true;
00324 
00325     }
00326 
00327     // u is now followed by i
00328     V->next_array[u]=i;
00329     V->pred_array[i]=u;
00330     V->pred_array[u]=pre_i;
00331     // We now need to make u's old predecessor pre_u point to post_u since
00332     // u is no longer there
00333     
00334     // If u was the first node in its route, then post_u is now the first node
00335     // in the route
00336     if(pre_u<=0 || post_u<=0)
00337     {
00338         // u is first or last in its route
00339         V->next_array[VRPH_ABS(pre_u)]=-VRPH_ABS(post_u);
00340         V->pred_array[VRPH_ABS(post_u)]=-VRPH_ABS(pre_u);
00341     }
00342     else
00343     {
00344         V->next_array[pre_u]=post_u;
00345         V->pred_array[VRPH_ABS(post_u)]=pre_u;
00346     }
00347     // The element who used to be after u is now preceded by the element
00348     // that was before u
00349     
00350     // The element who used to be after i is now preceded by u 
00351     if(pre_i>0)// was >=!!
00352         V->next_array[pre_i]=u;
00353     else
00354         // post_i 
00355         V->next_array[VRPH_ABS(pre_i)]=-u;
00356 
00357     // Update i_route information
00358     V->route_num[u]=i_route;
00359     V->route[i_route].end=new_i_end;
00360     V->route[i_route].start=new_i_start;
00361 
00362     // Check for VRPH_DEPOT-u-VRPH_DEPOT route
00363     if(start_u==end_u)
00364         return true;
00365     
00366 
00367     // Update u_route information
00368     if(u==start_u)
00369     {
00370         // u was first in its route-->post_u is new start
00371         start_u=VRPH_ABS(post_u);
00372     }
00373     if(u==end_u)
00374     {
00375         // u was last in its rotue --> pre_u is new end
00376         end_u=VRPH_ABS(pre_u);
00377     }
00378     if(u_route == i_route)
00379     {
00380         new_u_end=new_i_end;
00381         new_u_start=new_i_start;
00382     }
00383     
00384     V->route[u_route].end=new_u_end;
00385     V->route[u_route].start=new_u_start;
00386     
00387     return true;
00388 
00389 }
00390 
00391