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-sim.org/
12 // Copyright (C) 2002-2014 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"
47 #include "ReferencedItem.h"
48 #include "RORouteDef.h"
49 #include "ROVehicle.h"
50 #include "ROCostCalculator.h"
51 
52 #ifdef CHECK_MEMORY_LEAKS
53 #include <foreign/nvwa/debug_new.h>
54 #endif // CHECK_MEMORY_LEAKS
55 
56 
57 // ===========================================================================
58 // method definitions
59 // ===========================================================================
60 RORouteDef::RORouteDef(const std::string& id, const unsigned int lastUsed,
61  const bool tryRepair) :
62  ReferencedItem(), Named(StringUtils::convertUmlaute(id)),
63  myPrecomputed(0), myLastUsed(lastUsed), myTryRepair(tryRepair)
64 {}
65 
66 
68  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
69  delete *i;
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 }
85 
86 
87 RORoute*
89  SUMOTime begin, const ROVehicle& veh) const {
90  if (myPrecomputed == 0) {
91  preComputeCurrentRoute(router, begin, veh);
92  }
93  return myPrecomputed;
94 }
95 
96 
97 void
99  SUMOTime begin, const ROVehicle& veh) const {
100  myNewRoute = false;
101  assert(myAlternatives[0]->getEdgeVector().size() > 0);
102  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
104  if (myAlternatives[0]->getFirst()->prohibits(&veh)) {
106  mh->inform("Vehicle '" + veh.getID() + "' is not allowed to depart on edge '" +
107  myAlternatives[0]->getFirst()->getID() + "'.");
108  return;
109  } else if (myAlternatives[0]->getLast()->prohibits(&veh)) {
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) {
117  repairCurrentRoute(router, begin, veh);
118  return;
119  }
120  if (ROCostCalculator::getCalculator().skipRouteCalculation()) {
122  } else {
123  // build a new route to test whether it is better
124  std::vector<const ROEdge*> edges;
125  router.compute(myAlternatives[0]->getFirst(), myAlternatives[0]->getLast(), &veh, begin, edges);
126  // check whether the same route was already used
127  int cheapest = -1;
128  for (unsigned int i = 0; i < myAlternatives.size(); i++) {
129  if (edges == myAlternatives[i]->getEdgeVector()) {
130  cheapest = i;
131  break;
132  }
133  }
134  if (cheapest >= 0) {
135  myPrecomputed = myAlternatives[cheapest];
136  } else {
137  RGBColor* col = myAlternatives[0]->getColor() != 0 ? new RGBColor(*myAlternatives[0]->getColor()) : 0;
138  myPrecomputed = new RORoute(myID, 0, 1, edges, col, myAlternatives[0]->getStops());
139  myNewRoute = true;
140  }
141  }
142 }
143 
144 
145 void
147  SUMOTime begin, const ROVehicle& veh) const {
148  MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
150  std::vector<const ROEdge*> oldEdges = myAlternatives[0]->getEdgeVector();
151  std::vector<const ROEdge*> newEdges;
152  std::vector<const ROEdge*> mandatory;
153  if (oldEdges.size() == 1) {
155  router.compute(oldEdges.front(), oldEdges.front(), &veh, begin, newEdges);
156  } else {
157  // prepare mandatory edges
158  mandatory.push_back(oldEdges.front());
159  std::vector<const ROEdge*> stops = veh.getStopEdges();
160  for (std::vector<const ROEdge*>::const_iterator i = stops.begin(); i != stops.end(); ++i) {
161  if (*i != mandatory.back()) {
162  mandatory.push_back(*i);
163  }
164  }
165  if (mandatory.size() < 2 || oldEdges.back() != mandatory.back()) {
166  mandatory.push_back(oldEdges.back());
167  }
168  assert(mandatory.size() >= 2);
169  // removed prohibited
170  for (std::vector<const ROEdge*>::iterator i = oldEdges.begin(); i != oldEdges.end();) {
171  if ((*i)->prohibits(&veh)) {
172  if (std::find(mandatory.begin(), mandatory.end(), *i) != mandatory.end()) {
173  mh->inform("Mandatory edge '" + (*i)->getID() + "' does not allow vehicle '" + veh.getID() + "'.");
174  return;
175  }
176  i = oldEdges.erase(i);
177  } else {
178  ++i;
179  }
180  }
181  // reconnect remaining edges
182  newEdges.push_back(*(oldEdges.begin()));
183  std::vector<const ROEdge*>::iterator nextMandatory = mandatory.begin() + 1;
184  size_t lastMandatory = 0;
185  for (std::vector<const ROEdge*>::iterator i = oldEdges.begin() + 1;
186  i != oldEdges.end() && nextMandatory != mandatory.end(); ++i) {
187  if ((*(i - 1))->isConnectedTo(*i)) {
189  newEdges.push_back(*i);
190  } else {
191  std::vector<const ROEdge*> edges;
192  router.compute(newEdges.back(), *i, &veh, begin, edges);
193  if (edges.size() == 0) {
194  // backtrack: try to route from last mandatory edge to next mandatory edge
195  // XXX add option for backtracking in smaller increments
196  // (i.e. previous edge to edge after *i)
197  // we would then need to decide whether we have found a good
198  // tradeoff between faithfulness to the input data and detour-length
199  router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges);
200  if (edges.size() == 0) {
201  mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
202  return;
203  } else {
204  while (*i != *nextMandatory) {
205  ++i;
206  }
207  newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
208  }
209  }
210  std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
211  }
212  if (*i == *nextMandatory) {
213  nextMandatory++;
214  lastMandatory = newEdges.size() - 1;
215  }
216  }
217  }
218  if (myAlternatives[0]->getEdgeVector() != newEdges) {
219  WRITE_MESSAGE("Repaired route of vehicle '" + veh.getID() + "'.");
220  myNewRoute = true;
221  RGBColor* col = myAlternatives[0]->getColor() != 0 ? new RGBColor(*myAlternatives[0]->getColor()) : 0;
222  myPrecomputed = new RORoute(myID, 0, myAlternatives[0]->getProbability(), newEdges, col, myAlternatives[0]->getStops());
223  } else {
225  }
226 }
227 
228 
229 void
231  const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
232  if (myTryRepair) {
233  if (myNewRoute) {
234  delete myAlternatives[0];
235  myAlternatives.pop_back();
236  myAlternatives.push_back(current);
237  }
238  const SUMOReal costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
239  if (costs < 0) {
240  throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
241  }
242  current->setCosts(costs);
243  return;
244  }
245  // add the route when it's new
246  if (myNewRoute) {
247  myAlternatives.push_back(current);
248  }
249  // recompute the costs and (when a new route was added) scale the probabilities
250  const SUMOReal scale = SUMOReal(myAlternatives.size() - 1) / SUMOReal(myAlternatives.size());
251  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
252  RORoute* alt = *i;
253  // recompute the costs for all routes
254  const SUMOReal newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
255  if (newCosts < 0.) {
256  throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
257  }
258  assert(myAlternatives.size() != 0);
259  if (myNewRoute) {
260  if (*i == current) {
261  // set initial probability and costs
262  alt->setProbability((SUMOReal)(1.0 / (SUMOReal) myAlternatives.size()));
263  alt->setCosts(newCosts);
264  } else {
265  // rescale probs for all others
266  alt->setProbability(alt->getProbability() * scale);
267  }
268  }
270  }
271  assert(myAlternatives.size() != 0);
274  // remove with probability of 0 (not mentioned in Gawron)
275  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
276  if ((*i)->getProbability() == 0) {
277  delete *i;
278  i = myAlternatives.erase(i);
279  } else {
280  i++;
281  }
282  }
283  }
285  // only keep the routes with highest probability
286  sort(myAlternatives.begin(), myAlternatives.end(), ComparatorProbability());
287  for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + ROCostCalculator::getCalculator().getMaxRouteNumber(); i != myAlternatives.end(); i++) {
288  delete *i;
289  }
291  // rescale probabilities
292  SUMOReal newSum = 0;
293  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
294  newSum += (*i)->getProbability();
295  }
296  assert(newSum > 0);
297  // @note newSum may be larger than 1 for numerical reasons
298  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
299  (*i)->setProbability((*i)->getProbability() / newSum);
300  }
301  }
302 
303  // find the route to use
304  SUMOReal chosen = RandHelper::rand();
305  int pos = 0;
306  for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end() - 1; i++, pos++) {
307  chosen -= (*i)->getProbability();
308  if (chosen <= 0) {
309  myLastUsed = pos;
310  return;
311  }
312  }
313  myLastUsed = pos;
314 }
315 
316 
317 const ROEdge*
319  return myAlternatives[0]->getLast();
320 }
321 
322 
325  bool asAlternatives, bool withExitTimes) const {
326  if (asAlternatives) {
328  for (size_t i = 0; i != myAlternatives.size(); i++) {
329  myAlternatives[i]->writeXMLDefinition(dev, veh, true, withExitTimes);
330  }
331  dev.closeTag();
332  return dev;
333  } else {
334  return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, false, withExitTimes);
335  }
336 }
337 
338 
339 RORouteDef*
340 RORouteDef::copyOrigDest(const std::string& id) const {
341  RORouteDef* result = new RORouteDef(id, 0, true);
342  RORoute* route = myAlternatives[0];
343  RGBColor* col = route->getColor() != 0 ? new RGBColor(*route->getColor()) : 0;
344  std::vector<const ROEdge*> edges;
345  edges.push_back(route->getFirst());
346  edges.push_back(route->getLast());
347  result->addLoadedAlternative(new RORoute(id, 0, 1, edges, col, route->getStops()));
348  return result;
349 }
350 
351 
352 RORouteDef*
353 RORouteDef::copy(const std::string& id) const {
354  RORouteDef* result = new RORouteDef(id, 0, myTryRepair);
355  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
356  RORoute* route = *i;
357  RGBColor* col = route->getColor() != 0 ? new RGBColor(*route->getColor()) : 0;
358  result->addLoadedAlternative(new RORoute(id, 0, 1, route->getEdgeVector(), col, route->getStops()));
359  }
360  return result;
361 }
362 
363 
364 SUMOReal
366  SUMOReal sum = 0.;
367  for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
368  sum += (*i)->getProbability();
369  }
370  return sum;
371 }
372 
373 
374 /****************************************************************************/
SUMOTime getDepartureTime() const
Returns the time the vehicle starts at.
Definition: ROVehicle.h:111
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
const std::string & getID() const
Returns the id of the vehicle.
Definition: ROVehicle.h:102
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:257
bool myNewRoute
Information whether a new route was generated.
Definition: RORouteDef.h:158
static MsgHandler * getErrorInstance()
Returns the instance to add errors to.
Definition: MsgHandler.cpp:80
RORouteDef * copyOrigDest(const std::string &id) const
Returns a origin-destination copy of the route definition.
Definition: RORouteDef.cpp:340
const bool myTryRepair
Definition: RORouteDef.h:160
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:230
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:88
void addAlternativeDef(const RORouteDef *alternative)
Adds an alternative loaded from the file.
Definition: RORouteDef.cpp:81
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
static SUMOReal rand()
Returns a random real number in [0, 1)
Definition: RandHelper.h:62
void setProbability(SUMOReal prob)
Sets the probability of the route.
Definition: RORoute.cpp:80
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:98
void repairCurrentRoute(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:146
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:67
RORoute * myPrecomputed
precomputed route for out-of-order computation
Definition: RORouteDef.h:149
const std::string & getID() const
Returns the id.
Definition: Named.h:60
A vehicle as used by router.
Definition: ROVehicle.h:59
Helper base for things that are referenced and have to be saved only once.
const ROEdge * getLast() const
Returns the last edge in the route.
Definition: RORoute.h:102
OutputDevice & writeXMLDefinition(OutputDevice &dev, const ROVehicle *const veh, bool asAlternatives, bool withExitTimes) const
Saves the built route / route alternatives.
Definition: RORouteDef.cpp:324
const std::vector< const ROEdge * > & getStopEdges() const
Definition: ROVehicle.h:115
virtual void calculateProbabilities(std::vector< RORoute * > alternatives, const ROVehicle *const veh, const SUMOTime time)=0
calculate the probabilities in the logit model
const RGBColor * getColor() const
Returns this route's color.
Definition: RORoute.h:162
SUMOReal getProbability() const
Returns the probability the driver will take this route with.
Definition: RORoute.h:122
void setCosts(SUMOReal costs)
Sets the costs of the route.
Definition: RORoute.cpp:74
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:318
const ROEdge * getFirst() const
Returns the first edge in the route.
Definition: RORoute.h:93
A basic edge for routing applications.
Definition: ROEdge.h:69
Base class for objects which have an id.
Definition: Named.h:45
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:67
unsigned int myLastUsed
Index of the route used within the last step.
Definition: RORouteDef.h:152
RORouteDef(const std::string &id, const unsigned int lastUsed, const bool tryRepair)
Constructor.
Definition: RORouteDef.cpp:60
bool keepRoutes() const
std::string myID
The name of the object.
Definition: Named.h:128
const std::vector< const ROEdge * > & getEdgeVector() const
Returns the list of edges this route consists of.
Definition: RORoute.h:154
unsigned int getMaxRouteNumber() const
RORouteDef * copy(const std::string &id) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:353
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
Base class for a vehicle's route definition.
Definition: RORouteDef.h:64
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:71
virtual SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const =0
bool closeTag()
Closes the most recently opened tag.
#define SUMOReal
Definition: config.h:215
virtual void 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...
static ROCostCalculator & getCalculator()
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:201
std::vector< RORoute * > myAlternatives
The alternatives.
Definition: RORouteDef.h:155
SUMOReal getOverallProb() const
Returns the sum of the probablities of the contained routes.
Definition: RORouteDef.cpp:365
const std::vector< SUMOVehicleParameter::Stop > & getStops() const
Returns the list of stops this route contains.
Definition: RORoute.h:183
virtual void setCosts(RORoute *route, const SUMOReal costs, const bool isActive=false) const =0
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
A complete router's route.
Definition: RORoute.h:61