00001
00002
00003
00004
00005
00006
00007
00008
00009
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
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
00098
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