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" 00015 00016 VRPSolutionWarehouse::VRPSolutionWarehouse() 00017 { 00021 00022 this->max_size=0; 00023 this->sols=NULL; 00024 this->worst_obj=VRP_INFINITY; 00025 this->num_sols=0; 00026 00027 } 00028 00029 VRPSolutionWarehouse::VRPSolutionWarehouse(int max_sols, int n) 00030 { 00035 00036 this->max_size=max_sols; 00037 this->sols=new VRPSolution[this->max_size]; 00038 // This calls the default constructor so we have to allocate the memory for 00039 // the sol buffer still... 00040 for(int i=0;i<this->max_size;i++) 00041 this->sols[i].sol=new int[n+2]; 00042 00043 this->hash_table=new struct htable_entry[HASH_TABLE_SIZE]; 00044 00045 // Zeroize the hash table 00046 for(int i=0;i<HASH_TABLE_SIZE;i++) 00047 hash_table[i].num_vals=0; 00048 00049 this->worst_obj=VRP_INFINITY; 00050 this->num_sols=0; 00051 00052 } 00053 VRPSolutionWarehouse::~VRPSolutionWarehouse() 00054 { 00058 00059 if(this->hash_table) 00060 delete [] this->hash_table; 00061 //for(int i=0;i<this->max_size;i++) 00062 // this->sols[i].~VRPSolution(); 00063 00064 if(this->sols) 00065 delete [] this->sols; // Calls VRPSolution destructor 00066 00067 } 00068 00069 00070 int VRPSolutionWarehouse::add_sol(VRPSolution *new_sol, int start_index) 00071 { 00082 00083 int i,j; 00084 00085 if(start_index<0) 00086 return -1; 00087 00088 if( (this->num_sols == this->max_size) && (new_sol->obj > this->sols[num_sols-1].obj) ) 00089 { 00090 #if WAREHOUSE_DEBUG 00091 printf("WH is full and %f>%f(=?=%f)\n",new_sol->obj ,this->sols[num_sols-1].obj, 00092 this->worst_obj); 00093 #endif 00094 // It doesn't beat the worst solution and we are full 00095 return -1; 00096 } 00097 00098 // First check the hash table; 00099 int hash_val=new_sol->hash(SALT_1); 00100 int hash_val2=new_sol->hash(SALT_2); 00101 00102 if( (this->hash_table[hash_val].num_vals)>0) 00103 { 00104 #if WAREHOUSE_DEBUG 00105 printf("Possible duplicate at position %d\n",hash_val); 00106 #endif 00107 // We have possibly seen this solution before -- hash again and check the lengths 00108 for(j=0; j<this->hash_table[hash_val].num_vals;j++) 00109 { 00110 if( (VRPH_ABS(this->hash_table[hash_val].length[j] - new_sol->obj)<VRPH_EPSILON) && 00111 (this->hash_table[hash_val].hash_val_2[j]==hash_val2) ) 00112 { 00113 // This must be the same solution 00114 #if WAREHOUSE_DEBUG 00115 printf("Duplicate solution\n"); 00116 #endif 00117 return -1; 00118 } 00119 00120 } 00121 } 00122 00123 #if WAREHOUSE_DEBUG 00124 printf("New solution found (%d now at this location)\n",this->hash_table[hash_val].num_vals+1); 00125 #endif 00126 00127 // We believe this is a new solution that should live in position hash_val 00128 // Add a new length and hval2 entry 00129 this->hash_table[hash_val].length[this->hash_table[hash_val].num_vals]=new_sol->obj; 00130 this->hash_table[hash_val].hash_val_2[this->hash_table[hash_val].num_vals]=hash_val2; 00131 // Increment the counter 00132 this->hash_table[hash_val].num_vals++; 00133 00134 // The hash table is updated - now add the solution in the correct location 00135 // Otherwise, we have to find out where to put the solution--start searching at 00136 // start_index-1 00137 for(i=VRPH_MAX(0,start_index-1); i<this->num_sols;i++) 00138 { 00139 // Break if new_sol < sols[i] since the list in the WH is sorted 00140 if( new_sol->obj < this->sols[i].obj ) 00141 break; 00142 } 00143 00144 // This solution should be in position i 00145 #if WAREHOUSE_DEBUG 00146 printf("Putting %f before %dth[%f]\n",new_sol->obj,i,sols[i].obj); 00147 #endif 00148 00149 // Make room in position i 00150 for(j=VRPH_MIN(num_sols,max_size-1); j>i; j--) 00151 { 00152 this->sols[j].obj=this->sols[j-1].obj; 00153 this->sols[j].n=this->sols[j-1].n; 00154 this->sols[j].in_IP=this->sols[j-1].in_IP; 00155 this->sols[j].time=this->sols[j-1].time; 00156 memcpy(this->sols[j].sol,this->sols[j-1].sol,((new_sol->n) + 2)*sizeof(int)); 00157 } 00158 #if WAREHOUSE_DEBUG 00159 printf("WH after making room\n"); 00160 //this->show(); 00161 #endif 00162 00163 // Insert new solution 00164 if(i>=this->max_size) 00165 return -1; 00166 00167 // Otherwise insert the new solution 00168 this->sols[i].obj=new_sol->obj; 00169 this->sols[i].n=new_sol->n; 00170 this->sols[i].in_IP=false; // new solution 00171 this->sols[i].time=new_sol->time; 00172 memcpy(this->sols[i].sol,new_sol->sol,((new_sol->n) + 2)*sizeof(int)); 00173 if(this->num_sols < this->max_size) 00174 this->num_sols++; 00175 // Update worst 00176 this->worst_obj=this->sols[num_sols-1].obj; 00177 00178 #if WAREHOUSE_DEBUG 00179 this->show(); 00180 printf("Returning %d-WH has %d sols now\n", i, this->num_sols); 00181 #endif 00182 00183 return i; 00184 // Return the value of the solutions index in the WH 00185 00186 00187 } 00188 00189 void VRPSolutionWarehouse::show() 00190 { 00194 00195 printf("Solution Warehouse contents\n%d sols, worst is %f\n",num_sols,worst_obj); 00196 for(int i=0;i<this->num_sols;i++) 00197 { 00198 printf("%03d\t%5.3f\t",i,this->sols[i].obj); 00199 if(this->sols[i].in_IP==true) 00200 printf("true\n"); 00201 else 00202 printf("false\n"); 00203 } 00204 00205 00206 return; 00207 00208 00209 00210 } 00211 bool VRPSolutionWarehouse::liquidate() 00212 { 00216 00217 int i; 00218 00219 for(i=0;i<this->num_sols;i++) 00220 // Erase the existing solutions 00221 memset(this->sols[i].sol,0,this->sols[i].n*sizeof(int)); 00222 00223 this->num_sols=0; 00224 this->worst_obj=VRP_INFINITY; 00225 00226 // Zeroize the hash table 00227 for(i=0;i<HASH_TABLE_SIZE;i++) 00228 { 00229 for(int j=0;j<this->hash_table[i].num_vals;j++) 00230 { 00231 this->hash_table[i].hash_val_2[j]=0; 00232 this->hash_table[i].length[j]=0; 00233 00234 } 00235 this->hash_table[i].num_vals=0; 00236 00237 } 00238 00239 return true; 00240 00241 } 00242 00243 00244 void VRPSolutionWarehouse::sort_sols() 00245 { 00250 00251 qsort(this->sols,this->num_sols,sizeof(VRPSolution),VRPSolutionCompare); 00252 return; 00253 00254 } 00255 int VRPSolution::hash(int salt) 00256 { 00263 00264 int val = 0; 00265 int i; 00266 00267 for(i=0;i<this->n-1; i++)//was -2?? 00268 val ^= (randvals[(salt + VRPH_ABS(this->sol[i])+VRPH_ABS(this->sol[VRPH_MIN((this->n)-1,i+1)]) )% NUM_RANDVALS]); 00269 00270 val=val&(HASH_TABLE_SIZE-1); 00271 // Get the low # of bits 00272 return val; 00273 00274 } 00275 00276 00277 VRPSolution::VRPSolution(int n) 00278 { 00282 00283 this->n=n; 00284 this->sol=new int[n+2]; 00285 this->in_IP=false; 00286 this->obj=0; 00287 this->time=0; 00288 00289 00290 } 00291 00292 00293 VRPSolution::VRPSolution() 00294 { 00298 00299 this->n=0; 00300 this->time=0; 00301 this->in_IP=false; 00302 this->obj=0; 00303 this->sol=NULL; 00304 00305 } 00306 00307 VRPSolution::~VRPSolution() 00308 { 00312 00313 if(this->sol) 00314 delete [] this->sol; 00315 } 00316