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 41591 : MSDevice_Routing::insertOptions(OptionsCont& oc) {
49 83182 : insertDefaultAssignmentOptions("rerouting", "Routing", oc);
50 :
51 83182 : oc.doRegister("device.rerouting.period", new Option_String("0", "TIME"));
52 83182 : oc.addSynonyme("device.rerouting.period", "device.routing.period", true);
53 83182 : oc.addDescription("device.rerouting.period", "Routing", TL("The period with which the vehicle shall be rerouted"));
54 :
55 83182 : oc.doRegister("device.rerouting.pre-period", new Option_String("60", "TIME"));
56 83182 : oc.addSynonyme("device.rerouting.pre-period", "device.routing.pre-period", true);
57 83182 : oc.addDescription("device.rerouting.pre-period", "Routing", TL("The rerouting period before depart"));
58 :
59 41591 : oc.doRegister("device.rerouting.adaptation-weight", new Option_Float(0));
60 83182 : oc.addSynonyme("device.rerouting.adaptation-weight", "device.routing.adaptation-weight", true);
61 83182 : oc.addDescription("device.rerouting.adaptation-weight", "Routing", TL("The weight of prior edge weights for exponential moving average"));
62 :
63 41591 : oc.doRegister("device.rerouting.adaptation-steps", new Option_Integer(180));
64 83182 : oc.addSynonyme("device.rerouting.adaptation-steps", "device.routing.adaptation-steps", true);
65 83182 : oc.addDescription("device.rerouting.adaptation-steps", "Routing", TL("The number of steps for moving average weight of prior edge weights"));
66 :
67 83182 : oc.doRegister("device.rerouting.adaptation-interval", new Option_String("1", "TIME"));
68 83182 : oc.addSynonyme("device.rerouting.adaptation-interval", "device.routing.adaptation-interval", true);
69 83182 : oc.addDescription("device.rerouting.adaptation-interval", "Routing", TL("The interval for updating the edge weights"));
70 :
71 41591 : oc.doRegister("device.rerouting.threshold.factor", new Option_Float(1));
72 83182 : 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 83182 : oc.doRegister("device.rerouting.threshold.constant", new Option_String("0", "TIME"));
75 83182 : 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 41591 : oc.doRegister("device.rerouting.with-taz", new Option_Bool(false));
78 83182 : oc.addSynonyme("device.rerouting.with-taz", "device.routing.with-taz", true);
79 83182 : oc.addSynonyme("device.rerouting.with-taz", "with-taz");
80 83182 : oc.addDescription("device.rerouting.with-taz", "Routing", TL("Use zones (districts) as routing start- and endpoints"));
81 :
82 83182 : oc.doRegister("device.rerouting.mode", new Option_String("0"));
83 83182 : oc.addDescription("device.rerouting.mode", "Routing", TL("Set routing flags (8 ignores temporary blockages)"));
84 :
85 41591 : oc.doRegister("device.rerouting.init-with-loaded-weights", new Option_Bool(false));
86 83182 : oc.addDescription("device.rerouting.init-with-loaded-weights", "Routing", TL("Use weight files given with option --weight-files for initializing edge weights"));
87 :
88 41591 : oc.doRegister("device.rerouting.threads", new Option_Integer(0));
89 83182 : oc.addSynonyme("device.rerouting.threads", "routing-threads");
90 83182 : oc.addDescription("device.rerouting.threads", "Routing", TL("The number of parallel execution threads used for rerouting"));
91 :
92 41591 : oc.doRegister("device.rerouting.synchronize", new Option_Bool(false));
93 83182 : oc.addDescription("device.rerouting.synchronize", "Routing", TL("Let rerouting happen at the same time for all vehicles"));
94 :
95 41591 : oc.doRegister("device.rerouting.railsignal", new Option_Bool(false));
96 83182 : oc.addDescription("device.rerouting.railsignal", "Routing", TL("Allow rerouting triggered by rail signals."));
97 :
98 41591 : oc.doRegister("device.rerouting.bike-speeds", new Option_Bool(false));
99 83182 : oc.addDescription("device.rerouting.bike-speeds", "Routing", TL("Compute separate average speeds for bicycles"));
100 :
101 41591 : oc.doRegister("device.rerouting.output", new Option_FileName());
102 83182 : oc.addDescription("device.rerouting.output", "Routing", TL("Save adapting weights to FILE"));
103 41591 : }
104 :
105 :
106 : bool
107 40712 : MSDevice_Routing::checkOptions(OptionsCont& oc) {
108 : bool ok = true;
109 41038 : 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 81424 : 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 81424 : 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 122136 : if (oc.getFloat("device.rerouting.adaptation-weight") < 0. ||
122 122136 : 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 45104 : 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 40712 : return ok;
136 : }
137 :
138 :
139 : void
140 5336332 : MSDevice_Routing::buildVehicleDevices(SUMOVehicle& v, std::vector<MSVehicleDevice*>& into) {
141 5336332 : const OptionsCont& oc = OptionsCont::getOptions();
142 5336332 : const bool equip = equippedByDefaultAssignmentOptions(oc, "rerouting", v, false);
143 5336326 : 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 1383694 : const SUMOTime period = (equip || (
149 2766420 : oc.isDefault("device.rerouting.probability") &&
150 4317659 : v.getFloatParam("device.rerouting.probability") == oc.getFloat("device.rerouting.probability"))
151 4487070 : ? v.getTimeParam("device.rerouting.period") : 0);
152 1552207 : const SUMOTime prePeriod = MAX2((SUMOTime)0, v.getTimeParam("device.rerouting.pre-period"));
153 1552207 : MSRoutingEngine::initWeightUpdate();
154 : // build the device
155 3104414 : into.push_back(new MSDevice_Routing(v, "routing_" + v.getID(), period, prePeriod));
156 : }
157 5336326 : }
158 :
159 :
160 : // ---------------------------------------------------------------------------
161 : // MSDevice_Routing-methods
162 : // ---------------------------------------------------------------------------
163 1552207 : MSDevice_Routing::MSDevice_Routing(SUMOVehicle& holder, const std::string& id,
164 1552207 : SUMOTime period, SUMOTime preInsertionPeriod) :
165 : MSVehicleDevice(holder, id),
166 1552207 : myPeriod(period),
167 1552207 : myPreInsertionPeriod(preInsertionPeriod),
168 1552207 : myLastRouting(-1),
169 1552207 : mySkipRouting(-1),
170 1552207 : myRerouteCommand(nullptr),
171 1552207 : myRerouteRailSignal(holder.getBoolParam("device.rerouting.railsignal", true)),
172 1552207 : myLastLaneEntryTime(-1),
173 1552207 : myRerouteAfterStop(false),
174 1552207 : myThresholdFactor(holder.getFloatParam("device.rerouting.threshold.factor", true, 1)),
175 1552207 : myThresholdTime(STEPS2TIME(holder.getTimeParam("device.rerouting.threshold.constant", true, 0))),
176 1552207 : myActive(true) {
177 1552207 : 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 1551328 : 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 1551328 : const SUMOTime execTime = MSRoutingEngine::hasEdgeUpdates() ? holder.getParameter().depart : -1;
182 1551328 : MSNet::getInstance()->getInsertionEvents()->addEvent(myRerouteCommand, execTime);
183 : }
184 1552207 : }
185 :
186 :
187 3104390 : MSDevice_Routing::~MSDevice_Routing() {
188 : // make the rerouting command invalid if there is one
189 1552195 : if (myRerouteCommand != nullptr) {
190 : myRerouteCommand->deschedule();
191 : }
192 3104390 : }
193 :
194 :
195 : bool
196 1290306 : MSDevice_Routing::notifyEnter(SUMOTrafficObject& /*veh*/, MSMoveReminder::Notification reason, const MSLane* enteredLane) {
197 1290306 : if (reason == MSMoveReminder::NOTIFICATION_DEPARTED) {
198 1257285 : 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 2187642 : myHolder.reroute(MSNet::getInstance()->getCurrentTimeStep(), "device.rerouting",
202 1458428 : MSRoutingEngine::getRouterTT(myHolder.getRNGIndex(), myHolder.getVClass()),
203 : false, MSRoutingEngine::withTaz(), false);
204 : }
205 : // build repetition trigger if routing shall be done more often
206 1257285 : rebuildRerouteCommand(SIMSTEP + myPeriod);
207 : }
208 1290306 : 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 1259246 : MSDevice_Routing::rebuildRerouteCommand(SUMOTime start) {
235 1259246 : if (myRerouteCommand != nullptr) {
236 : myRerouteCommand->deschedule();
237 218456 : myRerouteCommand = nullptr;
238 : }
239 1259246 : if (myPeriod > 0) {
240 56709 : myRerouteCommand = new WrappingCommand<MSDevice_Routing>(this, &MSDevice_Routing::wrappedRerouteCommandExecute);
241 113418 : if (OptionsCont::getOptions().getBool("device.rerouting.synchronize")) {
242 1578 : start -= start % myPeriod;
243 : }
244 : // ensure stable sorting of events (for repeatable routing with randomness)
245 56709 : myRerouteCommand->priority = (int)myHolder.getNumericalID();
246 56709 : MSNet::getInstance()->getBeginOfTimestepEvents()->addEvent(myRerouteCommand, start);
247 : }
248 1259246 : }
249 :
250 :
251 : SUMOTime
252 19684355 : MSDevice_Routing::preInsertionReroute(const SUMOTime currentTime) {
253 19684355 : if (mySkipRouting == currentTime) {
254 17511435 : return DELTA_T;
255 : }
256 2172920 : 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 2172920 : const MSEdge* source = *myHolder.getRoute().begin();
261 2172920 : const MSEdge* dest = myHolder.getRoute().getLastEdge();
262 2172920 : if (source->isTazConnector() && dest->isTazConnector()) {
263 567361 : ConstMSRoutePtr cached = MSRoutingEngine::getCachedRoute(std::make_pair(source, dest));
264 567361 : 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 2172920 : if (myHolder.hasValidRouteStart(msg)) {
272 2172899 : reroute(currentTime, true);
273 : }
274 115 : } catch (ProcessError&) {
275 115 : myRerouteCommand = nullptr;
276 115 : throw;
277 115 : }
278 : // avoid repeated pre-insertion rerouting when the departure edge is fix and
279 : // the departure lane does not depend on the route
280 2172805 : if (myPreInsertionPeriod > 0 && !source->isTazConnector() && myHolder.getParameter().departLaneProcedure != DepartLaneDefinition::BEST_FREE) {
281 1078286 : myRerouteCommand = nullptr;
282 1078286 : return 0;
283 : }
284 1094519 : return myPreInsertionPeriod;
285 : }
286 :
287 :
288 : SUMOTime
289 174852 : MSDevice_Routing::wrappedRerouteCommandExecute(SUMOTime currentTime) {
290 174852 : if (myHolder.isStopped()) {
291 19532 : myRerouteAfterStop = true;
292 : } else {
293 155320 : reroute(currentTime);
294 : }
295 174852 : return myPeriod;
296 : }
297 :
298 :
299 : void
300 2328219 : MSDevice_Routing::reroute(const SUMOTime currentTime, const bool onInit) {
301 2328219 : MSRoutingEngine::initEdgeWeights(myHolder.getVClass());
302 : //check whether the weights did change since the last reroute
303 2328219 : if (myLastRouting >= MSRoutingEngine::getLastAdaptation() || !myActive) {
304 : return;
305 : }
306 2326602 : myLastRouting = currentTime;
307 4653204 : MSRoutingEngine::reroute(myHolder, currentTime, "device.rerouting", onInit);
308 : }
309 :
310 :
311 : bool
312 882162 : MSDevice_Routing::sufficientSaving(double oldCost, double newCost) {
313 882162 : if (newCost == 0) {
314 : return true;
315 : }
316 881948 : 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 3234 : MSDevice_Routing::saveState(OutputDevice& out) const {
363 3234 : out.openTag(SUMO_TAG_DEVICE);
364 3234 : out.writeAttr(SUMO_ATTR_ID, getID());
365 : std::vector<std::string> internals;
366 3234 : internals.push_back(toString(myPeriod));
367 3234 : internals.push_back(toString(myLastRouting));
368 3234 : out.writeAttr(SUMO_ATTR_STATE, toString(internals));
369 3234 : out.closeTag();
370 3234 : }
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 802 : offset = ((SIMSTEP - myHolder.getDeparture()) % myPeriod);
382 802 : if (offset != 0) {
383 780 : offset = myPeriod - offset;
384 : }
385 : }
386 1937 : rebuildRerouteCommand(SIMSTEP + offset);
387 : }
388 4814 : }
389 :
390 :
391 : /****************************************************************************/
|
