SUMO - Simulation of Urban MObility
AStarRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // A* Algorithm using euclidean distance heuristic.
10 // Based on DijkstraRouterTT. For routing by effort a novel heuristic would be needed.
11 /****************************************************************************/
12 // SUMO, Simulation of Urban MObility; see http://sumo-sim.org/
13 // Copyright (C) 2012-2014 DLR (http://www.dlr.de/) and contributors
14 /****************************************************************************/
15 //
16 // This file is part of SUMO.
17 // SUMO is free software: you can redistribute it and/or modify
18 // it under the terms of the GNU General Public License as published by
19 // the Free Software Foundation, either version 3 of the License, or
20 // (at your option) any later version.
21 //
22 /****************************************************************************/
23 #ifndef AStarRouterTT_h
24 #define AStarRouterTT_h
25 
26 
27 // ===========================================================================
28 // included modules
29 // ===========================================================================
30 #ifdef _MSC_VER
31 #include <windows_config.h>
32 #else
33 #include <config.h>
34 #endif
35 
36 #include <cassert>
37 #include <string>
38 #include <functional>
39 #include <vector>
40 #include <set>
41 #include <limits>
42 #include <algorithm>
43 #include <iterator>
45 #include <utils/common/StdDefs.h>
46 #include <utils/common/ToString.h>
47 #include "SUMOAbstractRouter.h"
48 
49 
50 // ===========================================================================
51 // class definitions
52 // ===========================================================================
68 template<class E, class V, class PF>
69 class AStarRouterTTBase : public SUMOAbstractRouter<E, V>, public PF {
72 
73 public:
75  AStarRouterTTBase(size_t noE, bool unbuildIsWarning):
76  SUMOAbstractRouter<E, V>("AStarRouter"),
77  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
78  for (size_t i = 0; i < noE; i++) {
79  myEdgeInfos.push_back(EdgeInfo(i));
80  }
81  }
82 
84  virtual ~AStarRouterTTBase() {}
85 
91  class EdgeInfo {
92  public:
94  EdgeInfo(size_t id) :
95  edge(E::dictionary(id)),
96  traveltime(std::numeric_limits<SUMOReal>::max()),
97  heuristicTime(std::numeric_limits<SUMOReal>::max()),
98  prev(0),
99  visited(false)
100  {}
101 
103  const E* edge;
104 
107 
110 
113 
115  bool visited;
116 
117  inline void reset() {
118  // heuristicTime is set before adding to the frontier, thus no reset is needed
119  traveltime = std::numeric_limits<SUMOReal>::max();
120  visited = false;
121  }
122 
123  };
124 
130  public:
132  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
133  if (nod1->heuristicTime == nod2->heuristicTime) {
134  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
135  }
136  return nod1->heuristicTime > nod2->heuristicTime;
137  }
138  };
139 
140  virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0;
141 
142 
143  void init() {
144  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
145  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
146  (*i)->reset();
147  }
148  myFrontierList.clear();
149  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
150  (*i)->reset();
151  }
152  myFound.clear();
153  }
154 
155 
157  virtual void compute(const E* from, const E* to, const V* const vehicle,
158  SUMOTime msTime, std::vector<const E*>& into) {
159  assert(from != 0 && to != 0);
160  startQuery();
161  const SUMOReal time = STEPS2TIME(msTime);
162  init();
163  // add begin node
164  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
165  fromInfo->traveltime = 0;
166  fromInfo->prev = 0;
167  myFrontierList.push_back(fromInfo);
168  // loop
169  int num_visited = 0;
170  while (!myFrontierList.empty()) {
171  num_visited += 1;
172  // use the node with the minimal length
173  EdgeInfo* const minimumInfo = myFrontierList.front();
174  const E* const minEdge = minimumInfo->edge;
175  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
176  myFrontierList.pop_back();
177  myFound.push_back(minimumInfo);
178  // check whether the destination node was already reached
179  if (minEdge == to) {
180  buildPathFrom(minimumInfo, into);
181  endQuery(num_visited);
182  // DEBUG
183  //std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
184  return;
185  }
186  minimumInfo->visited = true;
187  const SUMOReal traveltime = minimumInfo->traveltime + getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
188  // check all ways from the node with the minimal length
189  unsigned int i = 0;
190  const unsigned int length_size = minEdge->getNoFollowing();
191  for (i = 0; i < length_size; i++) {
192  const E* const follower = minEdge->getFollower(i);
193  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
194  // check whether it can be used
195  if (PF::operator()(follower, vehicle)) {
196  continue;
197  }
198  const SUMOReal oldEffort = followerInfo->traveltime;
199  if (!followerInfo->visited && traveltime < oldEffort) {
200  // admissible A* heuristic: straight line distance at maximum speed
201  const SUMOReal heuristic_remaining = minEdge->getDistanceTo(to) / vehicle->getMaxSpeed();
202  followerInfo->traveltime = traveltime;
203  followerInfo->heuristicTime = traveltime + heuristic_remaining;
204  followerInfo->prev = minimumInfo;
205  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
206  myFrontierList.push_back(followerInfo);
207  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
208  } else {
209  push_heap(myFrontierList.begin(),
210  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
211  myComparator);
212  }
213  }
214  }
215  }
216  endQuery(num_visited);
217  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
218  }
219 
220 
221  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
222  const SUMOReal time = STEPS2TIME(msTime);
223  SUMOReal costs = 0;
224  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
225  if (PF::operator()(*i, v)) {
226  return -1;
227  }
228  costs += getEffort(*i, v, time + costs);
229  }
230  return costs;
231  }
232 
233 public:
235  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
236  std::deque<const E*> tmp;
237  while (rbegin != 0) {
238  tmp.push_front((E*) rbegin->edge); // !!!
239  rbegin = rbegin->prev;
240  }
241  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
242  }
243 
244 protected:
246  std::vector<EdgeInfo> myEdgeInfos;
247 
249  std::vector<EdgeInfo*> myFrontierList;
251  std::vector<EdgeInfo*> myFound;
252 
253  EdgeInfoComparator myComparator;
254 
257 
258 };
259 
260 
261 template<class E, class V, class PF>
262 class AStarRouterTT_ByProxi : public AStarRouterTTBase<E, V, PF> {
263 public:
265  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
266 
267  AStarRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation operation):
268  AStarRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly),
269  myOperation(operation) {}
270 
271  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
272  return (*myOperation)(e, v, t);
273  }
274 
275 private:
278 };
279 
280 
281 template<class E, class V, class PF>
282 class AStarRouterTT_Direct : public AStarRouterTTBase<E, V, PF> {
283 public:
285  typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const;
286 
287  AStarRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation)
288  : AStarRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly), myOperation(operation) {}
289 
290  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
291  return (e->*myOperation)(v, t);
292  }
293 
294 private:
296 };
297 
298 
299 #endif
300 
301 /****************************************************************************/
302 
SUMOReal heuristicTime
Estimated time to reach the edge (traveltime + lower bound on remaining time)
Definition: AStarRouter.h:109
bool visited
The previous edge.
Definition: AStarRouter.h:115
EdgeInfoComparator myComparator
Definition: AStarRouter.h:253
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
Definition: AStarRouter.h:271
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
Definition: AStarRouter.h:249
AStarRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation)
Definition: AStarRouter.h:287
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
Definition: AStarRouter.h:246
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
Definition: AStarRouter.h:132
virtual SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const =0
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
Definition: AStarRouter.h:221
#define max(a, b)
Definition: polyfonts.c:65
SUMOReal(E::* Operation)(const V *const, SUMOReal) const
Type of the function that is used to retrieve the edge effort.
Definition: AStarRouter.h:285
SUMOReal traveltime
Effort to reach the edge.
Definition: AStarRouter.h:106
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
virtual ~AStarRouterTTBase()
Destructor.
Definition: AStarRouter.h:84
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
Definition: AStarRouter.h:290
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
Definition: AStarRouter.h:251
const E * edge
The current edge.
Definition: AStarRouter.h:103
EdgeInfo * prev
The previous edge.
Definition: AStarRouter.h:112
Operation myOperation
The object's operation to perform.
Definition: AStarRouter.h:277
AStarRouterTTBase(size_t noE, bool unbuildIsWarning)
Constructor.
Definition: AStarRouter.h:75
EdgeInfo(size_t id)
Constructor.
Definition: AStarRouter.h:94
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
void buildPathFrom(EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
Definition: AStarRouter.h:235
virtual 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.
Definition: AStarRouter.h:157
#define SUMOReal
Definition: config.h:215
void endQuery(int visits)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: AStarRouter.h:256
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
Definition: AStarRouter.h:265
AStarRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation operation)
Definition: AStarRouter.h:267