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