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 44603 : MSDevice_Routing::insertOptions(OptionsCont& oc) {
49 89206 : insertDefaultAssignmentOptions("rerouting", "Routing", oc);
50 :
51 89206 : oc.doRegister("device.rerouting.period", new Option_String("0", "TIME"));
52 89206 : oc.addSynonyme("device.rerouting.period", "device.routing.period", true);
53 89206 : oc.addDescription("device.rerouting.period", "Routing", TL("The period with which the vehicle shall be rerouted"));
54 :
55 89206 : oc.doRegister("device.rerouting.pre-period", new Option_String("60", "TIME"));
56 89206 : oc.addSynonyme("device.rerouting.pre-period", "device.routing.pre-period", true);
57 89206 : oc.addDescription("device.rerouting.pre-period", "Routing", TL("The rerouting period before depart"));
58 :
59 44603 : oc.doRegister("device.rerouting.adaptation-weight", new Option_Float(0));
60 89206 : oc.addSynonyme("device.rerouting.adaptation-weight", "device.routing.adaptation-weight", true);
61 89206 : oc.addDescription("device.rerouting.adaptation-weight", "Routing", TL("The weight of prior edge weights for exponential moving average"));
62 :
63 44603 : oc.doRegister("device.rerouting.adaptation-steps", new Option_Integer(180));
64 89206 : oc.addSynonyme("device.rerouting.adaptation-steps", "device.routing.adaptation-steps", true);
65 89206 : oc.addDescription("device.rerouting.adaptation-steps", "Routing", TL("The number of steps for moving average weight of prior edge weights"));
66 :
67 89206 : oc.doRegister("device.rerouting.adaptation-interval", new Option_String("1", "TIME"));
68 89206 : oc.addSynonyme("device.rerouting.adaptation-interval", "device.routing.adaptation-interval", true);
69 89206 : oc.addDescription("device.rerouting.adaptation-interval", "Routing", TL("The interval for updating the edge weights"));
70 :
71 44603 : oc.doRegister("device.rerouting.threshold.factor", new Option_Float(1));
72 89206 : 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 89206 : oc.doRegister("device.rerouting.threshold.constant", new Option_String("0", "TIME"));
75 89206 : 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 44603 : oc.doRegister("device.rerouting.with-taz", new Option_Bool(false));
78 89206 : oc.addSynonyme("device.rerouting.with-taz", "device.routing.with-taz", true);
79 89206 : oc.addSynonyme("device.rerouting.with-taz", "with-taz");
80 89206 : oc.addDescription("device.rerouting.with-taz", "Routing", TL("Use zones (districts) as routing start- and endpoints"));
81 :
82 89206 : oc.doRegister("device.rerouting.mode", new Option_String("0"));
83 89206 : oc.addDescription("device.rerouting.mode", "Routing", TL("Set routing flags (8 ignores temporary blockages)"));
84 :
85 44603 : oc.doRegister("device.rerouting.init-with-loaded-weights", new Option_Bool(false));
86 89206 : oc.addDescription("device.rerouting.init-with-loaded-weights", "Routing", TL("Use weight files given with option --weight-files for initializing edge weights"));
87 :
88 44603 : oc.doRegister("device.rerouting.threads", new Option_Integer(0));
89 89206 : oc.addSynonyme("device.rerouting.threads", "routing-threads");
90 89206 : oc.addDescription("device.rerouting.threads", "Routing", TL("The number of parallel execution threads used for rerouting"));
91 :
92 44603 : oc.doRegister("device.rerouting.synchronize", new Option_Bool(false));
93 89206 : oc.addDescription("device.rerouting.synchronize", "Routing", TL("Let rerouting happen at the same time for all vehicles"));
94 :
95 44603 : oc.doRegister("device.rerouting.railsignal", new Option_Bool(false));
96 89206 : oc.addDescription("device.rerouting.railsignal", "Routing", TL("Allow rerouting triggered by rail signals."));
97 :
98 44603 : oc.doRegister("device.rerouting.bike-speeds", new Option_Bool(false));
99 89206 : oc.addDescription("device.rerouting.bike-speeds", "Routing", TL("Compute separate average speeds for bicycles"));
100 :
101 44603 : oc.doRegister("device.rerouting.output", new Option_FileName());
102 89206 : oc.addDescription("device.rerouting.output", "Routing", TL("Save adapting weights to FILE"));
103 44603 : }
104 :
105 :
106 : bool
107 43905 : MSDevice_Routing::checkOptions(OptionsCont& oc) {
108 : bool ok = true;
109 44227 : 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 87810 : 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 87810 : 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 131715 : if (oc.getFloat("device.rerouting.adaptation-weight") < 0. ||
122 131715 : 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 48400 : 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 43905 : return ok;
136 : }
137 :
138 :
139 : void
140 5255360 : MSDevice_Routing::buildVehicleDevices(SUMOVehicle& v, std::vector<MSVehicleDevice*>& into) {
141 5255360 : const OptionsCont& oc = OptionsCont::getOptions();
142 5255360 : const bool equip = equippedByDefaultAssignmentOptions(oc, "rerouting", v, false);
143 5255354 : 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 1227226 : const SUMOTime period = (equip || (
149 2453484 : oc.isDefault("device.rerouting.probability") &&
150 3848234 : v.getFloatParam("device.rerouting.probability") == oc.getFloat("device.rerouting.probability"))
151 4017624 : ? v.getTimeParam("device.rerouting.period") : 0);
152 1395718 : const SUMOTime prePeriod = MAX2((SUMOTime)0, v.getTimeParam("device.rerouting.pre-period"));
153 1395718 : MSRoutingEngine::initWeightUpdate();
154 : // build the device
155 2791436 : into.push_back(new MSDevice_Routing(v, "routing_" + v.getID(), period, prePeriod));
156 : }
157 5255354 : }
158 :
159 :
160 : // ---------------------------------------------------------------------------
161 : // MSDevice_Routing-methods
162 : // ---------------------------------------------------------------------------
163 1395718 : MSDevice_Routing::MSDevice_Routing(SUMOVehicle& holder, const std::string& id,
164 1395718 : SUMOTime period, SUMOTime preInsertionPeriod) :
165 : MSVehicleDevice(holder, id),
166 1395718 : myPeriod(period),
167 1395718 : myPreInsertionPeriod(preInsertionPeriod),
168 1395718 : myLastRouting(-1),
169 1395718 : mySkipRouting(-1),
170 1395718 : myRerouteCommand(nullptr),
171 1395718 : myRerouteRailSignal(holder.getBoolParam("device.rerouting.railsignal", true)),
172 1395718 : myLastLaneEntryTime(-1),
173 1395718 : myRerouteAfterStop(false),
174 1395718 : myThresholdFactor(holder.getFloatParam("device.rerouting.threshold.factor", true, 1)),
175 1395718 : myThresholdTime(STEPS2TIME(holder.getTimeParam("device.rerouting.threshold.constant", true, 0))),
176 1395718 : myActive(true) {
177 1395718 : 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 1394888 : 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 1394888 : const SUMOTime execTime = MSRoutingEngine::hasEdgeUpdates() ? holder.getParameter().depart : -1;
182 1394888 : MSNet::getInstance()->getInsertionEvents()->addEvent(myRerouteCommand, execTime);
183 : }
184 1395718 : }
185 :
186 :
187 2791422 : MSDevice_Routing::~MSDevice_Routing() {
188 : // make the rerouting command invalid if there is one
189 1395711 : if (myRerouteCommand != nullptr) {
190 : myRerouteCommand->deschedule();
191 : }
192 2791422 : }
193 :
194 :
195 : bool
196 1155411 : MSDevice_Routing::notifyEnter(SUMOTrafficObject& /*veh*/, MSMoveReminder::Notification reason, const MSLane* enteredLane) {
197 1155411 : if (reason == MSMoveReminder::NOTIFICATION_DEPARTED) {
198 1122604 : 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 1720092 : myHolder.reroute(MSNet::getInstance()->getCurrentTimeStep(), "device.rerouting",
202 1146728 : MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass()),
203 : true, MSRoutingEngine::withTaz(), false);
204 : }
205 : // build repetition trigger if routing shall be done more often
206 1122604 : rebuildRerouteCommand(SIMSTEP + myPeriod);
207 : }
208 1155411 : if (MSGlobals::gWeightsSeparateTurns > 0 && enteredLane != nullptr) {
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 266 : MSDevice_Routing::notifyStopEnded() {
226 266 : if (myRerouteAfterStop) {
227 257 : reroute(SIMSTEP);
228 257 : myRerouteAfterStop = false;
229 : }
230 266 : }
231 :
232 :
233 : void
234 1124347 : MSDevice_Routing::rebuildRerouteCommand(SUMOTime start) {
235 1124347 : if (myRerouteCommand != nullptr) {
236 : myRerouteCommand->deschedule();
237 225790 : myRerouteCommand = nullptr;
238 : }
239 1124347 : if (myPeriod > 0) {
240 56711 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::wrappedRerouteCommandExecute);
241 113422 : if (OptionsCont::getOptions().getBool("device.rerouting.synchronize")) {
242 1580 : start -= start % myPeriod;
243 : }
244 : // ensure stable sorting of events (for repeatable routing with randomness)
245 56711 : myRerouteCommand->priority = (int)myHolder.getNumericalID();
246 56711 : MSNet::getInstance()->getBeginOfTimestepEvents()->addEvent(myRerouteCommand, start);
247 : }
248 1124347 : }
249 :
250 :
251 : SUMOTime
252 61815974 : MSDevice_Routing::preInsertionReroute(const SUMOTime currentTime) {
253 61815974 : if (mySkipRouting == currentTime) {
254 59704001 : return DELTA_T;
255 : }
256 2111973 : 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 2111973 : const MSEdge* source = *myHolder.getRoute().begin();
261 2111973 : const MSEdge* dest = myHolder.getRoute().getLastEdge();
262 2111973 : if (source->isTazConnector() && dest->isTazConnector()) {
263 465800 : ConstMSRoutePtr cached = MSRoutingEngine::getCachedRoute(std::make_pair(source, dest));
264 465800 : 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 2111973 : if (myHolder.hasValidRouteStart(msg)) {
272 2111952 : reroute(currentTime, true);
273 : }
274 95 : } catch (ProcessError&) {
275 95 : myRerouteCommand = nullptr;
276 95 : throw;
277 95 : }
278 : // avoid repeated pre-insertion rerouting when the departure edge is fix and
279 : // the departure lane does not depend on the route
280 2111878 : if (myPreInsertionPeriod > 0 && !source->isTazConnector() && myHolder.getParameter().departLaneProcedure != DepartLaneDefinition::BEST_FREE) {
281 915260 : myRerouteCommand = nullptr;
282 915260 : return 0;
283 : }
284 1196618 : return myPreInsertionPeriod;
285 : }
286 :
287 :
288 : SUMOTime
289 180289 : MSDevice_Routing::wrappedRerouteCommandExecute(SUMOTime currentTime) {
290 180289 : if (myHolder.isStopped()) {
291 20772 : myRerouteAfterStop = true;
292 : } else {
293 159517 : reroute(currentTime);
294 : }
295 180289 : return myPeriod;
296 : }
297 :
298 :
299 : void
300 2271726 : MSDevice_Routing::reroute(const SUMOTime currentTime, const bool onInit) {
301 2271726 : MSRoutingEngine::initEdgeWeights(myHolder.getVClass());
302 : //check whether the weights did change since the last reroute
303 2271726 : if (myLastRouting >= MSRoutingEngine::getLastAdaptation() || !myActive) {
304 : return;
305 : }
306 2270084 : myLastRouting = currentTime;
307 4540168 : MSRoutingEngine::reroute(myHolder, currentTime, "device.rerouting", onInit);
308 : }
309 :
310 :
311 : bool
312 157405 : MSDevice_Routing::sufficientSaving(double oldCost, double newCost) {
313 157405 : if (newCost == 0) {
314 : return true;
315 : }
316 157389 : 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 3260 : MSDevice_Routing::saveState(OutputDevice& out) const {
363 3260 : out.openTag(SUMO_TAG_DEVICE);
364 3260 : out.writeAttr(SUMO_ATTR_ID, getID());
365 : std::vector<std::string> internals;
366 3260 : internals.push_back(toString(myPeriod));
367 3260 : internals.push_back(toString(myLastRouting));
368 3260 : out.writeAttr(SUMO_ATTR_STATE, toString(internals));
369 3260 : out.closeTag();
370 3260 : }
371 :
372 :
373 : void
374 3905 : MSDevice_Routing::loadState(const SUMOSAXAttributes& attrs) {
375 3905 : std::istringstream bis(attrs.getString(SUMO_ATTR_STATE));
376 3905 : bis >> myPeriod;
377 3905 : bis >> myLastRouting;
378 3905 : if (myHolder.hasDeparted()) {
379 1719 : SUMOTime offset = myPeriod;
380 1719 : if (myPeriod > 0) {
381 803 : offset = ((SIMSTEP - myHolder.getDeparture()) % myPeriod);
382 803 : if (offset != 0) {
383 781 : offset = myPeriod - offset;
384 : }
385 : }
386 1719 : rebuildRerouteCommand(SIMSTEP + offset);
387 : }
388 3905 : }
389 :
390 :
391 : /****************************************************************************/
|
