Djinni
2.2
|
00001 #ifndef TSP_ROUTE_H 00002 #define TSP_ROUTE_H 00003 00004 #include <vector> 00005 #include <string> 00006 #include <ctime> 00007 #include <iostream> 00008 #include <iterator> 00009 #include <sys/types.h> 00010 00011 #if defined(__GNUC__) && (__GNUC__ >= 4) 00012 #include <tr1/memory> 00013 #define SHARED_PTR std::tr1::shared_ptr 00014 #else 00015 #include <boost/shared_ptr.hpp> 00016 #define SHARED_PTR boost::shared_ptr 00017 #endif 00018 00019 #include "TSPTWWorld.h" 00020 #include "../Twister/Twister.h" 00021 00023 00031 template <class WorldType> 00032 class TSPRoute { 00033 public: 00036 TSPRoute(WorldType& w) : 00037 _w(new WorldType(w)), _time(0.0), 00038 _cost(0.0), _timeWait(0.0) 00039 { 00040 _solution.resize(_w->data().size(), 0); 00041 _arrivaltime.resize(_solution.size(), 0); 00042 _penaltysum.resize(_solution.size(), 0); 00043 _identifier = "TSPRoute"; 00044 } 00045 00049 TSPRoute(const char* worldParam) : 00050 _w(new WorldType(worldParam)), 00051 _time(0.0), _cost(0.0), _timeWait(0.0) 00052 { 00053 _solution.resize(_w->data().size(), 0); 00054 _arrivaltime.resize(_solution.size(), 0); 00055 _penaltysum.resize(_solution.size(), 0); 00056 _identifier = "TSPRoute"; 00057 } 00058 00060 virtual ~TSPRoute() {} 00061 00064 void setF(const double& f) { _f = f; } 00065 00068 void setP(const double& p) { _p = p; } 00069 00072 double getF() const { return _f; } 00073 00076 double getP() const { return _p; } 00077 00080 void generateNeighbor(TSPRoute& neighbor) 00081 { 00082 u_int32_t firstswitch = 0; 00083 u_int32_t secondswitch; 00084 int holder; 00085 u_int32_t numCustomers = _solution.size(); 00086 neighbor.setF(getF()); 00087 neighbor.setP(getP()); 00088 while (0 == firstswitch) 00089 firstswitch = static_cast<int>((numCustomers - 1) * 00090 Twister::generateDouble()) + 1; 00091 secondswitch = firstswitch; 00092 while ((secondswitch == firstswitch) || 00093 (secondswitch == firstswitch - 1)) 00094 secondswitch = static_cast<int>((numCustomers - 1) * 00095 Twister::generateDouble())+1; 00096 holder = _solution[firstswitch]; 00097 if (firstswitch < secondswitch) 00098 { 00099 std::copy(_solution.begin(), _solution.begin() + firstswitch, 00100 neighbor._solution.begin()); 00101 std::copy(_solution.begin() + firstswitch + 1, 00102 _solution.begin() + secondswitch + 1, 00103 neighbor._solution.begin() + firstswitch); 00104 neighbor._solution[secondswitch] = holder; 00105 neighbor._firstarrival = 00106 static_cast<u_int32_t>(_arrivaltime[firstswitch-1]); 00107 neighbor._firstpenalty = 00108 static_cast<u_int32_t>(_penaltysum[firstswitch-1]); 00109 std::copy(_arrivaltime.begin(), 00110 _arrivaltime.begin() + firstswitch, 00111 neighbor._arrivaltime.begin()); 00112 std::copy(_penaltysum.begin(), 00113 _penaltysum.begin() + firstswitch, 00114 neighbor._penaltysum.begin()); 00115 } 00116 else 00117 { 00118 std::copy(_solution.begin(), 00119 _solution.begin() + secondswitch + 1, 00120 neighbor._solution.begin()); 00121 std::copy(_solution.begin() + secondswitch + 1, 00122 _solution.begin() + firstswitch, 00123 neighbor._solution.begin() + secondswitch + 2); 00124 neighbor._solution[secondswitch+1] = holder; 00125 neighbor._firstarrival = 00126 static_cast<u_int32_t>(_arrivaltime[secondswitch]); 00127 neighbor._firstpenalty = 00128 static_cast<u_int32_t>(_penaltysum[secondswitch]); 00129 std::copy(_arrivaltime.begin(), 00130 _arrivaltime.begin() + secondswitch + 1, 00131 neighbor._arrivaltime.begin()); 00132 std::copy(_penaltysum.begin(), 00133 _penaltysum.begin() + secondswitch + 1, 00134 neighbor._penaltysum.begin()); 00135 } 00136 if (std::max(firstswitch, secondswitch) != numCustomers) 00137 std::copy(_solution.begin() + 00138 std::max(firstswitch, secondswitch) + 1, _solution.end(), 00139 neighbor._solution.begin() + 00140 std::max(firstswitch, secondswitch) + 1); 00141 neighbor._firstswitch = firstswitch; 00142 neighbor._secondswitch = secondswitch; 00143 neighbor.update(); 00144 } 00145 00147 void update() 00148 { 00149 double cost = getF(); 00150 int firstswitch = _firstswitch; 00151 int secondswitch = _secondswitch; 00152 int numCustomers = _solution.size(); 00153 const std::vector<int>& tour = _solution; 00154 const Matrix<double, 2>& travTime = 00155 _w->travelTimes(); 00156 if (firstswitch <= secondswitch) 00157 { 00158 if (secondswitch != (numCustomers - 1)) 00159 { 00160 cost -= (travTime[tour[firstswitch - 1]][tour[secondswitch]] 00161 + travTime[tour[secondswitch]][tour[firstswitch]] 00162 + travTime[tour[secondswitch-1]][tour[secondswitch+1]]); 00163 cost += (travTime[tour[firstswitch - 1]][tour[firstswitch]] 00164 + travTime[tour[secondswitch-1]][tour[secondswitch]] 00165 + travTime[tour[secondswitch]][tour[secondswitch+1]]); 00166 } 00167 else 00168 { 00169 cost -= (travTime[tour[firstswitch - 1]][tour[secondswitch]] 00170 + travTime[tour[secondswitch]][tour[firstswitch]] 00171 + travTime[tour[secondswitch - 1]][tour[0]]); 00172 cost += (travTime[tour[firstswitch - 1]][tour[firstswitch]] 00173 + travTime[tour[secondswitch-1]][tour[secondswitch]] 00174 + travTime[tour[secondswitch]][tour[0]]); 00175 } 00176 timingUpdate(); 00177 } 00178 else 00179 { 00180 if(firstswitch != (numCustomers-1)) 00181 { 00182 cost -= (travTime[tour[secondswitch]][tour[secondswitch+2]] 00183 + travTime[tour[firstswitch]][tour[secondswitch+1]] 00184 + travTime[tour[secondswitch+1]][tour[firstswitch +1]]); 00185 cost += (travTime[tour[firstswitch]][tour[firstswitch+1]] 00186 + travTime[tour[secondswitch]][tour[secondswitch+1]] 00187 + travTime[tour[secondswitch+1]][tour[secondswitch+2]]); 00188 } 00189 else 00190 { 00191 cost -= (travTime[tour[secondswitch]][tour[secondswitch+2]] 00192 + travTime[tour[firstswitch]][tour[secondswitch+1]] 00193 + travTime[tour[secondswitch + 1]][tour[0]]); 00194 cost += (travTime[tour[firstswitch]][tour[0]] 00195 + travTime[tour[secondswitch]][tour[secondswitch+1]] 00196 + travTime[tour[secondswitch+1]][tour[secondswitch+2]]); 00197 } 00198 timingUpdate(); 00199 } 00200 setF(cost); 00201 setP(_penaltysum[numCustomers-1]); 00202 } 00203 00205 void randomize() 00206 { 00207 for (u_int32_t i = 0 ; i < _solution.size() ; i += 1) 00208 _solution[i] = static_cast<int>(i); 00209 std::vector<int>::iterator iter = _solution.begin(); 00210 ++iter; 00211 std::random_shuffle(iter, _solution.end(), Twister::stl_rng); 00212 } 00213 00216 TSPRoute(const TSPRoute<WorldType>& route) : 00217 _w(route._w), _solution(route._solution), 00218 _f(route._f), _p(route._p), 00219 _identifier(route._identifier), 00220 _arrivaltime(route._arrivaltime), 00221 _penaltysum(route._penaltysum), 00222 _time(route._time), _cost(route._cost), 00223 _timeWait(route._timeWait), 00224 _firstswitch(route._firstswitch), 00225 _secondswitch(route._secondswitch), 00226 _firstarrival(route._firstarrival), 00227 _firstpenalty(route._firstpenalty) 00228 {} 00229 00233 std::ostream& dump(std::ostream& os) const 00234 { 00235 std::ostream_iterator<int> oiter(os, " "); 00236 std::ostream_iterator<int> end(); 00237 std::copy(_solution.begin(), _solution.end(), oiter); 00238 return os; 00239 } 00240 00242 void compute() 00243 { 00244 double addEnergy = 0; 00245 double energy = 0; 00246 double minutesMissed = 0; 00247 double routeTime = 0; 00248 double waitTime = 0; 00249 00250 const Matrix<double, 2>& travTime = _w->travelTimes(); 00251 const std::vector<double>& lowdeadlines = _w->lowDeadlines(); 00252 const std::vector<double>& deadlines = _w->deadlines(); 00253 00254 _penaltysum[0] = 0; 00255 _arrivaltime[0] = 0; 00256 00257 for (u_int32_t i = 0 ; i < _solution.size() - 1 ; ++i) 00258 { 00259 energy += travTime[_solution[i]][_solution[i + 1]]; 00260 routeTime += travTime[_solution[i]][_solution[i + 1]]; 00261 _arrivaltime[i+1] = energy; 00262 if (energy < lowdeadlines[_solution[i+1]]) 00263 { 00264 addEnergy = lowdeadlines[_solution[i+1]] - energy; 00265 waitTime += addEnergy; 00266 energy += addEnergy; 00267 } 00268 if (energy > deadlines[_solution[i+1]]) 00269 minutesMissed += energy - deadlines[_solution[i+1]]; 00270 _penaltysum[i+1] = minutesMissed; 00271 } 00272 energy += travTime[_solution[_solution.size() - 1]][_solution[0]]; 00273 routeTime += travTime[_solution[_solution.size() - 1]][_solution[0]]; 00274 setF(routeTime); 00275 _time = routeTime; 00276 setP(minutesMissed); 00277 _timeWait = waitTime; 00278 } 00279 00280 protected: 00281 00283 void timingUpdate() 00284 { 00285 int start; 00286 int numCustomers = _solution.size(); 00287 const Matrix<double, 2>& travTime = 00288 _w->travelTimes(); 00289 const std::vector<double> & lowdeadlines = _w->lowDeadlines(); 00290 const std::vector<double> & deadlines = _w->deadlines(); 00291 const std::vector<int>& tour = _solution; 00292 00293 if (_firstswitch < _secondswitch) 00294 start = _firstswitch; 00295 else 00296 start = _secondswitch + 1; 00297 00298 _arrivaltime[start - 1] = _firstarrival; 00299 _penaltysum[start - 1] = _firstpenalty; 00300 for(int i = start; i <= numCustomers - 1; i++) 00301 { 00302 if (_arrivaltime[i-1] >= lowdeadlines[tour[i-1]]) 00303 _arrivaltime[i] = _arrivaltime[i-1] + 00304 travTime[tour[i-1]][tour[i]]; 00305 else 00306 _arrivaltime[i] = lowdeadlines[tour[i-1]] + 00307 travTime[tour[i-1]][tour[i]]; 00308 if (_arrivaltime[i] > deadlines[tour[i]]) 00309 _penaltysum[i] = _penaltysum[i-1] + 00310 (_arrivaltime[i] - deadlines[tour[i]]); 00311 else 00312 _penaltysum[i] = _penaltysum[i-1]; 00313 } 00314 } 00315 00316 SHARED_PTR<WorldType> _w; 00317 std::vector<int> _solution; 00318 double _f, _p; 00319 std::string _identifier; 00320 std::vector<double> _arrivaltime; 00321 std::vector<double> _penaltysum; 00322 double _time, _cost, _timeWait; 00323 u_int32_t _firstswitch, _secondswitch, _firstarrival, _firstpenalty; 00324 }; 00325 00332 template <class WorldType> 00333 std::ostream& operator<<(std::ostream& os, const TSPRoute<WorldType>& sol) 00334 { 00335 return sol.dump(os); 00336 } 00337 00339 typedef TSPRoute<TSPTWWorld> TravelingSalesman; 00340 00341 #endif 00342