00001
00002
00003
00004
00005
00006
00007
00008
00009
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
00039
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
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
00062
00063
00064 if(this->sols)
00065 delete [] this->sols;
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
00095 return -1;
00096 }
00097
00098
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
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
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
00128
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
00132 this->hash_table[hash_val].num_vals++;
00133
00134
00135
00136
00137 for(i=VRPH_MAX(0,start_index-1); i<this->num_sols;i++)
00138 {
00139
00140 if( new_sol->obj < this->sols[i].obj )
00141 break;
00142 }
00143
00144
00145 #if WAREHOUSE_DEBUG
00146 printf("Putting %f before %dth[%f]\n",new_sol->obj,i,sols[i].obj);
00147 #endif
00148
00149
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
00161 #endif
00162
00163
00164 if(i>=this->max_size)
00165 return -1;
00166
00167
00168 this->sols[i].obj=new_sol->obj;
00169 this->sols[i].n=new_sol->n;
00170 this->sols[i].in_IP=false;
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
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
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
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
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++)
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
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