VRPH  1.0
src/ClarkeWright.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 ClarkeWright::ClarkeWright(int n)
00017 {
00022 
00023     s=new VRPSavingsElement[n*(n-1)/2];
00024     has_savings_matrix = false;
00025     // Set this to true once we have the matrix    
00026 
00027 }
00028 
00029 ClarkeWright::~ClarkeWright()
00030 {
00031     delete [] this->s;
00032 
00033 }
00034 
00035 void ClarkeWright::CreateSavingsMatrix(class VRP *V, double lambda, bool use_neighbor_list)
00036 {
00042 
00043     int i,j,k,m,n;
00044 
00045     n = V->num_original_nodes;    // n is the max. # of non-VRPH_DEPOT nodes    
00046 
00047 
00048     if(!use_neighbor_list)
00049     {
00050         k=0;
00051         for(i=1;i<=n;i++)
00052         {
00053             for(j=i+1;j<=n;j++)
00054             {
00055                 if(V->routed[i] && V->routed[j])
00056                 {
00057                     // Make sure both are routed
00058                     //s[k].savings = V->d[VRPH_DEPOT][i] + V->d[j][VRPH_DEPOT] - lambda * V->d[j][i];// was d[i][j]
00059                     // d0i + di0 +d0j +dj0 - d0i -dij-dj0 = di0+d0j-sij
00060                     s[k].savings=V->d[i][VRPH_DEPOT]+V->d[VRPH_DEPOT][j]-lambda*V->d[i][j];
00061                     s[k].i=i;
00062                     s[k].j=j;
00063                     k++;
00064                 }
00065             }
00066 
00067         }
00068 
00069         // Now sort this list
00070 
00071         qsort (s, k, sizeof(class VRPSavingsElement), VRPSavingsCompare);
00072 
00073         // Set the flag to true
00074         has_savings_matrix = true;
00075         savings_matrix_size = k;
00076     }
00077     else
00078     {    
00079         // Use the neighbor_lists
00080         k=0;
00081         for(i=1;i<=n;i++)
00082         {
00083             for(m=0;m<V->neighbor_list_size;m++)
00084             {
00085                 j= V->nodes[i].neighbor_list[m].position;
00086                 if(j==VRPH_DEPOT)
00087                 {
00088                     m++;
00089                     if(m== V->neighbor_list_size)
00090                         break;//exit the m loop
00091                     else
00092                         j= V->nodes[i].neighbor_list[m].position;
00093                 }
00094 
00095 
00096                 if(V->routed[i] && V->routed[j])
00097                 {
00098                     s[k].savings = V->d[VRPH_DEPOT][i] + V->d[j][VRPH_DEPOT] - lambda * V->d[i][j];
00099                     s[k].i=i;
00100                     s[k].j=j;
00101                     k++;
00102                 }
00103             }
00104 
00105         }
00106 
00107         // Now sort this list
00108 
00109         qsort (s, k, sizeof(class VRPSavingsElement), VRPSavingsCompare);
00110 
00111         // Set the flag to true
00112         has_savings_matrix = true;
00113         savings_matrix_size = k;
00114 
00115     }
00116 
00117     return;
00118 
00119 }
00120 
00121 
00122 bool ClarkeWright::Construct(VRP *V, double lambda, bool use_neighbor_list)
00123 {
00129 
00130 
00131     int i,j,k,m,n,x;
00132     int num_routes;
00133     unsigned char *status;
00134     double savings;    
00135     int i_route, j_route;
00136 
00137     Postsert postsert;
00138     Presert presert;
00139     Concatenate concatenate;
00140 
00141     n= V->num_nodes;    // # of non-VRPH_DEPOT nodes.
00142     num_routes=n;
00143     status=new unsigned char[V->num_original_nodes+1];
00144 
00145     memset(status,VRPH_UNUSED,sizeof(unsigned char)*(V->num_original_nodes+1));
00146 
00147     // First, create the initial routes:  VRPH_DEPOT - node - VRPH_DEPOT for all nodes
00148 
00149 
00150     // Check to see if there are any routed nodes
00151     // If so, then we assume that a solution on a subset of nodes is desired
00152     // Otherwise, we construct the default routes for ALL possible nodes
00153     int num_routed=0;
00154     for(i=1;i<=V->num_original_nodes;i++)
00155     {
00156         if(V->routed[i])
00157             num_routed++;
00158         
00159     }
00160 
00161 #if CW_DEBUG
00162     printf("CW: %d nodes routed\n",num_routed);
00163 #endif
00164 
00165     if(num_routed==0)
00166     {
00167         if(V->create_default_routes() == false)
00168         {
00169             report_error("%s: Default CW routes are not feasible!!\n");
00170             // The default routes are not feasible!  
00171             return false;
00172 
00173         }
00174     }
00175 
00176 
00177     // Now start merging routes
00178     // Create the savings matrix 
00179     CreateSavingsMatrix(V,lambda,use_neighbor_list);
00180 
00181     k= savings_matrix_size; // Size of savings matrix
00182 
00183 
00184 #if CW_DEBUG
00185     printf("savings matrix complete\n");
00186 #endif
00187 
00188     for(m=0; m<k; m++)
00189     {
00190         // The savings list is already sorted and the savings_element structure contains 
00191         // the i and j values that we need
00192 
00193         i = s[m].i;
00194         j = s[m].j;
00195 
00196         savings = s[m].savings;
00197 
00198 #if CW_DEBUG
00199         printf("CW(%d of %d):%d,%d,%f\n",m,k,i,j,savings);
00200 #endif
00201 
00202         // Now check to see if we can merge these routes
00203 
00204         // Default is to skip
00205         x=-1;
00206 
00207         if(status[i]==VRPH_UNUSED && status[j]==VRPH_UNUSED)
00208             // Neither has been used yet
00209             x=0;
00210 
00211         if(status[i]==VRPH_ADDED && status[j]==VRPH_UNUSED)
00212             // i has been VRPH_ADDED but j is VRPH_UNUSED
00213             x=1;
00214 
00215         if(status[i]==VRPH_UNUSED && status[j]==VRPH_ADDED)
00216             // j has been VRPH_ADDED but i is VRPH_UNUSED
00217             x=2;
00218 
00219         if(status[i]==VRPH_ADDED && status[j]==VRPH_ADDED)
00220             // i and j both VRPH_ADDED
00221             x=3;        
00222 
00223         if(status[i]==VRPH_INTERIOR || status[j]==VRPH_INTERIOR  )
00224             // One is interior or the VRPH_DEPOT - skip and move on
00225             x=-1;
00226 
00227         if(i==0 || j==0)
00228         {
00229             fprintf(stderr,"CW::Savings matrix error!cw[m=%d of %d];  i=%d; j=%d; savings = %f\n",
00230                 m,k,i,j,savings);
00231             report_error("%s: Error in CW.construct\n");
00232         }
00233 
00234         // Possible values for x:
00235         // x=-1-->at least one VRPH_INTERIOR or not routed --do nothing
00236         // x=0-->both i and j VRPH_UNUSED
00237         // x=1-->j VRPH_UNUSED and i VRPH_ADDED
00238         // x=2-->i VRPH_UNUSED and j VRPH_ADDED
00239         // x=3-->i and j VRPH_ADDED
00240 
00241         switch(x)
00242         {
00243 
00244         case -1:
00245             // had an VRPH_INTERIOR node - nothing to do but move on...
00246             break;
00247 
00248         case 0:
00249             // both i and j VRPH_UNUSED - merge the two routes making 1-i-j-1
00250             if(postsert.move(V,j,i)==true)
00251             {
00252                 status[i]=VRPH_ADDED;
00253                 status[j]=VRPH_ADDED;
00254                 num_routes--;                    
00255             }
00256             break;
00257 
00258         case 1:
00259 
00260             // j VRPH_UNUSED and i previously VRPH_ADDED
00261 
00262             if(V->next_array[i]>0)
00263             {
00264                 // i is the first node in its route
00265                 if(presert.move(V,j,i)==true)
00266                 {
00267                     status[i]=VRPH_INTERIOR;
00268                     status[j]=VRPH_ADDED;
00269                     num_routes--;
00270                 }
00271             }
00272             else
00273             {
00274                 // i is the last node in its route
00275 
00276                 if(postsert.move(V,j,i)==true)
00277                 {
00278                     status[i]=VRPH_INTERIOR;
00279                     status[j]=VRPH_ADDED;
00280                     num_routes--;
00281                 }
00282             }
00283             break;
00284 
00285         case 2:
00286             // i VRPH_UNUSED and j previously VRPH_ADDED
00287             // Since j is not forbidden, it is in either position 2 or -2
00288 
00289             if(V->next_array[j]>0)
00290             {
00291                 // j is 2nd in its route
00292                 if(presert.move(V,i,j)==true)
00293                 {
00294                     status[j]=VRPH_INTERIOR;
00295                     status[i]=VRPH_ADDED;
00296                     num_routes--;
00297                 }
00298             }
00299             else
00300             {
00301                 // j is -2nd in its route
00302                 if(postsert.move(V,i,j)==true)
00303                 {
00304                     status[j]=VRPH_INTERIOR;
00305                     status[i]=VRPH_ADDED;
00306                     num_routes--;
00307 
00308                 }
00309             }
00310 
00311             break;
00312 
00313         case 3:                
00314             // i and j both previously added but neither VRPH_INTERIOR
00315             // Here we have to merge the two routes together        
00316 
00317             // First, make sure they are not in the same route!
00318             if( V->route_num[i] == V->route_num[j] )
00319                 break;    
00320 
00321             // Now we will rearrange the routes containing both i and j if necessary
00322             // so that i is the first node and j is the last node in their routes.
00323             // This will be done by a route reversal if necessary.
00324 
00325             num_routes--;
00326 
00327             if(V->next_array[i]<=0 && V->next_array[j]<=0)
00328             {
00329                 // Both in position -2 - reverse route containing i and merge
00330                 V->reverse_route(V->route_num[i]);
00331 
00332                 // So i is now in 2nd position of its route.
00333                 i_route= V->route_num[i];
00334                 j_route= V->route_num[j];
00335 
00336                 if(concatenate.move(V,i_route,j_route)==true)
00337                 {
00338                     status[i]=VRPH_INTERIOR;
00339                     status[j]=VRPH_INTERIOR;
00340                 }
00341                 break;
00342             }
00343 
00344 
00345             if(V->pred_array[i]<=0 && V->pred_array[j]<=0)
00346             {
00347                 // Both in position 2
00348                 V->reverse_route(V->route_num[j]);
00349 
00350                 i_route= V->route_num[i];
00351                 j_route= V->route_num[j];
00352 
00353                 if(concatenate.move(V,i_route,j_route)==true)
00354                 {
00355 
00356                     status[i]=VRPH_INTERIOR;
00357                     status[j]=VRPH_INTERIOR;
00358                 }
00359                 break;
00360             }
00361 
00362 
00363             if(V->next_array[i]>0 && V->next_array[j]<=0)
00364             {
00365                 // i in 2nd and j in -2nd
00366 
00367                 i_route= V->route_num[i];
00368                 j_route= V->route_num[j];
00369 
00370                 if(concatenate.move(V,i_route,j_route)==true)
00371                 {                        
00372                     status[i]=VRPH_INTERIOR;
00373                     status[j]=VRPH_INTERIOR;
00374                 }
00375                 break;
00376             }
00377 
00378             if(V->next_array[j]>0 && V->next_array[i]<=0)
00379             {
00380                 // j in 2nd and i in -2nd
00381                 i_route= V->route_num[i];
00382                 j_route= V->route_num[j];
00383 
00384                 if(concatenate.move(V,j_route,i_route)==true)
00385                 {
00386                     status[i]=VRPH_INTERIOR;
00387                     status[j]=VRPH_INTERIOR;
00388                 }
00389                 break;
00390             }
00391             break;
00392         }
00393         // End switch statement
00394     }
00395 
00396 #if CW_DEBUG
00397     printf("Loop complete\n");
00398 #endif
00399 
00400     delete [] status;
00401 
00402 #if CW_DEBUG
00403     printf("Cleanup complete\n");
00404 #endif
00405 
00406     // Set the record
00407     V->record = V->total_route_length;
00408 
00409     // Normalize the route numbers!
00410     V->normalize_route_numbers();
00411 
00412 #if CW_DEBUG
00413     printf("Done normalizing\n");
00414 #endif
00415 
00416     return true;
00417 }
00418