VRPH  1.0
src/VRPTabuList.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 
00015 VRPTabuList::VRPTabuList()
00016 {
00020 
00021     this->max_entries=NUM_VRPH_TABU_ROUTES;
00022     this->num_entries=0;
00023     this->full=false;
00024     this->start_index=0;
00025     this->hash_vals1=NULL;
00026     this->hash_vals2=NULL;
00027 
00028     
00029 }
00030 
00031 VRPTabuList::VRPTabuList(int t)
00032 {
00036 
00037     this->max_entries=t;
00038     this->num_entries=0;
00039     this->full=false;
00040     this->start_index=0;
00041     this->hash_vals1=new int[t];
00042     this->hash_vals2=new int[t];
00043 
00044     int i;
00045     for(i=0;i<this->max_entries;i++)
00046     {
00047         this->hash_vals1[i]=-1;
00048         this->hash_vals2[i]=-1;
00049     }
00050     
00051 
00052 }
00053 
00054 VRPTabuList::~VRPTabuList()
00055 {
00059 
00060     if(this->hash_vals1)
00061         delete [] hash_vals1;
00062 
00063     if(this->hash_vals2)
00064         delete [] hash_vals2;
00065 }
00066 
00067 void VRPTabuList::update_list(VRPRoute *r)
00068 {
00072 
00073     r->hash_val=r->hash(SALT_1);
00074     r->hash_val2=r->hash(SALT_2);
00075 
00076 #if VRPH_TABU_DEBUG
00077     printf("Adding route with hashes (%d, %d) and length, load (%5.2f, %d) to tabu list\n",
00078         r->hash_val,r->hash_val2,r->length,r->load);
00079 #endif
00080     
00081     if(this->num_entries < this->max_entries)
00082     {
00083         // Update the lists of hash_vals
00084         this->hash_vals1[this->num_entries]=r->hash_val;
00085         this->hash_vals2[this->num_entries]=r->hash_val2;
00086 
00087         this->num_entries++;
00088 #if VRPH_TABU_DEBUG
00089         printf("Tabu list after updating\n");
00090         this->show();
00091 #endif
00092 
00093         return;
00094     
00095     }
00096 
00097     // The list is full - overwrite the current start_index entry
00098     // and increment start_index
00099 
00100     this->hash_vals1[this->start_index]=r->hash_val;
00101     this->hash_vals2[this->start_index]=r->hash_val2;
00102     this->start_index = ((this->start_index + 1) % (this->num_entries));
00103     this->full=true;
00104 
00105 #if VRPH_TABU_DEBUG
00106     printf("Tabu list (full) after updating\n");
00107     this->show();
00108 #endif
00109 
00110     return;
00111 }
00112 
00113 void VRPTabuList::empty()
00114 {
00118 
00119 #if VRPH_TABU_DEBUG
00120     printf("Emptying tabu list -  max_entries is %d\n", this->max_entries);
00121 #endif
00122     int i;
00123     for(i=0;i<this->max_entries;i++)
00124     {
00125         this->hash_vals1[i]=-1;
00126         this->hash_vals2[i]=-1;
00127     }
00128 
00129     this->start_index=0;
00130     this->num_entries=0;
00131     this->full=false;
00132 
00133     return;
00134 
00135 }
00136 
00137 void VRPTabuList::show()
00138 {
00143 
00144     printf("Tabu List currently has %d entries starting at %d (max is %d)\n",
00145         this->num_entries,this->start_index, this->max_entries);
00146 
00147     for(int i=0;i<this->num_entries;i++)
00148     {
00149         printf("Tabu entry %d: (%d,%d)\n",((start_index+i)%this->max_entries),
00150             this->hash_vals1[((start_index+i)%this->max_entries)],
00151             this->hash_vals2[((start_index+i)%this->max_entries)]);
00152     }
00153 
00154     return;
00155 
00156 
00157 }
00158