Eclipse SUMO - Simulation of Urban MObility
MSDevice_Routing.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2007-2022 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 /****************************************************************************/
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>
31 #include <microsim/MSGlobals.h>
38 #include "MSRoutingEngine.h"
39 #include "MSDevice_Routing.h"
40 
41 
42 // ===========================================================================
43 // method definitions
44 // ===========================================================================
45 // ---------------------------------------------------------------------------
46 // static initialisation methods
47 // ---------------------------------------------------------------------------
48 void
50  insertDefaultAssignmentOptions("rerouting", "Routing", oc);
51 
52  oc.doRegister("device.rerouting.period", new Option_String("0", "TIME"));
53  oc.addSynonyme("device.rerouting.period", "device.routing.period", true);
54  oc.addDescription("device.rerouting.period", "Routing", "The period with which the vehicle shall be rerouted");
55 
56  oc.doRegister("device.rerouting.pre-period", new Option_String("60", "TIME"));
57  oc.addSynonyme("device.rerouting.pre-period", "device.routing.pre-period", true);
58  oc.addDescription("device.rerouting.pre-period", "Routing", "The rerouting period before depart");
59 
60  oc.doRegister("device.rerouting.adaptation-weight", new Option_Float(0));
61  oc.addSynonyme("device.rerouting.adaptation-weight", "device.routing.adaptation-weight", true);
62  oc.addDescription("device.rerouting.adaptation-weight", "Routing", "The weight of prior edge weights for exponential moving average");
63 
64  oc.doRegister("device.rerouting.adaptation-steps", new Option_Integer(180));
65  oc.addSynonyme("device.rerouting.adaptation-steps", "device.routing.adaptation-steps", true);
66  oc.addDescription("device.rerouting.adaptation-steps", "Routing", "The number of steps for moving average weight of prior edge weights");
67 
68  oc.doRegister("device.rerouting.adaptation-interval", new Option_String("1", "TIME"));
69  oc.addSynonyme("device.rerouting.adaptation-interval", "device.routing.adaptation-interval", true);
70  oc.addDescription("device.rerouting.adaptation-interval", "Routing", "The interval for updating the edge weights");
71 
72  oc.doRegister("device.rerouting.with-taz", new Option_Bool(false));
73  oc.addSynonyme("device.rerouting.with-taz", "device.routing.with-taz", true);
74  oc.addSynonyme("device.rerouting.with-taz", "with-taz");
75  oc.addDescription("device.rerouting.with-taz", "Routing", "Use zones (districts) as routing start- and endpoints");
76 
77  oc.doRegister("device.rerouting.init-with-loaded-weights", new Option_Bool(false));
78  oc.addDescription("device.rerouting.init-with-loaded-weights", "Routing", "Use weight files given with option --weight-files for initializing edge weights");
79 
80  oc.doRegister("device.rerouting.threads", new Option_Integer(0));
81  oc.addSynonyme("device.rerouting.threads", "routing-threads");
82  oc.addDescription("device.rerouting.threads", "Routing", "The number of parallel execution threads used for rerouting");
83 
84  oc.doRegister("device.rerouting.synchronize", new Option_Bool(false));
85  oc.addDescription("device.rerouting.synchronize", "Routing", "Let rerouting happen at the same time for all vehicles");
86 
87  oc.doRegister("device.rerouting.railsignal", new Option_Bool(true));
88  oc.addDescription("device.rerouting.railsignal", "Routing", "Allow rerouting triggered by rail signals.");
89 
90  oc.doRegister("device.rerouting.bike-speeds", new Option_Bool(false));
91  oc.addDescription("device.rerouting.bike-speeds", "Routing", "Compute separate average speeds for bicycles");
92 
93  oc.doRegister("device.rerouting.output", new Option_FileName());
94  oc.addDescription("device.rerouting.output", "Routing", "Save adapting weights to FILE");
95 }
96 
97 
98 bool
100  bool ok = true;
101  if (!oc.isDefault("device.rerouting.adaptation-steps") && !oc.isDefault("device.rerouting.adaptation-weight")) {
102  WRITE_ERROR("Only one of the options 'device.rerouting.adaptation-steps' or 'device.rerouting.adaptation-weight' may be given.");
103  ok = false;
104  }
105  if (oc.getFloat("weights.random-factor") < 1) {
106  WRITE_ERROR("weights.random-factor cannot be less than 1");
107  ok = false;
108  }
109  if (string2time(oc.getString("device.rerouting.adaptation-interval")) < 0) {
110  WRITE_ERROR("Negative value for device.rerouting.adaptation-interval!");
111  ok = false;
112  }
113  if (oc.getFloat("device.rerouting.adaptation-weight") < 0. ||
114  oc.getFloat("device.rerouting.adaptation-weight") > 1.) {
115  WRITE_ERROR("The value for device.rerouting.adaptation-weight must be between 0 and 1!");
116  ok = false;
117  }
118 #ifndef HAVE_FOX
119  if (oc.getInt("device.rerouting.threads") > 1) {
120  WRITE_ERROR("Parallel routing is only possible when compiled with Fox.");
121  ok = false;
122  }
123 #endif
124  if (oc.getInt("threads") > 1 && oc.getInt("device.rerouting.threads") > 1 && oc.getInt("threads") != oc.getInt("device.rerouting.threads")) {
125  WRITE_WARNING("Adapting number of routing threads to number of simulation threads.");
126  }
127  return ok;
128 }
129 
130 
131 void
132 MSDevice_Routing::buildVehicleDevices(SUMOVehicle& v, std::vector<MSVehicleDevice*>& into) {
133  const OptionsCont& oc = OptionsCont::getOptions();
134  const bool equip = equippedByDefaultAssignmentOptions(oc, "rerouting", v, false);
135  if (v.getParameter().wasSet(VEHPARS_FORCE_REROUTE) || equip) {
136  // route computation is enabled
137  // for implicitly equipped vehicles (trips, flows), option probability
138  // can still be used to disable periodic rerouting after insertion for
139  // parts of the fleet
140  const SUMOTime period = equip || oc.isDefault("device.rerouting.probability") ? getTimeParam(v, oc, "rerouting.period", 0, false) : 0;
141  const SUMOTime prePeriod = MAX2((SUMOTime)0, getTimeParam(v, oc, "rerouting.pre-period", string2time(oc.getString("device.rerouting.pre-period")), false));
143  // build the device
144  into.push_back(new MSDevice_Routing(v, "routing_" + v.getID(), period, prePeriod));
145  }
146 }
147 
148 
149 // ---------------------------------------------------------------------------
150 // MSDevice_Routing-methods
151 // ---------------------------------------------------------------------------
152 MSDevice_Routing::MSDevice_Routing(SUMOVehicle& holder, const std::string& id,
153  SUMOTime period, SUMOTime preInsertionPeriod) :
154  MSVehicleDevice(holder, id),
155  myPeriod(period),
156  myPreInsertionPeriod(preInsertionPeriod),
157  myLastRouting(-1),
158  mySkipRouting(-1),
159  myRerouteCommand(nullptr),
160  myRerouteRailSignal(getBoolParam(holder, OptionsCont::getOptions(), "rerouting.railsignal", true, true)),
161  myLastLaneEntryTime(-1) {
163  // 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")
165  // if we don't update the edge weights, we might as well reroute now and hopefully use our threads better
166  const SUMOTime execTime = MSRoutingEngine::hasEdgeUpdates() ? holder.getParameter().depart : -1;
168  }
169 }
170 
171 
173  // make the rerouting command invalid if there is one
174  if (myRerouteCommand != nullptr) {
176  }
177 }
178 
179 
180 bool
183  // clean up pre depart rerouting
184  if (myRerouteCommand != nullptr) {
186  } else if (myPreInsertionPeriod > 0 && myHolder.getDepartDelay() > myPreInsertionPeriod && enteredLane != nullptr) {
187  // pre-insertion rerouting was disabled. Reroute once if insertion was delayed
188  // this is happening in the run thread (not inbeginOfTimestepEvents) so we cannot safely use the threadPool
189  myHolder.reroute(MSNet::getInstance()->getCurrentTimeStep(), "device.rerouting",
191  false, MSRoutingEngine::withTaz(), false);
192  }
193  myRerouteCommand = nullptr;
194  // build repetition trigger if routing shall be done more often
195  if (myPeriod > 0) {
198  if (OptionsCont::getOptions().getBool("device.rerouting.synchronize")) {
199  start -= start % myPeriod;
200  }
202  }
203  }
206  const SUMOTime t = SIMSTEP;
207  if (myLastLaneEntryTime >= 0 && enteredLane->isInternal()) {
208  // record travel time on the previous edge but store on the internal ledge
210  }
212  }
213  return true;
214  } else {
215  return false;
216  }
217 }
218 
219 
220 SUMOTime
222  if (mySkipRouting == currentTime) {
223  return DELTA_T;
224  }
225  if (myPreInsertionPeriod == 0) {
226  // the event will deschedule and destroy itself so it does not need to be stored
227  myRerouteCommand = nullptr;
228  }
229  const MSEdge* source = *myHolder.getRoute().begin();
230  const MSEdge* dest = myHolder.getRoute().getLastEdge();
231  if (source->isTazConnector() && dest->isTazConnector()) {
232  const MSRoute* cached = MSRoutingEngine::getCachedRoute(std::make_pair(source, dest));
233  if (cached != nullptr && cached->size() > 2) {
234  myHolder.replaceRoute(cached, "device.rerouting", true);
235  return myPreInsertionPeriod;
236  }
237  }
238  try {
239  std::string msg;
240  if (myHolder.hasValidRouteStart(msg)) {
241  reroute(currentTime, true);
242  }
243  } catch (ProcessError&) {
244  myRerouteCommand = nullptr;
245  throw;
246  }
247  // avoid repeated pre-insertion rerouting when the departure edge is fix and
248  // the departure lane does not depend on the route
250  myRerouteCommand = nullptr;
251  return 0;
252  }
253  return myPreInsertionPeriod;
254 }
255 
256 
257 SUMOTime
259  reroute(currentTime);
260  return myPeriod;
261 }
262 
263 
264 void
265 MSDevice_Routing::reroute(const SUMOTime currentTime, const bool onInit) {
267  //check whether the weights did change since the last reroute
269  return;
270  }
271  myLastRouting = currentTime;
272  MSRoutingEngine::reroute(myHolder, currentTime, "device.rerouting", onInit);
273 }
274 
275 
276 std::string
277 MSDevice_Routing::getParameter(const std::string& key) const {
278  if (StringUtils::startsWith(key, "edge:")) {
279  const std::string edgeID = key.substr(5);
280  const MSEdge* edge = MSEdge::dictionary(edgeID);
281  if (edge == nullptr) {
282  throw InvalidArgument("Edge '" + edgeID + "' is invalid for parameter retrieval of '" + deviceName() + "'");
283  }
284  return toString(MSRoutingEngine::getEffort(edge, &myHolder, 0));
285  } else if (key == "period") {
286  return time2string(myPeriod);
287  }
288  throw InvalidArgument("Parameter '" + key + "' is not supported for device of type '" + deviceName() + "'");
289 }
290 
291 
292 void
293 MSDevice_Routing::setParameter(const std::string& key, const std::string& value) {
294  double doubleValue;
295  try {
296  doubleValue = StringUtils::toDouble(value);
297  } catch (NumberFormatException&) {
298  throw InvalidArgument("Setting parameter '" + key + "' requires a number for device of type '" + deviceName() + "'");
299  }
300  if (StringUtils::startsWith(key, "edge:")) {
301  const std::string edgeID = key.substr(5);
302  const MSEdge* edge = MSEdge::dictionary(edgeID);
303  if (edge == nullptr) {
304  throw InvalidArgument("Edge '" + edgeID + "' is invalid for parameter setting of '" + deviceName() + "'");
305  }
306  MSRoutingEngine::setEdgeTravelTime(edge, doubleValue);
307  } else if (key == "period") {
308  myPeriod = TIME2STEPS(doubleValue);
309  // re-schedule routing command
311  } else {
312  throw InvalidArgument("Setting parameter '" + key + "' is not supported for device of type '" + deviceName() + "'");
313  }
314 }
315 
316 
317 void
320  out.writeAttr(SUMO_ATTR_ID, getID());
321  std::vector<std::string> internals;
322  internals.push_back(toString(myPeriod));
323  out.writeAttr(SUMO_ATTR_STATE, toString(internals));
324  out.closeTag();
325 }
326 
327 
328 void
330  std::istringstream bis(attrs.getString(SUMO_ATTR_STATE));
331  bis >> myPeriod;
332 }
333 
334 
335 /****************************************************************************/
#define WRITE_ERROR(msg)
Definition: MsgHandler.h:288
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:280
SUMOTime DELTA_T
Definition: SUMOTime.cpp:37
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
SUMOTime string2time(const std::string &r)
convert string to SUMOTime
Definition: SUMOTime.cpp:45
#define SIMSTEP
Definition: SUMOTime.h:59
#define TIME2STEPS(x)
Definition: SUMOTime.h:55
long long int SUMOTime
Definition: SUMOTime.h:32
@ BEST_FREE
The least occupied lane from best lanes.
const int VEHPARS_FORCE_REROUTE
@ SUMO_TAG_DEVICE
@ SUMO_ATTR_ID
@ SUMO_ATTR_STATE
The state of a link.
T MAX2(T a, T b)
Definition: StdDefs.h:80
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:46
const std::string deviceName() const
return the name for this type of device
void saveState(OutputDevice &out) const
Saves the state of the device.
SUMOTime wrappedRerouteCommandExecute(SUMOTime currentTime)
Performs rerouting after a period.
SUMOTime mySkipRouting
The time for which routing may be skipped because we cannot be inserted.
static void insertOptions(OptionsCont &oc)
Inserts MSDevice_Routing-options.
std::string getParameter(const std::string &key) const
try to retrieve the given parameter from this device. Throw exception for unsupported key
bool notifyEnter(SUMOTrafficObject &veh, MSMoveReminder::Notification reason, const MSLane *enteredLane=0)
Computes a new route on vehicle insertion.
SUMOTime myPreInsertionPeriod
The period with which a vehicle shall be rerouted before insertion.
SUMOTime myPeriod
The period with which a vehicle shall be rerouted.
void loadState(const SUMOSAXAttributes &attrs)
Loads the state of the device from the given description.
void reroute(const SUMOTime currentTime, const bool onInit=false)
initiate the rerouting, create router / thread pool on first use
static bool checkOptions(OptionsCont &oc)
checks MSDevice_Routing-options
MSDevice_Routing(SUMOVehicle &holder, const std::string &id, SUMOTime period, SUMOTime preInsertionPeriod)
Constructor.
WrappingCommand< MSDevice_Routing > * myRerouteCommand
The (optional) command responsible for rerouting.
~MSDevice_Routing()
Destructor.
static void buildVehicleDevices(SUMOVehicle &v, std::vector< MSVehicleDevice * > &into)
Build devices for the given vehicle, if needed.
SUMOTime myLastLaneEntryTime
the previous time that a vehicle entered a lane
SUMOTime myLastRouting
The last time a routing took place.
void setParameter(const std::string &key, const std::string &value)
try to set the given parameter for this device. Throw exception for unsupported key
SUMOTime preInsertionReroute(const SUMOTime currentTime)
Performs rerouting before insertion into the network.
static SUMOTime getTimeParam(const SUMOVehicle &v, const OptionsCont &oc, std::string paramName, SUMOTime deflt, bool required)
Definition: MSDevice.cpp:214
static void insertDefaultAssignmentOptions(const std::string &deviceName, const std::string &optionsTopic, OptionsCont &oc, const bool isPerson=false)
Adds common command options that allow to assign devices to vehicles.
Definition: MSDevice.cpp:137
static bool equippedByDefaultAssignmentOptions(const OptionsCont &oc, const std::string &deviceName, DEVICEHOLDER &v, bool outputOptionSet, const bool isPerson=false)
Determines whether a vehicle should get a certain device.
Definition: MSDevice.h:205
A road/street connecting two junctions.
Definition: MSEdge.h:77
bool isTazConnector() const
Definition: MSEdge.h:285
static bool dictionary(const std::string &id, MSEdge *edge)
Inserts edge into the static dictionary Returns true if the key id isn't already in the dictionary....
Definition: MSEdge.cpp:885
virtual void addEvent(Command *operation, SUMOTime execTimeStep=-1)
Adds an Event.
static double gWeightsSeparateTurns
Whether turning specific weights are estimated (and how much)
Definition: MSGlobals.h:160
Representation of a lane in the micro simulation.
Definition: MSLane.h:82
bool isInternal() const
Definition: MSLane.cpp:2122
MSEdge & getEdge() const
Returns the lane's edge.
Definition: MSLane.h:674
Notification
Definition of a vehicle state.
@ NOTIFICATION_DEPARTED
The vehicle has departed (was inserted into the network)
@ NOTIFICATION_JUNCTION
The vehicle arrived at a junction.
static MSNet * getInstance()
Returns the pointer to the unique instance of MSNet (singleton).
Definition: MSNet.cpp:174
SUMOTime getCurrentTimeStep() const
Returns the current simulation step.
Definition: MSNet.h:318
MSEventControl * getInsertionEvents()
Returns the event control for insertion events.
Definition: MSNet.h:489
MSEventControl * getBeginOfTimestepEvents()
Returns the event control for events executed at the begin of a time step.
Definition: MSNet.h:469
int size() const
Returns the number of edges to pass.
Definition: MSRoute.cpp:81
const MSEdge * getLastEdge() const
returns the destination edge
Definition: MSRoute.cpp:87
MSRouteIterator begin() const
Returns the begin of the list of edges to pass.
Definition: MSRoute.cpp:69
static void setEdgeTravelTime(const MSEdge *const edge, const double travelTime)
adapt the known travel time for an edge
static void reroute(SUMOVehicle &vehicle, const SUMOTime currentTime, const std::string &info, const bool onInit=false, const bool silent=false, const MSEdgeVector &prohibited=MSEdgeVector())
initiate the rerouting, create router / thread pool on first use
static SUMOTime getLastAdaptation()
Information when the last edge weight adaptation occurred.
static bool withTaz()
whether taz-routing is enabled
static const MSRoute * getCachedRoute(const std::pair< const MSEdge *, const MSEdge * > &key)
return the cached route or nullptr on miss
static bool hasEdgeUpdates()
returns whether any routing actions take place
static void addEdgeTravelTime(const MSEdge &edge, const SUMOTime travelTime)
record actual travel time for an edge
static void initWeightUpdate()
intialize period edge weight update
static void initEdgeWeights(SUMOVehicleClass svc)
initialize the edge weights if not done before
static SUMOAbstractRouter< MSEdge, SUMOVehicle > & getRouterTT(const int rngIndex, SUMOVehicleClass svc, const MSEdgeVector &prohibited=MSEdgeVector())
return the router instance
static double getEffort(const MSEdge *const e, const SUMOVehicle *const v, double t)
Returns the effort to pass an edge.
Abstract in-vehicle device.
SUMOVehicle & myHolder
The vehicle that stores the device.
const std::string & getID() const
Returns the id.
Definition: Named.h:74
An integer-option.
Definition: Option.h:329
A storage for options typed value containers)
Definition: OptionsCont.h:89
void addDescription(const std::string &name, const std::string &subtopic, const std::string &description)
Adds a description for an option.
void doRegister(const std::string &name, Option *v)
Adds an option under the given name.
Definition: OptionsCont.cpp:75
double getFloat(const std::string &name) const
Returns the double-value of the named option (only for Option_Float)
int getInt(const std::string &name) const
Returns the int-value of the named option (only for Option_Integer)
std::string getString(const std::string &name) const
Returns the string-value of the named option (only for Option_String)
void addSynonyme(const std::string &name1, const std::string &name2, bool isDeprecated=false)
Adds a synonyme for an options name (any order)
Definition: OptionsCont.cpp:96
bool isDefault(const std::string &name) const
Returns the information whether the named option has still the default value.
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:58
Static storage of an output device and its base (abstract) implementation.
Definition: OutputDevice.h:61
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:248
bool closeTag(const std::string &comment="")
Closes the most recently opened tag and optionally adds a comment.
Encapsulated SAX-Attributes.
virtual std::string getString(int id) const =0
Returns the string-value of the named (by its enum-value) attribute.
Representation of a vehicle, person, or container.
virtual SUMOVehicleClass getVClass() const =0
Returns the object's access class.
virtual const SUMOVehicleParameter & getParameter() const =0
Returns the vehicle's parameter (including departure definition)
Representation of a vehicle.
Definition: SUMOVehicle.h:60
virtual const MSRoute & getRoute() const =0
Returns the current route.
virtual void reroute(SUMOTime t, const std::string &info, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, const bool onInit=false, const bool withTaz=false, const bool silent=false)=0
Performs a rerouting using the given router.
virtual int getRNGIndex() const =0
virtual bool replaceRoute(const MSRoute *route, const std::string &info, bool onInit=false, int offset=0, bool addStops=true, bool removeStops=true, std::string *msgReturn=nullptr)=0
Replaces the current route by the given one.
virtual bool hasValidRouteStart(std::string &msg)=0
checks wether the vehicle can depart on the first edge
virtual SUMOTime getDepartDelay() const =0
DepartLaneDefinition departLaneProcedure
Information how the vehicle shall choose the lane to depart from.
bool wasSet(int what) const
Returns whether the given parameter was set.
static double toDouble(const std::string &sData)
converts a string into the double value described by it by calling the char-type converter
static bool startsWith(const std::string &str, const std::string prefix)
Checks whether a given string starts with the prefix.
void deschedule()
Marks this Command as being descheduled.