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