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 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 39900 : MSDevice_Routing::insertOptions(OptionsCont& oc) {
49 79800 : insertDefaultAssignmentOptions("rerouting", "Routing", oc);
50 :
51 79800 : oc.doRegister("device.rerouting.period", new Option_String("0", "TIME"));
52 79800 : oc.addSynonyme("device.rerouting.period", "device.routing.period", true);
53 79800 : oc.addDescription("device.rerouting.period", "Routing", TL("The period with which the vehicle shall be rerouted"));
54 :
55 79800 : oc.doRegister("device.rerouting.pre-period", new Option_String("60", "TIME"));
56 79800 : oc.addSynonyme("device.rerouting.pre-period", "device.routing.pre-period", true);
57 79800 : oc.addDescription("device.rerouting.pre-period", "Routing", TL("The rerouting period before depart"));
58 :
59 39900 : oc.doRegister("device.rerouting.adaptation-weight", new Option_Float(0));
60 79800 : oc.addSynonyme("device.rerouting.adaptation-weight", "device.routing.adaptation-weight", true);
61 79800 : oc.addDescription("device.rerouting.adaptation-weight", "Routing", TL("The weight of prior edge weights for exponential moving average"));
62 :
63 39900 : oc.doRegister("device.rerouting.adaptation-steps", new Option_Integer(180));
64 79800 : oc.addSynonyme("device.rerouting.adaptation-steps", "device.routing.adaptation-steps", true);
65 79800 : oc.addDescription("device.rerouting.adaptation-steps", "Routing", TL("The number of steps for moving average weight of prior edge weights"));
66 :
67 79800 : oc.doRegister("device.rerouting.adaptation-interval", new Option_String("1", "TIME"));
68 79800 : oc.addSynonyme("device.rerouting.adaptation-interval", "device.routing.adaptation-interval", true);
69 79800 : oc.addDescription("device.rerouting.adaptation-interval", "Routing", TL("The interval for updating the edge weights"));
70 :
71 39900 : oc.doRegister("device.rerouting.threshold.factor", new Option_Float(1));
72 79800 : oc.addDescription("device.rerouting.threshold.factor", "Routing", TL("Only reroute if the new route is faster than the current route by the given factor"));
73 :
74 79800 : oc.doRegister("device.rerouting.threshold.constant", new Option_String("0", "TIME"));
75 79800 : oc.addDescription("device.rerouting.threshold.constant", "Routing", TL("Only reroute if the new route is faster than the current route by the given TIME"));
76 :
77 39900 : oc.doRegister("device.rerouting.with-taz", new Option_Bool(false));
78 79800 : oc.addSynonyme("device.rerouting.with-taz", "device.routing.with-taz", true);
79 79800 : oc.addSynonyme("device.rerouting.with-taz", "with-taz");
80 79800 : oc.addDescription("device.rerouting.with-taz", "Routing", TL("Use zones (districts) as routing start- and endpoints"));
81 :
82 79800 : oc.doRegister("device.rerouting.mode", new Option_String("0"));
83 79800 : oc.addDescription("device.rerouting.mode", "Routing", TL("Set routing flags (8 ignores temporary blockages)"));
84 :
85 39900 : oc.doRegister("device.rerouting.init-with-loaded-weights", new Option_Bool(false));
86 79800 : oc.addDescription("device.rerouting.init-with-loaded-weights", "Routing", TL("Use weight files given with option --weight-files for initializing edge weights"));
87 :
88 39900 : oc.doRegister("device.rerouting.threads", new Option_Integer(0));
89 79800 : oc.addSynonyme("device.rerouting.threads", "routing-threads");
90 79800 : oc.addDescription("device.rerouting.threads", "Routing", TL("The number of parallel execution threads used for rerouting"));
91 :
92 39900 : oc.doRegister("device.rerouting.synchronize", new Option_Bool(false));
93 79800 : oc.addDescription("device.rerouting.synchronize", "Routing", TL("Let rerouting happen at the same time for all vehicles"));
94 :
95 39900 : oc.doRegister("device.rerouting.railsignal", new Option_Bool(false));
96 79800 : oc.addDescription("device.rerouting.railsignal", "Routing", TL("Allow rerouting triggered by rail signals."));
97 :
98 39900 : oc.doRegister("device.rerouting.bike-speeds", new Option_Bool(false));
99 79800 : oc.addDescription("device.rerouting.bike-speeds", "Routing", TL("Compute separate average speeds for bicycles"));
100 :
101 39900 : oc.doRegister("device.rerouting.output", new Option_FileName());
102 79800 : oc.addDescription("device.rerouting.output", "Routing", TL("Save adapting weights to FILE"));
103 39900 : }
104 :
105 :
106 : bool
107 39440 : MSDevice_Routing::checkOptions(OptionsCont& oc) {
108 : bool ok = true;
109 39766 : if (!oc.isDefault("device.rerouting.adaptation-steps") && !oc.isDefault("device.rerouting.adaptation-weight")) {
110 0 : WRITE_ERROR(TL("Only one of the options 'device.rerouting.adaptation-steps' or 'device.rerouting.adaptation-weight' may be given."));
111 : ok = false;
112 : }
113 78880 : if (oc.getFloat("weights.random-factor") < 1) {
114 0 : WRITE_ERROR(TL("weights.random-factor cannot be less than 1"));
115 : ok = false;
116 : }
117 78880 : if (string2time(oc.getString("device.rerouting.adaptation-interval")) < 0) {
118 14 : WRITE_ERROR(TL("Negative value for device.rerouting.adaptation-interval!"));
119 : ok = false;
120 : }
121 118320 : if (oc.getFloat("device.rerouting.adaptation-weight") < 0. ||
122 118320 : oc.getFloat("device.rerouting.adaptation-weight") > 1.) {
123 0 : WRITE_ERROR(TL("The value for device.rerouting.adaptation-weight must be between 0 and 1!"));
124 : ok = false;
125 : }
126 : #ifndef HAVE_FOX
127 : if (oc.getInt("device.rerouting.threads") > 1) {
128 : WRITE_ERROR(TL("Parallel routing is only possible when compiled with Fox."));
129 : ok = false;
130 : }
131 : #endif
132 43823 : if (oc.getInt("threads") > 1 && oc.getInt("device.rerouting.threads") > 1 && oc.getInt("threads") != oc.getInt("device.rerouting.threads")) {
133 18 : WRITE_WARNING(TL("Adapting number of routing threads to number of simulation threads."));
134 : }
135 39440 : return ok;
136 : }
137 :
138 :
139 : void
140 5382025 : MSDevice_Routing::buildVehicleDevices(SUMOVehicle& v, std::vector<MSVehicleDevice*>& into) {
141 5382025 : const OptionsCont& oc = OptionsCont::getOptions();
142 5382025 : const bool equip = equippedByDefaultAssignmentOptions(oc, "rerouting", v, false);
143 5382019 : if (v.getParameter().wasSet(VEHPARS_FORCE_REROUTE) || equip) {
144 : // route computation is enabled
145 : // for implicitly equipped vehicles (trips, flows), option probability
146 : // can still be used to disable periodic rerouting after insertion for
147 : // parts of the fleet
148 1407395 : const SUMOTime period = (equip || (
149 2813822 : oc.isDefault("device.rerouting.probability") &&
150 4388713 : v.getFloatParam("device.rerouting.probability") == oc.getFloat("device.rerouting.probability"))
151 4558075 : ? v.getTimeParam("device.rerouting.period") : 0);
152 1575859 : const SUMOTime prePeriod = MAX2((SUMOTime)0, v.getTimeParam("device.rerouting.pre-period"));
153 1575859 : MSRoutingEngine::initWeightUpdate();
154 : // build the device
155 3151718 : into.push_back(new MSDevice_Routing(v, "routing_" + v.getID(), period, prePeriod));
156 : }
157 5382019 : }
158 :
159 :
160 : // ---------------------------------------------------------------------------
161 : // MSDevice_Routing-methods
162 : // ---------------------------------------------------------------------------
163 1575859 : MSDevice_Routing::MSDevice_Routing(SUMOVehicle& holder, const std::string& id,
164 1575859 : SUMOTime period, SUMOTime preInsertionPeriod) :
165 : MSVehicleDevice(holder, id),
166 1575859 : myPeriod(period),
167 1575859 : myPreInsertionPeriod(preInsertionPeriod),
168 1575859 : myLastRouting(-1),
169 1575859 : mySkipRouting(-1),
170 1575859 : myRerouteCommand(nullptr),
171 1575859 : myRerouteRailSignal(holder.getBoolParam("device.rerouting.railsignal", true)),
172 1575859 : myLastLaneEntryTime(-1),
173 1575859 : myRerouteAfterStop(false),
174 1575859 : myThresholdFactor(holder.getFloatParam("device.rerouting.threshold.factor", true, 1)),
175 1575859 : myThresholdTime(STEPS2TIME(holder.getTimeParam("device.rerouting.threshold.constant", true, 0))),
176 1575859 : myActive(true) {
177 1575859 : if (myPreInsertionPeriod > 0 || holder.getParameter().wasSet(VEHPARS_FORCE_REROUTE)) {
178 : // 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")
179 1575029 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::preInsertionReroute);
180 : // if we don't update the edge weights, we might as well reroute now and hopefully use our threads better
181 1575029 : const SUMOTime execTime = MSRoutingEngine::hasEdgeUpdates() ? holder.getParameter().depart : -1;
182 1575029 : MSNet::getInstance()->getInsertionEvents()->addEvent(myRerouteCommand, execTime);
183 : }
184 1575859 : }
185 :
186 :
187 3151704 : MSDevice_Routing::~MSDevice_Routing() {
188 : // make the rerouting command invalid if there is one
189 1575852 : if (myRerouteCommand != nullptr) {
190 : myRerouteCommand->deschedule();
191 : }
192 3151704 : }
193 :
194 :
195 : bool
196 1002987 : MSDevice_Routing::notifyEnter(SUMOTrafficObject& /*veh*/, MSMoveReminder::Notification reason, const MSLane* enteredLane) {
197 1002987 : if (reason == MSMoveReminder::NOTIFICATION_DEPARTED) {
198 969965 : if (myRerouteCommand == nullptr && myPreInsertionPeriod > 0 && myHolder.getDepartDelay() > myPreInsertionPeriod) {
199 : // pre-insertion rerouting was disabled. Reroute once if insertion was delayed
200 : // this is happening in the run thread (not inbeginOfTimestepEvents) so we cannot safely use the threadPool
201 1321074 : myHolder.reroute(MSNet::getInstance()->getCurrentTimeStep(), "device.rerouting",
202 880716 : MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass()),
203 : false, MSRoutingEngine::withTaz(), false);
204 : }
205 : // build repetition trigger if routing shall be done more often
206 969965 : rebuildRerouteCommand(SIMSTEP + myPeriod);
207 : }
208 1002987 : if (MSGlobals::gWeightsSeparateTurns > 0) {
209 36105 : if (reason == MSMoveReminder::NOTIFICATION_JUNCTION) {
210 31105 : const SUMOTime t = SIMSTEP;
211 31105 : if (myLastLaneEntryTime >= 0 && enteredLane->isInternal()) {
212 : // record travel time on the previous edge but store on the internal ledge
213 11090 : MSRoutingEngine::addEdgeTravelTime(enteredLane->getEdge(), t - myLastLaneEntryTime);
214 : }
215 31105 : myLastLaneEntryTime = t;
216 : }
217 36105 : return true;
218 : } else {
219 : return false;
220 : }
221 : }
222 :
223 :
224 : void
225 0 : MSDevice_Routing::notifyStopEnded() {
226 0 : if (myRerouteAfterStop) {
227 0 : reroute(SIMSTEP);
228 0 : myRerouteAfterStop = false;
229 : }
230 0 : }
231 :
232 :
233 : void
234 971926 : MSDevice_Routing::rebuildRerouteCommand(SUMOTime start) {
235 971926 : if (myRerouteCommand != nullptr) {
236 : myRerouteCommand->deschedule();
237 220316 : myRerouteCommand = nullptr;
238 : }
239 971926 : if (myPeriod > 0) {
240 56715 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::wrappedRerouteCommandExecute);
241 113430 : if (OptionsCont::getOptions().getBool("device.rerouting.synchronize")) {
242 1584 : start -= start % myPeriod;
243 : }
244 : // ensure stable sorting of events (for repeatable routing with randomness)
245 56715 : myRerouteCommand->priority = (int)myHolder.getNumericalID();
246 56715 : MSNet::getInstance()->getBeginOfTimestepEvents()->addEvent(myRerouteCommand, start);
247 : }
248 971926 : }
249 :
250 :
251 : SUMOTime
252 19646434 : MSDevice_Routing::preInsertionReroute(const SUMOTime currentTime) {
253 19646434 : if (mySkipRouting == currentTime) {
254 17474427 : return DELTA_T;
255 : }
256 2172007 : if (myPreInsertionPeriod == 0) {
257 : // the event will deschedule and destroy itself so it does not need to be stored
258 496 : myRerouteCommand = nullptr;
259 : }
260 2172007 : const MSEdge* source = *myHolder.getRoute().begin();
261 2172007 : const MSEdge* dest = myHolder.getRoute().getLastEdge();
262 2172007 : if (source->isTazConnector() && dest->isTazConnector()) {
263 583669 : ConstMSRoutePtr cached = MSRoutingEngine::getCachedRoute(std::make_pair(source, dest));
264 583669 : if (cached != nullptr && cached->size() > 2) {
265 0 : myHolder.replaceRoute(cached, "device.rerouting", true);
266 0 : return myPreInsertionPeriod;
267 : }
268 : }
269 : try {
270 : std::string msg;
271 2172007 : if (myHolder.hasValidRouteStart(msg)) {
272 2171986 : reroute(currentTime, true);
273 : }
274 116 : } catch (ProcessError&) {
275 116 : myRerouteCommand = nullptr;
276 116 : throw;
277 116 : }
278 : // avoid repeated pre-insertion rerouting when the departure edge is fix and
279 : // the departure lane does not depend on the route
280 2171891 : if (myPreInsertionPeriod > 0 && !source->isTazConnector() && myHolder.getParameter().departLaneProcedure != DepartLaneDefinition::BEST_FREE) {
281 1088384 : myRerouteCommand = nullptr;
282 1088384 : return 0;
283 : }
284 1083507 : return myPreInsertionPeriod;
285 : }
286 :
287 :
288 : SUMOTime
289 174829 : MSDevice_Routing::wrappedRerouteCommandExecute(SUMOTime currentTime) {
290 174829 : if (myHolder.isStopped()) {
291 19485 : myRerouteAfterStop = true;
292 : } else {
293 155344 : reroute(currentTime);
294 : }
295 174829 : return myPeriod;
296 : }
297 :
298 :
299 : void
300 2327330 : MSDevice_Routing::reroute(const SUMOTime currentTime, const bool onInit) {
301 2327330 : MSRoutingEngine::initEdgeWeights(myHolder.getVClass());
302 : //check whether the weights did change since the last reroute
303 2327330 : if (myLastRouting >= MSRoutingEngine::getLastAdaptation() || !myActive) {
304 : return;
305 : }
306 2325697 : myLastRouting = currentTime;
307 4651394 : MSRoutingEngine::reroute(myHolder, currentTime, "device.rerouting", onInit);
308 : }
309 :
310 :
311 : bool
312 593330 : MSDevice_Routing::sufficientSaving(double oldCost, double newCost) {
313 593330 : if (newCost == 0) {
314 : return true;
315 : }
316 593116 : return (oldCost / newCost > myThresholdFactor) && (oldCost - newCost > myThresholdTime);
317 : }
318 :
319 :
320 : std::string
321 36 : MSDevice_Routing::getParameter(const std::string& key) const {
322 72 : if (StringUtils::startsWith(key, "edge:")) {
323 18 : const std::string edgeID = key.substr(5);
324 18 : const MSEdge* edge = MSEdge::dictionary(edgeID);
325 18 : if (edge == nullptr) {
326 0 : throw InvalidArgument("Edge '" + edgeID + "' is invalid for parameter retrieval of '" + deviceName() + "'");
327 : }
328 18 : return toString(MSRoutingEngine::getEffort(edge, &myHolder, 0));
329 18 : } else if (key == "period") {
330 18 : return time2string(myPeriod);
331 : }
332 0 : throw InvalidArgument("Parameter '" + key + "' is not supported for device of type '" + deviceName() + "'");
333 : }
334 :
335 :
336 : void
337 33 : MSDevice_Routing::setParameter(const std::string& key, const std::string& value) {
338 : double doubleValue;
339 : try {
340 33 : doubleValue = StringUtils::toDouble(value);
341 0 : } catch (NumberFormatException&) {
342 0 : throw InvalidArgument("Setting parameter '" + key + "' requires a number for device of type '" + deviceName() + "'");
343 0 : }
344 66 : if (StringUtils::startsWith(key, "edge:")) {
345 9 : const std::string edgeID = key.substr(5);
346 9 : const MSEdge* edge = MSEdge::dictionary(edgeID);
347 9 : if (edge == nullptr) {
348 0 : throw InvalidArgument("Edge '" + edgeID + "' is invalid for parameter setting of '" + deviceName() + "'");
349 : }
350 9 : MSRoutingEngine::setEdgeTravelTime(edge, doubleValue);
351 24 : } else if (key == "period") {
352 24 : myPeriod = TIME2STEPS(doubleValue);
353 : // re-schedule routing command
354 24 : rebuildRerouteCommand(SIMSTEP + myPeriod);
355 : } else {
356 0 : throw InvalidArgument("Setting parameter '" + key + "' is not supported for device of type '" + deviceName() + "'");
357 : }
358 33 : }
359 :
360 :
361 : void
362 3236 : MSDevice_Routing::saveState(OutputDevice& out) const {
363 3236 : out.openTag(SUMO_TAG_DEVICE);
364 3236 : out.writeAttr(SUMO_ATTR_ID, getID());
365 : std::vector<std::string> internals;
366 3236 : internals.push_back(toString(myPeriod));
367 3236 : internals.push_back(toString(myLastRouting));
368 3236 : out.writeAttr(SUMO_ATTR_STATE, toString(internals));
369 3236 : out.closeTag();
370 3236 : }
371 :
372 :
373 : void
374 4814 : MSDevice_Routing::loadState(const SUMOSAXAttributes& attrs) {
375 4814 : std::istringstream bis(attrs.getString(SUMO_ATTR_STATE));
376 4814 : bis >> myPeriod;
377 4814 : bis >> myLastRouting;
378 4814 : if (myHolder.hasDeparted()) {
379 1937 : SUMOTime offset = myPeriod;
380 1937 : if (myPeriod > 0) {
381 805 : offset = ((SIMSTEP - myHolder.getDeparture()) % myPeriod);
382 805 : if (offset != 0) {
383 783 : offset = myPeriod - offset;
384 : }
385 : }
386 1937 : rebuildRerouteCommand(SIMSTEP + offset);
387 : }
388 4814 : }
389 :
390 :
391 : /****************************************************************************/
|
