VRPH
1.0
|
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