VRPH  1.0
src/VRPRoute.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"    // 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