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-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 /****************************************************************************/
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  if (myTryRepair || myUsingJTRR) {
117  ConstROEdgeVector newEdges;
118  if (repairCurrentRoute(router, begin, veh, myAlternatives[0]->getEdgeVector(), newEdges)) {
119  if (myAlternatives[0]->getEdgeVector() != newEdges) {
120  if (!myMayBeDisconnected) {
121  WRITE_WARNING("Repaired route of vehicle '" + veh.getID() + "'.");
122  }
123  myNewRoute = true;
124  RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
125  myPrecomputed = new RORoute(myID, 0, myAlternatives[0]->getProbability(), newEdges, col, myAlternatives[0]->getStops());
126  } else {
128  }
129  }
130  return;
131  }
133  || OptionsCont::getOptions().getBool("remove-loops")) {
135  } else {
136  // build a new route to test whether it is better
137  ConstROEdgeVector oldEdges;
138  oldEdges.push_back(myAlternatives[0]->getFirst());
139  oldEdges.push_back(myAlternatives[0]->getLast());
140  ConstROEdgeVector edges;
141  repairCurrentRoute(router, begin, veh, oldEdges, edges);
142  // check whether the same route was already used
143  int cheapest = -1;
144  for (int i = 0; i < (int)myAlternatives.size(); i++) {
145  if (edges == myAlternatives[i]->getEdgeVector()) {
146  cheapest = i;
147  break;
148  }
149  }
150  if (cheapest >= 0) {
151  myPrecomputed = myAlternatives[cheapest];
152  } else {
153  RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
154  myPrecomputed = new RORoute(myID, 0, 1, edges, col, myAlternatives[0]->getStops());
155  myNewRoute = true;
156  }
157  }
158 }
159 
160 
161 bool
163  SUMOTime begin, const ROVehicle& veh,
164  ConstROEdgeVector oldEdges, ConstROEdgeVector& newEdges) const {
165  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
167  const int initialSize = (int)oldEdges.size();
168  if (initialSize == 1) {
169  if (myUsingJTRR) {
171  router.compute(oldEdges.front(), nullptr, &veh, begin, newEdges);
172  } else {
173  newEdges = oldEdges;
174  }
175  } else {
176  if (oldEdges.front()->prohibits(&veh)) {
177  // option repair.from is in effect
178  const std::string& frontID = oldEdges.front()->getID();
179  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
180  if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
181  i = oldEdges.erase(i);
182  } else {
183  WRITE_MESSAGE("Changing invalid starting edge '" + frontID
184  + "' to '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
185  break;
186  }
187  }
188  }
189  if (oldEdges.size() == 0) {
190  mh->inform("Could not find new starting edge for vehicle '" + veh.getID() + "'.");
191  return false;
192  }
193  if (oldEdges.back()->prohibits(&veh)) {
194  // option repair.to is in effect
195  const std::string& backID = oldEdges.back()->getID();
196  // oldEdges cannot get empty here, otherwise we would have left the stage when checking "from"
197  while (oldEdges.back()->prohibits(&veh) || oldEdges.back()->isInternal()) {
198  oldEdges.pop_back();
199  }
200  WRITE_MESSAGE("Changing invalid destination edge '" + backID
201  + "' to edge '" + oldEdges.back()->getID() + "' for vehicle '" + veh.getID() + "'.");
202  }
203  ConstROEdgeVector mandatory = veh.getMandatoryEdges(oldEdges.front(), oldEdges.back());
204  assert(mandatory.size() >= 2);
205  // removed prohibited
206  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
207  if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
208  // no need to check the mandatories here, this was done before
209  i = oldEdges.erase(i);
210  } else {
211  ++i;
212  }
213  }
214  // reconnect remaining edges
215  if (mandatory.size() > oldEdges.size() && initialSize > 2) {
216  WRITE_MESSAGE("There are stop edges which were not part of the original route for vehicle '" + veh.getID() + "'.");
217  }
218  const ConstROEdgeVector& targets = mandatory.size() > oldEdges.size() ? mandatory : oldEdges;
219  newEdges.push_back(*(targets.begin()));
220  ConstROEdgeVector::iterator nextMandatory = mandatory.begin() + 1;
221  int lastMandatory = 0;
222  for (ConstROEdgeVector::const_iterator i = targets.begin() + 1;
223  i != targets.end() && nextMandatory != mandatory.end(); ++i) {
224  if ((*(i - 1))->isConnectedTo(*i, &veh)) {
225  newEdges.push_back(*i);
226  } else {
227  if (initialSize > 2) {
228  // only inform if the input is (probably) not a trip
229  WRITE_MESSAGE("Edge '" + (*(i - 1))->getID() + "' not connected to edge '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
230  }
231  const ROEdge* const last = newEdges.back();
232  newEdges.pop_back();
233  if (!router.compute(last, *i, &veh, begin, newEdges)) {
234  // backtrack: try to route from last mandatory edge to next mandatory edge
235  // XXX add option for backtracking in smaller increments
236  // (i.e. previous edge to edge after *i)
237  // we would then need to decide whether we have found a good
238  // tradeoff between faithfulness to the input data and detour-length
239  ConstROEdgeVector edges;
240  if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
241  mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
242  return false;
243  }
244  while (*i != *nextMandatory) {
245  ++i;
246  }
247  newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
248  std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
249  }
250  }
251  if (*i == *nextMandatory) {
252  nextMandatory++;
253  lastMandatory = (int)newEdges.size() - 1;
254  }
255  }
256  }
257  return true;
258 }
259 
260 
261 void
263  const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
264  if (myTryRepair || myUsingJTRR) {
265  if (myNewRoute) {
266  delete myAlternatives[0];
267  myAlternatives[0] = current;
268  }
269  const double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
270  if (costs < 0) {
271  throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
272  }
273  current->setCosts(costs);
274  return;
275  }
276  // add the route when it's new
277  if (myNewRoute) {
278  myAlternatives.push_back(current);
279  }
280  // recompute the costs and (when a new route was added) scale the probabilities
281  const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
282  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
283  RORoute* alt = *i;
284  // recompute the costs for all routes
285  const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
286  if (newCosts < 0.) {
287  throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
288  }
289  assert(myAlternatives.size() != 0);
290  if (myNewRoute) {
291  if (*i == current) {
292  // set initial probability and costs
293  alt->setProbability((double)(1.0 / (double) myAlternatives.size()));
294  alt->setCosts(newCosts);
295  } else {
296  // rescale probs for all others
297  alt->setProbability(alt->getProbability() * scale);
298  }
299  }
301  }
302  assert(myAlternatives.size() != 0);
305  // remove with probability of 0 (not mentioned in Gawron)
306  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
307  if ((*i)->getProbability() == 0) {
308  delete *i;
309  i = myAlternatives.erase(i);
310  } else {
311  i++;
312  }
313  }
314  }
315  if ((int)myAlternatives.size() > RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber()) {
316  // only keep the routes with highest probability
317  sort(myAlternatives.begin(), myAlternatives.end(), ComparatorProbability());
318  for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber(); i != myAlternatives.end(); i++) {
319  delete *i;
320  }
322  // rescale probabilities
323  double newSum = 0;
324  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
325  newSum += (*i)->getProbability();
326  }
327  assert(newSum > 0);
328  // @note newSum may be larger than 1 for numerical reasons
329  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
330  (*i)->setProbability((*i)->getProbability() / newSum);
331  }
332  }
333 
334  // find the route to use
335  double chosen = RandHelper::rand();
336  int pos = 0;
337  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end() - 1; i++, pos++) {
338  chosen -= (*i)->getProbability();
339  if (chosen <= 0) {
340  myLastUsed = pos;
341  return;
342  }
343  }
344  myLastUsed = pos;
345 }
346 
347 
348 const ROEdge*
350  return myAlternatives[0]->getLast();
351 }
352 
353 
356  bool asAlternatives, bool withExitTimes) const {
357  if (asAlternatives) {
359  for (int i = 0; i != (int)myAlternatives.size(); i++) {
360  myAlternatives[i]->writeXMLDefinition(dev, veh, true, withExitTimes);
361  }
362  dev.closeTag();
363  return dev;
364  } else {
365  return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, false, withExitTimes);
366  }
367 }
368 
369 
370 RORouteDef*
371 RORouteDef::copyOrigDest(const std::string& id) const {
372  RORouteDef* result = new RORouteDef(id, 0, true, true);
373  RORoute* route = myAlternatives[0];
374  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
375  ConstROEdgeVector edges;
376  edges.push_back(route->getFirst());
377  edges.push_back(route->getLast());
378  result->addLoadedAlternative(new RORoute(id, 0, 1, edges, col, route->getStops()));
379  return result;
380 }
381 
382 
383 RORouteDef*
384 RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
385  RORouteDef* result = new RORouteDef(id, 0, myTryRepair, myMayBeDisconnected);
386  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
387  RORoute* route = *i;
388  RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
389  RORoute* newRoute = new RORoute(id, 0, 1, route->getEdgeVector(), col, route->getStops());
390  newRoute->addStopOffset(stopOffset);
391  result->addLoadedAlternative(newRoute);
392  }
393  return result;
394 }
395 
396 
397 double
399  double sum = 0.;
400  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
401  sum += (*i)->getProbability();
402  }
403  return sum;
404 }
405 
406 
407 /****************************************************************************/
RORouteDef * copy(const std::string &id, const SUMOTime stopOffset) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:384
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:67
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:76
long long int SUMOTime
Definition: SUMOTime.h:36
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:355
distribution of a route
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:349
Some static methods for string processing.
Definition: StringUtils.h:40
void addAlternative(SUMOAbstractRouter< ROEdge, ROVehicle > &router, const ROVehicle *const, RORoute *current, SUMOTime begin)
Adds an alternative to the list of routes.
Definition: RORouteDef.cpp:262
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:162
static double rand(std::mt19937 *rng=0)
Returns a random real number in [0, 1)
Definition: RandHelper.h:61
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
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:371
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:56
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:78
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:398
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:241
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
ConstROEdgeVector getMandatoryEdges(const ROEdge *requiredStart, const ROEdge *requiredEnd) const
compute mandatory edges
Definition: ROVehicle.cpp:164
const std::vector< SUMOVehicleParameter::Stop > & getStops() const
Returns the list of stops this route contains.
Definition: RORoute.h:184
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:72
Base class for objects which have an id.
Definition: Named.h:58
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:59
std::string myID
The name of the object.
Definition: Named.h:130
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
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:113
A storage for options typed value containers)
Definition: OptionsCont.h:92
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.
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
static RouteCostCalculator< R, E, V > & getCalculator()
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:242
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