Djinni  2.2
TSPRoute.h
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