VRPH  1.0
src/Swap.cpp
Go to the documentation of this file.
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