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

This the goal direction heuristic used for transit searches. Euclidean heuristics are terrible for transit routing 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 approach it according to the travel time metric. This heuristic is designed to be good for transit. After many experiments storing travel time metrics in tables or embedding them in 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 vertex over the street and transit network, removing any time-dependent component of the network (e.g. by evaluating all boarding wait times as zero). This produces an admissible heuristic (i.e. it 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. Because we often make use of the first path we find in the main search, this heuristic must be both admissible and consistent (monotonic). If the heuristic is non-monotonic, nodes can be re-discovered and paths are not necessarily discovered in order of increasing weight. When finding paths one by one and banning trips or routes, suboptimal paths may be found and reported before or instead of optimal ones. This heuristic was previously not consistent for the reasons discussed in ticket #2153. It was possible for the "zero zone" around the origin to overlap the egress zone around the destination, leading to decreases in the heuristic across an edge that were greater in magnitude than the weight of that edge. This has been solved by creating two separate distance maps, one pre-transit and one post-transit. Note that the backward search does not happen in a separate thread. It is interleaved with the main search in a ratio of N:1 iterations.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
InterleavedBidirectionalHeuristic()

Method Summary

Modifier and Type	Method and Description
void	doSomeWork() Move backward N steps through the transit network.
double	estimateRemainingWeight(State s) This function supplies the main search with an (under)estimate of the remaining path weight to the target.
void	initialize(RoutingRequest request, long abortTime) Before the main search begins, the heuristic must search on the streets around the origin and destination.
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()

Method Detail

initialize

public void initialize(RoutingRequest request,
                       long abortTime)

Before the main search begins, the heuristic must search on the streets around the origin and destination. This also sets up the initial states for the reverse search through the transit network, which progressively improves lower bounds on travel time to the target to guide the main search.

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.

estimateRemainingWeight

public double estimateRemainingWeight(State s)

This function supplies the main search with an (under)estimate of the remaining path weight to the target. No matter how much progress has been made on the reverse heuristic search, we must return an underestimate of the cost to reach the target (i.e. the heuristic must be admissible). All on-street vertices within walking distance of the origin or destination will have been explored by the heuristic before the main search starts.

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

doSomeWork

public void doSomeWork()

Move backward N steps through the transit network. This improves the heuristic's knowledge of the transit network as seen from the target, making its lower bounds on path weight progressively more accurate.

Specified by:

doSomeWork in interface RemainingWeightHeuristic