org.opentripplanner.routing.algorithm.strategies

Class InterleavedBidirectionalHeuristic

java.lang.Object

org.opentripplanner.routing.algorithm.strategies.InterleavedBidirectionalHeuristic

All Implemented Interfaces:

Serializable, RemainingWeightHeuristic

public class InterleavedBidirectionalHeuristic
extends Object
implements RemainingWeightHeuristic

Euclidean heuristics are terrible for transit because the maximum transit speed is quite high, especially relative to the walk speed. Transit can require going away from the destination in Euclidean space to get closer according to the travel time metric. This heuristic is designed to be good for transit. After many experiments embedding transit travel time metrics in tables or low-dimensional Euclidean space I eventually came to the conclusion that the most efficient structure for representing the metric was already right in front of us: a graph. This heuristic searches backward from the target over the street and transit network, modifying it on the fly to remove any time-dependent component (e.g. by evaluating all boarding wait times as zero). This produces an admissible heuristic (which always underestimates path weight) making it valid independent of the clock time. This is important because you don't know precisely what time you will arrive at the destination until you get there.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
InterleavedBidirectionalHeuristic(Graph graph)

Method Summary

Modifier and Type	Method and Description
void	doSomeWork() Do up to N iterations as long as the queue is not empty
double	estimateRemainingWeight(State s) We must return an underestimate of the cost to reach the destination no matter how much progress has been made on the heuristic search.
void	initialize(RoutingRequest options, long abortTime) Perform any one-time setup and pre-computation that will be needed by later calls to computeForwardWeight/computeReverseWeight.
void	reset() Reset any cached data in the heuristic, before reuse in a search with the same destination.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

InterleavedBidirectionalHeuristic

public InterleavedBidirectionalHeuristic(Graph graph)

Method Detail

initialize

public void initialize(RoutingRequest options,
                       long abortTime)

Description copied from interface: RemainingWeightHeuristic

Perform any one-time setup and pre-computation that will be needed by later calls to computeForwardWeight/computeReverseWeight. We may want to start from multiple origin states, so initialization cannot depend on the origin vertex or state.

Specified by:

initialize in interface RemainingWeightHeuristic

abortTime - time since the Epoch in milliseconds at which we should bail out of initialization, or Long.MAX_VALUE for no limit.

doSomeWork

public void doSomeWork()

Do up to N iterations as long as the queue is not empty

Specified by:

doSomeWork in interface RemainingWeightHeuristic

estimateRemainingWeight

public double estimateRemainingWeight(State s)

We must return an underestimate of the cost to reach the destination no matter how much progress has been made on the heuristic search. All on-street vertices must be explored by the heuristic before the main search starts. This allows us to completely skip walking outside a certain radius of the origin/destination.

Specified by:

estimateRemainingWeight in interface RemainingWeightHeuristic

reset

public void reset()

Description copied from interface: RemainingWeightHeuristic

Reset any cached data in the heuristic, before reuse in a search with the same destination.

Specified by:

reset in interface RemainingWeightHeuristic