VRPH  1.0
src/MoveString.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 #include "VRPH.h"
00013 
00014 bool MoveString::evaluate(VRP *V, int a, int b, int u, int v, VRPMove *M)
00015 {
00021 
00022     // First make sure u or v is not the VRPH_DEPOT
00023 
00024     if(u==VRPH_DEPOT || v==VRPH_DEPOT || u==v)
00025     {
00026         fprintf(stderr,"(%d,%d,%d,%d)\n",a,b,u,v);
00027         report_error("%s: evaluate called with u or v as VRPH_DEPOT or u==v\n",__FUNCTION__);
00028 
00029     }
00030 
00031     int t,w;
00032 
00033     t=VRPH_MAX(V->pred_array[u],0);
00034     w=VRPH_MAX(V->next_array[v],0);    
00035 
00036     int a_route, u_route;
00037 
00038     u_route = V->route_num[u];
00039     if(u_route!= V->route_num[v])
00040         report_error("%s: u and v not in same route\n",__FUNCTION__);
00041 
00042     if(a!=VRPH_DEPOT)
00043         a_route = V->route_num[a];
00044     else
00045         a_route = V->route_num[b];
00046 
00047     double tu, vw, ab, au, vb, tw, savings, new_a_len=0, new_u_len=0;
00048     int new_a_load=0, new_u_load=0;
00049 
00050     ab= V->d[a][b];
00051     tu= V->d[t][u];
00052     vw= V->d[v][w];
00053     au= V->d[a][u];
00054     vb= V->d[v][b];
00055     tw= V->d[t][w];
00056 
00057     //savings=new-old
00058     savings = (au+vb+tw) - (ab+tu+vw);
00059 
00060 
00061     // Now find the total length and demand of the string
00062     // Should use get segment info here...
00063     VRPSegment S;
00064     V->get_segment_info(u,v,&S);
00065 
00066 
00067 #    if(STRING_DEBUG>1)
00068     printf("STRING::string_len: %f;  string_load: %d; string_custs: %d\n",string_len, string_load);
00069 #endif
00070 
00071     // Check feasibility
00072     if(a_route==u_route)
00073     {
00074         // Same route - only check length change
00075         new_a_len= V->route[a_route].length + savings;
00076         if(new_a_len > V->max_route_length)
00077         {
00078 #            if(STRING_DEBUG>1)
00079             printf("STRING::a_len too long: %f\n",new_a_len);
00080 #endif
00081             // Exceeds length capacity
00082             return false;
00083         }
00084 
00085         M->num_affected_routes=1;
00086         M->route_nums[0]=a_route;
00087         M->savings = savings;
00088         M->route_lens[0]=new_a_len;
00089         M->route_loads[0]=V->route[a_route].load;
00090         M->route_custs[0]= V->route[a_route].num_customers;
00091         M->move_type=MOVE_STRING;
00092         M->num_arguments=4;
00093         M->move_arguments[0]=a;
00094         M->move_arguments[1]=b;
00095         M->move_arguments[2]=u;
00096         M->move_arguments[3]=v;
00097         M->new_total_route_length=V->total_route_length+savings;
00098 
00099 
00100 
00101         return true;
00102 
00103 
00104     }
00105     else
00106     {
00107         // Different routes!
00108         new_a_len = V->route[a_route].length + ( (au+vb+S.len)-ab);
00109         if(new_a_len > V->max_route_length)
00110         {
00111 # if STRING_DEBUG>1
00112             printf("STRING::a_len too long: %f\n",new_a_len);
00113 #endif
00114             // Exceeds length 
00115             return false;
00116         }
00117 
00118         new_u_len = V->route[u_route].length + ( (tw)-(tu+vw+S.len) );
00119         if(new_u_len > V->max_route_length)
00120         {
00121 #            if(STRING_DEBUG>1)
00122             printf("STRING::u_len too long: %f\n",new_u_len);
00123 #endif
00124             // Exceeds length 
00125             return false;
00126         }
00127 
00128         // Now check loads;
00129 
00130         new_a_load = V->route[a_route].load + S.load;
00131         if(new_a_load > V->max_veh_capacity)
00132         {
00133 #            if(STRING_DEBUG>1)
00134             printf("STRING::a_load too big: %f\n",new_a_load);
00135 #endif
00136             // Exceeds capacity
00137             return false;
00138         }
00139 
00140         new_u_load = V->route[u_route].load - S.load;
00141         // new_u_load decreases, so no point checking capacity
00142 
00143         // If we get here, the move is feasible-record it.
00144 
00145         M->num_affected_routes=2;
00146         M->route_nums[0]=a_route;
00147         M->route_nums[1]=u_route;
00148         M->savings = savings;
00149         M->route_lens[0]=new_a_len;
00150         M->route_lens[1]=new_u_len;
00151         M->route_loads[0]=new_a_load;
00152         M->route_loads[1]=new_u_load;
00153         M->route_custs[0]= V->route[a_route].num_customers+S.num_custs;
00154         M->route_custs[1]= V->route[u_route].num_customers-S.num_custs;
00155         M->new_total_route_length= V->total_route_length+M->savings;
00156         M->move_type=MOVE_STRING;
00157         M->num_arguments=4;
00158         M->move_arguments[0]=a;
00159         M->move_arguments[1]=b;
00160         M->move_arguments[2]=u;
00161         M->move_arguments[3]=v;
00162 
00163 
00164         // See if we reduce the # of routes
00165         if(u== V->route[u_route].start && v== V->route[u_route].end)
00166         {
00167             // We are moving an entire route!
00168             M->total_number_of_routes = V->total_number_of_routes - 1;
00169         }
00170         else
00171             M->total_number_of_routes= V->total_number_of_routes;
00172 
00173 
00174         return true;
00175     }
00176 
00177 }
00178 
00179 bool MoveString::move(VRP *V, int a, int b, int u, int v)
00180 {
00184 
00185     VRPMove M;
00186 
00187     if(evaluate(V,a,b,u,v, &M)==false)
00188     {
00189         report_error("%s: evaluate is false in MoveString.move\n",__FUNCTION__);
00190 
00191     }
00192 
00193 
00194     if(a!=VRPH_DEPOT)
00195     {
00196         // We can do this via a sequence of postserts    
00197         Postsert postsert;
00198 
00199         int string[100];
00200         int len=1;
00201         int i;
00202 
00203         // Find the length of the string of nodes and then store it in the
00204         // string[] array
00205         int current=u;
00206         while(current!=v)
00207         {
00208             current= VRPH_MAX(VRPH_DEPOT,V->next_array[current]);
00209             len++;
00210         }
00211 
00212         string[0]=u;
00213         for(i=1;i<len;i++)
00214         {
00215             string[i]= VRPH_MAX(V->next_array[string[i-1]],0);
00216 
00217         }
00218 
00219         // Artificially inflate the constraints!
00220         double real_max_len= V->max_route_length;
00221         int real_veh_max= V->max_veh_capacity;
00222 
00223         V->max_route_length=VRP_INFINITY;
00224         V->max_veh_capacity=VRP_INFINITY;
00225 
00226         postsert.move(V,string[0],a);
00227         for(i=1;i<len;i++)
00228         {    
00229             postsert.move(V,string[i],string[i-1]);
00230         }
00231 
00232         V->max_route_length=real_max_len;
00233         V->max_veh_capacity=real_veh_max;
00234 
00235 #if STRING_DEBUG
00236         printf("Routes after move:\n");
00237         V->show_route(u_route);
00238         V->show_route(V->route_num[a]);
00239 
00240 #endif
00241 
00242 
00243 #if STRING_VERIFY
00244         V->verify_routes("After Postsert move string\n");
00245 #endif
00246     }
00247     else
00248     {
00249         // Have to use presert
00250         Presert presert;
00251 
00252         int next_to_presert=v;
00253         int next_node=b;
00254         int t=VRPH_MAX(V->pred_array[u],0);
00255 
00256         // Artificially inflate the constraints!
00257         double real_max_len= V->max_route_length;
00258         int real_veh_max= V->max_veh_capacity;
00259 
00260         V->max_route_length=VRP_INFINITY;
00261         V->max_veh_capacity=VRP_INFINITY;
00262 
00263 
00264         while(next_to_presert!=t)
00265         {
00266             presert.move(V,next_to_presert,next_node);
00267             next_node=next_to_presert;
00268             next_to_presert= VRPH_MAX(VRPH_DEPOT, V->pred_array[next_to_presert]);//V->pred(next_to_presert);
00269 
00270         }
00271 
00272         V->max_route_length=real_max_len;
00273         V->max_veh_capacity=real_veh_max;
00274 
00275         // Don't update with M since the postsert/presert did it for us...
00276 
00277 
00278 #if STRING_VERIFY
00279         V->verify_routes("After movestring\n");
00280 #endif
00281     }
00282 
00283     return true;
00284 }
00285 
00286 
00287