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 #include "randvals.h" // included for hashing 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];// Used to add as column 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 // Associate a random integer with each node in the route 00071 // XOR them together and take the low log_2(HASH_TABLE_SIZE) bits 00072 00073 // Return 0 if # customers is 0 (the "NULL" route) 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 // Get the right # of bits 00102 00103 return val; 00104 00105 } 00106 00107 00108 void VRPRoute::create_name() 00109 { 00114 00115 // Make sure we have memory for the name 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 // Write the hash value 00126 sprintf(this->name,"%d_%d_",this->hash(SALT_1),this->hash(SALT_2)); 00127 00128 // Write the ordering 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 // Allocate memory for the hash_table 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 // Look for the second hash value 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 // This is the one to remove-shift everyone else down one 00217 // and decrement num_vals 00218 for(j=i+1;j<this->hash_table[hash_val].num_vals;j++) 00219 { 00220 // [j] -> [j-1] 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 // We shouldn't get here! 00236 // Annoying... 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 // Hash the route 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 // The entry is not vacant-must investigate further... 00265 // Make sure that we haven't filled up all the entries--should NEVER happen... 00266 // as long as the hash_table is big enough 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 // Otherwise, there is room in the table 00282 for(i=0;i<this->hash_table[hval].num_vals;i++) 00283 { 00284 // Compare the second hash value- 00285 if(this->hash_table[hval].hash_val_2[i] == hval2) 00286 { 00287 00288 // These surely must cover the same nodes - now see if we have 00289 // a lower cost tour 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 // The column/route was the same or worse. 00299 00300 } 00301 } 00302 00303 00304 // We didn't match any of the previous entries with this hval 00305 // New entry at this location 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 // ELSE... 00318 // This is a new entry--update the hash table 00319 this->hash_table[hval].num_vals=1; 00320 // Insert the length and h2 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