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