00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014 #include "randvals.h"
00015
00016
00017 VRPRoute::VRPRoute()
00018 {
00022
00023 this->name=NULL;
00024 this->ordering=NULL;
00025 this->x=NULL;
00026 this->y=NULL;
00027
00028 }
00029
00030 VRPRoute::VRPRoute(int n)
00031 {
00036
00037 this->name=new char[8*n];
00038 this->ordering=new int[n];
00039 this->x=new double[n];
00040 this->y=new double[n];
00041
00042 }
00043
00044
00045 VRPRoute::~VRPRoute()
00046 {
00050
00051 if(this->name)
00052 delete [] this->name;
00053 if(this->ordering)
00054 delete [] this->ordering;
00055 if(this->x)
00056 delete [] this->x;
00057 if(this->y)
00058 delete [] this->y;
00059
00060 }
00061
00062
00063 int VRPRoute::hash(int salt)
00064 {
00069
00070
00071
00072
00073
00074 if(this->num_customers==0)
00075 return 0;
00076
00077 int i;
00078
00079 if(this->ordering[num_customers-1]<this->ordering[0])
00080 {
00081 fprintf(stderr,"Route has %d customers\n",this->num_customers);
00082 fprintf(stderr,"end<start! %d<%d\n",this->ordering[num_customers-1],this->ordering[0]);
00083 for(i=0;i<this->num_customers;i++)
00084 fprintf(stderr,"%d ",this->ordering[i]);
00085 fprintf(stderr,"Length=%f;\nLoad=%d\nObj=%fStart=%d\nEnd=%d\n",this->length,this->load,this->obj_val,
00086 this->start,this->end);
00087
00088 report_error("%s: Error in route hash\n",__FUNCTION__);
00089 }
00090
00091 int val = 0;
00092
00093 for(i=0;i<this->num_customers; i++)
00094 val ^= (randvals[(salt + VRPH_ABS(this->ordering[i])+
00095 VRPH_ABS(this->ordering[VRPH_MIN((this->num_customers)-1,i+1)]) )% NUM_RANDVALS]);
00096
00097 for(i=0;i<this->num_customers; i++)
00098 val+=this->ordering[i];
00099
00100 val=val&(HASH_TABLE_SIZE-1);
00101
00102
00103 return val;
00104
00105 }
00106
00107
00108 void VRPRoute::create_name()
00109 {
00114
00115
00116 if(!this->name)
00117 {
00118 fprintf(stderr,"No memory allocated for the route name!\n");
00119 exit(-1);
00120 }
00121
00122 int i;
00123 char temp[100];
00124
00125
00126 sprintf(this->name,"%d_%d_",this->hash(SALT_1),this->hash(SALT_2));
00127
00128
00129 for(i=0;i<this->num_customers-1;i++)
00130 {
00131 sprintf(temp,"%d_",this->ordering[i]);
00132 strcat(this->name,(const char *)temp);
00133 }
00134 sprintf(temp,"%d",this->ordering[this->num_customers-1]);
00135 strcat(this->name,(const char *)temp);
00136
00137 return;
00138
00139 }
00140
00141 VRPRouteWarehouse::VRPRouteWarehouse()
00142 {
00146
00147 this->hash_table_size=0;
00148 this->num_unique_routes=0;
00149
00150 }
00151
00152 VRPRouteWarehouse::VRPRouteWarehouse(int h_size)
00153 {
00158
00159
00160 this->hash_table=new struct htable_entry[h_size];
00161
00162 this->hash_table_size=h_size;
00163 this->num_unique_routes=0;
00164
00165 for(int i=0;i<h_size;i++)
00166 this->hash_table[i].num_vals=0;
00167
00168 }
00169
00170
00171 VRPRouteWarehouse::~VRPRouteWarehouse()
00172 {
00176
00177 delete [] this->hash_table;
00178
00179 }
00180
00181 void VRPRouteWarehouse::liquidate()
00182 {
00186
00187 this->num_unique_routes=0;
00188
00189 for(int i=0;i<this->hash_table_size;i++)
00190 this->hash_table[i].num_vals=0;
00191 }
00192
00193
00194 void VRPRouteWarehouse::remove_route(int hash_val, int hash_val2)
00195 {
00201
00202 int i,j;
00203
00204 if(this->hash_table[hash_val].num_vals==0)
00205 {
00206 fprintf(stderr,"Tried to remove empty hash_table entry!\n");
00207 fprintf(stderr,"hash_val=%d\n;hash_val2=%d\n",hash_val,hash_val2);
00208 report_error("%s: Error removing route from WH\n",__FUNCTION__);
00209 }
00210
00211
00212 for(i=0;i<this->hash_table[hash_val].num_vals;i++)
00213 {
00214 if( this->hash_table[hash_val].hash_val_2[i]==hash_val2)
00215 {
00216
00217
00218 for(j=i+1;j<this->hash_table[hash_val].num_vals;j++)
00219 {
00220
00221 this->hash_table[hash_val].length[j-1]=
00222 this->hash_table[hash_val].length[j];
00223 this->hash_table[hash_val].hash_val_2[j-1]=
00224 this->hash_table[hash_val].hash_val_2[j];
00225 }
00226
00227 this->hash_table[hash_val].num_vals--;
00228
00229 this->num_unique_routes--;
00230
00231 return;
00232 }
00233 }
00234
00235
00236
00237 fprintf(stderr,"Never found the route when removing from WH!!!\n");
00238 fprintf(stderr,"Looking for (%d, %d)\n",hash_val, hash_val2);
00239 for(i=0;i<this->hash_table[hash_val].num_vals;i++)
00240 fprintf(stderr,"Position %d: (%d, %d, %f)\n",i, hash_val,
00241 this->hash_table[hash_val].hash_val_2[i], hash_table[hash_val].length[i]);
00242
00243 report_error("%s: Error removing route from WH\n",__FUNCTION__);
00244
00245 }
00246
00247
00248 int VRPRouteWarehouse::add_route(VRPRoute *R)
00249 {
00254
00255
00256 int i;
00257 R->hash_val = R->hash(SALT_1);
00258 R->hash_val2 = R->hash(SALT_2);
00259 int hval=R->hash_val;
00260 int hval2=R->hash_val2;
00261
00262 if(this->hash_table[hval].num_vals>0)
00263 {
00264
00265
00266
00267 if(this->hash_table[hval].num_vals==NUM_ENTRIES)
00268 {
00269 fprintf(stderr, "Route hash table is too small!! \n");
00270 fprintf(stderr, "At entry %d\n",hval);
00271 fflush(stderr);
00272 for(i=0;i<this->hash_table[hval].num_vals;i++)
00273 {
00274 fprintf(stderr,"%d %f\n",i,this->hash_table[hval].length[i]);
00275 fflush(stderr);
00276 }
00277 fflush(stderr);
00278 report_error("%s: Error adding route to WH\n",__FUNCTION__);
00279 }
00280
00281
00282 for(i=0;i<this->hash_table[hval].num_vals;i++)
00283 {
00284
00285 if(this->hash_table[hval].hash_val_2[i] == hval2)
00286 {
00287
00288
00289
00290 if(R->length<this->hash_table[hval].length[i] &&
00291 VRPH_ABS(R->length - this->hash_table[hval].length[i])>VRPH_EPSILON)
00292 {
00293 this->hash_table[hval].length[i]=R->length;
00294 return BETTER_ROUTE;
00295 }
00296 else
00297 return DUPLICATE_ROUTE;
00298
00299
00300 }
00301 }
00302
00303
00304
00305
00306 this->hash_table[hval].length[this->hash_table[hval].num_vals]=
00307 R->length ;
00308 this->hash_table[hval].hash_val_2[this->hash_table[hval].num_vals]=
00309 hval2;
00310
00311 this->hash_table[hval].num_vals++;
00312 this->num_unique_routes++;
00313 return ADDED_ROUTE;
00314
00315 }
00316
00317
00318
00319 this->hash_table[hval].num_vals=1;
00320
00321 this->hash_table[hval].length[0]=R->length ;
00322 this->hash_table[hval].hash_val_2[0]=hval2;
00323 this->num_unique_routes++;
00324 return ADDED_ROUTE;
00325 }
00326
00327
00328
00329