SUMO - Simulation of Urban MObility
MSRoutingEngine.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-2018 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
19 // A device that performs vehicle rerouting based on current edge speeds
20 /****************************************************************************/
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26 
27 #include "MSRoutingEngine.h"
28 #include <microsim/MSNet.h>
29 #include <microsim/MSLane.h>
30 #include <microsim/MSEdge.h>
31 #include <microsim/MSEdgeControl.h>
33 #include <microsim/MSGlobals.h>
42 #include <utils/vehicle/CHRouter.h>
44 
45 
46 // ===========================================================================
47 // static member variables
48 // ===========================================================================
49 std::vector<double> MSRoutingEngine::myEdgeSpeeds;
50 std::vector<std::vector<double> > MSRoutingEngine::myPastEdgeSpeeds;
61 std::map<std::pair<const MSEdge*, const MSEdge*>, const MSRoute*> MSRoutingEngine::myCachedRoutes;
62 #ifdef HAVE_FOX
63 FXWorkerThread::Pool MSRoutingEngine::myThreadPool;
64 #endif
65 
66 
67 // ===========================================================================
68 // method definitions
69 // ===========================================================================
70 // ---------------------------------------------------------------------------
71 // static initialisation methods
72 // ---------------------------------------------------------------------------
73 void
75  if (myAdaptationInterval == -1) {
77  myEdgeSpeeds.clear();
79  myAdaptationSteps = -1;
80  myLastAdaptation = -1;
82  myWithTaz = oc.getBool("device.rerouting.with-taz");
83  myAdaptationInterval = string2time(oc.getString("device.rerouting.adaptation-interval"));
84  myAdaptationWeight = oc.getFloat("device.rerouting.adaptation-weight");
85  const SUMOTime period = string2time(oc.getString("device.rerouting.period"));
86  if (myAdaptationWeight < 1. && myAdaptationInterval > 0) {
89  } else if (period > 0) {
90  WRITE_WARNING("Rerouting is useless if the edge weights do not get updated!");
91  }
92  OutputDevice::createDeviceByOption("device.rerouting.output", "weights", "meandata_file.xsd");
93  }
94 }
95 
96 // ---------------------------------------------------------------------------
97 // MSRoutingEngine-methods
98 // ---------------------------------------------------------------------------
99 void
101  if (myEdgeSpeeds.empty()) {
102  const OptionsCont& oc = OptionsCont::getOptions();
103  myAdaptationSteps = oc.getInt("device.rerouting.adaptation-steps");
104  const bool useLoaded = oc.getBool("device.rerouting.init-with-loaded-weights");
105  const double currentSecond = SIMTIME;
106  for (const MSEdge* const edge : MSNet::getInstance()->getEdgeControl().getEdges()) {
107  while (edge->getNumericalID() >= (int)myEdgeSpeeds.size()) {
108  myEdgeSpeeds.push_back(0);
109  if (myAdaptationSteps > 0) {
110  myPastEdgeSpeeds.push_back(std::vector<double>());
111  }
112  }
113  if (useLoaded) {
114  myEdgeSpeeds[edge->getNumericalID()] = edge->getLength() / MSNet::getTravelTime(edge, nullptr, currentSecond);
115  } else {
116  myEdgeSpeeds[edge->getNumericalID()] = edge->getMeanSpeed();
117  }
118  if (myAdaptationSteps > 0) {
119  myPastEdgeSpeeds[edge->getNumericalID()] = std::vector<double>(myAdaptationSteps, myEdgeSpeeds[edge->getNumericalID()]);
120  }
121  }
123  myRandomizeWeightsFactor = oc.getFloat("weights.random-factor");
124  }
125 }
126 
127 
128 double
129 MSRoutingEngine::getEffort(const MSEdge* const e, const SUMOVehicle* const v, double) {
130  const int id = e->getNumericalID();
131  if (id < (int)myEdgeSpeeds.size()) {
132  double effort = MAX2(e->getLength() / MAX2(myEdgeSpeeds[id], NUMERICAL_EPS), e->getMinimumTravelTime(v));
133  if (myRandomizeWeightsFactor != 1.) {
135  }
136  return effort;
137  }
138  return 0.;
139 }
140 
141 
142 double
144  return edge->getLength() / getEffort(edge, nullptr, 0);
145 }
146 
147 
148 SUMOTime
150  initEdgeWeights();
151  if (MSNet::getInstance()->getVehicleControl().getDepartedVehicleNo() == 0) {
152  return myAdaptationInterval;
153  }
154  std::map<std::pair<const MSEdge*, const MSEdge*>, const MSRoute*>::iterator it = myCachedRoutes.begin();
155  for (; it != myCachedRoutes.end(); ++it) {
156  it->second->release();
157  }
158  myCachedRoutes.clear();
160  if (myAdaptationSteps > 0) {
161  // moving average
162  for (MSEdgeVector::const_iterator i = edges.begin(); i != edges.end(); ++i) {
163  if ((*i)->isDelayed()) {
164  const int id = (*i)->getNumericalID();
165  const double currSpeed = (*i)->getMeanSpeed();
167  myPastEdgeSpeeds[id][myAdaptationStepsIndex] = currSpeed;
168  }
169  }
171  } else {
172  // exponential moving average
173  const double newWeightFactor = (double)(1. - myAdaptationWeight);
174  for (MSEdgeVector::const_iterator i = edges.begin(); i != edges.end(); ++i) {
175  if ((*i)->isDelayed()) {
176  const int id = (*i)->getNumericalID();
177  const double currSpeed = (*i)->getMeanSpeed();
178  if (currSpeed != myEdgeSpeeds[id]) {
179  myEdgeSpeeds[id] = myEdgeSpeeds[id] * myAdaptationWeight + currSpeed * newWeightFactor;
180  }
181  }
182  }
183  }
184  myLastAdaptation = currentTime + DELTA_T; // because we run at the end of the time step
185  if (OptionsCont::getOptions().isSet("device.rerouting.output")) {
186  OutputDevice& dev = OutputDevice::getDeviceByOption("device.rerouting.output");
188  dev.writeAttr(SUMO_ATTR_ID, "device.rerouting");
189  dev.writeAttr(SUMO_ATTR_BEGIN, STEPS2TIME(currentTime));
191  for (MSEdgeVector::const_iterator i = edges.begin(); i != edges.end(); ++i) {
192  const int id = (*i)->getNumericalID();
193  dev.openTag(SUMO_TAG_EDGE);
194  dev.writeAttr(SUMO_ATTR_ID, (*i)->getID());
195  dev.writeAttr("traveltime", (*i)->getLength() / myEdgeSpeeds[id]);
196  dev.closeTag();
197  }
198  dev.closeTag();
199  }
200  return myAdaptationInterval;
201 }
202 
203 
204 const MSRoute*
205 MSRoutingEngine::getCachedRoute(const std::pair<const MSEdge*, const MSEdge*>& key) {
206  auto routeIt = myCachedRoutes.find(key);
207  if (routeIt != myCachedRoutes.end()) {
208  return routeIt->second;
209  }
210  return nullptr;
211 }
212 
213 
214 void
215 MSRoutingEngine::reroute(SUMOVehicle& vehicle, const SUMOTime currentTime, const bool onInit) {
216 #ifdef HAVE_FOX
217  const bool needThread = (myRouter == nullptr && myThreadPool.isFull());
218 #else
219  const bool needThread = true;
220 #endif
221  if (needThread && myRouter == nullptr) {
223  const std::string routingAlgorithm = oc.getString("routing-algorithm");
224  const bool mayHaveRestrictions = MSNet::getInstance()->hasPermissions() || oc.getInt("remote-port") != 0;
225  if (routingAlgorithm == "dijkstra") {
226  if (mayHaveRestrictions) {
229  } else {
232  }
233  } else if (routingAlgorithm == "astar") {
234  if (mayHaveRestrictions) {
236  std::shared_ptr<const AStar::LookupTable> lookup;
237  if (oc.isSet("astar.all-distances")) {
238  lookup = std::make_shared<const AStar::FLT>(oc.getString("astar.all-distances"), (int)MSEdge::getAllEdges().size());
239  } else if (oc.isSet("astar.landmark-distances")) {
240  const double speedFactor = vehicle.getChosenSpeedFactor();
241  // we need an exemplary vehicle with speedFactor 1
242  vehicle.setChosenSpeedFactor(1);
245  string2time(oc.getString("begin")), string2time(oc.getString("end")), std::numeric_limits<int>::max(), 1);
246  lookup = std::make_shared<const AStar::LMLT>(oc.getString("astar.landmark-distances"), MSEdge::getAllEdges(), &router, &vehicle, "", oc.getInt("device.rerouting.threads"));
247  vehicle.setChosenSpeedFactor(speedFactor);
248  }
249  myRouter = new AStar(MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, lookup);
250  } else {
252  std::shared_ptr<const AStar::LookupTable> lookup;
253  if (oc.isSet("astar.all-distances")) {
254  lookup = std::shared_ptr<const AStar::LookupTable> ( new AStar::FLT(oc.getString("astar.all-distances"), (int)MSEdge::getAllEdges().size()));
255  } else if (oc.isSet("astar.landmark-distances")) {
256  const double speedFactor = vehicle.getChosenSpeedFactor();
257  // we need an exemplary vehicle with speedFactor 1
258  vehicle.setChosenSpeedFactor(1);
261  string2time(oc.getString("begin")), string2time(oc.getString("end")), std::numeric_limits<int>::max(), 1);
262  lookup = std::make_shared<const AStar::LMLT>(oc.getString("astar.landmark-distances"), MSEdge::getAllEdges(), &router, &vehicle, "", oc.getInt("device.rerouting.threads"));
263  vehicle.setChosenSpeedFactor(speedFactor);
264  }
265  myRouter = new AStar(MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, lookup);
266  }
267  } else if (routingAlgorithm == "CH") {
268  const SUMOTime weightPeriod = myAdaptationInterval > 0 ? myAdaptationInterval : std::numeric_limits<int>::max();
269  if (mayHaveRestrictions) {
271  MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, vehicle.getVClass(), weightPeriod, true);
272  } else {
274  MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, vehicle.getVClass(), weightPeriod, false);
275  }
276  } else if (routingAlgorithm == "CHWrapper") {
277  const SUMOTime weightPeriod = myAdaptationInterval > 0 ? myAdaptationInterval : std::numeric_limits<int>::max();
280  string2time(oc.getString("begin")), string2time(oc.getString("end")), weightPeriod, oc.getInt("device.rerouting.threads"));
281  } else {
282  throw ProcessError("Unknown routing algorithm '" + routingAlgorithm + "'!");
283  }
284  }
285 #ifdef HAVE_FOX
286  if (needThread) {
287  const int numThreads = OptionsCont::getOptions().getInt("device.rerouting.threads");
288  if (myThreadPool.size() < numThreads) {
289  new WorkerThread(myThreadPool, myRouter);
290  }
291  if (myThreadPool.size() < numThreads) {
292  myRouter = nullptr;
293  }
294  }
295  if (myThreadPool.size() > 0) {
296  myThreadPool.add(new RoutingTask(vehicle, currentTime, onInit));
297  return;
298  }
299 #endif
300  vehicle.reroute(currentTime, "device.rerouting", *myRouter, onInit, myWithTaz);
301 }
302 
303 
304 void
305 MSRoutingEngine::setEdgeTravelTime(const MSEdge* const edge, const double travelTime) {
306  myEdgeSpeeds[edge->getNumericalID()] = edge->getLength() / travelTime;
307 }
308 
309 
312  if (myRouterWithProhibited == nullptr) {
314  initEdgeWeights();
317  }
318  myRouterWithProhibited->prohibit(prohibited);
319  return *myRouterWithProhibited;
320 }
321 
322 
323 void
325  delete myRouterWithProhibited;
326  myRouterWithProhibited = nullptr;
327  myAdaptationInterval = -1; // responsible for triggering initEdgeWeights
328  myPastEdgeSpeeds.clear();
329  myEdgeSpeeds.clear();
330  // @todo recheck. calling release crashes in parallel routing
331  //for (auto& item : myCachedRoutes) {
332  // item.second->release();
333  //}
334  myCachedRoutes.clear();
336 #ifdef HAVE_FOX
337  if (myThreadPool.size() > 0) {
338  // we cannot wait for the static destructor to do the cleanup
339  // because the output devices are gone by then
340  myThreadPool.clear();
341  // router deletion is done in thread destructor
342  myRouter = nullptr;
343  return;
344  }
345 #endif
346  delete myRouter;
347  myRouter = nullptr;
348 }
349 
350 
351 #ifdef HAVE_FOX
352 void
353 MSRoutingEngine::waitForAll() {
354  if (myThreadPool.size() > 0) {
355  myThreadPool.waitAll();
356  }
357 }
358 
359 
360 // ---------------------------------------------------------------------------
361 // MSRoutingEngine::RoutingTask-methods
362 // ---------------------------------------------------------------------------
363 void
364 MSRoutingEngine::RoutingTask::run(FXWorkerThread* context) {
365  myVehicle.reroute(myTime, "device.rerouting", static_cast<WorkerThread*>(context)->getRouter(), myOnInit, myWithTaz);
366  const MSEdge* source = *myVehicle.getRoute().begin();
367  const MSEdge* dest = myVehicle.getRoute().getLastEdge();
368  if (source->isTazConnector() && dest->isTazConnector()) {
369  const std::pair<const MSEdge*, const MSEdge*> key = std::make_pair(source, dest);
370  lock();
372  MSRoutingEngine::myCachedRoutes[key] = &myVehicle.getRoute();
373  myVehicle.getRoute().addReference();
374  }
375  unlock();
376  }
377 }
378 #endif
379 
380 
381 /****************************************************************************/
382 
Computes the shortest path through a contracted network.
Definition: CHRouter.h:63
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:256
static void setEdgeTravelTime(const MSEdge *const edge, const double travelTime)
adapt the known travel time for an edge
static SUMOTime myLastAdaptation
Information when the last edge weight adaptation occurred.
long long int SUMOTime
Definition: SUMOTime.h:36
static int myAdaptationSteps
The number of steps for averaging edge speeds (ring-buffer)
int getInt(const std::string &name) const
Returns the int-value of the named option (only for Option_Integer)
static SUMOTime myAdaptationInterval
At which time interval the edge weights get updated.
bool hasPermissions() const
Returns whether the network has specific vehicle class permissions.
Definition: MSNet.h:177
static int myAdaptationStepsIndex
The current index in the pastEdgeSpeed ring-buffer.
static AStarRouter< MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions< MSEdge, SUMOVehicle > > * myRouterWithProhibited
The router to use by rerouter elements.
static void initWeightUpdate()
intialize period edge weight update
static double rand(std::mt19937 *rng=0)
Returns a random real number in [0, 1)
Definition: RandHelper.h:61
Computes the shortest path through a network using the A* algorithm.
Definition: AStarRouter.h:78
weights: time range begin
static MSNet * getInstance()
Returns the pointer to the unique instance of MSNet (singleton).
Definition: MSNet.cpp:165
T MAX2(T a, T b)
Definition: StdDefs.h:76
SUMOTime DELTA_T
Definition: SUMOTime.cpp:35
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
static SUMOAbstractRouter< MSEdge, SUMOVehicle > & getRouterTT(const MSEdgeVector &prohibited=MSEdgeVector())
return the router instance
Base (microsim) event class.
Definition: Command.h:54
double getLength() const
return the length of the edge
Definition: MSEdge.h:568
int getNumericalID() const
Returns the numerical id of the edge.
Definition: MSEdge.h:255
static void initEdgeWeights()
initialize the edge weights if not done before
static SUMOTime adaptEdgeEfforts(SUMOTime currentTime)
Adapt edge efforts by the current edge states.
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:241
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:58
#define SIMTIME
Definition: SUMOTime.h:65
void prohibit(const std::vector< E *> &toProhibit)
A road/street connecting two junctions.
Definition: MSEdge.h:75
bool isSet(const std::string &name, bool failOnNonExistant=true) const
Returns the information whether the named option is set.
virtual SUMOVehicleClass getVClass() const =0
Returns the vehicle&#39;s access class.
virtual void setChosenSpeedFactor(const double factor)=0
static const MSRoute * getCachedRoute(const std::pair< const MSEdge *, const MSEdge *> &key)
return the cached route or nullptr on miss
Representation of a vehicle.
Definition: SUMOVehicle.h:60
Computes the shortest path through a network using the Dijkstra algorithm.
static double getTravelTime(const MSEdge *const e, const SUMOVehicle *const v, double t)
Returns the travel time to pass an edge.
Definition: MSNet.cpp:148
std::string getString(const std::string &name) const
Returns the string-value of the named option (only for Option_String)
static double myAdaptationWeight
Information which weight prior edge efforts have.
double getMinimumTravelTime(const SUMOVehicle *const veh) const
returns the minimum travel time for the given vehicle
Definition: MSEdge.h:405
virtual void addEvent(Command *operation, SUMOTime execTimeStep=-1)
Adds an Event.
#define STEPS2TIME(x)
Definition: SUMOTime.h:58
A wrapper for a Command function.
Definition: StaticCommand.h:42
static void reroute(SUMOVehicle &vehicle, const SUMOTime currentTime, const bool onInit)
initiate the rerouting, create router / thread pool on first use
static std::vector< std::vector< double > > myPastEdgeSpeeds
The container of edge speeds.
SUMOTime getCurrentTimeStep() const
Returns the current simulation step.
Definition: MSNet.h:263
SUMOTime string2time(const std::string &r)
Definition: SUMOTime.cpp:42
static Command * myEdgeWeightSettingCommand
The weights adaptation/overwriting command.
virtual double getChosenSpeedFactor() const =0
double getFloat(const std::string &name) const
Returns the double-value of the named option (only for Option_Float)
begin/end of the description of an edge
MSEventControl * getEndOfTimestepEvents()
Returns the event control for events executed at the end of a time step.
Definition: MSNet.h:419
static double myRandomizeWeightsFactor
Whether to disturb edge weights dynamically.
static std::vector< double > myEdgeSpeeds
The container of edge speeds.
A pool of worker threads which distributes the tasks and collects the results.
static SUMOAbstractRouter< MSEdge, SUMOVehicle > * myRouter
The router to use.
static std::map< std::pair< const MSEdge *, const MSEdge * >, const MSRoute * > myCachedRoutes
The container of pre-calculated routes.
bool isTazConnector() const
Definition: MSEdge.h:248
static double getAssumedSpeed(const MSEdge *edge)
return current travel speed assumption
static const MSEdgeVector & getAllEdges()
Returns all edges with a numerical id.
Definition: MSEdge.cpp:821
static OutputDevice & getDeviceByOption(const std::string &name)
Returns the device described by the option.
static double getEffort(const MSEdge *const e, const SUMOVehicle *const v, double t)
Returns the effort to pass an edge.
weights: time range end
static bool myWithTaz
whether taz shall be used at initial rerouting
A storage for options typed value containers)
Definition: OptionsCont.h:92
const MSEdgeVector & getEdges() const
Returns loaded edges.
an aggreagated-output interval
static bool createDeviceByOption(const std::string &optionName, const std::string &rootElement="", const std::string &schemaFile="")
Creates the device using the output definition stored in the named option.
Static storage of an output device and its base (abstract) implementation.
Definition: OutputDevice.h:64
bool closeTag(const std::string &comment="")
Closes the most recently opened tag and optionally adds a comment.
A thread repeatingly calculating incoming tasks.
MSEdgeControl & getEdgeControl()
Returns the edge control.
Definition: MSNet.h:359
#define NUMERICAL_EPS
Definition: config.h:148
static void cleanup()
deletes the router instance
std::vector< MSEdge * > MSEdgeVector
Definition: MSEdge.h:71
virtual void reroute(SUMOTime t, const std::string &info, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, const bool onInit=false, const bool withTaz=false)=0
Performs a rerouting using the given router.
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
Computes the shortest path through a contracted network.