Eclipse SUMO - Simulation of Urban MObility
RORouteDef.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2002-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 /****************************************************************************/
20 // Base class for a vehicle's route definition
21 /****************************************************************************/
22 #include <config.h>
23 
24 #include <string>
25 #include <iterator>
26 #include <algorithm>
28 #include <utils/common/ToString.h>
29 #include <utils/common/Named.h>
35 #include "ROEdge.h"
36 #include "RORoute.h"
39 #include "RORouteDef.h"
40 #include "ROVehicle.h"
41 
42 // ===========================================================================
43 // static members
44 // ===========================================================================
45 bool RORouteDef::myUsingJTRR(false);
46 
47 // ===========================================================================
48 // method definitions
49 // ===========================================================================
50 RORouteDef::RORouteDef(const std::string& id, const int lastUsed,
51  const bool tryRepair, const bool mayBeDisconnected) :
52  Named(StringUtils::convertUmlaute(id)),
53  myPrecomputed(nullptr), myLastUsed(lastUsed), myTryRepair(tryRepair),
54  myMayBeDisconnected(mayBeDisconnected),
55  myDiscardSilent(false) {
56 }
57 
58 
60  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
61  if (myRouteRefs.count(*i) == 0) {
62  delete *i;
63  }
64  }
65 }
66 
67 
68 void
70  myAlternatives.push_back(alt);
71 }
72 
73 
74 void
76  std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
77  back_inserter(myAlternatives));
78  std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
79  std::inserter(myRouteRefs, myRouteRefs.end()));
80 }
81 
82 
83 RORoute*
85  SUMOTime begin, const ROVehicle& veh) const {
86  if (myPrecomputed == nullptr) {
87  preComputeCurrentRoute(router, begin, veh);
88  }
89  return myPrecomputed;
90 }
91 
92 
93 void
95  SUMOTime begin, const ROVehicle& veh) const {
96  myNewRoute = false;
98  assert(myAlternatives[0]->getEdgeVector().size() > 0);
99  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
101  if (myAlternatives[0]->getFirst()->prohibits(&veh) && (!oc.getBool("repair.from")
102  // do not try to reassign starting edge for trip input
103  || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
104  mh->inform("Vehicle '" + veh.getID() + "' is not allowed to depart on edge '" +
105  myAlternatives[0]->getFirst()->getID() + "'.");
106  return;
107  } else if (myAlternatives[0]->getLast()->prohibits(&veh) && (!oc.getBool("repair.to")
108  // do not try to reassign destination edge for trip input
109  || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
110  // this check is not strictly necessary unless myTryRepair is set.
111  // However, the error message is more helpful than "no connection found"
112  mh->inform("Vehicle '" + veh.getID() + "' is not allowed to arrive on edge '" +
113  myAlternatives[0]->getLast()->getID() + "'.");
114  return;
115  }
116  const bool skipTripRouting = (oc.exists("write-trips") && oc.getBool("write-trips")
118  if ((myTryRepair && !skipTripRouting) || myUsingJTRR) {
119  ConstROEdgeVector newEdges;
120  if (repairCurrentRoute(router, begin, veh, myAlternatives[0]->getEdgeVector(), newEdges)) {
121  if (myAlternatives[0]->getEdgeVector() != newEdges) {
122  if (!myMayBeDisconnected) {
123  WRITE_WARNING("Repaired route of vehicle '" + veh.getID() + "'.");
124  }
125  myNewRoute = true;
126  RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
127  myPrecomputed = new RORoute(myID, 0, myAlternatives[0]->getProbability(), newEdges, col, myAlternatives[0]->getStops());
128  } else {
130  }
131  }
132  return;
133  }
135  || OptionsCont::getOptions().getBool("remove-loops")) {
137  } else {
138  // build a new route to test whether it is better
139  ConstROEdgeVector oldEdges;
140  oldEdges.push_back(myAlternatives[0]->getFirst());
141  oldEdges.push_back(myAlternatives[0]->getLast());
142  ConstROEdgeVector edges;
143  repairCurrentRoute(router, begin, veh, oldEdges, edges);
144  // check whether the same route was already used
145  int cheapest = -1;
146  for (int i = 0; i < (int)myAlternatives.size(); i++) {
147  if (edges == myAlternatives[i]->getEdgeVector()) {
148  cheapest = i;
149  break;
150  }
151  }
152  if (cheapest >= 0) {
153  myPrecomputed = myAlternatives[cheapest];
154  } else {
155  RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
156  myPrecomputed = new RORoute(myID, 0, 1, edges, col, myAlternatives[0]->getStops());
157  myNewRoute = true;
158  }
159  }
160 }
161 
162 
163 bool
165  SUMOTime begin, const ROVehicle& veh,
166  ConstROEdgeVector oldEdges, ConstROEdgeVector& newEdges) const {
167  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
169  const int initialSize = (int)oldEdges.size();
170  if (initialSize == 1) {
171  if (myUsingJTRR) {
173  bool ok = router.compute(oldEdges.front(), nullptr, &veh, begin, newEdges);
174  myDiscardSilent = ok && newEdges.size() == 0;
175  } else {
176  newEdges = oldEdges;
177  }
178  } else {
179  if (oldEdges.front()->prohibits(&veh)) {
180  // option repair.from is in effect
181  const std::string& frontID = oldEdges.front()->getID();
182  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
183  if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
184  i = oldEdges.erase(i);
185  } else {
186  WRITE_MESSAGE("Changing invalid starting edge '" + frontID
187  + "' to '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
188  break;
189  }
190  }
191  }
192  if (oldEdges.size() == 0) {
193  mh->inform("Could not find new starting edge for vehicle '" + veh.getID() + "'.");
194  return false;
195  }
196  if (oldEdges.back()->prohibits(&veh)) {
197  // option repair.to is in effect
198  const std::string& backID = oldEdges.back()->getID();
199  // oldEdges cannot get empty here, otherwise we would have left the stage when checking "from"
200  while (oldEdges.back()->prohibits(&veh) || oldEdges.back()->isInternal()) {
201  oldEdges.pop_back();
202  }
203  WRITE_MESSAGE("Changing invalid destination edge '" + backID
204  + "' to edge '" + oldEdges.back()->getID() + "' for vehicle '" + veh.getID() + "'.");
205  }
206  ConstROEdgeVector mandatory = veh.getMandatoryEdges(oldEdges.front(), oldEdges.back());
207  assert(mandatory.size() >= 2);
208  // removed prohibited
209  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
210  if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
211  // no need to check the mandatories here, this was done before
212  i = oldEdges.erase(i);
213  } else {
214  ++i;
215  }
216  }
217  // reconnect remaining edges
218  if (mandatory.size() > oldEdges.size() && initialSize > 2) {
219  WRITE_MESSAGE("There are stop edges which were not part of the original route for vehicle '" + veh.getID() + "'.");
220  }
221  const ConstROEdgeVector& targets = mandatory.size() > oldEdges.size() ? mandatory : oldEdges;
222  newEdges.push_back(targets.front());
223  ConstROEdgeVector::iterator nextMandatory = mandatory.begin() + 1;
224  int lastMandatory = 0;
225  for (ConstROEdgeVector::const_iterator i = targets.begin() + 1;
226  i != targets.end() && nextMandatory != mandatory.end(); ++i) {
227  const ROEdge* prev = *(i - 1);
228  const ROEdge* cur = *i;
229  if (prev->isConnectedTo(*cur, veh.getVClass()) && (!isRailway(veh.getVClass()) || prev->getBidiEdge() != cur)) {
230  newEdges.push_back(cur);
231  } else {
232  if (initialSize > 2) {
233  // only inform if the input is (probably) not a trip
234  WRITE_MESSAGE("Edge '" + (*(i - 1))->getID() + "' not connected to edge '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
235  }
236  const ROEdge* last = newEdges.back();
237  newEdges.pop_back();
238  if (last->isTazConnector() && newEdges.size() > 1) {
239  // assume this was a viaTaz
240  last = newEdges.back();
241  newEdges.pop_back();
242  }
243 // router.setHint(targets.begin(), i, &veh, begin);
244  if (!router.compute(last, *i, &veh, begin, newEdges)) {
245  // backtrack: try to route from last mandatory edge to next mandatory edge
246  // XXX add option for backtracking in smaller increments
247  // (i.e. previous edge to edge after *i)
248  // we would then need to decide whether we have found a good
249  // tradeoff between faithfulness to the input data and detour-length
250  ConstROEdgeVector edges;
251  if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
252  mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
253  return false;
254  }
255  while (*i != *nextMandatory) {
256  ++i;
257  }
258  newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
259  std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
260  }
261  }
262  if (*i == *nextMandatory) {
263  nextMandatory++;
264  lastMandatory = (int)newEdges.size() - 1;
265  }
266  }
267  }
268  return true;
269 }
270 
271 
272 void
274  const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
275  if (myTryRepair || myUsingJTRR) {
276  if (myNewRoute) {
277  delete myAlternatives[0];
278  myAlternatives[0] = current;
279  }
280  const double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
281  if (costs < 0) {
282  throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
283  }
284  current->setCosts(costs);
285  return;
286  }
287  // add the route when it's new
288  if (myNewRoute) {
289  myAlternatives.push_back(current);
290  }
291  // recompute the costs and (when a new route was added) scale the probabilities
292  const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
293  for (RORoute* const alt : myAlternatives) {
294  // recompute the costs for all routes
295  const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
296  if (newCosts < 0.) {
297  throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
298  }
299  assert(myAlternatives.size() != 0);
300  if (myNewRoute) {
301  if (alt == current) {
302  // set initial probability and costs
303  alt->setProbability(1. / (double) myAlternatives.size());
304  alt->setCosts(newCosts);
305  } else {
306  // rescale probs for all others
307  alt->setProbability(alt->getProbability() * scale);
308  }
309  }
311  }
312  assert(myAlternatives.size() != 0);
314  const bool keepRoute = RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().keepRoute();
315  if (!RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().keepAllRoutes() && !keepRoute) {
316  // remove with probability of 0 (not mentioned in Gawron)
317  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
318  if ((*i)->getProbability() == 0) {
319  delete *i;
320  i = myAlternatives.erase(i);
321  } else {
322  i++;
323  }
324  }
325  }
326  int maxNumber = RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber();
327  if ((int)myAlternatives.size() > maxNumber) {
328  const RORoute* last = myAlternatives[myLastUsed];
329  // only keep the routes with highest probability
330  sort(myAlternatives.begin(), myAlternatives.end(), [](const RORoute * const a, const RORoute * const b) {
331  return a->getProbability() > b->getProbability();
332  });
333  if (keepRoute) {
334  for (int i = 0; i < (int)myAlternatives.size(); i++) {
335  if (myAlternatives[i] == last) {
336  myLastUsed = i;
337  break;
338  }
339  }
340  if (myLastUsed >= maxNumber) {
341  std::swap(myAlternatives[maxNumber - 1], myAlternatives[myLastUsed]);
342  myLastUsed = maxNumber - 1;
343  }
344  }
345  for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + maxNumber; i != myAlternatives.end(); i++) {
346  delete *i;
347  }
348  myAlternatives.erase(myAlternatives.begin() + maxNumber, myAlternatives.end());
349  }
350  // rescale probabilities
351  double newSum = 0.;
352  for (const RORoute* const alt : myAlternatives) {
353  newSum += alt->getProbability();
354  }
355  assert(newSum > 0);
356  // @note newSum may be larger than 1 for numerical reasons
357  for (RORoute* const alt : myAlternatives) {
358  alt->setProbability(alt->getProbability() / newSum);
359  }
360 
361  // find the route to use
362  if (!keepRoute) {
363  double chosen = RandHelper::rand();
364  myLastUsed = 0;
365  for (const RORoute* const alt : myAlternatives) {
366  chosen -= alt->getProbability();
367  if (chosen <= 0) {
368  return;
369  }
370  myLastUsed++;
371  }
372  }
373 }
374 
375 
376 const ROEdge*
378  return myAlternatives[0]->getLast();
379 }
380 
381 
384  bool asAlternatives, bool withExitTimes, bool withCost, bool withLength) const {
385  if (asAlternatives) {
387  for (int i = 0; i != (int)myAlternatives.size(); i++) {
388  myAlternatives[i]->writeXMLDefinition(dev, veh, true, true, withExitTimes, withLength);
389  }
390  dev.closeTag();
391  return dev;
392  } else {
393  return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, withCost, false, withExitTimes, withLength);
394  }
395 }
396 
397 
398 RORouteDef*
399 RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
400  RORouteDef* result = new RORouteDef(id, 0, myTryRepair, myMayBeDisconnected);
401  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
402  RORoute* route = *i;
403  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
404  RORoute* newRoute = new RORoute(id, route->getCosts(), route->getProbability(), route->getEdgeVector(), col, route->getStops());
405  newRoute->addStopOffset(stopOffset);
406  result->addLoadedAlternative(newRoute);
407  }
408  return result;
409 }
410 
411 
412 double
414  double sum = 0.;
415  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
416  sum += (*i)->getProbability();
417  }
418  return sum;
419 }
420 
421 
422 /****************************************************************************/
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:282
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:280
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:54
long long int SUMOTime
Definition: SUMOTime.h:32
bool isRailway(SVCPermissions permissions)
Returns whether an edge with the given permission is a railway edge.
@ SUMO_TAG_ROUTE_DISTRIBUTION
distribution of a route
@ SUMO_ATTR_LAST
static MsgHandler * getErrorInstance()
Returns the instance to add errors to.
Definition: MsgHandler.cpp:80
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:117
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
Base class for objects which have an id.
Definition: Named.h:54
std::string myID
The name of the object.
Definition: Named.h:125
const std::string & getID() const
Returns the id.
Definition: Named.h:74
A storage for options typed value containers)
Definition: OptionsCont.h:89
bool exists(const std::string &name) const
Returns the information whether the named option is known.
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
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.
A basic edge for routing applications.
Definition: ROEdge.h:70
bool isTazConnector() const
Definition: ROEdge.h:159
const ROEdge * getBidiEdge() const
return opposite superposable/congruent edge, if it exist and 0 else
Definition: ROEdge.h:525
bool isConnectedTo(const ROEdge &e, const SUMOVehicleClass vClass) const
returns the information whether this edge is directly connected to the given
Definition: ROEdge.cpp:436
const std::string & getID() const
Returns the id of the routable.
Definition: RORoutable.h:91
SUMOVehicleClass getVClass() const
Definition: RORoutable.h:109
Base class for a vehicle's route definition.
Definition: RORouteDef.h:53
RORoute * myPrecomputed
precomputed route for out-of-order computation
Definition: RORouteDef.h:148
void addLoadedAlternative(RORoute *alternative)
Adds a single alternative loaded from the file An alternative may also be generated during DUA.
Definition: RORouteDef.cpp:69
RORouteDef(const std::string &id, const int lastUsed, const bool tryRepair, const bool mayBeDisconnected)
Constructor.
Definition: RORouteDef.cpp:50
double getOverallProb() const
Returns the sum of the probablities of the contained routes.
Definition: RORouteDef.cpp:413
std::vector< RORoute * > myAlternatives
The alternatives.
Definition: RORouteDef.h:154
OutputDevice & writeXMLDefinition(OutputDevice &dev, const ROVehicle *const veh, bool asAlternatives, bool withExitTimes, bool withCost, bool withLength) const
Saves the built route / route alternatives.
Definition: RORouteDef.cpp:383
RORoute * buildCurrentRoute(SUMOAbstractRouter< ROEdge, ROVehicle > &router, SUMOTime begin, const ROVehicle &veh) const
Triggers building of the complete route (via preComputeCurrentRoute) or returns precomputed route.
Definition: RORouteDef.cpp:84
const bool myMayBeDisconnected
Definition: RORouteDef.h:163
void addAlternativeDef(const RORouteDef *alternative)
Adds an alternative loaded from the file.
Definition: RORouteDef.cpp:75
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:59
bool myDiscardSilent
Whether this route should be silently discarded.
Definition: RORouteDef.h:166
void preComputeCurrentRoute(SUMOAbstractRouter< ROEdge, ROVehicle > &router, SUMOTime begin, const ROVehicle &veh) const
Builds the complete route (or chooses her from the list of alternatives, when existing)
Definition: RORouteDef.cpp:94
static bool myUsingJTRR
Definition: RORouteDef.h:168
bool myNewRoute
Information whether a new route was generated.
Definition: RORouteDef.h:160
void addAlternative(SUMOAbstractRouter< ROEdge, ROVehicle > &router, const ROVehicle *const, RORoute *current, SUMOTime begin)
Adds an alternative to the list of routes.
Definition: RORouteDef.cpp:273
const bool myTryRepair
Definition: RORouteDef.h:162
int myLastUsed
Index of the route used within the last step.
Definition: RORouteDef.h:151
std::set< RORoute * > myRouteRefs
Routes which are deleted someplace else.
Definition: RORouteDef.h:157
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:377
RORouteDef * copy(const std::string &id, const SUMOTime stopOffset) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:399
bool repairCurrentRoute(SUMOAbstractRouter< ROEdge, ROVehicle > &router, SUMOTime begin, const ROVehicle &veh, ConstROEdgeVector oldEdges, ConstROEdgeVector &newEdges) const
Builds the complete route (or chooses her from the list of alternatives, when existing)
Definition: RORouteDef.cpp:164
A complete router's route.
Definition: RORoute.h:52
double getCosts() const
Returns the costs of the route.
Definition: RORoute.h:110
const std::vector< SUMOVehicleParameter::Stop > & getStops() const
Returns the list of stops this route contains.
Definition: RORoute.h:183
double getProbability() const
Returns the probability the driver will take this route with.
Definition: RORoute.h:120
void addStopOffset(const SUMOTime offset)
Adapts the until time of all stops by the given offset.
Definition: RORoute.h:189
const RGBColor * getColor() const
Returns this route's color.
Definition: RORoute.h:160
const ConstROEdgeVector & getEdgeVector() const
Returns the list of edges this route consists of.
Definition: RORoute.h:152
void setCosts(double costs)
Sets the costs of the route.
Definition: RORoute.cpp:64
A vehicle as used by router.
Definition: ROVehicle.h:50
SUMOTime getDepartureTime() const
Returns the time the vehicle starts at, 0 for triggered vehicles.
Definition: ROVehicle.h:92
ConstROEdgeVector getMandatoryEdges(const ROEdge *requiredStart, const ROEdge *requiredEnd) const
compute mandatory edges
Definition: ROVehicle.cpp:170
static double rand(SumoRNG *rng=nullptr)
Returns a random real number in [0, 1)
Definition: RandHelper.h:119
Abstract base class providing static factory method.
static RouteCostCalculator< R, E, V > & getCalculator()
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
Some static methods for string processing.
Definition: StringUtils.h:37