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