SUMO - Simulation of Urban MObility
RORouteDef_Alternatives.cpp
Go to the documentation of this file.
00001 /****************************************************************************/
00008 // A route with alternative routes
00009 /****************************************************************************/
00010 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
00011 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
00012 /****************************************************************************/
00013 //
00014 //   This file is part of SUMO.
00015 //   SUMO is free software: you can redistribute it and/or modify
00016 //   it under the terms of the GNU General Public License as published by
00017 //   the Free Software Foundation, either version 3 of the License, or
00018 //   (at your option) any later version.
00019 //
00020 /****************************************************************************/
00021 
00022 
00023 // ===========================================================================
00024 // included modules
00025 // ===========================================================================
00026 #ifdef _MSC_VER
00027 #include <windows_config.h>
00028 #else
00029 #include <config.h>
00030 #endif
00031 
00032 #include <utils/common/RandHelper.h>
00033 #include <utils/iodevices/OutputDevice.h>
00034 #include "ROHelper.h"
00035 #include "ROEdge.h"
00036 #include "RORouteDef.h"
00037 #include "ROVehicle.h"
00038 #include "ROCostCalculator.h"
00039 #include "RORouteDef_Alternatives.h"
00040 
00041 #ifdef CHECK_MEMORY_LEAKS
00042 #include <foreign/nvwa/debug_new.h>
00043 #endif // CHECK_MEMORY_LEAKS
00044 
00045 
00046 // ===========================================================================
00047 // method definitions
00048 // ===========================================================================
00049 RORouteDef_Alternatives::RORouteDef_Alternatives(const std::string& id,
00050         unsigned int lastUsed, 
00051         const int maxRoutes, const bool keepRoutes, const bool skipRouteCalculation)
00052     : RORouteDef(id, 0), myLastUsed((int) lastUsed),
00053       myMaxRouteNumber(maxRoutes), myKeepRoutes(keepRoutes),
00054       mySkipRouteCalculation(skipRouteCalculation) {
00055 }
00056 
00057 
00058 RORouteDef_Alternatives::~RORouteDef_Alternatives() {
00059     for (AlternativesVector::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
00060         delete *i;
00061     }
00062 }
00063 
00064 
00065 void
00066 RORouteDef_Alternatives::addLoadedAlternative(RORoute* alt) {
00067     myAlternatives.push_back(alt);
00068 }
00069 
00070 
00071 void
00072 RORouteDef_Alternatives::preComputeCurrentRoute(SUMOAbstractRouter<ROEdge, ROVehicle> &router,
00073         SUMOTime begin, const ROVehicle& veh) const {
00074     if (mySkipRouteCalculation) {
00075         myLastUsed = 0;
00076         myNewRoute = false;
00077         myPrecomputed = myAlternatives[myLastUsed];
00078         return;
00079     }
00080     // recompute duration of the last route used
00081     // build a new route to test whether it is better
00082     std::vector<const ROEdge*> edges;
00083     router.compute(myAlternatives[0]->getFirst(), myAlternatives[0]->getLast(), &veh, begin, edges);
00084     RORoute* opt = new RORoute(myID, 0, 1, edges, copyColorIfGiven());
00085     const SUMOReal costs = router.recomputeCosts(edges, &veh, begin);
00086     // check whether the same route was already used
00087     myLastUsed = findRoute(opt);
00088     myNewRoute = true;
00089     // delete the route when it already existed
00090     if (myLastUsed >= 0) {
00091         delete opt;
00092         myNewRoute = false;
00093         myAlternatives[myLastUsed]->setCosts(costs);
00094         myPrecomputed = myAlternatives[myLastUsed];
00095         return;
00096     }
00097     // return the built route
00098     ROCostCalculator::getCalculator().setCosts(opt, costs, true);
00099     myPrecomputed = opt;
00100 }
00101 
00102 
00103 int
00104 RORouteDef_Alternatives::findRoute(RORoute* opt) const {
00105     for (unsigned int i = 0; i < myAlternatives.size(); i++) {
00106         if (opt->getEdgeVector() == myAlternatives[i]->getEdgeVector()) {
00107             return (int) i;
00108         }
00109     }
00110     return -1;
00111 }
00112 
00113 
00114 void
00115 RORouteDef_Alternatives::addAlternative(SUMOAbstractRouter<ROEdge, ROVehicle> &router,
00116                                         const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
00117     // add the route when it's new
00118     if (myLastUsed < 0) {
00119         myAlternatives.push_back(current);
00120         myLastUsed = (int) myAlternatives.size() - 1;
00121     }
00122     // recompute the costs and (when a new route was added) the probabilities
00123     for (AlternativesVector::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
00124         RORoute* alt = *i;
00125         // apply changes for old routes only
00126         //  (the costs for the current were computed already)
00127         if ((*i) != current || !myNewRoute) {
00128             // recompute the costs for old routes
00129             const SUMOReal newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
00130             if (newCosts < 0.) {
00131                 throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
00132             }
00133             ROCostCalculator::getCalculator().setCosts(alt, newCosts);
00134         }
00135         assert(myAlternatives.size() != 0);
00136         if (myNewRoute) {
00137             if ((*i) != current) {
00138                 alt->setProbability(
00139                     alt->getProbability()
00140                     * SUMOReal(myAlternatives.size() - 1)
00141                     / SUMOReal(myAlternatives.size()));
00142             } else {
00143                 alt->setProbability((SUMOReal)(1.0 / (SUMOReal) myAlternatives.size()));
00144             }
00145         }
00146     }
00147     assert(myAlternatives.size() != 0);
00148     ROCostCalculator::getCalculator().calculateProbabilities(veh, myAlternatives);
00149     if (!myKeepRoutes) {
00150         // remove with probability of 0 (not mentioned in Gawron)
00151         for (AlternativesVector::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
00152             if ((*i)->getProbability() == 0) {
00153                 i = myAlternatives.erase(i);
00154             } else {
00155                 i++;
00156             }
00157         }
00158     }
00159     if (myAlternatives.size() > (unsigned)myMaxRouteNumber) {
00160         // only keep the routes with highest probability
00161         sort(myAlternatives.begin(), myAlternatives.end(), ComparatorProbability());
00162         for (AlternativesVector::iterator i = myAlternatives.begin() + myMaxRouteNumber; i != myAlternatives.end(); i++) {
00163             delete *i;
00164         }
00165         myAlternatives.erase(myAlternatives.begin() + myMaxRouteNumber, myAlternatives.end());
00166         // rescale probabilities
00167         SUMOReal newSum = 0;
00168         for (AlternativesVector::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
00169             newSum += (*i)->getProbability();
00170         }
00171         assert(newSum > 0);
00172         // @note newSum may be larger than 1 for numerical reasons
00173         for (AlternativesVector::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
00174             (*i)->setProbability((*i)->getProbability() / newSum);
00175         }
00176     }
00177 
00178     // find the route to use
00179     SUMOReal chosen = RandHelper::rand();
00180     int pos = 0;
00181     for (AlternativesVector::iterator i = myAlternatives.begin(); i != myAlternatives.end() - 1; i++, pos++) {
00182         chosen = chosen - (*i)->getProbability();
00183         if (chosen <= 0) {
00184             myLastUsed = pos;
00185             return;
00186         }
00187     }
00188     myLastUsed = pos;
00189 }
00190 
00191 
00192 RORouteDef*
00193 RORouteDef_Alternatives::copy(const std::string& id) const {
00194     RORouteDef_Alternatives* ret = new RORouteDef_Alternatives(id,
00195             myLastUsed, myMaxRouteNumber, myKeepRoutes, mySkipRouteCalculation);
00196     for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
00197         ret->addLoadedAlternative(new RORoute(*(*i)));
00198     }
00199     return ret;
00200 }
00201 
00202 
00203 void
00204 RORouteDef_Alternatives::invalidateLast() {
00205     myLastUsed = -1;
00206 }
00207 
00208 
00209 void
00210 RORouteDef_Alternatives::removeLast() {
00211     assert(myAlternatives.size() >= 2);
00212     myAlternatives.erase(myAlternatives.end() - 1);
00213     myLastUsed = (int) myAlternatives.size() - 1;
00214     // !!! recompute probabilities
00215 }
00216 
00217 
00218 OutputDevice&
00219 RORouteDef_Alternatives::writeXMLDefinition(SUMOAbstractRouter<ROEdge, ROVehicle> &router,
00220         OutputDevice& dev, const ROVehicle* const veh,
00221         bool asAlternatives, bool withExitTimes) const {
00222     // (optional) alternatives header
00223     if (asAlternatives) {
00224         dev.openTag(SUMO_TAG_ROUTE_DISTRIBUTION).writeAttr(SUMO_ATTR_LAST, myLastUsed).closeOpener();
00225         for (size_t i = 0; i != myAlternatives.size(); i++) {
00226             const RORoute& alt = *(myAlternatives[i]);
00227             dev.openTag(SUMO_TAG_ROUTE).writeAttr(SUMO_ATTR_COST, alt.getCosts());
00228             dev.setPrecision(8);
00229             dev.writeAttr(SUMO_ATTR_PROB, alt.getProbability());
00230             dev.setPrecision();
00231             if (alt.getColor() != 0) {
00232                 dev.writeAttr(SUMO_ATTR_COLOR, *alt.getColor());
00233             } else if (myColor != 0) {
00234                 dev.writeAttr(SUMO_ATTR_COLOR, *myColor);
00235             }
00236             dev.writeAttr(SUMO_ATTR_EDGES, alt.getEdgeVector());
00237             if (withExitTimes) {
00238                 std::string exitTimes;
00239                 SUMOReal time = STEPS2TIME(veh->getDepartureTime());
00240                 for (std::vector<const ROEdge*>::const_iterator i = alt.getEdgeVector().begin(); i != alt.getEdgeVector().end(); ++i) {
00241                     if (i != alt.getEdgeVector().begin()) {
00242                         exitTimes += " ";
00243                     }
00244                     time += (*i)->getTravelTime(veh, time);
00245                     exitTimes += toString(time);
00246                 }
00247                 dev.writeAttr("exitTimes", exitTimes);
00248             }
00249             dev.closeTag(true);
00250         }
00251         dev.closeTag();
00252         return dev;
00253     } else {
00254         return myAlternatives[myLastUsed]->writeXMLDefinition(router, dev, veh, asAlternatives, withExitTimes);
00255     }
00256 }
00257 
00258 
00259 const ROEdge*
00260 RORouteDef_Alternatives::getDestination() const {
00261     return myAlternatives[0]->getLast();
00262 }
00263 
00264 
00265 
00266 /****************************************************************************/
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines