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 1576029 : MSRoutingEngine::initWeightUpdate() {
85 1576029 : if (myAdaptationInterval == -1) {
86 7499 : myEdgeWeightSettingCommand = nullptr;
87 : myEdgeSpeeds.clear();
88 : myEdgeTravelTimes.clear();
89 7499 : myAdaptationSteps = -1;
90 7499 : myLastAdaptation = -1;
91 7499 : const OptionsCont& oc = OptionsCont::getOptions();
92 7499 : myWithTaz = oc.getBool("device.rerouting.with-taz");
93 7499 : myAdaptationInterval = string2time(oc.getString("device.rerouting.adaptation-interval"));
94 7499 : myAdaptationWeight = oc.getFloat("device.rerouting.adaptation-weight");
95 7499 : const SUMOTime period = string2time(oc.getString("device.rerouting.period"));
96 7499 : if (myAdaptationWeight < 1. && myAdaptationInterval > 0) {
97 7431 : myEdgeWeightSettingCommand = new StaticCommand<MSRoutingEngine>(&MSRoutingEngine::adaptEdgeEfforts);
98 7431 : 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 14998 : OutputDevice::createDeviceByOption("device.rerouting.output", "weights", "meandata_file.xsd");
103 : }
104 1576029 : }
105 :
106 :
107 : void
108 17196924 : MSRoutingEngine::initEdgeWeights(SUMOVehicleClass svc, SUMOTime lastAdaption, int index) {
109 17196924 : if (myBikeSpeeds && svc == SVC_BICYCLE) {
110 294 : _initEdgeWeights(myEdgeBikeSpeeds, myPastEdgeBikeSpeeds);
111 : } else {
112 17196630 : _initEdgeWeights(myEdgeSpeeds, myPastEdgeSpeeds);
113 : }
114 17196924 : if (lastAdaption >= 0) {
115 81 : myLastAdaptation = lastAdaption;
116 : }
117 17196924 : if (index >= 0) {
118 : assert(index < (int)myPastEdgeSpeeds.size());
119 81 : myAdaptationStepsIndex = index;
120 : }
121 17196924 : }
122 :
123 :
124 : void
125 17196924 : MSRoutingEngine::_initEdgeWeights(std::vector<double>& edgeSpeeds, std::vector<std::vector<double> >& pastEdgeSpeeds) {
126 17196924 : if (edgeSpeeds.empty()) {
127 7423 : const OptionsCont& oc = OptionsCont::getOptions();
128 7513 : if (myAdaptationWeight == 0 || !oc.isDefault("device.rerouting.adaptation-steps")) {
129 7333 : myAdaptationSteps = oc.getInt("device.rerouting.adaptation-steps");
130 : }
131 7423 : const bool useLoaded = oc.getBool("device.rerouting.init-with-loaded-weights");
132 7423 : const double currentSecond = SIMTIME;
133 : double maxEdgePriority = -std::numeric_limits<double>::max();
134 722825 : for (const MSEdge* const edge : MSNet::getInstance()->getEdgeControl().getEdges()) {
135 1430804 : while (edge->getNumericalID() >= (int)edgeSpeeds.size()) {
136 715402 : edgeSpeeds.push_back(0);
137 715402 : if (myAdaptationSteps > 0) {
138 714716 : pastEdgeSpeeds.push_back(std::vector<double>());
139 : }
140 716577 : if (MSGlobals::gWeightsSeparateTurns && edgeSpeeds == myEdgeSpeeds) {
141 1175 : myEdgeTravelTimes.push_back(TimeAndCount(0, 0));
142 : }
143 : }
144 715402 : if (useLoaded) {
145 114 : edgeSpeeds[edge->getNumericalID()] = edge->getLength() / MSNet::getTravelTime(edge, nullptr, currentSecond);
146 : } else {
147 715288 : edgeSpeeds[edge->getNumericalID()] = edge->getMeanSpeed();
148 : }
149 715402 : if (myAdaptationSteps > 0) {
150 714716 : pastEdgeSpeeds[edge->getNumericalID()] = std::vector<double>(myAdaptationSteps, edgeSpeeds[edge->getNumericalID()]);
151 : }
152 715402 : maxEdgePriority = MAX2(maxEdgePriority, (double)edge->getPriority());
153 1402809 : myMinEdgePriority = MIN2(myMinEdgePriority, (double)edge->getPriority());
154 : }
155 7423 : myEdgePriorityRange = maxEdgePriority - myMinEdgePriority;
156 7423 : myLastAdaptation = MSNet::getInstance()->getCurrentTimeStep();
157 7423 : myPriorityFactor = oc.getFloat("weights.priority-factor");
158 7423 : myDynamicRandomness = oc.getBool("weights.random-factor.dynamic");
159 7423 : if (myPriorityFactor < 0) {
160 0 : throw ProcessError(TL("weights.priority-factor cannot be negative."));
161 : }
162 7423 : 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 17196924 : }
170 :
171 :
172 : double
173 175563761 : MSRoutingEngine::getEffort(const MSEdge* const e, const SUMOVehicle* const v, double) {
174 : const int id = e->getNumericalID();
175 175563761 : if (id < (int)myEdgeSpeeds.size()) {
176 162409534 : return MAX2(e->getLength() / MAX2(myEdgeSpeeds[id], NUMERICAL_EPS), e->getMinimumTravelTime(v));
177 : }
178 13376147 : 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 69744 : MSRoutingEngine::getEffortExtra(const MSEdge* const e, const SUMOVehicle* const v, double t) {
194 5054 : double effort = (!myBikeSpeeds || v == nullptr || v->getVClass() != SVC_BICYCLE
195 73278 : ? getEffort(e, v, t)
196 1520 : : getEffortBike(e, v, t));
197 69744 : 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 69744 : 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 69744 : if (gRoutingPreferences) {
211 3360 : effort /= MSNet::getInstance()->getPreference(e->getRoutingType(), v->getVTypeParameter());
212 : }
213 69744 : 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 14869008 : MSRoutingEngine::adaptEdgeEfforts(SUMOTime currentTime) {
225 14869008 : initEdgeWeights(SVC_PASSENGER);
226 14869008 : if (myBikeSpeeds) {
227 224 : initEdgeWeights(SVC_BICYCLE);
228 : }
229 14869008 : if (MSNet::getInstance()->getVehicleControl().getDepartedVehicleNo() == 0) {
230 95117 : return myAdaptationInterval;
231 : }
232 : myCachedRoutes.clear();
233 14773891 : const MSEdgeVector& edges = MSNet::getInstance()->getEdgeControl().getEdges();
234 14773891 : const double newWeightFactor = (double)(1. - myAdaptationWeight);
235 761583056 : for (const MSEdge* const e : edges) {
236 8744475 : if (e->isDelayed()) {
237 : const int id = e->getNumericalID();
238 173301386 : double currSpeed = e->getMeanSpeed();
239 173301386 : 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 173301386 : if (myAdaptationSteps > 0) {
253 : // moving average
254 173238138 : myEdgeSpeeds[id] += (currSpeed - myPastEdgeSpeeds[id][myAdaptationStepsIndex]) / myAdaptationSteps;
255 173238138 : myPastEdgeSpeeds[id][myAdaptationStepsIndex] = currSpeed;
256 173238138 : 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 14773891 : if (myAdaptationSteps > 0) {
276 14754345 : myAdaptationStepsIndex = (myAdaptationStepsIndex + 1) % myAdaptationSteps;
277 : }
278 14773891 : myLastAdaptation = currentTime + DELTA_T; // because we run at the end of the time step
279 29547782 : 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 14773891 : 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 583669 : MSRoutingEngine::getCachedRoute(const std::pair<const MSEdge*, const MSEdge*>& key) {
371 : auto routeIt = myCachedRoutes.find(key);
372 583669 : if (routeIt != myCachedRoutes.end()) {
373 : return routeIt->second;
374 : }
375 : return nullptr;
376 : }
377 :
378 :
379 : void
380 7313 : MSRoutingEngine::initRouter(SUMOVehicle* vehicle) {
381 7313 : OptionsCont& oc = OptionsCont::getOptions();
382 7313 : const std::string routingAlgorithm = oc.getString("routing-algorithm");
383 7313 : const bool hasPermissions = MSNet::getInstance()->hasPermissions();
384 7313 : myBikeSpeeds = oc.getBool("device.rerouting.bike-speeds");
385 7313 : myEffortFunc = ((gWeightsRandomFactor != 1 || myPriorityFactor != 0 || myBikeSpeeds || gRoutingPreferences) ? &MSRoutingEngine::getEffortExtra : &MSRoutingEngine::getEffort);
386 :
387 : SUMOAbstractRouter<MSEdge, SUMOVehicle>* router = nullptr;
388 7313 : if (routingAlgorithm == "dijkstra") {
389 7027 : 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 7313 : if (MSNet::getInstance()->hasBidiEdges()) {
423 538 : railRouter = new RailwayRouter<MSEdge, SUMOVehicle>(MSEdge::getAllEdges(), true, myEffortFunc, nullptr, false, true, false,
424 : oc.getFloat("railway.max-train-length"),
425 1076 : oc.getFloat("weights.reversal-penalty"));
426 : }
427 8095 : const int carWalk = SUMOVehicleParserHelper::parseCarWalkTransfer(oc, MSDevice_Taxi::hasFleet() || MSNet::getInstance()->getInsertionControl().hasTaxiFlow());
428 7313 : const double taxiWait = STEPS2TIME(string2time(OptionsCont::getOptions().getString("persontrip.taxi.waiting-time")));
429 7313 : MSTransportableRouter* transRouter = new MSTransportableRouter(MSNet::adaptIntermodalRouter, carWalk, taxiWait, routingAlgorithm, 0);
430 7313 : myRouterProvider = new MSRouterProvider(router, nullptr, transRouter, railRouter);
431 : #ifndef THREAD_POOL
432 : #ifdef HAVE_FOX
433 7313 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
434 7313 : 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 7313 : }
445 :
446 :
447 : void
448 2325703 : MSRoutingEngine::reroute(SUMOVehicle& vehicle, const SUMOTime currentTime, const std::string& info,
449 : const bool onInit, const bool silent, const Prohibitions& prohibited) {
450 2325703 : if (myRouterProvider == nullptr) {
451 7150 : initRouter(&vehicle);
452 : }
453 2325703 : auto& router = myRouterProvider->getVehicleRouter(vehicle.getVClass());
454 : #ifndef THREAD_POOL
455 : #ifdef HAVE_FOX
456 2325703 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
457 2325703 : if (threadPool.size() > 0) {
458 188386 : threadPool.add(new RoutingTask(vehicle, currentTime, info, onInit, silent, prohibited));
459 188386 : return;
460 : }
461 : #endif
462 : #endif
463 2137317 : if (!prohibited.empty()) {
464 4 : router.prohibit(prohibited);
465 : }
466 : try {
467 2137317 : vehicle.reroute(currentTime, info, router, onInit, myWithTaz, silent);
468 116 : } catch (ProcessError&) {
469 116 : if (!silent) {
470 116 : if (!prohibited.empty()) {
471 0 : router.prohibit(Prohibitions());
472 : }
473 116 : throw;
474 : }
475 116 : }
476 2137201 : 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 482657 : MSRoutingEngine::getRouterTT(const int rngIndex, SUMOVehicleClass svc, const Prohibitions& prohibited) {
529 482657 : if (myRouterProvider == nullptr) {
530 163 : initWeightUpdate();
531 163 : initEdgeWeights(svc);
532 163 : initRouter();
533 : }
534 : #ifndef THREAD_POOL
535 : #ifdef HAVE_FOX
536 482657 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
537 482657 : if (threadPool.size() > 0) {
538 32603 : auto& router = static_cast<MSEdgeControl::WorkerThread*>(threadPool.getWorkers()[rngIndex % MSGlobals::gNumThreads])->getRouter(svc);
539 32603 : router.prohibit(prohibited);
540 32603 : return router;
541 : }
542 : #else
543 : UNUSED_PARAMETER(rngIndex);
544 : #endif
545 : #endif
546 900108 : myRouterProvider->getVehicleRouter(svc).prohibit(prohibited);
547 450054 : 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 38777 : MSRoutingEngine::cleanup() {
577 38777 : 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 38777 : myAdaptationStepsIndex = 0;
589 : #ifdef HAVE_FOX
590 38777 : if (MSGlobals::gNumThreads > 1) {
591 : // router deletion is done in thread destructor
592 4334 : myRouterProvider = nullptr;
593 4334 : return;
594 : }
595 : #endif
596 34443 : delete myRouterProvider;
597 34443 : myRouterProvider = nullptr;
598 : }
599 :
600 :
601 : void
602 476 : MSRoutingEngine::saveState(OutputDevice& out) {
603 476 : if (myEdgeSpeeds.size() == 0) {
604 : return;
605 : }
606 98 : out.openTag(SUMO_TAG_ROUTINGENGINE);
607 98 : out.writeAttr(SUMO_ATTR_LAST, myLastAdaptation);
608 98 : out.writeAttr(SUMO_ATTR_INDEX, myAdaptationStepsIndex);
609 98 : const MSEdgeVector& edges = MSNet::getInstance()->getEdgeControl().getEdges();
610 5208 : for (const MSEdge* const e : edges) {
611 0 : if (e->isDelayed()) {
612 : const int id = e->getNumericalID();
613 984 : out.openTag(SUMO_TAG_EDGE);
614 984 : out.writeAttr(SUMO_ATTR_ID, e->getID());
615 984 : out.writeAttr(SUMO_ATTR_SPEED, myEdgeSpeeds[id]);
616 984 : if (myAdaptationSteps > 0) {
617 984 : out.writeAttr(SUMO_ATTR_PASTSPEED, myPastEdgeSpeeds[id]);
618 : }
619 984 : 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 1968 : out.closeTag();
626 : }
627 : }
628 196 : out.closeTag();
629 : }
630 :
631 :
632 : void
633 903 : MSRoutingEngine::loadState(const SUMOSAXAttributes& attrs) {
634 1806 : 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 903 : bool ok = true;
640 903 : if ((int)myEdgeSpeeds.size() > id) {
641 903 : myEdgeSpeeds[id] = attrs.get<double>(SUMO_ATTR_SPEED, nullptr, ok);
642 903 : 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 903 : if (myAdaptationSteps > 0) {
651 903 : const std::vector<double> speeds = attrs.getOpt<std::vector<double> >(SUMO_ATTR_PASTSPEED, nullptr, ok);
652 903 : if ((int)speeds.size() == myAdaptationSteps) {
653 903 : myPastEdgeSpeeds[id] = speeds;
654 903 : 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 903 : }
662 : }
663 903 : }
664 :
665 :
666 : #ifdef HAVE_FOX
667 : void
668 142569481 : MSRoutingEngine::waitForAll() {
669 : #ifndef THREAD_POOL
670 142569481 : MFXWorkerThread::Pool& threadPool = MSNet::getInstance()->getEdgeControl().getThreadPool();
671 142569481 : if (threadPool.size() > 0) {
672 16746260 : threadPool.waitAll();
673 : }
674 : #endif
675 142569456 : }
676 :
677 :
678 : // ---------------------------------------------------------------------------
679 : // MSRoutingEngine::RoutingTask-methods
680 : // ---------------------------------------------------------------------------
681 : void
682 188386 : MSRoutingEngine::RoutingTask::run(MFXWorkerThread* context) {
683 188386 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router = static_cast<MSEdgeControl::WorkerThread*>(context)->getRouter(myVehicle.getVClass());
684 188386 : if (!myProhibited.empty()) {
685 2 : router.prohibit(myProhibited);
686 : }
687 : try {
688 188386 : 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 188361 : if (!myProhibited.empty()) {
698 4 : router.prohibit(Prohibitions());
699 : }
700 188361 : const MSEdge* source = *myVehicle.getRoute().begin();
701 188361 : const MSEdge* dest = myVehicle.getRoute().getLastEdge();
702 188361 : 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 188361 : }
710 :
711 :
712 : #endif
713 :
714 :
715 : /****************************************************************************/
|
