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 46292 : MSDevice_Routing::insertOptions(OptionsCont& oc) {
49 92584 : insertDefaultAssignmentOptions("rerouting", "Routing", oc);
50 :
51 92584 : oc.doRegister("device.rerouting.period", new Option_String("0", "TIME"));
52 92584 : oc.addSynonyme("device.rerouting.period", "device.routing.period", true);
53 92584 : oc.addDescription("device.rerouting.period", "Routing", TL("The period with which the vehicle shall be rerouted"));
54 :
55 92584 : oc.doRegister("device.rerouting.pre-period", new Option_String("60", "TIME"));
56 92584 : oc.addSynonyme("device.rerouting.pre-period", "device.routing.pre-period", true);
57 92584 : oc.addDescription("device.rerouting.pre-period", "Routing", TL("The rerouting period before depart"));
58 :
59 46292 : oc.doRegister("device.rerouting.adaptation-weight", new Option_Float(0));
60 92584 : oc.addSynonyme("device.rerouting.adaptation-weight", "device.routing.adaptation-weight", true);
61 92584 : oc.addDescription("device.rerouting.adaptation-weight", "Routing", TL("The weight of prior edge weights for exponential moving average"));
62 :
63 46292 : oc.doRegister("device.rerouting.adaptation-steps", new Option_Integer(180));
64 92584 : oc.addSynonyme("device.rerouting.adaptation-steps", "device.routing.adaptation-steps", true);
65 92584 : oc.addDescription("device.rerouting.adaptation-steps", "Routing", TL("The number of steps for moving average weight of prior edge weights"));
66 :
67 92584 : oc.doRegister("device.rerouting.adaptation-interval", new Option_String("1", "TIME"));
68 92584 : oc.addSynonyme("device.rerouting.adaptation-interval", "device.routing.adaptation-interval", true);
69 92584 : oc.addDescription("device.rerouting.adaptation-interval", "Routing", TL("The interval for updating the edge weights"));
70 :
71 46292 : oc.doRegister("device.rerouting.cch-update-threshold.factor", new Option_Float(1));
72 92584 : 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 92584 : oc.doRegister("device.rerouting.cch-update-threshold.constant", new Option_String("0", "TIME"));
75 92584 : 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 46292 : oc.doRegister("device.rerouting.cch-ensemble", new Option_Integer(1));
77 92584 : 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 46292 : oc.doRegister("device.rerouting.threshold.factor", new Option_Float(1));
80 92584 : 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 92584 : oc.doRegister("device.rerouting.threshold.constant", new Option_String("0", "TIME"));
83 92584 : 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 46292 : oc.doRegister("device.rerouting.invalidation", new Option_Bool(false));
86 92584 : 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 46292 : oc.doRegister("device.rerouting.with-taz", new Option_Bool(false));
89 92584 : oc.addSynonyme("device.rerouting.with-taz", "device.routing.with-taz", true);
90 92584 : oc.addSynonyme("device.rerouting.with-taz", "with-taz");
91 92584 : oc.addDescription("device.rerouting.with-taz", "Routing", TL("Use zones (districts) as routing start- and endpoints"));
92 :
93 92584 : oc.doRegister("device.rerouting.mode", new Option_String("0"));
94 92584 : oc.addDescription("device.rerouting.mode", "Routing", TL("Set routing flags (8 ignores temporary blockages)"));
95 :
96 46292 : oc.doRegister("device.rerouting.init-with-loaded-weights", new Option_Bool(false));
97 92584 : oc.addDescription("device.rerouting.init-with-loaded-weights", "Routing", TL("Use weight files given with option --weight-files for initializing edge weights"));
98 :
99 46292 : oc.doRegister("device.rerouting.threads", new Option_Integer(0));
100 92584 : oc.addSynonyme("device.rerouting.threads", "routing-threads");
101 92584 : oc.addDescription("device.rerouting.threads", "Routing", TL("The number of parallel execution threads used for rerouting"));
102 :
103 46292 : oc.doRegister("device.rerouting.synchronize", new Option_Bool(false));
104 92584 : oc.addDescription("device.rerouting.synchronize", "Routing", TL("Let rerouting happen at the same time for all vehicles"));
105 :
106 46292 : oc.doRegister("device.rerouting.railsignal", new Option_Bool(false));
107 92584 : oc.addDescription("device.rerouting.railsignal", "Routing", TL("Allow rerouting triggered by rail signals."));
108 :
109 46292 : oc.doRegister("device.rerouting.bike-speeds", new Option_Bool(false));
110 92584 : oc.addDescription("device.rerouting.bike-speeds", "Routing", TL("Compute separate average speeds for bicycles"));
111 :
112 46292 : oc.doRegister("device.rerouting.output", new Option_FileName());
113 92584 : oc.addDescription("device.rerouting.output", "Routing", TL("Save adapting weights to FILE"));
114 46292 : }
115 :
116 :
117 : bool
118 45592 : MSDevice_Routing::checkOptions(OptionsCont& oc) {
119 : bool ok = true;
120 45952 : 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 91184 : 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 91184 : 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 136776 : if (oc.getFloat("device.rerouting.adaptation-weight") < 0. ||
133 136776 : 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 50198 : 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 45592 : return ok;
147 : }
148 :
149 :
150 : void
151 5489596 : MSDevice_Routing::buildVehicleDevices(SUMOVehicle& v, std::vector<MSVehicleDevice*>& into) {
152 5489596 : const OptionsCont& oc = OptionsCont::getOptions();
153 5489596 : const bool equip = equippedByDefaultAssignmentOptions(oc, "rerouting", v, false);
154 5489590 : 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 1243552 : const SUMOTime period = (equip || (
160 2486126 : oc.isDefault("device.rerouting.probability") &&
161 3898187 : v.getFloatParam("device.rerouting.probability") == oc.getFloat("device.rerouting.probability"))
162 4068572 : ? v.getTimeParam("device.rerouting.period") : 0);
163 1413039 : const SUMOTime prePeriod = MAX2((SUMOTime)0, v.getTimeParam("device.rerouting.pre-period"));
164 1413039 : MSRoutingEngine::initWeightUpdate();
165 : // build the device
166 2826078 : into.push_back(new MSDevice_Routing(v, "routing_" + v.getID(), period, prePeriod));
167 : }
168 5489590 : }
169 :
170 :
171 : // ---------------------------------------------------------------------------
172 : // MSDevice_Routing-methods
173 : // ---------------------------------------------------------------------------
174 1413039 : MSDevice_Routing::MSDevice_Routing(SUMOVehicle& holder, const std::string& id,
175 1413039 : SUMOTime period, SUMOTime preInsertionPeriod) :
176 : MSVehicleDevice(holder, id),
177 1413039 : myPeriod(period),
178 1413039 : myPreInsertionPeriod(preInsertionPeriod),
179 1413039 : myLastRouting(-1),
180 1413039 : mySkipRouting(-1),
181 1413039 : myRerouteCommand(nullptr),
182 1413039 : myRerouteRailSignal(holder.getBoolParam("device.rerouting.railsignal", true)),
183 1413039 : myLastLaneEntryTime(-1),
184 1413039 : myRerouteAfterStop(false),
185 1413039 : myThresholdFactor(holder.getFloatParam("device.rerouting.threshold.factor", true, 1)),
186 1413039 : myThresholdTime(STEPS2TIME(holder.getTimeParam("device.rerouting.threshold.constant", true, 0))),
187 1413039 : myActive(true),
188 1413039 : myInvalidation(OptionsCont::getOptions().getBool("device.rerouting.invalidation")),
189 1413039 : myLastRouteCost(-1.) {
190 1413039 : 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 1412094 : 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 1412094 : const SUMOTime execTime = MSRoutingEngine::hasEdgeUpdates() ? holder.getParameter().depart : -1;
195 1412094 : MSNet::getInstance()->getInsertionEvents()->addEvent(myRerouteCommand, execTime);
196 : }
197 1413039 : }
198 :
199 :
200 2826066 : MSDevice_Routing::~MSDevice_Routing() {
201 : // make the rerouting command invalid if there is one
202 1413033 : if (myRerouteCommand != nullptr) {
203 : myRerouteCommand->deschedule();
204 : }
205 2826066 : }
206 :
207 :
208 : bool
209 1179266 : MSDevice_Routing::notifyEnter(SUMOTrafficObject& /*veh*/, MSMoveReminder::Notification reason, const MSLane* enteredLane) {
210 1179266 : if (reason == MSMoveReminder::NOTIFICATION_DEPARTED) {
211 1139942 : 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 1732647 : myHolder.reroute(MSNet::getInstance()->getCurrentTimeStep(), "device.rerouting",
215 1155098 : MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass()),
216 : true, MSRoutingEngine::withTaz(), false);
217 : }
218 : // build repetition trigger if routing shall be done more often
219 1139942 : rebuildRerouteCommand(SIMSTEP + myPeriod);
220 : }
221 1179266 : 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 6339 : MSDevice_Routing::notifyStopEnded() {
239 6339 : if (myRerouteAfterStop) {
240 257 : reroute(SIMSTEP);
241 257 : myRerouteAfterStop = false;
242 : }
243 6339 : }
244 :
245 :
246 : void
247 1141691 : MSDevice_Routing::rebuildRerouteCommand(SUMOTime start) {
248 1141691 : if (myRerouteCommand != nullptr) {
249 : myRerouteCommand->deschedule();
250 228966 : myRerouteCommand = nullptr;
251 : }
252 1141691 : if (myPeriod > 0) {
253 61780 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::wrappedRerouteCommandExecute);
254 123560 : 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 61780 : myRerouteCommand->priority = (int)myHolder.getNumericalID();
259 61780 : MSNet::getInstance()->getBeginOfTimestepEvents()->addEvent(myRerouteCommand, start);
260 : }
261 1141691 : }
262 :
263 :
264 : SUMOTime
265 45668764 : MSDevice_Routing::preInsertionReroute(const SUMOTime currentTime) {
266 45668764 : if (mySkipRouting == currentTime) {
267 43570100 : return DELTA_T;
268 : }
269 2098664 : 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 2098664 : const MSEdge* source = *myHolder.getRoute().begin();
274 2098664 : const MSEdge* dest = myHolder.getRoute().getLastEdge();
275 2098664 : 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 2098664 : if (myHolder.hasValidRouteStart(msg)) {
285 2098642 : reroute(currentTime, true);
286 : }
287 109 : } catch (ProcessError&) {
288 109 : myRerouteCommand = nullptr;
289 109 : throw;
290 109 : }
291 : // avoid repeated pre-insertion rerouting when the departure edge is fix and
292 : // the departure lane does not depend on the route
293 3730629 : if (myPreInsertionPeriod > 0 && !source->isTazConnector() && myHolder.getParameter().departLaneProcedure != DepartLaneDefinition::BEST_FREE) {
294 928989 : myRerouteCommand = nullptr;
295 928989 : return 0;
296 : }
297 1169566 : return myPreInsertionPeriod;
298 : }
299 :
300 :
301 : SUMOTime
302 199601 : MSDevice_Routing::wrappedRerouteCommandExecute(SUMOTime currentTime) {
303 199601 : if (myHolder.isStopped()) {
304 21674 : myRerouteAfterStop = true;
305 : } else {
306 177927 : reroute(currentTime);
307 : }
308 199601 : return myPeriod;
309 : }
310 :
311 :
312 : void
313 2276826 : MSDevice_Routing::reroute(const SUMOTime currentTime, const bool onInit) {
314 2276826 : MSRoutingEngine::initEdgeWeights(myHolder.getVClass());
315 : //check whether the weights did change since the last reroute
316 2276826 : 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 2272145 : 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 2272145 : myLastRouting = currentTime;
339 4544290 : MSRoutingEngine::reroute(myHolder, currentTime, "device.rerouting", onInit);
340 2272036 : 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 172773 : MSDevice_Routing::sufficientSaving(double oldCost, double newCost) {
350 172773 : if (newCost == 0) {
351 : return true;
352 : }
353 172757 : 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 3274 : MSDevice_Routing::saveState(OutputDevice& out) const {
400 3274 : out.openTag(SUMO_TAG_DEVICE);
401 3274 : out.writeAttr(SUMO_ATTR_ID, getID());
402 : std::vector<std::string> internals;
403 3274 : internals.push_back(toString(myPeriod));
404 3274 : internals.push_back(toString(myLastRouting));
405 3274 : out.writeAttr(SUMO_ATTR_STATE, toString(internals));
406 3274 : out.closeTag();
407 3274 : }
408 :
409 :
410 : void
411 4057 : MSDevice_Routing::loadState(const SUMOSAXAttributes& attrs) {
412 4057 : std::istringstream bis(attrs.getString(SUMO_ATTR_STATE));
413 4057 : bis >> myPeriod;
414 4057 : bis >> myLastRouting;
415 4057 : if (myHolder.hasDeparted()) {
416 1725 : SUMOTime offset = myPeriod;
417 1725 : if (myPeriod > 0) {
418 807 : offset = ((SIMSTEP - myHolder.getDeparture()) % myPeriod);
419 807 : if (offset != 0) {
420 785 : offset = myPeriod - offset;
421 : }
422 : }
423 1725 : rebuildRerouteCommand(SIMSTEP + offset);
424 : }
425 4057 : }
426 :
427 :
428 : /****************************************************************************/
|
