SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
BulkStarRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // A* Algorithm using shortest-path-in-fast-graph-heuristic for bulk routing
10 // This router is made for routing multiple sources (at different times) to the same destination
11 // In the reverse graph (using maximum edge speed) a lower-bound shortest path tree from the target is built.
12 // These optimistic distances are then used as admissable heuristc
13 // when routing forward in the time-dependent graph from multiple sources.
14 // @note: this heuristic does not perform well if the actual vehicles are much slower than the maximum edge speeds
15 // @note: this heuristic also does not perform well if the actual vehicles have usage restrictions
16 // @todo: add option for setting maximum speed
17 /****************************************************************************/
18 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
19 // Copyright (C) 2001-2015 DLR (http://www.dlr.de/) and contributors
20 /****************************************************************************/
21 //
22 // This file is part of SUMO.
23 // SUMO is free software: you can redistribute it and/or modify
24 // it under the terms of the GNU General Public License as published by
25 // the Free Software Foundation, either version 3 of the License, or
26 // (at your option) any later version.
27 //
28 /****************************************************************************/
29 #ifndef BulkStarRouter_h
30 #define BulkStarRouter_h
31 
32 
33 // ===========================================================================
34 // included modules
35 // ===========================================================================
36 #ifdef _MSC_VER
37 #include <windows_config.h>
38 #else
39 #include <config.h>
40 #endif
41 
42 #include <string>
43 #include <functional>
44 #include <vector>
45 #include <set>
46 #include <limits>
47 #include <algorithm>
48 #include <iterator>
50 #include <utils/common/StdDefs.h>
51 #include <utils/common/ToString.h>
53 
54 
55 // ===========================================================================
56 // class definitions
57 // ===========================================================================
73 template<class E, class V, class PF>
74 class BulkStarRouter: public SUMOAbstractRouter<E, V>, public PF {
75 
76 public:
78  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
79  typedef SUMOReal(E::* MinTTOperation)(const V* const) const;
80 
81 
83  BulkStarRouter(size_t noE, bool unbuildIsWarning, Operation operation, MinTTOperation minTTOperation) :
84  SUMOAbstractRouter<E, V>(operation, "BulkStarRouter"),
85  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
86  myMinTTOperation(minTTOperation),
88  for (size_t i = 0; i < noE; i++) {
89  myEdgeInfos.push_back(EdgeInfo(i));
90  }
91  }
92 
94  virtual ~BulkStarRouter() {}
95 
96  virtual SUMOAbstractRouter<E, V>* clone() const {
98  }
99 
105  class EdgeInfo {
106  public:
108  EdgeInfo(size_t id) :
109  edge(E::dictionary(id)),
110  traveltime(std::numeric_limits<SUMOReal>::max()),
111  heuristicTime(std::numeric_limits<SUMOReal>::max()),
112  minRemaining(0),
113  prev(0),
114  visited(false) {}
115 
117  const E* edge;
118 
121 
124 
127 
130 
132  bool visited;
133 
134  inline void reset() {
135  // heuristicTime is set before adding to the frontier, thus no reset is needed
136  traveltime = std::numeric_limits<SUMOReal>::max();
137  visited = false;
138  }
139  };
140 
146  public:
148  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
149  if (nod1->heuristicTime == nod2->heuristicTime) {
150  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
151  }
152  return nod1->heuristicTime > nod2->heuristicTime;
153  }
154  };
155 
156  inline SUMOReal getMinEffort(const E* const e, const V* const v) const {
157  return (e->*myMinTTOperation)(v);
158  }
159 
160 
167  void prepare(const E* destination, const V* fastestVehicle, bool skip) {
168  if (skip) {
170  return;
171  }
172  myPreparedDestination = destination;
173  for (typename std::vector<EdgeInfo>::iterator i = myEdgeInfos.begin(); i != myEdgeInfos.end(); i++) {
174  (*i).reset();
175  (*i).minRemaining = 0;
176  }
177  myFrontier.clear();
178  myFound.clear();
179  // add begin node
180  EdgeInfo* const fromInfo = &(myEdgeInfos[destination->getNumericalID()]);
181  fromInfo->traveltime = 0;
182  fromInfo->prev = 0;
183  myFrontier.push_back(fromInfo);
184  // loop
185  int num_visited = 0;
186  while (!myFrontier.empty()) {
187  num_visited += 1;
188  // use the node with the minimal length
189  EdgeInfo* const minimumInfo = myFrontier.front();
190  const E* const minEdge = minimumInfo->edge;
191  pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
192  myFrontier.pop_back();
193  myFound.push_back(minimumInfo);
194  minimumInfo->visited = true;
195  const SUMOReal traveltime = minimumInfo->traveltime + getMinEffort(minEdge, fastestVehicle);
196  // check all ways from the node with the minimal length
197  for (typename std::vector<E*>::const_iterator it = minEdge->getPredecessors().begin(); it != minEdge->getPredecessors().end(); it++) {
198  const E* const follower = *it;
199  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
200  const SUMOReal oldEffort = followerInfo->traveltime;
201  if (!followerInfo->visited && traveltime < oldEffort) {
202  followerInfo->traveltime = traveltime;
203  followerInfo->minRemaining = traveltime;
204  followerInfo->heuristicTime = traveltime; // plain dijkstra
205  followerInfo->prev = minimumInfo;
206  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
207  myFrontier.push_back(followerInfo);
208  push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
209  } else {
210  push_heap(myFrontier.begin(),
211  find(myFrontier.begin(), myFrontier.end(), followerInfo) + 1,
212  myComparator);
213  }
214  }
215  }
216  }
217  // DEBUG
218  //std::cout << "visited " + toString(num_visited) + " edges during pre-computation\n";
219 
220  // DEBUG
221  //std::vector<const E*> debugPath;
222  //for (typename std::vector<EdgeInfo>::iterator it = myEdgeInfos.begin(); it != myEdgeInfos.end(); it++) {
223  // if (it->edge->getID() == "src") {
224  // buildPathFrom(&(*it), debugPath);
225  // std::cout << "shortest path in reverse graph:\n";
226  // for (typename std::vector<const E*>::iterator it_path = debugPath.begin(); it_path != debugPath.end(); it_path++) {
227  // std::cout << (*it_path)->getID() << " ";
228  // }
229  // std::cout << "\n";
230  // }
231  //}
232  }
233 
234 
235  void init() {
236  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
237  for (typename std::vector<EdgeInfo*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
238  (*i)->reset();
239  }
240  myFrontier.clear();
241  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
242  (*i)->reset();
243  }
244  myFound.clear();
245  }
246 
247 
249  void compute(const E* from, const E* to, const V* const vehicle,
250  SUMOTime msTime, std::vector<const E*>& into) {
251  assert(from != 0 && to != 0);
252  this->startQuery();
253  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
254  init();
255  const Prepared prepared = (myPreparedDestination == 0 ?
256  NO : (myPreparedDestination == to ? YES_EXACT : YES));
257  const SUMOReal time = STEPS2TIME(msTime);
258  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
259  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
260  fromInfo->traveltime = 0;
261  fromInfo->prev = 0;
262  myFrontier.push_back(fromInfo);
263  // loop
264  int num_visited = 0;
265  while (!myFrontier.empty()) {
266  num_visited += 1;
267  // use the node with the minimal length
268  EdgeInfo* const minimumInfo = myFrontier.front();
269  const E* const minEdge = minimumInfo->edge;
270  pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
271  myFrontier.pop_back();
272  myFound.push_back(minimumInfo);
273  // check whether the destination node was already reached
274  if (minEdge == to) {
275  buildPathFrom(minimumInfo, into);
276  this->endQuery(num_visited);
277  // DEBUG
278  //std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
279  return;
280  }
281  minimumInfo->visited = true;
282  const SUMOReal traveltime = minimumInfo->traveltime + this->getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
283  // check all ways from the node with the minimal length
284  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
285  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
286  const E* const follower = *it;
287  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
288  // check whether it can be used
289  if (PF::operator()(follower, vehicle)) {
290  continue;
291  }
292  const SUMOReal oldEffort = followerInfo->traveltime;
293  if (!followerInfo->visited && traveltime < oldEffort) {
294  followerInfo->traveltime = traveltime;
295  // admissible A* heuristic:
296  SUMOReal heuristic_remaining = 0;
297  switch (prepared) {
298  case NO:
299  // straight line distance at maximum speed
300  heuristic_remaining = minEdge->getDistanceTo(to) / vehicle->getMaxSpeed();
301  break;
302  case YES_EXACT:
303  // shortest path for fastest vehicle in uncongested network
304  heuristic_remaining = minimumInfo->minRemaining;
305  break;
306  case YES:
307  // triangle inequality
308  heuristic_remaining = MAX2(
309  minimumInfo->minRemaining - toInfo.minRemaining,
310  minEdge->getDistanceTo(to) / vehicle->getMaxSpeed());
311  break;
312  }
313  followerInfo->heuristicTime = traveltime + heuristic_remaining;
314  followerInfo->prev = minimumInfo;
315  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
316  myFrontier.push_back(followerInfo);
317  push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
318  } else {
319  push_heap(myFrontier.begin(),
320  find(myFrontier.begin(), myFrontier.end(), followerInfo) + 1,
321  myComparator);
322  }
323  }
324  }
325  }
326  this->endQuery(num_visited);
327  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
328  }
329 
330 
331  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
332  const SUMOReal time = STEPS2TIME(msTime);
333  SUMOReal costs = 0;
334  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
335  if (PF::operator()(*i, v)) {
336  return -1;
337  }
338  costs += this->getEffort(*i, v, time + costs);
339  }
340  return costs;
341  }
342 
343 public:
345  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
346  std::deque<const E*> tmp;
347  while (rbegin != 0) {
348  tmp.push_front((E*) rbegin->edge); // !!!
349  rbegin = rbegin->prev;
350  }
351  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
352  }
353 
354 private:
355  enum Prepared {
356  NO,
358  YES_EXACT // optimistic shortest paths are computed for the current destination
359  };
360 
362  std::vector<EdgeInfo> myEdgeInfos;
363 
365  std::vector<EdgeInfo*> myFrontier;
367  std::vector<EdgeInfo*> myFound;
368 
370 
373 
375 
377 };
378 
379 
380 #endif
381 
382 /****************************************************************************/
383 
MinTTOperation myMinTTOperation
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
const E * edge
The current edge.
void compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into)
Builds the route between the given edges using the minimum travel time.
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
EdgeInfo * prev
The previous edge.
void prepare(const E *destination, const V *fastestVehicle, bool skip)
Builds a complete shorteset path tree in the (static) reverse graph from destination (Dijkstra until ...
T MAX2(T a, T b)
Definition: StdDefs.h:74
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
MsgHandler *const myErrorMsgHandler
the handler for routing errors
SUMOReal minRemaining
minimum time to destination
const E * myPreparedDestination
#define max(a, b)
Definition: polyfonts.c:65
bool visited
The previous edge.
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
Operation myOperation
The object's operation to perform.
virtual ~BulkStarRouter()
Destructor.
void buildPathFrom(EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
SUMOReal traveltime
Effort to reach the edge.
BulkStarRouter(size_t noE, bool unbuildIsWarning, Operation operation, MinTTOperation minTTOperation)
Constructor.
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
std::vector< EdgeInfo * > myFrontier
A container for reusage of the min edge heap.
virtual SUMOAbstractRouter< E, V > * clone() const
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
EdgeInfo(size_t id)
Constructor.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
int SUMOTime
Definition: SUMOTime.h:43
SUMOReal getMinEffort(const E *const e, const V *const v) const
#define SUMOReal
Definition: config.h:218
SUMOReal heuristicTime
Estimated time to reach the edge (traveltime + lower bound on remaining time)
void endQuery(int visits)
SUMOReal(E::* MinTTOperation)(const V *const) const
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
EdgeInfoComparator myComparator
vehicles ignoring classes