00001
00002
00003
00004
00005
00006
00007
00008
00009
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
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;
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
00058
00059
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
00070
00071 qsort (s, k, sizeof(class VRPSavingsElement), VRPSavingsCompare);
00072
00073
00074 has_savings_matrix = true;
00075 savings_matrix_size = k;
00076 }
00077 else
00078 {
00079
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;
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
00108
00109 qsort (s, k, sizeof(class VRPSavingsElement), VRPSavingsCompare);
00110
00111
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;
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
00148
00149
00150
00151
00152
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
00171 return false;
00172
00173 }
00174 }
00175
00176
00177
00178
00179 CreateSavingsMatrix(V,lambda,use_neighbor_list);
00180
00181 k= savings_matrix_size;
00182
00183
00184 #if CW_DEBUG
00185 printf("savings matrix complete\n");
00186 #endif
00187
00188 for(m=0; m<k; m++)
00189 {
00190
00191
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
00203
00204
00205 x=-1;
00206
00207 if(status[i]==VRPH_UNUSED && status[j]==VRPH_UNUSED)
00208
00209 x=0;
00210
00211 if(status[i]==VRPH_ADDED && status[j]==VRPH_UNUSED)
00212
00213 x=1;
00214
00215 if(status[i]==VRPH_UNUSED && status[j]==VRPH_ADDED)
00216
00217 x=2;
00218
00219 if(status[i]==VRPH_ADDED && status[j]==VRPH_ADDED)
00220
00221 x=3;
00222
00223 if(status[i]==VRPH_INTERIOR || status[j]==VRPH_INTERIOR )
00224
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
00235
00236
00237
00238
00239
00240
00241 switch(x)
00242 {
00243
00244 case -1:
00245
00246 break;
00247
00248 case 0:
00249
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
00261
00262 if(V->next_array[i]>0)
00263 {
00264
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
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
00287
00288
00289 if(V->next_array[j]>0)
00290 {
00291
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
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
00315
00316
00317
00318 if( V->route_num[i] == V->route_num[j] )
00319 break;
00320
00321
00322
00323
00324
00325 num_routes--;
00326
00327 if(V->next_array[i]<=0 && V->next_array[j]<=0)
00328 {
00329
00330 V->reverse_route(V->route_num[i]);
00331
00332
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
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
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
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
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
00407 V->record = V->total_route_length;
00408
00409
00410 V->normalize_route_numbers();
00411
00412 #if CW_DEBUG
00413 printf("Done normalizing\n");
00414 #endif
00415
00416 return true;
00417 }
00418