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-2017 German Aerospace Center (DLR) and others.
4 /****************************************************************************/
5 //
6 // This program and the accompanying materials
7 // are made available under the terms of the Eclipse Public License v2.0
8 // which accompanies this distribution, and is available at
9 // http://www.eclipse.org/legal/epl-v20.html
10 //
11 /****************************************************************************/
19 // Base class for a vehicle's route definition
20 /****************************************************************************/
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #ifdef _MSC_VER
27 #include <windows_config.h>
28 #else
29 #include <config.h>
30 #endif
31 
32 #include <string>
33 #include <iterator>
34 #include <algorithm>
36 #include <utils/common/ToString.h>
37 #include <utils/common/Named.h>
43 #include "ROEdge.h"
44 #include "RORoute.h"
47 #include "RORouteDef.h"
48 #include "ROVehicle.h"
49 
50 // ===========================================================================
51 // static members
52 // ===========================================================================
53 bool RORouteDef::myUsingJTRR(false);
54 
55 // ===========================================================================
56 // method definitions
57 // ===========================================================================
58 RORouteDef::RORouteDef(const std::string& id, const int lastUsed,
59  const bool tryRepair, const bool mayBeDisconnected) :
60  Named(StringUtils::convertUmlaute(id)),
61  myPrecomputed(0), myLastUsed(lastUsed), myTryRepair(tryRepair), myMayBeDisconnected(mayBeDisconnected) {
62 }
63 
64 
66  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
67  if (myRouteRefs.count(*i) == 0) {
68  delete *i;
69  }
70  }
71 }
72 
73 
74 void
76  myAlternatives.push_back(alt);
77 }
78 
79 
80 void
82  std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
83  back_inserter(myAlternatives));
84  std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
85  std::inserter(myRouteRefs, myRouteRefs.end()));
86 }
87 
88 
89 RORoute*
91  SUMOTime begin, const ROVehicle& veh) const {
92  if (myPrecomputed == 0) {
93  preComputeCurrentRoute(router, begin, veh);
94  }
95  return myPrecomputed;
96 }
97 
98 
99 void
101  SUMOTime begin, const ROVehicle& veh) const {
102  myNewRoute = false;
103  const OptionsCont& oc = OptionsCont::getOptions();
104  assert(myAlternatives[0]->getEdgeVector().size() > 0);
105  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
107  if (myAlternatives[0]->getFirst()->prohibits(&veh) && (!oc.getBool("repair.from")
108  // do not try to reassign starting edge for trip input
109  || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
110  mh->inform("Vehicle '" + veh.getID() + "' is not allowed to depart on edge '" +
111  myAlternatives[0]->getFirst()->getID() + "'.");
112  return;
113  } else if (myAlternatives[0]->getLast()->prohibits(&veh) && (!oc.getBool("repair.to")
114  // do not try to reassign destination edge for trip input
115  || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
116  // this check is not strictly necessary unless myTryRepair is set.
117  // However, the error message is more helpful than "no connection found"
118  mh->inform("Vehicle '" + veh.getID() + "' is not allowed to arrive on edge '" +
119  myAlternatives[0]->getLast()->getID() + "'.");
120  return;
121  }
122  if (myTryRepair || myUsingJTRR) {
123  ConstROEdgeVector newEdges;
124  if (repairCurrentRoute(router, begin, veh, myAlternatives[0]->getEdgeVector(), newEdges)) {
125  if (myAlternatives[0]->getEdgeVector() != newEdges) {
126  if (!myMayBeDisconnected) {
127  WRITE_WARNING("Repaired route of vehicle '" + veh.getID() + "'.");
128  }
129  myNewRoute = true;
130  RGBColor* col = myAlternatives[0]->getColor() != 0 ? new RGBColor(*myAlternatives[0]->getColor()) : 0;
131  myPrecomputed = new RORoute(myID, 0, myAlternatives[0]->getProbability(), newEdges, col, myAlternatives[0]->getStops());
132  } else {
134  }
135  }
136  return;
137  }
139  || OptionsCont::getOptions().getBool("remove-loops")) {
141  } else {
142  // build a new route to test whether it is better
143  ConstROEdgeVector oldEdges;
144  oldEdges.push_back(myAlternatives[0]->getFirst());
145  oldEdges.push_back(myAlternatives[0]->getLast());
146  ConstROEdgeVector edges;
147  repairCurrentRoute(router, begin, veh, oldEdges, edges);
148  // check whether the same route was already used
149  int cheapest = -1;
150  for (int i = 0; i < (int)myAlternatives.size(); i++) {
151  if (edges == myAlternatives[i]->getEdgeVector()) {
152  cheapest = i;
153  break;
154  }
155  }
156  if (cheapest >= 0) {
157  myPrecomputed = myAlternatives[cheapest];
158  } else {
159  RGBColor* col = myAlternatives[0]->getColor() != 0 ? new RGBColor(*myAlternatives[0]->getColor()) : 0;
160  myPrecomputed = new RORoute(myID, 0, 1, edges, col, myAlternatives[0]->getStops());
161  myNewRoute = true;
162  }
163  }
164 }
165 
166 
167 bool
169  SUMOTime begin, const ROVehicle& veh,
170  ConstROEdgeVector oldEdges, ConstROEdgeVector& newEdges) const {
171  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
173  ConstROEdgeVector mandatory;
174  const int initialSize = (int)oldEdges.size();
175  if (initialSize == 1) {
176  if (myUsingJTRR) {
178  router.compute(oldEdges.front(), 0, &veh, begin, newEdges);
179  } else {
180  newEdges = oldEdges;
181  }
182  } else {
183  // prepare mandatory edges
184  if (oldEdges.front()->prohibits(&veh)) {
185  // option repair.from is in effect
186  const std::string& frontID = oldEdges.front()->getID();
187  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
188  if ((*i)->prohibits(&veh)) {
189  i = oldEdges.erase(i);
190  } else {
191  WRITE_MESSAGE("Changing invalid starting edge '" + frontID
192  + "' to '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
193  break;
194  }
195  }
196  }
197  if (oldEdges.size() == 0) {
198  mh->inform("Could not find new starting edge for vehicle '" + veh.getID() + "'.");
199  return false;
200  }
201  mandatory.push_back(oldEdges.front());
202  ConstROEdgeVector stops = veh.getStopEdges();
203  for (ConstROEdgeVector::const_iterator i = stops.begin(); i != stops.end(); ++i) {
204  if ((*i)->isInternal()) {
205  // the edges before and after the internal edge are mandatory
206  const ROEdge* before = (*i)->getNormalBefore();
207  const ROEdge* after = (*i)->getNormalAfter();
208  if (after != mandatory.back()) {
209  mandatory.push_back(before);
210  mandatory.push_back(after);
211  }
212  } else {
213  if (*i != mandatory.back()) {
214  mandatory.push_back(*i);
215  }
216  }
217  }
218  if (oldEdges.back()->prohibits(&veh)) {
219  // option repair.to is in effect
220  const std::string& backID = oldEdges.back()->getID();
221  // oldEdges cannot get empty here, otherwise we would have left the stage when checking "from"
222  while (oldEdges.back()->prohibits(&veh)) {
223  oldEdges.pop_back();
224  }
225  WRITE_MESSAGE("Changing invalid destination edge '" + backID
226  + "' to edge '" + oldEdges.back()->getID() + "' for vehicle '" + veh.getID() + "'.");
227  }
228  if (mandatory.size() < 2 || oldEdges.back() != mandatory.back()) {
229  mandatory.push_back(oldEdges.back());
230  }
231  assert(mandatory.size() >= 2);
232  // removed prohibited
233  for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
234  if ((*i)->prohibits(&veh)) {
235  // no need to check the mandatories here, this was done before
236  i = oldEdges.erase(i);
237  } else {
238  ++i;
239  }
240  }
241  // reconnect remaining edges
242  if (mandatory.size() > oldEdges.size() && initialSize > 2) {
243  WRITE_MESSAGE("There are stop edges which were not part of the original route for vehicle '" + veh.getID() + "'.");
244  }
245  const ConstROEdgeVector& targets = mandatory.size() > oldEdges.size() ? mandatory : oldEdges;
246  newEdges.push_back(*(targets.begin()));
247  ConstROEdgeVector::iterator nextMandatory = mandatory.begin() + 1;
248  int lastMandatory = 0;
249  for (ConstROEdgeVector::const_iterator i = targets.begin() + 1;
250  i != targets.end() && nextMandatory != mandatory.end(); ++i) {
251  if ((*(i - 1))->isConnectedTo(*i, &veh)) {
252  newEdges.push_back(*i);
253  } else {
254  if (initialSize > 2) {
255  // only inform if the input is (probably) not a trip
256  WRITE_MESSAGE("Edge '" + (*(i - 1))->getID() + "' not connected to edge '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
257  }
258  const ROEdge* const last = newEdges.back();
259  newEdges.pop_back();
260  if (!router.compute(last, *i, &veh, begin, newEdges)) {
261  // backtrack: try to route from last mandatory edge to next mandatory edge
262  // XXX add option for backtracking in smaller increments
263  // (i.e. previous edge to edge after *i)
264  // we would then need to decide whether we have found a good
265  // tradeoff between faithfulness to the input data and detour-length
266  ConstROEdgeVector edges;
267  if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
268  mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
269  return false;
270  }
271  while (*i != *nextMandatory) {
272  ++i;
273  }
274  newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
275  std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
276  }
277  }
278  if (*i == *nextMandatory) {
279  nextMandatory++;
280  lastMandatory = (int)newEdges.size() - 1;
281  }
282  }
283  }
284  return true;
285 }
286 
287 
288 void
290  const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
291  if (myTryRepair || myUsingJTRR) {
292  if (myNewRoute) {
293  delete myAlternatives[0];
294  myAlternatives[0] = current;
295  }
296  const double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
297  if (costs < 0) {
298  throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
299  }
300  current->setCosts(costs);
301  return;
302  }
303  // add the route when it's new
304  if (myNewRoute) {
305  myAlternatives.push_back(current);
306  }
307  // recompute the costs and (when a new route was added) scale the probabilities
308  const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
309  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
310  RORoute* alt = *i;
311  // recompute the costs for all routes
312  const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
313  if (newCosts < 0.) {
314  throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
315  }
316  assert(myAlternatives.size() != 0);
317  if (myNewRoute) {
318  if (*i == current) {
319  // set initial probability and costs
320  alt->setProbability((double)(1.0 / (double) myAlternatives.size()));
321  alt->setCosts(newCosts);
322  } else {
323  // rescale probs for all others
324  alt->setProbability(alt->getProbability() * scale);
325  }
326  }
328  }
329  assert(myAlternatives.size() != 0);
332  // remove with probability of 0 (not mentioned in Gawron)
333  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
334  if ((*i)->getProbability() == 0) {
335  delete *i;
336  i = myAlternatives.erase(i);
337  } else {
338  i++;
339  }
340  }
341  }
342  if ((int)myAlternatives.size() > RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber()) {
343  // only keep the routes with highest probability
344  sort(myAlternatives.begin(), myAlternatives.end(), ComparatorProbability());
345  for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber(); i != myAlternatives.end(); i++) {
346  delete *i;
347  }
349  // rescale probabilities
350  double newSum = 0;
351  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
352  newSum += (*i)->getProbability();
353  }
354  assert(newSum > 0);
355  // @note newSum may be larger than 1 for numerical reasons
356  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
357  (*i)->setProbability((*i)->getProbability() / newSum);
358  }
359  }
360 
361  // find the route to use
362  double chosen = RandHelper::rand();
363  int pos = 0;
364  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end() - 1; i++, pos++) {
365  chosen -= (*i)->getProbability();
366  if (chosen <= 0) {
367  myLastUsed = pos;
368  return;
369  }
370  }
371  myLastUsed = pos;
372 }
373 
374 
375 const ROEdge*
377  return myAlternatives[0]->getLast();
378 }
379 
380 
383  bool asAlternatives, bool withExitTimes) const {
384  if (asAlternatives) {
386  for (int i = 0; i != (int)myAlternatives.size(); i++) {
387  myAlternatives[i]->writeXMLDefinition(dev, veh, true, withExitTimes);
388  }
389  dev.closeTag();
390  return dev;
391  } else {
392  return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, false, withExitTimes);
393  }
394 }
395 
396 
397 RORouteDef*
398 RORouteDef::copyOrigDest(const std::string& id) const {
399  RORouteDef* result = new RORouteDef(id, 0, true, true);
400  RORoute* route = myAlternatives[0];
401  RGBColor* col = route->getColor() != 0 ? new RGBColor(*route->getColor()) : 0;
402  ConstROEdgeVector edges;
403  edges.push_back(route->getFirst());
404  edges.push_back(route->getLast());
405  result->addLoadedAlternative(new RORoute(id, 0, 1, edges, col, route->getStops()));
406  return result;
407 }
408 
409 
410 RORouteDef*
411 RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
412  RORouteDef* result = new RORouteDef(id, 0, myTryRepair, myMayBeDisconnected);
413  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
414  RORoute* route = *i;
415  RGBColor* col = route->getColor() != 0 ? new RGBColor(*route->getColor()) : 0;
416  RORoute* newRoute = new RORoute(id, 0, 1, route->getEdgeVector(), col, route->getStops());
417  newRoute->addStopOffset(stopOffset);
418  result->addLoadedAlternative(newRoute);
419  }
420  return result;
421 }
422 
423 
424 double
426  double sum = 0.;
427  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
428  sum += (*i)->getProbability();
429  }
430  return sum;
431 }
432 
433 
434 /****************************************************************************/
RORouteDef * copy(const std::string &id, const SUMOTime stopOffset) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:411
int myLastUsed
Index of the route used within the last step.
Definition: RORouteDef.h:158
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:66
void setProbability(double prob)
Sets the probability of the route.
Definition: RORoute.cpp:78
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:260
bool myNewRoute
Information whether a new route was generated.
Definition: RORouteDef.h:167
static MsgHandler * getErrorInstance()
Returns the instance to add errors to.
Definition: MsgHandler.cpp:75
const bool myTryRepair
Definition: RORouteDef.h:169
OutputDevice & writeXMLDefinition(OutputDevice &dev, const ROVehicle *const veh, bool asAlternatives, bool withExitTimes) const
Saves the built route / route alternatives.
Definition: RORouteDef.cpp:382
distribution of a route
virtual double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const =0
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:376
Some static methods for string processing.
Definition: StringUtils.h:44
void addAlternative(SUMOAbstractRouter< ROEdge, ROVehicle > &router, const ROVehicle *const, RORoute *current, SUMOTime begin)
Adds an alternative to the list of routes.
Definition: RORouteDef.cpp:289
void addAlternativeDef(const RORouteDef *alternative)
Adds an alternative loaded from the file.
Definition: RORouteDef.cpp:81
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:168
static double rand(std::mt19937 *rng=0)
Returns a random real number in [0, 1)
Definition: RandHelper.h:64
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:196
const ROEdge * getFirst() const
Returns the first edge in the route.
Definition: RORoute.h:100
RORouteDef * copyOrigDest(const std::string &id) const
Returns a origin-destination copy of the route definition.
Definition: RORouteDef.cpp:398
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:62
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:74
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:100
static bool myUsingJTRR
Definition: RORouteDef.h:172
double getOverallProb() const
Returns the sum of the probablities of the contained routes.
Definition: RORouteDef.cpp:425
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:199
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:64
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:90
RORoute * myPrecomputed
precomputed route for out-of-order computation
Definition: RORouteDef.h:155
const bool myMayBeDisconnected
Definition: RORouteDef.h:170
A vehicle as used by router.
Definition: ROVehicle.h:59
std::set< RORoute * > myRouteRefs
Routes which are deleted someplace else.
Definition: RORouteDef.h:164
const ROEdge * getNormalAfter() const
if this edge is an internal edge, return its first normal successor, otherwise the edge itself ...
Definition: ROEdge.cpp:263
double getProbability() const
Returns the probability the driver will take this route with.
Definition: RORoute.h:129
const std::vector< SUMOVehicleParameter::Stop > & getStops() const
Returns the list of stops this route contains.
Definition: RORoute.h:190
const ConstROEdgeVector & getStopEdges() const
Definition: ROVehicle.h:106
const ROEdge * getLast() const
Returns the last edge in the route.
Definition: RORoute.h:109
RORouteDef(const std::string &id, const int lastUsed, const bool tryRepair, const bool mayBeDisconnected)
Constructor.
Definition: RORouteDef.cpp:58
Abstract base class providing static factory method.
const std::string & getID() const
Returns the id of the routable.
Definition: RORoutable.h:100
SUMOTime getDepartureTime() const
Returns the time the vehicle starts at, 0 for triggered vehicles.
Definition: ROVehicle.h:101
const RGBColor * getColor() const
Returns this route&#39;s color.
Definition: RORoute.h:169
A basic edge for routing applications.
Definition: ROEdge.h:77
Base class for objects which have an id.
Definition: Named.h:54
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:65
std::string myID
The name of the object.
Definition: Named.h:126
void setCosts(double costs)
Sets the costs of the route.
Definition: RORoute.cpp:72
const ConstROEdgeVector & getEdgeVector() const
Returns the list of edges this route consists of.
Definition: RORoute.h:161
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:84
A storage for options typed value containers)
Definition: OptionsCont.h:98
Base class for a vehicle&#39;s route definition.
Definition: RORouteDef.h:62
void addLoadedAlternative(RORoute *alternative)
Adds a single alternative loaded from the file An alternative may also be generated during DUA...
Definition: RORouteDef.cpp:75
Static storage of an output device and its base (abstract) implementation.
Definition: OutputDevice.h:70
bool closeTag()
Closes the most recently opened tag.
long long int SUMOTime
Definition: TraCIDefs.h:51
const ROEdge * getNormalBefore() const
if this edge is an internal edge, return its first normal predecessor, otherwise the edge itself ...
Definition: ROEdge.cpp:252
static RouteCostCalculator< R, E, V > & getCalculator()
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:200
std::vector< RORoute * > myAlternatives
The alternatives.
Definition: RORouteDef.h:161
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
A complete router&#39;s route.
Definition: RORoute.h:61