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 00016 bool Swap::evaluate(class VRP *V, int u, int i, VRPMove *M) 00017 { 00024 00025 if(V->routed[u]==false || V->routed[i]==false) 00026 return false; 00027 00028 if(u==VRPH_DEPOT || i==VRPH_DEPOT) 00029 report_error("%s: called with VRPH_DEPOT node\n",__FUNCTION__); 00030 00031 if(u==i) 00032 { 00033 fprintf(stderr,"SWAP::%d=%d??\n",u,i); 00034 V->show_route(V->route_num[u]); 00035 report_error("%s: called with u=i\n",__FUNCTION__); 00036 } 00037 00038 int t,v,h,j,u_route,i_route,swap_type=0; 00039 double savings,u_change=0,i_change=0; 00040 00041 t=VRPH_MAX(V->pred_array[u],0); 00042 v=VRPH_MAX(V->next_array[u],0); 00043 h=VRPH_MAX(V->pred_array[i],0); 00044 j=VRPH_MAX(V->next_array[i],0); 00045 00046 // Don't bother with this move if we have u or i as a singleton route 00047 if( (h==VRPH_DEPOT && j==VRPH_DEPOT) || (t==VRPH_DEPOT && v==VRPH_DEPOT) ) 00048 return false; 00049 00050 savings=VRP_INFINITY; 00051 00052 //savings=new-old 00053 if(h==u) 00054 { 00055 // t-h/u-i/v-j --> t-i/v-h/u-j 00056 savings=(V->d[t][i]+V->d[i][h]+V->d[u][j])- 00057 (V->d[t][u]+V->d[u][v]+V->d[i][j]); 00058 swap_type=1; 00059 } 00060 00061 if(h==v) 00062 { 00063 savings=(V->d[t][i]+V->d[i][h]+V->d[v][u]+V->d[u][j])- 00064 (V->d[t][u]+V->d[u][v]+V->d[h][i]+V->d[i][j]); 00065 swap_type=2; 00066 } 00067 00068 if(j==t && t!=VRPH_DEPOT) 00069 { 00070 savings=(V->d[h][u]+V->d[u][t]+V->d[j][i]+V->d[i][v])- 00071 (V->d[h][i]+V->d[i][j]+V->d[t][u]+V->d[u][v]); 00072 swap_type=3; 00073 } 00074 00075 if(j==u) 00076 { 00077 savings=(V->d[h][j]+V->d[j][i]+V->d[i][v])- 00078 (V->d[h][i]+V->d[i][j]+V->d[u][v]); 00079 swap_type=4; 00080 } 00081 00082 if(swap_type==0) 00083 { 00084 // Normal case w/ no exceptions 00085 savings=(V->d[t][i]+V->d[i][v] + V->d[h][u]+V->d[u][j])- 00086 (V->d[t][u]+V->d[u][v] + V->d[h][i]+V->d[i][j]); 00087 00088 i_change=(V->d[h][u]+V->d[u][j])-(V->d[h][i]+V->d[i][j]); 00089 00090 // Route u was t-u-v and is now t-i-v 00091 u_change=(V->d[t][i]+V->d[i][v])-(V->d[t][u]+V->d[u][v]); 00092 00093 swap_type=5; 00094 } 00095 00096 // Now need to check feasibility 00097 00098 u_route= V->route_num[u]; 00099 i_route= V->route_num[i]; 00100 00101 if(u_route==i_route) 00102 { 00103 // Same route, so the length changes by savings 00104 if(V->route[u_route].length+savings>V->max_route_length) 00105 return false; // infeasible 00106 00107 // Otherwise record the move 00108 00109 M->num_affected_routes=1; 00110 M->savings=savings; 00111 M->route_nums[0]=u_route; 00112 M->route_lens[0]=V->route[u_route].length+savings; 00113 M->route_loads[0]=V->route[u_route].load; 00114 M->route_custs[0]= V->route[u_route].num_customers; // no change 00115 M->new_total_route_length= V->total_route_length+savings; 00116 M->total_number_of_routes = V->total_number_of_routes; 00117 M->move_type=SWAP; 00118 M->num_arguments=2; 00119 M->move_arguments[0]=u; 00120 M->move_arguments[1]=i; 00121 } 00122 else 00123 { 00124 // Different routes--but in this case we can't have any of the 00125 // overlap conditions unless the VRPH_DEPOT is involved!! 00126 00127 00128 M->num_affected_routes=2; 00129 M->route_nums[0] = u_route; 00130 M->route_nums[1] = i_route; 00131 M->move_type=SWAP; 00132 M->num_arguments=2; 00133 M->move_arguments[0]=u; 00134 M->move_arguments[1]=i; 00135 00136 if(swap_type==1) 00137 { 00138 report_error("%s: should not be in different routes(1)\n",__FUNCTION__); 00139 00140 } 00141 00142 if(swap_type==2) 00143 { 00144 //h=v: must have v=h=VRPH_DEPOT 00145 u_change=(V->d[t][i]+V->d[v][i])-(V->d[t][u]+V->d[u][v]); 00146 i_change=(V->d[h][u]+V->d[u][j])-(V->d[h][i]+V->d[i][j]); 00147 00148 } 00149 00150 if(swap_type==3) 00151 { 00152 //j=t=VRPH_DEPOT 00153 u_change=(V->d[t][i]+V->d[v][i])-(V->d[t][u]+V->d[u][v]); 00154 i_change=(V->d[h][u]+V->d[u][j])-(V->d[h][i]+V->d[i][j]); 00155 00156 } 00157 00158 if(swap_type==4) 00159 { 00160 00161 //j==u- not possible 00162 report_error("%s: should not be in different routes(4)\n",__FUNCTION__); 00163 00164 00165 } 00166 00167 if(swap_type==5) 00168 { 00169 // Route i was h-i-j and is now h-u-j 00170 i_change=(V->d[h][u]+V->d[u][j])-(V->d[h][i]+V->d[i][j]); 00171 // Route u was t-u-v and is now t-i-v 00172 u_change=(V->d[t][i]+V->d[i][v])-(V->d[t][u]+V->d[u][v]); 00173 00174 } 00175 00176 if( ( M->route_lens[1] = V->route[i_route].length+i_change ) >V->max_route_length ) 00177 return false; // route that used to contain i is infeasible 00178 00179 00180 if( ( M->route_lens[0] = V->route[u_route].length+u_change ) >V->max_route_length ) 00181 return false; // route that used to contain u is infeasible 00182 00183 // Now check capacity constraints 00184 00185 if( (M->route_loads[1] = V->route[i_route].load+V->nodes[u].demand- 00186 V->nodes[i].demand ) > V->max_veh_capacity) 00187 return false; // route that used to contain i is infeasible 00188 00189 if( ( M->route_loads[0]= V->route[u_route].load+V->nodes[i].demand- 00190 V->nodes[u].demand ) > V->max_veh_capacity) 00191 return false; // route that used to contain u is infeasible 00192 00193 } 00194 // The move is feasible - store the rest and check 00195 M->savings=savings; 00196 M->new_total_route_length=V->total_route_length+savings; 00197 M->total_number_of_routes=V->total_number_of_routes; 00198 M->route_custs[0]=V->route[u_route].num_customers; 00199 M->route_custs[1]=V->route[i_route].num_customers; 00200 00201 return true; 00202 00203 } 00204 00205 bool Swap::move(VRP *V, int u, int i) 00206 { 00213 00214 VRPMove M; 00215 int u_route, i_route; 00216 00217 if(evaluate(V,u,i,&M)==false) 00218 { 00219 report_error("%s: evaluate is false in move!\n",__FUNCTION__); 00220 return false; 00221 } 00222 00223 00224 // else we make the move 00225 00226 // Don't update here since some special cases are 00227 // handled w/ postsert and presert... 00228 00229 00230 int h,j,t,v,hh,jj,tt,vv; 00231 class Postsert postsert; 00232 class Presert presert; 00233 00234 t= V->pred_array[u]; 00235 v= V->next_array[u]; 00236 h= V->pred_array[i]; 00237 j= V->next_array[i]; 00238 00239 hh=VRPH_MAX(V->pred_array[i],0); 00240 jj=VRPH_MAX(V->next_array[i],0); 00241 tt=VRPH_MAX(V->pred_array[u],0); 00242 vv=VRPH_MAX(V->next_array[u],0); 00243 00244 if(hh==u) 00245 { 00246 // old: h-i-j, t-u-v == t-u-i-j 00247 // new: t-i-u-j 00248 // t-h/u-i/v-j --> t-i/v-h/u-j 00249 00250 #if SWAP_DEBUG 00251 printf("swapping u=%d; i=%d; t-u-v=%d-%d-%d; h-i-j=%d=%d=%d\n",u,i,tt,u,vv,hh,i,jj); 00252 V->show_route(V->route_num[u]); 00253 printf("predicted savings is %f\n",M.savings); 00254 printf("recalculated savings is %f\n",(V->d[tt][i]+V->d[i][u]+V->d[u][jj])- 00255 (V->d[tt][u]+V->d[u][i]+V->d[i][jj])); 00256 00257 #endif 00258 00259 #if SWAP_VERIFY 00260 V->verify_routes("Before h==u SWAP\n"); 00261 #endif 00262 // Put u after i 00263 if(postsert.move(V,u,i)==false) 00264 { 00265 fprintf(stderr,"postsert(%d,%d) is false in SWAP!\n",u,i); 00266 fprintf(stderr,"predicted savings is %f\n",M.savings); 00267 V->show_route(V->route_num[u]); 00268 V->summary(); 00269 report_error("%s: postsert evaluates to false\n",__FUNCTION__); 00270 } 00271 else 00272 { 00273 #if SWAP_VERIFY 00274 V->verify_routes("After h==u SWAP\n"); 00275 #endif 00276 00277 return true; 00278 } 00279 } 00280 00281 if(jj==u) 00282 { 00283 #if SWAP_VERIFY 00284 V->verify_routes("Before j==u SWAP\n"); 00285 #endif 00286 // We have h-i/t-u/j-v, so just put i after u 00287 double t1= V->max_route_length; 00288 int t2= V->max_veh_capacity; 00289 V->max_route_length=VRP_INFINITY; 00290 V->max_veh_capacity=VRP_INFINITY; 00291 00292 if(postsert.move(V,i,u)==false) 00293 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,i,u); 00294 00295 // reset the constraints 00296 V->max_route_length=t1; 00297 V->max_veh_capacity=t2; 00298 00299 #if SWAP_VERIFY 00300 V->verify_routes("After j==u SWAP\n"); 00301 #endif 00302 00303 return true; 00304 00305 } 00306 if(hh==vv) 00307 { 00308 #if SWAP_VERIFY 00309 V->verify_routes("Before h==v SWAP\n"); 00310 #endif 00311 00312 00313 //Current: t-u-h/v-i-j 00314 //New: t-i-h/v-u-j 00315 00316 // Put u after i first, and then move i 00317 00318 // To make sure the move isn't prevented due to infeasibility! 00319 double t1= V->max_route_length; 00320 int t2= V->max_veh_capacity; 00321 V->max_route_length=VRP_INFINITY; 00322 V->max_veh_capacity=VRP_INFINITY; 00323 00324 if(postsert.move(V,u,i)==false) 00325 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,u,i); 00326 00327 // Now put i where u used to be 00328 if(t>0) 00329 { 00330 if(postsert.move(V,i,t)==false) 00331 { 00332 fprintf(stderr,"i=%d, t=%d\n",i,t); 00333 V->show_route(V->route_num[i]); 00334 V->show_route(V->route_num[t]); 00335 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,i,t); 00336 } 00337 } 00338 else 00339 { 00340 // t must be the end of a route, so put i before h/v 00341 if(presert.move(V,i,v)==false) 00342 report_error("%s: presert %d,%d is false!\n",__FUNCTION__,i,v); 00343 } 00344 00345 // reset the constraints 00346 V->max_route_length=t1; 00347 V->max_veh_capacity=t2; 00348 #if SWAP_VERIFY 00349 V->verify_routes("After h==v SWAP\n"); 00350 #endif 00351 00352 return true; 00353 } 00354 00355 00356 if(jj==tt) 00357 { 00358 00359 #if SWAP_VERIFY 00360 V->verify_routes("Before j==t SWAP\n"); 00361 #endif 00362 00363 //Current: h-i-j/t-u-v 00364 //New: h-u-j/t-i-v 00365 00366 // Put i after u first, and then move u 00367 00368 00369 // To make sure the move isn't prevented due to infeasibility! 00370 double t1= V->max_route_length; 00371 int t2= V->max_veh_capacity; 00372 V->max_route_length=VRP_INFINITY; 00373 V->max_veh_capacity=VRP_INFINITY; 00374 00375 if(postsert.move(V,i,u)==false) 00376 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,i,u); 00377 00378 // Now put u where i used to be 00379 if(h>0) 00380 { 00381 if(postsert.move(V,u,h)==false) 00382 report_error("%s: postsert %d,%d is false!\n",__FUNCTION__,u,h); 00383 } 00384 else 00385 { 00386 // h must be the end of a route, so put u before j/t 00387 if(presert.move(V,u,j)==false) 00388 report_error("%s: presert %d,%d is false!\n",__FUNCTION__,u,j); 00389 } 00390 00391 // reset the constraints 00392 V->max_route_length=t1; 00393 V->max_veh_capacity=t2; 00394 00395 #if SWAP_VERIFY 00396 V->verify_routes("After j==t SWAP\n"); 00397 #endif 00398 00399 return true; 00400 } 00401 00402 #if SWAP_VERIFY 00403 V->verify_routes("Before normal SWAP\n"); 00404 #endif 00405 // Here is the "normal" case 00406 00407 V->update(&M); 00408 00409 // Put u in between h and j; 00410 00411 if(h>0) 00412 { 00413 V->next_array[h]=u; 00414 V->pred_array[u]=h; 00415 } 00416 else 00417 { 00418 V->pred_array[u]=h; 00419 V->next_array[VRPH_ABS(h)]=-u; 00420 } 00421 00422 if(j>0) 00423 { 00424 V->next_array[u]=j; 00425 V->pred_array[j]=u; 00426 } 00427 else 00428 { 00429 V->next_array[u]=j; 00430 V->pred_array[VRPH_ABS(j)]=-u; 00431 } 00432 00433 00434 // Put i in between t and v; 00435 00436 if(t>0) 00437 { 00438 V->next_array[t]=i; 00439 V->pred_array[i]=t; 00440 } 00441 else 00442 { 00443 V->pred_array[i]=t; 00444 V->next_array[VRPH_ABS(t)]=-i; 00445 } 00446 00447 if(v>0) 00448 { 00449 V->next_array[i]=v; 00450 V->pred_array[v]=i; 00451 } 00452 else 00453 { 00454 V->next_array[i]=v; 00455 V->pred_array[VRPH_ABS(v)]=-i; 00456 } 00457 00458 // Now adjust the start and end routes 00459 // Get the old route nums 00460 u_route= V->route_num[u]; 00461 i_route= V->route_num[i]; 00462 00463 if(u_route!=i_route) 00464 { 00465 if(V->route[u_route].start==u) 00466 // i is the new start 00467 V->route[u_route].start=i; 00468 00469 if(V->route[u_route].end==u) 00470 // i is the new end 00471 V->route[u_route].end=i; 00472 00473 if(V->route[i_route].start==i) 00474 // i is the new start 00475 V->route[i_route].start=u; 00476 00477 if(V->route[i_route].end==i) 00478 // i is the new end 00479 V->route[i_route].end=u; 00480 00481 V->route_num[u]=i_route; 00482 V->route_num[i]=u_route; 00483 00484 00485 #if SWAP_VERIFY 00486 V->verify_routes("After inter SWAP\n"); 00487 #endif 00488 00489 } 00490 else 00491 { 00492 // Same route 00493 00494 if(V->route[u_route].start==u) 00495 // i is the new start 00496 V->route[u_route].start=i; 00497 else 00498 { 00499 00500 if(V->route[u_route].start==i) 00501 // u is the new start 00502 V->route[u_route].start=u; 00503 } 00504 00505 if(V->route[u_route].end==u) 00506 // i is the new end 00507 V->route[u_route].end=i; 00508 else 00509 { 00510 00511 if(V->route[u_route].end==i) 00512 // u is the new end 00513 V->route[u_route].end=u; 00514 } 00515 00516 #if SWAP_VERIFY 00517 V->verify_routes("After intra SWAP\n"); 00518 #endif 00519 00520 00521 } 00522 00523 00524 return true; 00525 } 00526