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-2020 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.begin()));
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  if ((*(i - 1))->isConnectedTo(**i, veh.getVClass())) {
228  newEdges.push_back(*i);
229  } else {
230  if (initialSize > 2) {
231  // only inform if the input is (probably) not a trip
232  WRITE_MESSAGE("Edge '" + (*(i - 1))->getID() + "' not connected to edge '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
233  }
234  const ROEdge* last = newEdges.back();
235  newEdges.pop_back();
236  if (last->isTazConnector() && newEdges.size() > 1) {
237  // assume this was a viaTaz
238  last = newEdges.back();
239  newEdges.pop_back();
240  }
241  if (!router.compute(last, *i, &veh, begin, newEdges)) {
242  // backtrack: try to route from last mandatory edge to next mandatory edge
243  // XXX add option for backtracking in smaller increments
244  // (i.e. previous edge to edge after *i)
245  // we would then need to decide whether we have found a good
246  // tradeoff between faithfulness to the input data and detour-length
247  ConstROEdgeVector edges;
248  if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
249  mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
250  return false;
251  }
252  while (*i != *nextMandatory) {
253  ++i;
254  }
255  newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
256  std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
257  }
258  }
259  if (*i == *nextMandatory) {
260  nextMandatory++;
261  lastMandatory = (int)newEdges.size() - 1;
262  }
263  }
264  }
265  return true;
266 }
267 
268 
269 void
271  const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
272  if (myTryRepair || myUsingJTRR) {
273  if (myNewRoute) {
274  delete myAlternatives[0];
275  myAlternatives[0] = current;
276  }
277  const double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
278  if (costs < 0) {
279  throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
280  }
281  current->setCosts(costs);
282  return;
283  }
284  // add the route when it's new
285  if (myNewRoute) {
286  myAlternatives.push_back(current);
287  }
288  // recompute the costs and (when a new route was added) scale the probabilities
289  const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
290  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
291  RORoute* alt = *i;
292  // recompute the costs for all routes
293  const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
294  if (newCosts < 0.) {
295  throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
296  }
297  assert(myAlternatives.size() != 0);
298  if (myNewRoute) {
299  if (*i == current) {
300  // set initial probability and costs
301  alt->setProbability((double)(1.0 / (double) myAlternatives.size()));
302  alt->setCosts(newCosts);
303  } else {
304  // rescale probs for all others
305  alt->setProbability(alt->getProbability() * scale);
306  }
307  }
309  }
310  assert(myAlternatives.size() != 0);
313  // remove with probability of 0 (not mentioned in Gawron)
314  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
315  if ((*i)->getProbability() == 0) {
316  delete *i;
317  i = myAlternatives.erase(i);
318  } else {
319  i++;
320  }
321  }
322  }
324  // only keep the routes with highest probability
325  sort(myAlternatives.begin(), myAlternatives.end(), ComparatorProbability());
326  for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber(); i != myAlternatives.end(); i++) {
327  delete *i;
328  }
330  // rescale probabilities
331  double newSum = 0;
332  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
333  newSum += (*i)->getProbability();
334  }
335  assert(newSum > 0);
336  // @note newSum may be larger than 1 for numerical reasons
337  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
338  (*i)->setProbability((*i)->getProbability() / newSum);
339  }
340  }
341 
342  // find the route to use
343  double chosen = RandHelper::rand();
344  int pos = 0;
345  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end() - 1; i++, pos++) {
346  chosen -= (*i)->getProbability();
347  if (chosen <= 0) {
348  myLastUsed = pos;
349  return;
350  }
351  }
352  myLastUsed = pos;
353 }
354 
355 
356 const ROEdge*
358  return myAlternatives[0]->getLast();
359 }
360 
361 
364  bool asAlternatives, bool withExitTimes) const {
365  if (asAlternatives) {
367  for (int i = 0; i != (int)myAlternatives.size(); i++) {
368  myAlternatives[i]->writeXMLDefinition(dev, veh, true, withExitTimes);
369  }
370  dev.closeTag();
371  return dev;
372  } else {
373  return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, false, withExitTimes);
374  }
375 }
376 
377 
378 RORouteDef*
379 RORouteDef::copyOrigDest(const std::string& id) const {
380  RORouteDef* result = new RORouteDef(id, 0, true, true);
381  RORoute* route = myAlternatives[0];
382  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
383  ConstROEdgeVector edges;
384  edges.push_back(route->getFirst());
385  edges.push_back(route->getLast());
386  result->addLoadedAlternative(new RORoute(id, 0, 1, edges, col, route->getStops()));
387  return result;
388 }
389 
390 
391 RORouteDef*
392 RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
393  RORouteDef* result = new RORouteDef(id, 0, myTryRepair, myMayBeDisconnected);
394  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
395  RORoute* route = *i;
396  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
397  RORoute* newRoute = new RORoute(id, 0, 1, route->getEdgeVector(), col, route->getStops());
398  newRoute->addStopOffset(stopOffset);
399  result->addLoadedAlternative(newRoute);
400  }
401  return result;
402 }
403 
404 
405 double
407  double sum = 0.;
408  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
409  sum += (*i)->getProbability();
410  }
411  return sum;
412 }
413 
414 
415 /****************************************************************************/
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:278
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:276
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:54
long long int SUMOTime
Definition: SUMOTime.h:31
@ 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:53
std::string myID
The name of the object.
Definition: Named.h:124
const std::string & getID() const
Returns the id.
Definition: Named.h:73
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:60
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:239
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 std::string & getID() const
Returns the id of the routable.
Definition: RORoutable.h:91
SUMOVehicleClass getVClass() const
Definition: RORoutable.h:105
Base class for a vehicle's route definition.
Definition: RORouteDef.h:53
RORoute * myPrecomputed
precomputed route for out-of-order computation
Definition: RORouteDef.h:153
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:406
std::vector< RORoute * > myAlternatives
The alternatives.
Definition: RORouteDef.h:159
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:168
void addAlternativeDef(const RORouteDef *alternative)
Adds an alternative loaded from the file.
Definition: RORouteDef.cpp:75
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:59
OutputDevice & writeXMLDefinition(OutputDevice &dev, const ROVehicle *const veh, bool asAlternatives, bool withExitTimes) const
Saves the built route / route alternatives.
Definition: RORouteDef.cpp:363
bool myDiscardSilent
Whether this route should be silently discarded.
Definition: RORouteDef.h:171
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:173
bool myNewRoute
Information whether a new route was generated.
Definition: RORouteDef.h:165
RORouteDef * copyOrigDest(const std::string &id) const
Returns a origin-destination copy of the route definition.
Definition: RORouteDef.cpp:379
void addAlternative(SUMOAbstractRouter< ROEdge, ROVehicle > &router, const ROVehicle *const, RORoute *current, SUMOTime begin)
Adds an alternative to the list of routes.
Definition: RORouteDef.cpp:270
const bool myTryRepair
Definition: RORouteDef.h:167
int myLastUsed
Index of the route used within the last step.
Definition: RORouteDef.h:156
std::set< RORoute * > myRouteRefs
Routes which are deleted someplace else.
Definition: RORouteDef.h:162
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:357
RORouteDef * copy(const std::string &id, const SUMOTime stopOffset) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:392
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
const ROEdge * getFirst() const
Returns the first edge in the route.
Definition: RORoute.h:91
void setProbability(double prob)
Sets the probability of the route.
Definition: RORoute.cpp:70
const std::vector< SUMOVehicleParameter::Stop > & getStops() const
Returns the list of stops this route contains.
Definition: RORoute.h:181
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:187
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
const ROEdge * getLast() const
Returns the last edge in the route.
Definition: RORoute.h:100
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:166
static double rand(std::mt19937 *rng=nullptr)
Returns a random real number in [0, 1)
Definition: RandHelper.h:51
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:36