Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-2025 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file MSRoutingEngine.cpp
15 : /// @author Michael Behrisch
16 : /// @author Daniel Krajzewicz
17 : /// @author Laura Bieker
18 : /// @author Christoph Sommer
19 : /// @author Jakob Erdmann
20 : /// @date Tue, 04 Dec 2007
21 : ///
22 : // A device that performs vehicle rerouting based on current edge speeds
23 : /****************************************************************************/
24 : #include <config.h>
25 :
26 : #include "MSRoutingEngine.h"
27 : #include <microsim/MSNet.h>
28 : #include <microsim/MSLane.h>
29 : #include <microsim/MSEdge.h>
30 : #include <microsim/MSEdgeControl.h>
31 : #include <microsim/MSEventControl.h>
32 : #include <microsim/MSGlobals.h>
33 : #include <microsim/MSVehicleControl.h>
34 : #include <microsim/MSInsertionControl.h>
35 : #include <microsim/transportables/MSTransportable.h>
36 : #include <microsim/devices/MSDevice_Taxi.h>
37 : #include <utils/options/OptionsCont.h>
38 : #include <utils/common/WrappingCommand.h>
39 : #include <utils/common/StaticCommand.h>
40 : #include <utils/common/StringUtils.h>
41 : #include <utils/xml/SUMOSAXAttributes.h>
42 : #include <utils/router/DijkstraRouter.h>
43 : #include <utils/router/AStarRouter.h>
44 : #include <utils/router/CHRouter.h>
45 : #include <utils/router/CHRouterWrapper.h>
46 : #include <utils/vehicle/SUMOVehicleParserHelper.h>
47 :
48 : //#define DEBUG_SEPARATE_TURNS
49 : #define DEBUG_COND(obj) (obj->isSelected())
50 :
51 : // ===========================================================================
52 : // static member variables
53 : // ===========================================================================
54 : std::vector<double> MSRoutingEngine::myEdgeSpeeds;
55 : std::vector<double> MSRoutingEngine::myEdgeBikeSpeeds;
56 : std::vector<MSRoutingEngine::TimeAndCount> MSRoutingEngine::myEdgeTravelTimes;
57 : std::vector<std::vector<double> > MSRoutingEngine::myPastEdgeSpeeds;
58 : std::vector<std::vector<double> > MSRoutingEngine::myPastEdgeBikeSpeeds;
59 : Command* MSRoutingEngine::myEdgeWeightSettingCommand = nullptr;
60 : double MSRoutingEngine::myAdaptationWeight;
61 : int MSRoutingEngine::myAdaptationSteps;
62 : int MSRoutingEngine::myAdaptationStepsIndex = 0;
63 : SUMOTime MSRoutingEngine::myAdaptationInterval = -1;
64 : SUMOTime MSRoutingEngine::myLastAdaptation = -1;
65 : bool MSRoutingEngine::myWithTaz;
66 : bool MSRoutingEngine::myBikeSpeeds;
67 : MSRouterProvider* MSRoutingEngine::myRouterProvider = nullptr;
68 : std::map<std::pair<const MSEdge*, const MSEdge*>, ConstMSRoutePtr> MSRoutingEngine::myCachedRoutes;
69 : double MSRoutingEngine::myPriorityFactor(0);
70 : double MSRoutingEngine::myMinEdgePriority(std::numeric_limits<double>::max());
71 : double MSRoutingEngine::myEdgePriorityRange(0);
72 : bool MSRoutingEngine::myDynamicRandomness(false);
73 :
74 : SUMOAbstractRouter<MSEdge, SUMOVehicle>::Operation MSRoutingEngine::myEffortFunc = &MSRoutingEngine::getEffort;
75 : #ifdef HAVE_FOX
76 : FXMutex MSRoutingEngine::myRouteCacheMutex;
77 : #endif
78 :
79 :
80 : // ===========================================================================
81 : // method definitions
82 : // ===========================================================================
83 : void
84 1552378 : MSRoutingEngine::initWeightUpdate() {
85 1552378 : if (myAdaptationInterval == -1) {
86 7422 : myEdgeWeightSettingCommand = nullptr;
87 : myEdgeSpeeds.clear();
88 : myEdgeTravelTimes.clear();
89 7422 : myAdaptationSteps = -1;
90 7422 : myLastAdaptation = -1;
91 7422 : const OptionsCont& oc = OptionsCont::getOptions();
92 7422 : myWithTaz = oc.getBool("device.rerouting.with-taz");
93 7422 : myAdaptationInterval = string2time(oc.getString("device.rerouting.adaptation-interval"));
94 7422 : myAdaptationWeight = oc.getFloat("device.rerouting.adaptation-weight");
95 7422 : const SUMOTime period = string2time(oc.getString("device.rerouting.period"));
96 7422 : if (myAdaptationWeight < 1. && myAdaptationInterval > 0) {
97 7354 : myEdgeWeightSettingCommand = new StaticCommand<MSRoutingEngine>(&MSRoutingEngine::adaptEdgeEfforts);
98 7354 : MSNet::getInstance()->getEndOfTimestepEvents()->addEvent(myEdgeWeightSettingCommand);
99 68 : } else if (period > 0) {
100 0 : WRITE_WARNING(TL("Rerouting is useless if the edge weights do not get updated!"));
101 : }
102 14844 : OutputDevice::createDeviceByOption("device.rerouting.output", "weights", "meandata_file.xsd");
103 : }
104 1552378 : }
105 :
106 :
107 : void
108 14019373 : MSRoutingEngine::initEdgeWeights(SUMOVehicleClass svc, SUMOTime lastAdaption, int index) {
109 14019373 : if (myBikeSpeeds && svc == SVC_BICYCLE) {
110 294 : _initEdgeWeights(myEdgeBikeSpeeds, myPastEdgeBikeSpeeds);
111 : } else {
112 14019079 : _initEdgeWeights(myEdgeSpeeds, myPastEdgeSpeeds);
113 : }
114 14019373 : if (lastAdaption >= 0) {
115 87 : myLastAdaptation = lastAdaption;
116 : }
117 14019373 : if (index >= 0) {
118 : assert(index < (int)myPastEdgeSpeeds.size());
119 87 : myAdaptationStepsIndex = index;
120 : }
121 14019373 : }
122 :
123 :
124 : void
125 14019373 : MSRoutingEngine::_initEdgeWeights(std::vector<double>& edgeSpeeds, std::vector<std::vector<double> >& pastEdgeSpeeds) {
126 14019373 : if (edgeSpeeds.empty()) {
127 7341 : const OptionsCont& oc = OptionsCont::getOptions();
128 7431 : if (myAdaptationWeight == 0 || !oc.isDefault("device.rerouting.adaptation-steps")) {
129 7251 : myAdaptationSteps = oc.getInt("device.rerouting.adaptation-steps");
130 : }
131 7341 : const bool useLoaded = oc.getBool("device.rerouting.init-with-loaded-weights");
132 7341 : const double currentSecond = SIMTIME;
133 : double maxEdgePriority = -std::numeric_limits<double>::max();
134 717991 : for (const MSEdge* const edge : MSNet::getInstance()->getEdgeControl().getEdges()) {
135 1421300 : while (edge->getNumericalID() >= (int)edgeSpeeds.size()) {
136 710650 : edgeSpeeds.push_back(0);
137 710650 : if (myAdaptationSteps > 0) {
138 709964 : pastEdgeSpeeds.push_back(std::vector<double>());
139 : }
140 711825 : if (MSGlobals::gWeightsSeparateTurns && edgeSpeeds == myEdgeSpeeds) {
141 1175 : myEdgeTravelTimes.push_back(TimeAndCount(0, 0));
142 : }
143 : }
144 710650 : if (useLoaded) {
145 114 : edgeSpeeds[edge->getNumericalID()] = edge->getLength() / MSNet::getTravelTime(edge, nullptr, currentSecond);
146 : } else {
147 710536 : edgeSpeeds[edge->getNumericalID()] = edge->getMeanSpeed();
148 : }
149 710650 : if (myAdaptationSteps > 0) {
150 709964 : pastEdgeSpeeds[edge->getNumericalID()] = std::vector<double>(myAdaptationSteps, edgeSpeeds[edge->getNumericalID()]);
151 : }
152 710650 : maxEdgePriority = MAX2(maxEdgePriority, (double)edge->getPriority());
153 1393311 : myMinEdgePriority = MIN2(myMinEdgePriority, (double)edge->getPriority());
154 : }
155 7341 : myEdgePriorityRange = maxEdgePriority - myMinEdgePriority;
156 7341 : myLastAdaptation = MSNet::getInstance()->getCurrentTimeStep();
157 7341 : myPriorityFactor = oc.getFloat("weights.priority-factor");
158 7341 : myDynamicRandomness = oc.getBool("weights.random-factor.dynamic");
159 7341 : if (myPriorityFactor < 0) {
160 0 : throw ProcessError(TL("weights.priority-factor cannot be negative."));
161 : }
162 7341 : if (myPriorityFactor > 0) {
163 7 : if (myEdgePriorityRange == 0) {
164 0 : WRITE_WARNING(TL("Option weights.priority-factor does not take effect because all edges have the same priority"));
165 0 : myPriorityFactor = 0;
166 : }
167 : }
168 : }
169 14019373 : }
170 :
171 :
172 : double
173 181769439 : MSRoutingEngine::getEffort(const MSEdge* const e, const SUMOVehicle* const v, double) {
174 : const int id = e->getNumericalID();
175 181769439 : if (id < (int)myEdgeSpeeds.size()) {
176 170512364 : return MAX2(e->getLength() / MAX2(myEdgeSpeeds[id], NUMERICAL_EPS), e->getMinimumTravelTime(v));
177 : }
178 11478316 : return e->getMinimumTravelTime(v);
179 : }
180 :
181 :
182 : double
183 3088 : MSRoutingEngine::getEffortBike(const MSEdge* const e, const SUMOVehicle* const v, double) {
184 : const int id = e->getNumericalID();
185 3088 : if (id < (int)myEdgeBikeSpeeds.size()) {
186 3088 : return MAX2(e->getLength() / MAX2(myEdgeBikeSpeeds[id], NUMERICAL_EPS), e->getMinimumTravelTime(v));
187 : }
188 0 : return e->getMinimumTravelTime(v);
189 : }
190 :
191 :
192 : double
193 69631 : MSRoutingEngine::getEffortExtra(const MSEdge* const e, const SUMOVehicle* const v, double t) {
194 5054 : double effort = (!myBikeSpeeds || v == nullptr || v->getVClass() != SVC_BICYCLE
195 73165 : ? getEffort(e, v, t)
196 1520 : : getEffortBike(e, v, t));
197 69631 : if (gWeightsRandomFactor != 1.) {
198 58122 : long long int key = v->getRandomSeed() ^ e->getNumericalID();
199 58122 : if (myDynamicRandomness) {
200 12560 : key ^= SIMSTEP;
201 : }
202 58122 : effort *= (1 + RandHelper::randHash(key) * (gWeightsRandomFactor - 1));
203 : }
204 69631 : if (myPriorityFactor != 0) {
205 : // lower priority should result in higher effort (and the edge with
206 : // minimum priority receives a factor of 1 + myPriorityFactor
207 1960 : const double relativeInversePrio = 1 - ((e->getPriority() - myMinEdgePriority) / myEdgePriorityRange);
208 1960 : effort *= 1 + relativeInversePrio * myPriorityFactor;
209 : }
210 69631 : if (gRoutingPreferences) {
211 3360 : effort /= MSNet::getInstance()->getPreference(e->getRoutingType(), v->getVTypeParameter());
212 : }
213 69631 : return effort;
214 : }
215 :
216 :
217 : double
218 4240 : MSRoutingEngine::getAssumedSpeed(const MSEdge* edge, const SUMOVehicle* veh) {
219 4240 : return edge->getLength() / myEffortFunc(edge, veh, 0);
220 : }
221 :
222 :
223 : SUMOTime
224 11690561 : MSRoutingEngine::adaptEdgeEfforts(SUMOTime currentTime) {
225 11690561 : initEdgeWeights(SVC_PASSENGER);
226 11690561 : if (myBikeSpeeds) {
227 224 : initEdgeWeights(SVC_BICYCLE);
228 : }
229 11690561 : if (MSNet::getInstance()->getVehicleControl().getDepartedVehicleNo() == 0) {
230 37473 : return myAdaptationInterval;
231 : }
232 : myCachedRoutes.clear();
233 11653088 : const MSEdgeVector& edges = MSNet::getInstance()->getEdgeControl().getEdges();
234 11653088 : const double newWeightFactor = (double)(1. - myAdaptationWeight);
235 647040479 : for (const MSEdge* const e : edges) {
236 8759612 : if (e->isDelayed()) {
237 : const int id = e->getNumericalID();
238 146272384 : double currSpeed = e->getMeanSpeed();
239 146272384 : if (MSGlobals::gWeightsSeparateTurns > 0 && e->getNumSuccessors() > 1) {
240 129055 : currSpeed = patchSpeedForTurns(e, currSpeed);
241 : }
242 : #ifdef DEBUG_SEPARATE_TURNS
243 : if (DEBUG_COND(e->getLanes()[0])) {
244 : std::cout << SIMTIME << " edge=" << e->getID()
245 : << " meanSpeed=" << e->getMeanSpeed()
246 : << " currSpeed=" << currSpeed
247 : << " oldestSpeed=" << myPastEdgeSpeeds[id][myAdaptationStepsIndex]
248 : << " oldAvg=" << myEdgeSpeeds[id]
249 : << "\n";
250 : }
251 : #endif
252 146272384 : if (myAdaptationSteps > 0) {
253 : // moving average
254 146209136 : myEdgeSpeeds[id] += (currSpeed - myPastEdgeSpeeds[id][myAdaptationStepsIndex]) / myAdaptationSteps;
255 146209136 : myPastEdgeSpeeds[id][myAdaptationStepsIndex] = currSpeed;
256 146209136 : if (myBikeSpeeds) {
257 0 : const double currBikeSpeed = e->getMeanSpeedBike();
258 0 : myEdgeBikeSpeeds[id] += (currBikeSpeed - myPastEdgeBikeSpeeds[id][myAdaptationStepsIndex]) / myAdaptationSteps;
259 0 : myPastEdgeBikeSpeeds[id][myAdaptationStepsIndex] = currBikeSpeed;
260 : }
261 : } else {
262 : // exponential moving average
263 63248 : if (currSpeed != myEdgeSpeeds[id]) {
264 25418 : myEdgeSpeeds[id] = myEdgeSpeeds[id] * myAdaptationWeight + currSpeed * newWeightFactor;
265 : }
266 63248 : if (myBikeSpeeds) {
267 1272 : const double currBikeSpeed = e->getMeanSpeedBike();
268 1272 : if (currBikeSpeed != myEdgeBikeSpeeds[id]) {
269 812 : myEdgeBikeSpeeds[id] = myEdgeBikeSpeeds[id] * myAdaptationWeight + currBikeSpeed * newWeightFactor;
270 : }
271 : }
272 : }
273 : }
274 : }
275 11653088 : if (myAdaptationSteps > 0) {
276 11633542 : myAdaptationStepsIndex = (myAdaptationStepsIndex + 1) % myAdaptationSteps;
277 : }
278 11653088 : myLastAdaptation = currentTime + DELTA_T; // because we run at the end of the time step
279 23306176 : if (OptionsCont::getOptions().isSet("device.rerouting.output")) {
280 11839 : OutputDevice& dev = OutputDevice::getDeviceByOption("device.rerouting.output");
281 11839 : dev.openTag(SUMO_TAG_INTERVAL);
282 11839 : dev.writeAttr(SUMO_ATTR_ID, "device.rerouting");
283 11839 : dev.writeAttr(SUMO_ATTR_BEGIN, STEPS2TIME(currentTime));
284 11839 : dev.writeAttr(SUMO_ATTR_END, STEPS2TIME(currentTime + myAdaptationInterval));
285 142395 : for (const MSEdge* e : edges) {
286 130556 : dev.openTag(SUMO_TAG_EDGE);
287 130556 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
288 130556 : dev.writeAttr("traveltime", myEffortFunc(e, nullptr, STEPS2TIME(currentTime)));
289 130556 : if (myBikeSpeeds) {
290 : // @note edge-priority is not included here
291 3136 : dev.writeAttr("traveltimeBike", getEffortBike(e, nullptr, STEPS2TIME(currentTime)));
292 : }
293 261112 : dev.closeTag();
294 : }
295 23678 : dev.closeTag();
296 : }
297 11653088 : return myAdaptationInterval;
298 : }
299 :
300 :
301 : double
302 129055 : MSRoutingEngine::patchSpeedForTurns(const MSEdge* edge, double currSpeed) {
303 : const double length = edge->getLength();
304 : double maxSpeed = 0;
305 556115 : for (const auto& pair : edge->getViaSuccessors()) {
306 427060 : if (pair.second == nullptr) {
307 40125 : continue;
308 : }
309 386935 : TimeAndCount& tc = myEdgeTravelTimes[pair.second->getNumericalID()];
310 386935 : if (tc.second > 0) {
311 52850 : const double avgSpeed = length / STEPS2TIME(tc.first / tc.second);
312 : maxSpeed = MAX2(avgSpeed, maxSpeed);
313 : }
314 : }
315 129055 : if (maxSpeed > 0) {
316 : // perform correction
317 31095 : const double correctedSpeed = MSGlobals::gWeightsSeparateTurns * maxSpeed + (1 - MSGlobals::gWeightsSeparateTurns) * currSpeed;
318 138070 : for (const auto& pair : edge->getViaSuccessors()) {
319 106975 : if (pair.second == nullptr) {
320 10065 : continue;
321 : }
322 : const int iid = pair.second->getNumericalID();
323 96910 : TimeAndCount& tc = myEdgeTravelTimes[iid];
324 96910 : if (tc.second > 0) {
325 52850 : const double avgSpeed = length / STEPS2TIME(tc.first / tc.second);
326 52850 : if (avgSpeed < correctedSpeed) {
327 21530 : double internalTT = pair.second->getLength() / pair.second->getSpeedLimit();
328 21530 : internalTT += (length / avgSpeed - length / correctedSpeed) * MSGlobals::gWeightsSeparateTurns;
329 21530 : const double origInternalSpeed = myEdgeSpeeds[iid];
330 21530 : const double newInternalSpeed = pair.second->getLength() / internalTT;
331 21530 : const double origCurrSpeed = myPastEdgeSpeeds[iid][myAdaptationStepsIndex];
332 :
333 21530 : myEdgeSpeeds[iid] = newInternalSpeed;
334 : // to ensure myEdgeSpeed reverts to the speed limit
335 : // when there are no updates, we also have to patch
336 : // myPastEdgeSpeeds with a virtual value that is consistent
337 : // with the updated speed
338 : // note: internal edges were handled before the normal ones
339 21530 : const double virtualSpeed = (newInternalSpeed - (origInternalSpeed - origCurrSpeed / myAdaptationSteps)) * myAdaptationSteps;
340 21530 : myPastEdgeSpeeds[iid][myAdaptationStepsIndex] = virtualSpeed;
341 :
342 : #ifdef DEBUG_SEPARATE_TURNS
343 : if (DEBUG_COND(pair.second->getLanes()[0])) {
344 : std::cout << SIMTIME << " edge=" << edge->getID() << " to=" << pair.first->getID() << " via=" << pair.second->getID()
345 : << " origSpeed=" << currSpeed
346 : << " maxSpeed=" << maxSpeed
347 : << " correctedSpeed=" << correctedSpeed
348 : << " avgSpeed=" << avgSpeed
349 : << " internalTT=" << internalTT
350 : << " internalSpeed=" << origInternalSpeed
351 : << " newInternalSpeed=" << newInternalSpeed
352 : << " virtualSpeed=" << virtualSpeed
353 : << "\n";
354 : }
355 : #endif
356 : }
357 52850 : if (myAdaptationStepsIndex == 0) {
358 550 : tc.first = 0;
359 550 : tc.second = 0;
360 : }
361 : }
362 : }
363 : return correctedSpeed;
364 : }
365 : return currSpeed;
366 : }
367 :
368 :
369 : ConstMSRoutePtr
370 567361 : MSRoutingEngine::getCachedRoute(const std::pair<const MSEdge*, const MSEdge*>& key) {
371 : auto routeIt = myCachedRoutes.find(key);
372 567361 : if (routeIt != myCachedRoutes.end()) {
373 : return routeIt->second;
374 : }
375 : return nullptr;
376 : }
377 :
378 :
379 : void
380 7231 : MSRoutingEngine::initRouter(SUMOVehicle* vehicle) {
381 7231 : OptionsCont& oc = OptionsCont::getOptions();
382 7231 : const std::string routingAlgorithm = oc.getString("routing-algorithm");
383 7231 : const bool hasPermissions = MSNet::getInstance()->hasPermissions();
384 7231 : myBikeSpeeds = oc.getBool("device.rerouting.bike-speeds");
385 7231 : myEffortFunc = ((gWeightsRandomFactor != 1 || myPriorityFactor != 0 || myBikeSpeeds || gRoutingPreferences) ? &MSRoutingEngine::getEffortExtra : &MSRoutingEngine::getEffort);
386 :
387 : SUMOAbstractRouter<MSEdge, SUMOVehicle>* router = nullptr;
388 7231 : if (routingAlgorithm == "dijkstra") {
389 6945 : router = new DijkstraRouter<MSEdge, SUMOVehicle>(MSEdge::getAllEdges(), true, myEffortFunc, nullptr, false, nullptr, true);
390 286 : } else if (routingAlgorithm == "astar") {
391 : typedef AStarRouter<MSEdge, SUMOVehicle, MSMapMatcher> AStar;
392 : std::shared_ptr<const AStar::LookupTable> lookup = nullptr;
393 536 : if (oc.isSet("astar.all-distances")) {
394 0 : lookup = std::make_shared<const AStar::FLT>(oc.getString("astar.all-distances"), (int)MSEdge::getAllEdges().size());
395 536 : } else if (oc.isSet("astar.landmark-distances") && vehicle != nullptr) {
396 35 : const double speedFactor = vehicle->getChosenSpeedFactor();
397 : // we need an exemplary vehicle with speedFactor 1
398 35 : vehicle->setChosenSpeedFactor(1);
399 : CHRouterWrapper<MSEdge, SUMOVehicle> chrouter(
400 35 : MSEdge::getAllEdges(), true, &MSNet::getTravelTime,
401 105 : string2time(oc.getString("begin")), string2time(oc.getString("end")), SUMOTime_MAX, hasPermissions, 1);
402 35 : lookup = std::make_shared<const AStar::LMLT>(oc.getString("astar.landmark-distances"), MSEdge::getAllEdges(), &chrouter,
403 70 : nullptr, vehicle, "", oc.getInt("device.rerouting.threads"), MSNet::getInstance()->getMapMatcher());
404 35 : vehicle->setChosenSpeedFactor(speedFactor);
405 35 : }
406 804 : router = new AStar(MSEdge::getAllEdges(), true, myEffortFunc, lookup, true);
407 18 : } else if (routingAlgorithm == "CH" && !hasPermissions) {
408 6 : const SUMOTime weightPeriod = myAdaptationInterval > 0 ? myAdaptationInterval : SUMOTime_MAX;
409 : router = new CHRouter<MSEdge, SUMOVehicle>(
410 6 : MSEdge::getAllEdges(), true, myEffortFunc, vehicle == nullptr ? SVC_PASSENGER : vehicle->getVClass(), weightPeriod, true, false);
411 12 : } else if (routingAlgorithm == "CHWrapper" || routingAlgorithm == "CH") {
412 : // use CHWrapper instead of CH if the net has permissions
413 12 : const SUMOTime weightPeriod = myAdaptationInterval > 0 ? myAdaptationInterval : SUMOTime_MAX;
414 : router = new CHRouterWrapper<MSEdge, SUMOVehicle>(
415 12 : MSEdge::getAllEdges(), true, myEffortFunc,
416 36 : string2time(oc.getString("begin")), string2time(oc.getString("end")), weightPeriod, hasPermissions, oc.getInt("device.rerouting.threads"));
417 : } else {
418 0 : throw ProcessError(TLF("Unknown routing algorithm '%'!", routingAlgorithm));
419 : }
420 :
421 : RailwayRouter<MSEdge, SUMOVehicle>* railRouter = nullptr;
422 7231 : if (MSNet::getInstance()->hasBidiEdges()) {
423 543 : railRouter = new RailwayRouter<MSEdge, SUMOVehicle>(MSEdge::getAllEdges(), true, myEffortFunc, nullptr, false, true, false,
424 : oc.getFloat("railway.max-train-length"),
425 1086 : oc.getFloat("weights.reversal-penalty"));
426 : }
427 8013 : const int carWalk = SUMOVehicleParserHelper::parseCarWalkTransfer(oc, MSDevice_Taxi::hasFleet() || MSNet::getInstance()->getInsertionControl().hasTaxiFlow());
428 7231 : const double taxiWait = STEPS2TIME(string2time(OptionsCont::getOptions().getString("persontrip.taxi.waiting-time")));
429 7231 : MSTransportableRouter* transRouter = new MSTransportableRouter(MSNet::adaptIntermodalRouter, carWalk, taxiWait, routingAlgorithm, 0);
430 7231 : myRouterProvider = new MSRouterProvider(router, nullptr, transRouter, railRouter);
431 : #ifndef THREAD_POOL
432 : #ifdef HAVE_FOX
433 7231 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
434 7231 : if (threadPool.size() > 0) {
435 : const std::vector<MFXWorkerThread*>& threads = threadPool.getWorkers();
436 894 : if (static_cast<MSEdgeControl::WorkerThread*>(threads.front())->setRouterProvider(myRouterProvider)) {
437 3508 : for (std::vector<MFXWorkerThread*>::const_iterator t = threads.begin() + 1; t != threads.end(); ++t) {
438 2614 : static_cast<MSEdgeControl::WorkerThread*>(*t)->setRouterProvider(myRouterProvider->clone());
439 : }
440 : }
441 : }
442 : #endif
443 : #endif
444 7231 : }
445 :
446 :
447 : void
448 2326608 : MSRoutingEngine::reroute(SUMOVehicle& vehicle, const SUMOTime currentTime, const std::string& info,
449 : const bool onInit, const bool silent, const Prohibitions& prohibited) {
450 2326608 : if (myRouterProvider == nullptr) {
451 7067 : initRouter(&vehicle);
452 : }
453 2326608 : auto& router = myRouterProvider->getVehicleRouter(vehicle.getVClass());
454 : #ifndef THREAD_POOL
455 : #ifdef HAVE_FOX
456 2326608 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
457 2326608 : if (threadPool.size() > 0) {
458 188385 : threadPool.add(new RoutingTask(vehicle, currentTime, info, onInit, silent, prohibited));
459 188385 : return;
460 : }
461 : #endif
462 : #endif
463 2138223 : if (!prohibited.empty()) {
464 4 : router.prohibit(prohibited);
465 : }
466 : try {
467 2138223 : vehicle.reroute(currentTime, info, router, onInit, myWithTaz, silent);
468 115 : } catch (ProcessError&) {
469 115 : if (!silent) {
470 115 : if (!prohibited.empty()) {
471 0 : router.prohibit(Prohibitions());
472 : }
473 115 : throw;
474 : }
475 115 : }
476 2138108 : if (!prohibited.empty()) {
477 8 : router.prohibit(Prohibitions());
478 : }
479 : }
480 :
481 :
482 : void
483 118 : MSRoutingEngine::reroute(MSTransportable& t, const SUMOTime currentTime, const std::string& info,
484 : const bool onInit, const bool silent, const Prohibitions& prohibited) {
485 118 : MSTransportableRouter& router = getIntermodalRouterTT(t.getRNGIndex(), prohibited);
486 : #ifndef THREAD_POOL
487 : #ifdef HAVE_FOX
488 118 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
489 118 : if (threadPool.size() > 0) {
490 : // threadPool.add(new RoutingTask(t, currentTime, info, onInit, silent, prohibited));
491 : return;
492 : }
493 : #endif
494 : #endif
495 100 : if (!prohibited.empty()) {
496 0 : router.prohibit(prohibited);
497 : }
498 : try {
499 100 : t.reroute(currentTime, info, router, onInit, myWithTaz, silent);
500 0 : } catch (ProcessError&) {
501 0 : if (!silent) {
502 0 : if (!prohibited.empty()) {
503 0 : router.prohibit(Prohibitions());
504 : }
505 0 : throw;
506 : }
507 0 : }
508 100 : if (!prohibited.empty()) {
509 0 : router.prohibit(Prohibitions());
510 : }
511 : }
512 :
513 :
514 : void
515 9 : MSRoutingEngine::setEdgeTravelTime(const MSEdge* const edge, const double travelTime) {
516 9 : myEdgeSpeeds[edge->getNumericalID()] = edge->getLength() / travelTime;
517 9 : }
518 :
519 : void
520 11090 : MSRoutingEngine::addEdgeTravelTime(const MSEdge& edge, const SUMOTime travelTime) {
521 11090 : TimeAndCount& tc = myEdgeTravelTimes[edge.getNumericalID()];
522 11090 : tc.first += travelTime;
523 11090 : tc.second += 1;
524 11090 : }
525 :
526 :
527 : MSVehicleRouter&
528 771505 : MSRoutingEngine::getRouterTT(const int rngIndex, SUMOVehicleClass svc, const Prohibitions& prohibited) {
529 771505 : if (myRouterProvider == nullptr) {
530 164 : initWeightUpdate();
531 164 : initEdgeWeights(svc);
532 164 : initRouter();
533 : }
534 : #ifndef THREAD_POOL
535 : #ifdef HAVE_FOX
536 771505 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
537 771505 : if (threadPool.size() > 0) {
538 32437 : auto& router = static_cast<MSEdgeControl::WorkerThread*>(threadPool.getWorkers()[rngIndex % MSGlobals::gNumThreads])->getRouter(svc);
539 32437 : router.prohibit(prohibited);
540 32437 : return router;
541 : }
542 : #else
543 : UNUSED_PARAMETER(rngIndex);
544 : #endif
545 : #endif
546 1478136 : myRouterProvider->getVehicleRouter(svc).prohibit(prohibited);
547 739068 : return myRouterProvider->getVehicleRouter(svc);
548 : }
549 :
550 :
551 : MSTransportableRouter&
552 118 : MSRoutingEngine::getIntermodalRouterTT(const int rngIndex, const Prohibitions& prohibited) {
553 118 : if (myRouterProvider == nullptr) {
554 0 : initWeightUpdate();
555 0 : initEdgeWeights(SVC_PEDESTRIAN);
556 0 : initRouter();
557 : }
558 : #ifndef THREAD_POOL
559 : #ifdef HAVE_FOX
560 118 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
561 118 : if (threadPool.size() > 0) {
562 18 : auto& router = static_cast<MSEdgeControl::WorkerThread*>(threadPool.getWorkers()[rngIndex % MSGlobals::gNumThreads])->getIntermodalRouter();
563 18 : router.prohibit(prohibited);
564 18 : return router;
565 : }
566 : #else
567 : UNUSED_PARAMETER(rngIndex);
568 : #endif
569 : #endif
570 100 : myRouterProvider->getIntermodalRouter().prohibit(prohibited);
571 100 : return myRouterProvider->getIntermodalRouter();
572 : }
573 :
574 :
575 : void
576 40047 : MSRoutingEngine::cleanup() {
577 40047 : myAdaptationInterval = -1; // responsible for triggering initEdgeWeights
578 : myPastEdgeSpeeds.clear();
579 : myEdgeSpeeds.clear();
580 : myEdgeTravelTimes.clear();
581 : myPastEdgeBikeSpeeds.clear();
582 : myEdgeBikeSpeeds.clear();
583 : // @todo recheck. calling release crashes in parallel routing
584 : //for (auto& item : myCachedRoutes) {
585 : // item.second->release();
586 : //}
587 : myCachedRoutes.clear();
588 40047 : myAdaptationStepsIndex = 0;
589 : #ifdef HAVE_FOX
590 40047 : if (MSGlobals::gNumThreads > 1) {
591 : // router deletion is done in thread destructor
592 4343 : myRouterProvider = nullptr;
593 4343 : return;
594 : }
595 : #endif
596 35704 : delete myRouterProvider;
597 35704 : myRouterProvider = nullptr;
598 : }
599 :
600 :
601 : void
602 476 : MSRoutingEngine::saveState(OutputDevice& out) {
603 476 : if (myEdgeSpeeds.size() == 0) {
604 : return;
605 : }
606 99 : out.openTag(SUMO_TAG_ROUTINGENGINE);
607 99 : out.writeAttr(SUMO_ATTR_LAST, myLastAdaptation);
608 99 : out.writeAttr(SUMO_ATTR_INDEX, myAdaptationStepsIndex);
609 99 : const MSEdgeVector& edges = MSNet::getInstance()->getEdgeControl().getEdges();
610 5457 : for (const MSEdge* const e : edges) {
611 0 : if (e->isDelayed()) {
612 : const int id = e->getNumericalID();
613 991 : out.openTag(SUMO_TAG_EDGE);
614 991 : out.writeAttr(SUMO_ATTR_ID, e->getID());
615 991 : out.writeAttr(SUMO_ATTR_SPEED, myEdgeSpeeds[id]);
616 991 : if (myAdaptationSteps > 0) {
617 991 : out.writeAttr(SUMO_ATTR_PASTSPEED, myPastEdgeSpeeds[id]);
618 : }
619 991 : if (myBikeSpeeds) {
620 0 : out.writeAttr(SUMO_ATTR_BIKESPEED, myEdgeBikeSpeeds[id]);
621 0 : if (myAdaptationSteps > 0) {
622 0 : out.writeAttr(SUMO_ATTR_PASTBIKESPEED, myPastEdgeBikeSpeeds[id]);
623 : }
624 : }
625 1982 : out.closeTag();
626 : }
627 : }
628 198 : out.closeTag();
629 : }
630 :
631 :
632 : void
633 925 : MSRoutingEngine::loadState(const SUMOSAXAttributes& attrs) {
634 1850 : const MSEdge* const e = MSEdge::dictionary(attrs.getString(SUMO_ATTR_ID));
635 : e->markDelayed();
636 : const int id = e->getNumericalID();
637 : bool checkedSteps = false;
638 : bool checkedBikeSpeeds = false;
639 925 : bool ok = true;
640 925 : if ((int)myEdgeSpeeds.size() > id) {
641 925 : myEdgeSpeeds[id] = attrs.get<double>(SUMO_ATTR_SPEED, nullptr, ok);
642 925 : if (myBikeSpeeds) {
643 0 : if (attrs.hasAttribute(SUMO_ATTR_BIKESPEED)) {
644 0 : myEdgeBikeSpeeds[id] = attrs.get<double>(SUMO_ATTR_BIKESPEED, nullptr, ok);
645 : } else if (!checkedBikeSpeeds) {
646 : checkedBikeSpeeds = true;
647 0 : WRITE_WARNING("Bike speeds missing in loaded state");
648 : }
649 : }
650 925 : if (myAdaptationSteps > 0) {
651 925 : const std::vector<double> speeds = attrs.getOpt<std::vector<double> >(SUMO_ATTR_PASTSPEED, nullptr, ok);
652 925 : if ((int)speeds.size() == myAdaptationSteps) {
653 925 : myPastEdgeSpeeds[id] = speeds;
654 925 : if (myBikeSpeeds && attrs.hasAttribute(SUMO_ATTR_PASTBIKESPEED)) {
655 0 : myPastEdgeBikeSpeeds[id] = attrs.getOpt<std::vector<double> >(SUMO_ATTR_PASTBIKESPEED, nullptr, ok);
656 : }
657 : } else if (!checkedSteps) {
658 : checkedSteps = true;
659 0 : WRITE_WARNING("Number of adaptation speeds in loaded state doesn't match option --device.rerouting.adaptation-steps");
660 : }
661 925 : }
662 : }
663 925 : }
664 :
665 :
666 : #ifdef HAVE_FOX
667 : void
668 103587229 : MSRoutingEngine::waitForAll() {
669 : #ifndef THREAD_POOL
670 103587229 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
671 103587229 : if (threadPool.size() > 0) {
672 16249536 : threadPool.waitAll();
673 : }
674 : #endif
675 103587204 : }
676 :
677 :
678 : // ---------------------------------------------------------------------------
679 : // MSRoutingEngine::RoutingTask-methods
680 : // ---------------------------------------------------------------------------
681 : void
682 188385 : MSRoutingEngine::RoutingTask::run(MFXWorkerThread* context) {
683 188385 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router = static_cast<MSEdgeControl::WorkerThread*>(context)->getRouter(myVehicle.getVClass());
684 188385 : if (!myProhibited.empty()) {
685 2 : router.prohibit(myProhibited);
686 : }
687 : try {
688 188385 : myVehicle.reroute(myTime, myInfo, router, myOnInit, myWithTaz, mySilent);
689 25 : } catch (ProcessError&) {
690 25 : if (!mySilent) {
691 25 : if (!myProhibited.empty()) {
692 0 : router.prohibit(Prohibitions());
693 : }
694 25 : throw;
695 : }
696 25 : }
697 188360 : if (!myProhibited.empty()) {
698 4 : router.prohibit(Prohibitions());
699 : }
700 188360 : const MSEdge* source = *myVehicle.getRoute().begin();
701 188360 : const MSEdge* dest = myVehicle.getRoute().getLastEdge();
702 188360 : if (source->isTazConnector() && dest->isTazConnector()) {
703 4 : const std::pair<const MSEdge*, const MSEdge*> key = std::make_pair(source, dest);
704 : FXMutexLock lock(myRouteCacheMutex);
705 4 : if (MSRoutingEngine::myCachedRoutes.find(key) == MSRoutingEngine::myCachedRoutes.end()) {
706 6 : MSRoutingEngine::myCachedRoutes[key] = myVehicle.getRoutePtr();
707 : }
708 : }
709 188360 : }
710 :
711 :
712 : #endif
713 :
714 :
715 : /****************************************************************************/
|
