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