VRPH  1.0
src/VRPSolution.cpp
Go to the documentation of this file.
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