VRPH
1.0
|
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