Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-2026 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 MSDevice_Routing.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 <microsim/MSNet.h>
27 : #include <microsim/MSLane.h>
28 : #include <microsim/MSEdge.h>
29 : #include <microsim/MSEdgeControl.h>
30 : #include <microsim/MSEventControl.h>
31 : #include <microsim/MSGlobals.h>
32 : #include <microsim/MSVehicleControl.h>
33 : #include <utils/options/OptionsCont.h>
34 : #include <utils/common/WrappingCommand.h>
35 : #include <utils/common/StringUtils.h>
36 : #include <utils/xml/SUMOSAXAttributes.h>
37 : #include "MSRoutingEngine.h"
38 : #include "MSDevice_Routing.h"
39 :
40 :
41 : // ===========================================================================
42 : // method definitions
43 : // ===========================================================================
44 : // ---------------------------------------------------------------------------
45 : // static initialisation methods
46 : // ---------------------------------------------------------------------------
47 : void
48 46427 : MSDevice_Routing::insertOptions(OptionsCont& oc) {
49 92854 : insertDefaultAssignmentOptions("rerouting", "Routing", oc);
50 :
51 92854 : oc.doRegister("device.rerouting.period", new Option_String("0", "TIME"));
52 92854 : oc.addSynonyme("device.rerouting.period", "device.routing.period", true);
53 92854 : oc.addDescription("device.rerouting.period", "Routing", TL("The period with which the vehicle shall be rerouted"));
54 :
55 92854 : oc.doRegister("device.rerouting.pre-period", new Option_String("60", "TIME"));
56 92854 : oc.addSynonyme("device.rerouting.pre-period", "device.routing.pre-period", true);
57 92854 : oc.addDescription("device.rerouting.pre-period", "Routing", TL("The rerouting period before depart"));
58 :
59 46427 : oc.doRegister("device.rerouting.adaptation-weight", new Option_Float(0));
60 92854 : oc.addSynonyme("device.rerouting.adaptation-weight", "device.routing.adaptation-weight", true);
61 92854 : oc.addDescription("device.rerouting.adaptation-weight", "Routing", TL("The weight of prior edge weights for exponential moving average"));
62 :
63 46427 : oc.doRegister("device.rerouting.adaptation-steps", new Option_Integer(180));
64 92854 : oc.addSynonyme("device.rerouting.adaptation-steps", "device.routing.adaptation-steps", true);
65 92854 : oc.addDescription("device.rerouting.adaptation-steps", "Routing", TL("The number of steps for moving average weight of prior edge weights"));
66 :
67 92854 : oc.doRegister("device.rerouting.adaptation-interval", new Option_String("1", "TIME"));
68 92854 : oc.addSynonyme("device.rerouting.adaptation-interval", "device.routing.adaptation-interval", true);
69 92854 : oc.addDescription("device.rerouting.adaptation-interval", "Routing", TL("The interval for updating the edge weights"));
70 :
71 46427 : oc.doRegister("device.rerouting.cch-update-threshold.factor", new Option_Float(1));
72 92854 : oc.addDescription("device.rerouting.cch-update-threshold.factor", "Routing", TL("Only propagate an arc weight into the CCH metric if it changed by more than the given factor"));
73 :
74 92854 : oc.doRegister("device.rerouting.cch-update-threshold.constant", new Option_String("0", "TIME"));
75 92854 : oc.addDescription("device.rerouting.cch-update-threshold.constant", "Routing", TL("Only propagate an arc weight into the CCH metric if it changed by more than the given TIME"));
76 46427 : oc.doRegister("device.rerouting.cch-ensemble", new Option_Integer(1));
77 92854 : oc.addDescription("device.rerouting.cch-ensemble", "Routing", TL("Keep this many frozen weights.random-factor realizations (CCH metrics) per vehicle type and assign vehicles to them by a stable id hash"));
78 :
79 46427 : oc.doRegister("device.rerouting.threshold.factor", new Option_Float(1));
80 92854 : oc.addDescription("device.rerouting.threshold.factor", "Routing", TL("Only reroute if the new route is faster than the current route by the given factor"));
81 :
82 92854 : oc.doRegister("device.rerouting.threshold.constant", new Option_String("0", "TIME"));
83 92854 : oc.addDescription("device.rerouting.threshold.constant", "Routing", TL("Only reroute if the new route is faster than the current route by the given TIME"));
84 :
85 46427 : oc.doRegister("device.rerouting.invalidation", new Option_Bool(false));
86 92854 : oc.addDescription("device.rerouting.invalidation", "Routing", TL("Only perform a periodic reroute when the current route's remaining cost has drifted beyond the threshold (cheap re-scoring gate before the full reroute)"));
87 :
88 46427 : oc.doRegister("device.rerouting.with-taz", new Option_Bool(false));
89 92854 : oc.addSynonyme("device.rerouting.with-taz", "device.routing.with-taz", true);
90 92854 : oc.addSynonyme("device.rerouting.with-taz", "with-taz");
91 92854 : oc.addDescription("device.rerouting.with-taz", "Routing", TL("Use zones (districts) as routing start- and endpoints"));
92 :
93 92854 : oc.doRegister("device.rerouting.mode", new Option_String("0"));
94 92854 : oc.addDescription("device.rerouting.mode", "Routing", TL("Set routing flags (8 ignores temporary blockages)"));
95 :
96 46427 : oc.doRegister("device.rerouting.init-with-loaded-weights", new Option_Bool(false));
97 92854 : oc.addDescription("device.rerouting.init-with-loaded-weights", "Routing", TL("Use weight files given with option --weight-files for initializing edge weights"));
98 :
99 46427 : oc.doRegister("device.rerouting.threads", new Option_Integer(0));
100 92854 : oc.addSynonyme("device.rerouting.threads", "routing-threads");
101 92854 : oc.addDescription("device.rerouting.threads", "Routing", TL("The number of parallel execution threads used for rerouting"));
102 :
103 46427 : oc.doRegister("device.rerouting.synchronize", new Option_Bool(false));
104 92854 : oc.addDescription("device.rerouting.synchronize", "Routing", TL("Let rerouting happen at the same time for all vehicles"));
105 :
106 46427 : oc.doRegister("device.rerouting.railsignal", new Option_Bool(false));
107 92854 : oc.addDescription("device.rerouting.railsignal", "Routing", TL("Allow rerouting triggered by rail signals."));
108 :
109 46427 : oc.doRegister("device.rerouting.bike-speeds", new Option_Bool(false));
110 92854 : oc.addDescription("device.rerouting.bike-speeds", "Routing", TL("Compute separate average speeds for bicycles"));
111 :
112 46427 : oc.doRegister("device.rerouting.output", new Option_FileName());
113 92854 : oc.addDescription("device.rerouting.output", "Routing", TL("Save adapting weights to FILE"));
114 46427 : }
115 :
116 :
117 : bool
118 45727 : MSDevice_Routing::checkOptions(OptionsCont& oc) {
119 : bool ok = true;
120 46091 : if (!oc.isDefault("device.rerouting.adaptation-steps") && !oc.isDefault("device.rerouting.adaptation-weight")) {
121 0 : WRITE_ERROR(TL("Only one of the options 'device.rerouting.adaptation-steps' or 'device.rerouting.adaptation-weight' may be given."));
122 : ok = false;
123 : }
124 91454 : if (oc.getFloat("weights.random-factor") < 1) {
125 0 : WRITE_ERROR(TL("weights.random-factor cannot be less than 1"));
126 : ok = false;
127 : }
128 91454 : if (string2time(oc.getString("device.rerouting.adaptation-interval")) < 0) {
129 16 : WRITE_ERROR(TL("Negative value for device.rerouting.adaptation-interval!"));
130 : ok = false;
131 : }
132 137181 : if (oc.getFloat("device.rerouting.adaptation-weight") < 0. ||
133 137181 : oc.getFloat("device.rerouting.adaptation-weight") > 1.) {
134 0 : WRITE_ERROR(TL("The value for device.rerouting.adaptation-weight must be between 0 and 1!"));
135 : ok = false;
136 : }
137 : #ifndef HAVE_FOX
138 : if (oc.getInt("device.rerouting.threads") > 1) {
139 : WRITE_ERROR(TL("Parallel routing is only possible when compiled with Fox."));
140 : ok = false;
141 : }
142 : #endif
143 50351 : if (oc.getInt("threads") > 1 && oc.getInt("device.rerouting.threads") > 1 && oc.getInt("threads") != oc.getInt("device.rerouting.threads")) {
144 18 : WRITE_WARNING(TL("Adapting number of routing threads to number of simulation threads."));
145 : }
146 45727 : return ok;
147 : }
148 :
149 :
150 : void
151 5496638 : MSDevice_Routing::buildVehicleDevices(SUMOVehicle& v, std::vector<MSVehicleDevice*>& into) {
152 5496638 : const OptionsCont& oc = OptionsCont::getOptions();
153 5496638 : const bool equip = equippedByDefaultAssignmentOptions(oc, "rerouting", v, false);
154 5496632 : if (v.getParameter().wasSet(VEHPARS_FORCE_REROUTE) || equip) {
155 : // route computation is enabled
156 : // for implicitly equipped vehicles (trips, flows), option probability
157 : // can still be used to disable periodic rerouting after insertion for
158 : // parts of the fleet
159 1248679 : const SUMOTime period = (equip || (
160 2496380 : oc.isDefault("device.rerouting.probability") &&
161 3913617 : v.getFloatParam("device.rerouting.probability") == oc.getFloat("device.rerouting.probability"))
162 4084051 : ? v.getTimeParam("device.rerouting.period") : 0);
163 1418215 : const SUMOTime prePeriod = MAX2((SUMOTime)0, v.getTimeParam("device.rerouting.pre-period"));
164 1418215 : MSRoutingEngine::initWeightUpdate();
165 : // build the device
166 2836430 : into.push_back(new MSDevice_Routing(v, "routing_" + v.getID(), period, prePeriod));
167 : }
168 5496632 : }
169 :
170 :
171 : // ---------------------------------------------------------------------------
172 : // MSDevice_Routing-methods
173 : // ---------------------------------------------------------------------------
174 1418215 : MSDevice_Routing::MSDevice_Routing(SUMOVehicle& holder, const std::string& id,
175 1418215 : SUMOTime period, SUMOTime preInsertionPeriod) :
176 : MSVehicleDevice(holder, id),
177 1418215 : myPeriod(period),
178 1418215 : myPreInsertionPeriod(preInsertionPeriod),
179 1418215 : myLastRouting(-1),
180 1418215 : mySkipRouting(-1),
181 1418215 : myRerouteCommand(nullptr),
182 1418215 : myRerouteRailSignal(holder.getBoolParam("device.rerouting.railsignal", true)),
183 1418215 : myLastLaneEntryTime(-1),
184 1418215 : myRerouteAfterStop(false),
185 1418215 : myThresholdFactor(holder.getFloatParam("device.rerouting.threshold.factor", true, 1)),
186 1418215 : myThresholdTime(STEPS2TIME(holder.getTimeParam("device.rerouting.threshold.constant", true, 0))),
187 1418215 : myActive(true),
188 1418215 : myInvalidation(OptionsCont::getOptions().getBool("device.rerouting.invalidation")),
189 1418215 : myLastRouteCost(-1.) {
190 1418215 : if (myPreInsertionPeriod > 0 || holder.getParameter().wasSet(VEHPARS_FORCE_REROUTE)) {
191 : // we do always a pre insertion reroute for trips to fill the best lanes of the vehicle with somehow meaningful values (especially for deaprtLane="best")
192 1417221 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::preInsertionReroute);
193 : // if we don't update the edge weights, we might as well reroute now and hopefully use our threads better
194 1417221 : const SUMOTime execTime = MSRoutingEngine::hasEdgeUpdates() ? holder.getParameter().depart : -1;
195 1417221 : MSNet::getInstance()->getInsertionEvents()->addEvent(myRerouteCommand, execTime);
196 : }
197 1418215 : }
198 :
199 :
200 2836416 : MSDevice_Routing::~MSDevice_Routing() {
201 : // make the rerouting command invalid if there is one
202 1418208 : if (myRerouteCommand != nullptr) {
203 : myRerouteCommand->deschedule();
204 : }
205 2836416 : }
206 :
207 :
208 : bool
209 1184170 : MSDevice_Routing::notifyEnter(SUMOTrafficObject& /*veh*/, MSMoveReminder::Notification reason, const MSLane* enteredLane) {
210 1184170 : if (reason == MSMoveReminder::NOTIFICATION_DEPARTED) {
211 1144845 : if (myRerouteCommand == nullptr && myPreInsertionPeriod > 0 && myHolder.getDepartDelay() > myPreInsertionPeriod) {
212 : // pre-insertion rerouting was disabled. Reroute once if insertion was delayed
213 : // this is happening in the run thread (not inbeginOfTimestepEvents) so we cannot safely use the threadPool
214 1733535 : myHolder.reroute(MSNet::getInstance()->getCurrentTimeStep(), "device.rerouting",
215 1155690 : MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass()),
216 : true, MSRoutingEngine::withTaz(), false);
217 : }
218 : // build repetition trigger if routing shall be done more often
219 1144845 : rebuildRerouteCommand(SIMSTEP + myPeriod);
220 : }
221 1184170 : if (MSGlobals::gWeightsSeparateTurns > 0 && enteredLane != nullptr) {
222 43622 : if (reason == MSMoveReminder::NOTIFICATION_JUNCTION) {
223 37512 : const SUMOTime t = SIMSTEP;
224 37512 : if (myLastLaneEntryTime >= 0 && enteredLane->isInternal()) {
225 : // record travel time on the previous edge but store on the internal ledge
226 13518 : MSRoutingEngine::addEdgeTravelTime(enteredLane->getEdge(), t - myLastLaneEntryTime);
227 : }
228 37512 : myLastLaneEntryTime = t;
229 : }
230 43622 : return true;
231 : } else {
232 : return false;
233 : }
234 : }
235 :
236 :
237 : void
238 6340 : MSDevice_Routing::notifyStopEnded() {
239 6340 : if (myRerouteAfterStop) {
240 257 : reroute(SIMSTEP);
241 257 : myRerouteAfterStop = false;
242 : }
243 6340 : }
244 :
245 :
246 : void
247 1146596 : MSDevice_Routing::rebuildRerouteCommand(SUMOTime start) {
248 1146596 : if (myRerouteCommand != nullptr) {
249 : myRerouteCommand->deschedule();
250 228966 : myRerouteCommand = nullptr;
251 : }
252 1146596 : if (myPeriod > 0) {
253 61788 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::wrappedRerouteCommandExecute);
254 123576 : if (OptionsCont::getOptions().getBool("device.rerouting.synchronize")) {
255 1590 : start -= start % myPeriod;
256 : }
257 : // ensure stable sorting of events (for repeatable routing with randomness)
258 61788 : myRerouteCommand->priority = (int)myHolder.getNumericalID();
259 61788 : MSNet::getInstance()->getBeginOfTimestepEvents()->addEvent(myRerouteCommand, start);
260 : }
261 1146596 : }
262 :
263 :
264 : SUMOTime
265 45692189 : MSDevice_Routing::preInsertionReroute(const SUMOTime currentTime) {
266 45692189 : if (mySkipRouting == currentTime) {
267 43594787 : return DELTA_T;
268 : }
269 2097402 : if (myPreInsertionPeriod == 0) {
270 : // the event will deschedule and destroy itself so it does not need to be stored
271 566 : myRerouteCommand = nullptr;
272 : }
273 2097402 : const MSEdge* source = *myHolder.getRoute().begin();
274 2097402 : const MSEdge* dest = myHolder.getRoute().getLastEdge();
275 2097402 : if (source->isTazConnector() && dest->isTazConnector()) {
276 465910 : ConstMSRoutePtr cached = MSRoutingEngine::getCachedRoute(std::make_pair(source, dest));
277 465910 : if (cached != nullptr && cached->size() > 2) {
278 0 : myHolder.replaceRoute(cached, "device.rerouting", true);
279 0 : return myPreInsertionPeriod;
280 : }
281 : }
282 : try {
283 : std::string msg;
284 2097402 : if (myHolder.hasValidRouteStart(msg)) {
285 2097380 : reroute(currentTime, true);
286 : }
287 113 : } catch (ProcessError&) {
288 113 : myRerouteCommand = nullptr;
289 113 : throw;
290 113 : }
291 : // avoid repeated pre-insertion rerouting when the departure edge is fix and
292 : // the departure lane does not depend on the route
293 3728097 : if (myPreInsertionPeriod > 0 && !source->isTazConnector() && myHolder.getParameter().departLaneProcedure != DepartLaneDefinition::BEST_FREE) {
294 934111 : myRerouteCommand = nullptr;
295 934111 : return 0;
296 : }
297 1163178 : return myPreInsertionPeriod;
298 : }
299 :
300 :
301 : SUMOTime
302 199865 : MSDevice_Routing::wrappedRerouteCommandExecute(SUMOTime currentTime) {
303 199865 : if (myHolder.isStopped()) {
304 21674 : myRerouteAfterStop = true;
305 : } else {
306 178191 : reroute(currentTime);
307 : }
308 199865 : return myPeriod;
309 : }
310 :
311 :
312 : void
313 2275828 : MSDevice_Routing::reroute(const SUMOTime currentTime, const bool onInit) {
314 2275828 : MSRoutingEngine::initEdgeWeights(myHolder.getVClass());
315 : //check whether the weights did change since the last reroute
316 2275828 : if (myLastRouting >= MSRoutingEngine::getLastAdaptation() || !myActive) {
317 : return;
318 : }
319 : // Invalidation gate: even when the metric changed, skip the (expensive)
320 : // reroute unless THIS vehicle's remaining route has actually degraded.
321 : // recomputeCosts is O(remaining-route length) array reads, far cheaper
322 : // than a shortest-path search. Only meaningful once the vehicle is on the
323 : // road with a concrete route (getCurrentRouteEdge is only valid then);
324 : // pre-insertion / onInit reroutes always run and don't track cost.
325 2271147 : const bool canGate = myInvalidation && !onInit && myHolder.isOnRoad();
326 0 : if (canGate && myLastRouteCost >= 0.) {
327 0 : MSVehicleRouter& router = MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass());
328 0 : const ConstMSEdgeVector remaining(myHolder.getCurrentRouteEdge(), myHolder.getRoute().end());
329 0 : if (!remaining.empty()) {
330 0 : const double costNow = router.recomputeCosts(remaining, &myHolder, currentTime);
331 0 : if (costNow - myLastRouteCost <= myThresholdTime && costNow <= myLastRouteCost * myThresholdFactor) {
332 0 : myLastRouting = currentTime; // route still good enough; skip the search
333 0 : myLastRouteCost = costNow;
334 : return;
335 : }
336 : }
337 0 : }
338 2271147 : myLastRouting = currentTime;
339 4542294 : MSRoutingEngine::reroute(myHolder, currentTime, "device.rerouting", onInit);
340 2271034 : if (myInvalidation && myHolder.isOnRoad()) {
341 0 : MSVehicleRouter& router = MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass());
342 0 : const ConstMSEdgeVector remaining(myHolder.getCurrentRouteEdge(), myHolder.getRoute().end());
343 0 : myLastRouteCost = remaining.empty() ? -1. : router.recomputeCosts(remaining, &myHolder, currentTime);
344 0 : }
345 : }
346 :
347 :
348 : bool
349 173037 : MSDevice_Routing::sufficientSaving(double oldCost, double newCost) {
350 173037 : if (newCost == 0) {
351 : return true;
352 : }
353 173021 : return (oldCost / newCost > myThresholdFactor) && (oldCost - newCost > myThresholdTime);
354 : }
355 :
356 :
357 : std::string
358 36 : MSDevice_Routing::getParameter(const std::string& key) const {
359 72 : if (StringUtils::startsWith(key, "edge:")) {
360 18 : const std::string edgeID = key.substr(5);
361 18 : const MSEdge* edge = MSEdge::dictionary(edgeID);
362 18 : if (edge == nullptr) {
363 0 : throw InvalidArgument("Edge '" + edgeID + "' is invalid for parameter retrieval of '" + deviceName() + "'");
364 : }
365 18 : return toString(MSRoutingEngine::getEffort(edge, &myHolder, 0));
366 18 : } else if (key == "period") {
367 18 : return time2string(myPeriod);
368 : }
369 0 : throw InvalidArgument("Parameter '" + key + "' is not supported for device of type '" + deviceName() + "'");
370 : }
371 :
372 :
373 : void
374 33 : MSDevice_Routing::setParameter(const std::string& key, const std::string& value) {
375 : double doubleValue;
376 : try {
377 33 : doubleValue = StringUtils::toDouble(value);
378 0 : } catch (NumberFormatException&) {
379 0 : throw InvalidArgument("Setting parameter '" + key + "' requires a number for device of type '" + deviceName() + "'");
380 0 : }
381 66 : if (StringUtils::startsWith(key, "edge:")) {
382 9 : const std::string edgeID = key.substr(5);
383 9 : const MSEdge* edge = MSEdge::dictionary(edgeID);
384 9 : if (edge == nullptr) {
385 0 : throw InvalidArgument("Edge '" + edgeID + "' is invalid for parameter setting of '" + deviceName() + "'");
386 : }
387 9 : MSRoutingEngine::setEdgeTravelTime(edge, doubleValue);
388 24 : } else if (key == "period") {
389 24 : myPeriod = TIME2STEPS(doubleValue);
390 : // re-schedule routing command
391 24 : rebuildRerouteCommand(SIMSTEP + myPeriod);
392 : } else {
393 0 : throw InvalidArgument("Setting parameter '" + key + "' is not supported for device of type '" + deviceName() + "'");
394 : }
395 33 : }
396 :
397 :
398 : void
399 3276 : MSDevice_Routing::saveState(OutputDevice& out) const {
400 3276 : out.openTag(SUMO_TAG_DEVICE);
401 3276 : out.writeAttr(SUMO_ATTR_ID, getID());
402 : std::vector<std::string> internals;
403 3276 : internals.push_back(toString(myPeriod));
404 3276 : internals.push_back(toString(myLastRouting));
405 3276 : out.writeAttr(SUMO_ATTR_STATE, toString(internals));
406 3276 : out.closeTag();
407 3276 : }
408 :
409 :
410 : void
411 4059 : MSDevice_Routing::loadState(const SUMOSAXAttributes& attrs) {
412 4059 : std::istringstream bis(attrs.getString(SUMO_ATTR_STATE));
413 4059 : bis >> myPeriod;
414 4059 : bis >> myLastRouting;
415 4059 : if (myHolder.hasDeparted()) {
416 1727 : SUMOTime offset = myPeriod;
417 1727 : if (myPeriod > 0) {
418 807 : offset = ((SIMSTEP - myHolder.getDeparture()) % myPeriod);
419 807 : if (offset != 0) {
420 785 : offset = myPeriod - offset;
421 : }
422 : }
423 1727 : rebuildRerouteCommand(SIMSTEP + offset);
424 : }
425 4059 : }
426 :
427 :
428 : /****************************************************************************/
|
