SUMO - Simulation of Urban MObility
|
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 /****************************************************************************/