55 #define UNREACHABLE (std::numeric_limits<double>::max() / 1000.0) 83 template<
class E,
class V,
class PF>
90 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
104 traveltime(std::numeric_limits<double>::max()),
127 traveltime = std::numeric_limits<double>::max();
142 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
149 AStarRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
Operation operation,
const LookupTable*
const lookup = 0):
154 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
160 AStarRouter(
const std::vector<EdgeInfo>& edgeInfos,
bool unbuildIsWarning,
Operation operation,
const LookupTable*
const lookup = 0):
165 for (
typename std::vector<EdgeInfo>::const_iterator i = edgeInfos.begin(); i != edgeInfos.end(); ++i) {
184 for (
typename std::vector<EdgeInfo*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
192 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
193 SUMOTime msTime, std::vector<const E*>& into) {
194 assert(from != 0 && to != 0);
196 if (PF::operator()(from, vehicle)) {
197 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on source edge '" + from->getID() +
"'.");
200 if (PF::operator()(to, vehicle)) {
201 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on destination edge '" + to->getID() +
"'.");
205 #ifdef ASTAR_DEBUG_QUERY 206 std::cout <<
"DEBUG: starting search for '" << vehicle->getID() <<
"' speed: " <<
MIN2(vehicle->getMaxSpeed(),
myMaxSpeed * vehicle->getChosenSpeedFactor()) <<
" time: " <<
STEPS2TIME(msTime) <<
"\n";
212 if (toInfo.visited) {
221 fromInfo->traveltime = 0;
228 const double speed =
MIN2(vehicle->getMaxSpeed(),
myMaxSpeed * vehicle->getChosenSpeedFactor());
233 const E*
const minEdge = minimumInfo->edge;
238 #ifdef ASTAR_DEBUG_QUERY_PERF 239 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size())
241 +
" edges=" +
toString(into) +
")\n";
243 #ifdef ASTAR_DEBUG_VISITED 245 for (
typename std::vector<EdgeInfo>::const_iterator i =
myEdgeInfos.begin(); i !=
myEdgeInfos.end(); ++i) {
247 dev <<
"edge:" << i->edge->getID() <<
"\n";
256 myFound.push_back(minimumInfo);
257 minimumInfo->visited =
true;
258 #ifdef ASTAR_DEBUG_QUERY 259 std::cout <<
"DEBUG: hit=" << minEdge->getID()
260 <<
" TT=" << minimumInfo->traveltime
261 <<
" EF=" << this->
getEffort(minEdge, vehicle, time + minimumInfo->traveltime)
262 <<
" HT=" << minimumInfo->heuristicTime
263 <<
" Q(TT,HT,Edge)=";
265 std::cout << (*it)->traveltime <<
"," << (*it)->heuristicTime <<
"," << (*it)->edge->getID() <<
" ";
269 const double traveltime = minimumInfo->traveltime + this->
getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
271 const double heuristic_remaining = (
myLookupTable == 0 ? minEdge->getDistanceTo(to) / speed :
272 myLookupTable->
lowerBound(minEdge, to, speed, vehicle->getChosenSpeedFactor(), minEdge->getMinimumTravelTime(0), to->getMinimumTravelTime(0)));
277 const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
278 for (
typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
279 const E*
const follower = *it;
282 if (PF::operator()(follower, vehicle)) {
285 const double oldEffort = followerInfo->traveltime;
286 if ((!followerInfo->visited || mayRevisit) && traveltime < oldEffort) {
288 followerInfo->heuristicTime = traveltime + heuristic_remaining;
300 #ifdef ASTAR_DEBUG_QUERY_FOLLOWERS 301 std::cout <<
" follower=" << followerInfo->edge->getID() <<
" OEF=" << oldEffort <<
" TT=" << traveltime <<
" HR=" << heuristic_remaining <<
" HT=" << followerInfo->heuristicTime <<
"\n";
303 followerInfo->prev = minimumInfo;
304 if (oldEffort == std::numeric_limits<double>::max()) {
321 #ifdef ASTAR_DEBUG_QUERY_PERF 322 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccesful path length: " +
toString(into.size()) +
")\n";
324 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
332 for (
typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
333 if (PF::operator()(*i, v)) {
336 costs += this->
getEffort(*i, v, time + costs);
344 std::vector<const E*> tmp;
345 while (rbegin != 0) {
346 tmp.push_back(rbegin->edge);
347 rbegin = rbegin->prev;
349 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
double getEffort(const E *const e, const V *const v, double t) const
void close()
Closes the device and removes it from the dictionary.
AStarRouter(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation operation, const LookupTable *const lookup=0)
bool visited
The previous edge.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
virtual bool 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.
EdgeInfoComparator myComparator
std::string time2string(SUMOTime t)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Computes the shortest path through a network using the A* algorithm.
AStarRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const LookupTable *const lookup=0)
Constructor.
double myMaxSpeed
maximum speed in the network
double heuristicTime
Estimated time to reach the edge (traveltime + lower bound on remaining time)
double(* Operation)(const E *const, const V *const, double)
EdgeInfo * prev
The previous edge.
virtual SUMOAbstractRouter< E, V > * clone()
FullLookupTable< E, V > FLT
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
EdgeInfo(const E *e)
Constructor.
virtual ~AStarRouter()
Destructor.
bool myBulkMode
whether we are currently operating several route queries in a bulk
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
Operation myOperation
The object's operation to perform.
LandmarkLookupTable< E, V > LMLT
virtual bool consistent() const =0
whether the heuristic ist consistent (found nodes are always visited on the shortest path the first t...
double traveltime
Effort to reach the edge.
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
virtual double lowerBound(const E *from, const E *to, double speed, double speedFactor, double fromEffort, double toEffort) const =0
provide a lower bound on the distance between from and to (excluding traveltime of both edges) ...
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
static OutputDevice & getDevice(const std::string &name)
Returns the described OutputDevice.
void inform(std::string msg, bool addType=true)
adds a new error to the list
Static storage of an output device and its base (abstract) implementation.
void endQuery(int visits)
const LookupTable *const myLookupTable
the lookup table for travel time heuristics
Computes the shortest path through a network using the A* algorithm.
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
AbstractLookupTable< E, V > LookupTable
vehicles ignoring classes
const E * edge
The current edge.