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-2019 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 /****************************************************************************/
17 // Base class for a vehicle's route definition
18 /****************************************************************************/
19 
20 
21 // ===========================================================================
22 // included modules
23 // ===========================================================================
24 #include <config.h>
25 
26 #include <string>
27 #include <iterator>
28 #include <algorithm>
30 #include <utils/common/ToString.h>
31 #include <utils/common/Named.h>
37 #include "ROEdge.h"
38 #include "RORoute.h"
41 #include "RORouteDef.h"
42 #include "ROVehicle.h"
43 
44 // ===========================================================================
45 // static members
46 // ===========================================================================
47 bool RORouteDef::myUsingJTRR(false);
48 
49 // ===========================================================================
50 // method definitions
51 // ===========================================================================
52 RORouteDef::RORouteDef(const std::string& id, const int lastUsed,
53  const bool tryRepair, const bool mayBeDisconnected) :
54  Named(StringUtils::convertUmlaute(id)),
55  myPrecomputed(nullptr), myLastUsed(lastUsed), myTryRepair(tryRepair), myMayBeDisconnected(mayBeDisconnected) {
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  router.compute(oldEdges.front(), nullptr, &veh, begin, newEdges);
174  } else {
175  newEdges = oldEdges;
176  }
177  } else {
178  if (oldEdges.front()->prohibits(&veh)) {
179  // option repair.from is in effect
180  const std::string& frontID = oldEdges.front()->getID();
181  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
182  if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
183  i = oldEdges.erase(i);
184  } else {
185  WRITE_MESSAGE("Changing invalid starting edge '" + frontID
186  + "' to '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
187  break;
188  }
189  }
190  }
191  if (oldEdges.size() == 0) {
192  mh->inform("Could not find new starting edge for vehicle '" + veh.getID() + "'.");
193  return false;
194  }
195  if (oldEdges.back()->prohibits(&veh)) {
196  // option repair.to is in effect
197  const std::string& backID = oldEdges.back()->getID();
198  // oldEdges cannot get empty here, otherwise we would have left the stage when checking "from"
199  while (oldEdges.back()->prohibits(&veh) || oldEdges.back()->isInternal()) {
200  oldEdges.pop_back();
201  }
202  WRITE_MESSAGE("Changing invalid destination edge '" + backID
203  + "' to edge '" + oldEdges.back()->getID() + "' for vehicle '" + veh.getID() + "'.");
204  }
205  ConstROEdgeVector mandatory = veh.getMandatoryEdges(oldEdges.front(), oldEdges.back());
206  assert(mandatory.size() >= 2);
207  // removed prohibited
208  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
209  if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
210  // no need to check the mandatories here, this was done before
211  i = oldEdges.erase(i);
212  } else {
213  ++i;
214  }
215  }
216  // reconnect remaining edges
217  if (mandatory.size() > oldEdges.size() && initialSize > 2) {
218  WRITE_MESSAGE("There are stop edges which were not part of the original route for vehicle '" + veh.getID() + "'.");
219  }
220  const ConstROEdgeVector& targets = mandatory.size() > oldEdges.size() ? mandatory : oldEdges;
221  newEdges.push_back(*(targets.begin()));
222  ConstROEdgeVector::iterator nextMandatory = mandatory.begin() + 1;
223  int lastMandatory = 0;
224  for (ConstROEdgeVector::const_iterator i = targets.begin() + 1;
225  i != targets.end() && nextMandatory != mandatory.end(); ++i) {
226  if ((*(i - 1))->isConnectedTo(*i, &veh)) {
227  newEdges.push_back(*i);
228  } else {
229  if (initialSize > 2) {
230  // only inform if the input is (probably) not a trip
231  WRITE_MESSAGE("Edge '" + (*(i - 1))->getID() + "' not connected to edge '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
232  }
233  const ROEdge* const last = newEdges.back();
234  newEdges.pop_back();
235  if (!router.compute(last, *i, &veh, begin, newEdges)) {
236  // backtrack: try to route from last mandatory edge to next mandatory edge
237  // XXX add option for backtracking in smaller increments
238  // (i.e. previous edge to edge after *i)
239  // we would then need to decide whether we have found a good
240  // tradeoff between faithfulness to the input data and detour-length
241  ConstROEdgeVector edges;
242  if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
243  mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
244  return false;
245  }
246  while (*i != *nextMandatory) {
247  ++i;
248  }
249  newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
250  std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
251  }
252  }
253  if (*i == *nextMandatory) {
254  nextMandatory++;
255  lastMandatory = (int)newEdges.size() - 1;
256  }
257  }
258  }
259  return true;
260 }
261 
262 
263 void
265  const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
266  if (myTryRepair || myUsingJTRR) {
267  if (myNewRoute) {
268  delete myAlternatives[0];
269  myAlternatives[0] = current;
270  }
271  const double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
272  if (costs < 0) {
273  throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
274  }
275  current->setCosts(costs);
276  return;
277  }
278  // add the route when it's new
279  if (myNewRoute) {
280  myAlternatives.push_back(current);
281  }
282  // recompute the costs and (when a new route was added) scale the probabilities
283  const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
284  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
285  RORoute* alt = *i;
286  // recompute the costs for all routes
287  const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
288  if (newCosts < 0.) {
289  throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
290  }
291  assert(myAlternatives.size() != 0);
292  if (myNewRoute) {
293  if (*i == current) {
294  // set initial probability and costs
295  alt->setProbability((double)(1.0 / (double) myAlternatives.size()));
296  alt->setCosts(newCosts);
297  } else {
298  // rescale probs for all others
299  alt->setProbability(alt->getProbability() * scale);
300  }
301  }
303  }
304  assert(myAlternatives.size() != 0);
307  // remove with probability of 0 (not mentioned in Gawron)
308  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
309  if ((*i)->getProbability() == 0) {
310  delete *i;
311  i = myAlternatives.erase(i);
312  } else {
313  i++;
314  }
315  }
316  }
317  if ((int)myAlternatives.size() > RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber()) {
318  // only keep the routes with highest probability
319  sort(myAlternatives.begin(), myAlternatives.end(), ComparatorProbability());
320  for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber(); i != myAlternatives.end(); i++) {
321  delete *i;
322  }
324  // rescale probabilities
325  double newSum = 0;
326  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
327  newSum += (*i)->getProbability();
328  }
329  assert(newSum > 0);
330  // @note newSum may be larger than 1 for numerical reasons
331  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
332  (*i)->setProbability((*i)->getProbability() / newSum);
333  }
334  }
335 
336  // find the route to use
337  double chosen = RandHelper::rand();
338  int pos = 0;
339  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end() - 1; i++, pos++) {
340  chosen -= (*i)->getProbability();
341  if (chosen <= 0) {
342  myLastUsed = pos;
343  return;
344  }
345  }
346  myLastUsed = pos;
347 }
348 
349 
350 const ROEdge*
352  return myAlternatives[0]->getLast();
353 }
354 
355 
358  bool asAlternatives, bool withExitTimes) const {
359  if (asAlternatives) {
361  for (int i = 0; i != (int)myAlternatives.size(); i++) {
362  myAlternatives[i]->writeXMLDefinition(dev, veh, true, withExitTimes);
363  }
364  dev.closeTag();
365  return dev;
366  } else {
367  return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, false, withExitTimes);
368  }
369 }
370 
371 
372 RORouteDef*
373 RORouteDef::copyOrigDest(const std::string& id) const {
374  RORouteDef* result = new RORouteDef(id, 0, true, true);
375  RORoute* route = myAlternatives[0];
376  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
377  ConstROEdgeVector edges;
378  edges.push_back(route->getFirst());
379  edges.push_back(route->getLast());
380  result->addLoadedAlternative(new RORoute(id, 0, 1, edges, col, route->getStops()));
381  return result;
382 }
383 
384 
385 RORouteDef*
386 RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
387  RORouteDef* result = new RORouteDef(id, 0, myTryRepair, myMayBeDisconnected);
388  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
389  RORoute* route = *i;
390  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
391  RORoute* newRoute = new RORoute(id, 0, 1, route->getEdgeVector(), col, route->getStops());
392  newRoute->addStopOffset(stopOffset);
393  result->addLoadedAlternative(newRoute);
394  }
395  return result;
396 }
397 
398 
399 double
401  double sum = 0.;
402  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
403  sum += (*i)->getProbability();
404  }
405  return sum;
406 }
407 
408 
409 /****************************************************************************/
RORouteDef * copy(const std::string &id, const SUMOTime stopOffset) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:386
int myLastUsed
Index of the route used within the last step.
Definition: RORouteDef.h:152
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:72
void setProbability(double prob)
Sets the probability of the route.
Definition: RORoute.cpp:72
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:256
bool myNewRoute
Information whether a new route was generated.
Definition: RORouteDef.h:161
static MsgHandler * getErrorInstance()
Returns the instance to add errors to.
Definition: MsgHandler.cpp:81
long long int SUMOTime
Definition: SUMOTime.h:35
const bool myTryRepair
Definition: RORouteDef.h:163
OutputDevice & writeXMLDefinition(OutputDevice &dev, const ROVehicle *const veh, bool asAlternatives, bool withExitTimes) const
Saves the built route / route alternatives.
Definition: RORouteDef.cpp:357
distribution of a route
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:351
Some static methods for string processing.
Definition: StringUtils.h:39
void addAlternative(SUMOAbstractRouter< ROEdge, ROVehicle > &router, const ROVehicle *const, RORoute *current, SUMOTime begin)
Adds an alternative to the list of routes.
Definition: RORouteDef.cpp:264
void addAlternativeDef(const RORouteDef *alternative)
Adds an alternative loaded from the file.
Definition: RORouteDef.cpp:75
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
static double rand(std::mt19937 *rng=0)
Returns a random real number in [0, 1)
Definition: RandHelper.h:60
void addStopOffset(const SUMOTime offset)
Adapts the until time of all stops by the given offset.
Definition: RORoute.h:190
const ROEdge * getFirst() const
Returns the first edge in the route.
Definition: RORoute.h:94
RORouteDef * copyOrigDest(const std::string &id) const
Returns a origin-destination copy of the route definition.
Definition: RORouteDef.cpp:373
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:57
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
const std::string & getID() const
Returns the id.
Definition: Named.h:77
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:166
double getOverallProb() const
Returns the sum of the probablities of the contained routes.
Definition: RORouteDef.cpp:400
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:239
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:58
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
RORoute * myPrecomputed
precomputed route for out-of-order computation
Definition: RORouteDef.h:149
const bool myMayBeDisconnected
Definition: RORouteDef.h:164
A vehicle as used by router.
Definition: ROVehicle.h:53
std::set< RORoute * > myRouteRefs
Routes which are deleted someplace else.
Definition: RORouteDef.h:158
double getProbability() const
Returns the probability the driver will take this route with.
Definition: RORoute.h:123
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
ConstROEdgeVector getMandatoryEdges(const ROEdge *requiredStart, const ROEdge *requiredEnd) const
compute mandatory edges
Definition: ROVehicle.cpp:166
const std::vector< SUMOVehicleParameter::Stop > & getStops() const
Returns the list of stops this route contains.
Definition: RORoute.h:184
bool exists(const std::string &name) const
Returns the information whether the named option is known.
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...
const ROEdge * getLast() const
Returns the last edge in the route.
Definition: RORoute.h:103
RORouteDef(const std::string &id, const int lastUsed, const bool tryRepair, const bool mayBeDisconnected)
Constructor.
Definition: RORouteDef.cpp:52
Abstract base class providing static factory method.
const std::string & getID() const
Returns the id of the routable.
Definition: RORoutable.h:94
SUMOTime getDepartureTime() const
Returns the time the vehicle starts at, 0 for triggered vehicles.
Definition: ROVehicle.h:95
const RGBColor * getColor() const
Returns this route&#39;s color.
Definition: RORoute.h:163
A basic edge for routing applications.
Definition: ROEdge.h:73
Base class for objects which have an id.
Definition: Named.h:57
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:59
std::string myID
The name of the object.
Definition: Named.h:134
void setCosts(double costs)
Sets the costs of the route.
Definition: RORoute.cpp:66
const ConstROEdgeVector & getEdgeVector() const
Returns the list of edges this route consists of.
Definition: RORoute.h:155
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:118
A storage for options typed value containers)
Definition: OptionsCont.h:90
Base class for a vehicle&#39;s route definition.
Definition: RORouteDef.h:56
void addLoadedAlternative(RORoute *alternative)
Adds a single alternative loaded from the file An alternative may also be generated during DUA...
Definition: RORouteDef.cpp:69
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.
static RouteCostCalculator< R, E, V > & getCalculator()
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:240
std::vector< RORoute * > myAlternatives
The alternatives.
Definition: RORouteDef.h:155
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
A complete router&#39;s route.
Definition: RORoute.h:55