00001
00002
00003
00004
00005
00006
00007
00008
00009
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
00047 if( (h==VRPH_DEPOT && j==VRPH_DEPOT) || (t==VRPH_DEPOT && v==VRPH_DEPOT) )
00048 return false;
00049
00050 savings=VRP_INFINITY;
00051
00052
00053 if(h==u)
00054 {
00055
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
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
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
00097
00098 u_route= V->route_num[u];
00099 i_route= V->route_num[i];
00100
00101 if(u_route==i_route)
00102 {
00103
00104 if(V->route[u_route].length+savings>V->max_route_length)
00105 return false;
00106
00107
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;
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
00125
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
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
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
00162 report_error("%s: should not be in different routes(4)\n",__FUNCTION__);
00163
00164
00165 }
00166
00167 if(swap_type==5)
00168 {
00169
00170 i_change=(V->d[h][u]+V->d[u][j])-(V->d[h][i]+V->d[i][j]);
00171
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;
00178
00179
00180 if( ( M->route_lens[0] = V->route[u_route].length+u_change ) >V->max_route_length )
00181 return false;
00182
00183
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;
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;
00192
00193 }
00194
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
00225
00226
00227
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
00247
00248
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
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
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
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
00314
00315
00316
00317
00318
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
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
00341 if(presert.move(V,i,v)==false)
00342 report_error("%s: presert %d,%d is false!\n",__FUNCTION__,i,v);
00343 }
00344
00345
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
00364
00365
00366
00367
00368
00369
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
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
00387 if(presert.move(V,u,j)==false)
00388 report_error("%s: presert %d,%d is false!\n",__FUNCTION__,u,j);
00389 }
00390
00391
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
00406
00407 V->update(&M);
00408
00409
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
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
00459
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
00467 V->route[u_route].start=i;
00468
00469 if(V->route[u_route].end==u)
00470
00471 V->route[u_route].end=i;
00472
00473 if(V->route[i_route].start==i)
00474
00475 V->route[i_route].start=u;
00476
00477 if(V->route[i_route].end==i)
00478
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
00493
00494 if(V->route[u_route].start==u)
00495
00496 V->route[u_route].start=i;
00497 else
00498 {
00499
00500 if(V->route[u_route].start==i)
00501
00502 V->route[u_route].start=u;
00503 }
00504
00505 if(V->route[u_route].end==u)
00506
00507 V->route[u_route].end=i;
00508 else
00509 {
00510
00511 if(V->route[u_route].end==i)
00512
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