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