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. This heuristic effectively makes traversal of non-transit vertices far away from the origin and destination impossible by returning an estimated weight of Inifinity for vertices not within walking or driving distance of the origin or destination. The heuristic is initialized before the main graph search and attempts to discover all non-transit verticies up to a certain limit. Transit vertices are also explored, but only during the main graph search in the doSomeWork() method. During the main graph search, this heuristic estimates remaining weights of vertices by returning the lower bound weights at vertices found during the heuristic initialization and doSomeWork method. The limits encountered are currently either the RoutingRequest.maxWalkDistance or the RoutingRequest.maxPreTransitTime. The maxWalkDistance currently applies to both walking and bicycling. When traversing the network in a car, the maxWalkDistance is not incremented. To mask off excessive travel by car, the maxPreTransitTime is used as a limiter. However for driving a car after using transit (for example with either a TNC, car rental or ride and kiss) a limitation is added in streetSearch(org.opentripplanner.routing.core.RoutingRequest, boolean, long) to stop searching through the graph once the origin has been found. In order for this heuristic to return the proper estimated weights during the main graph search, it must be sensitive to the current mode of the current state in the main graph search. For example, in Park and Ride searches, the initialization of the heuristic will have explored many more vertices while driving compared to the number of vertices explored by walking from the origin/destination. Therefore in the estimateRemainingWeight(org.opentripplanner.routing.core.State) method, a mode-specific weight is returned when a non-transit vertex is being evaluated. Shown below are a few visualizations of what the heuristic will do in various searches. Key: O = origin vertex D = destination vertex W = reachable by walking up to maxWalkDistance C = reachable by car up to the maxPreTransitTime B = reachable by car or walking - = vertices unreachable by either mode In a simple TRANSIT,WALK search, only the vertices within walking distance are marked as reachable by the heuristic. ---------------- ----WWW-----WWW- ----WOW-----WDW- ----WWW-----WWW- ---------------- In a TRANSIT,WALK,CAR (park and ride) search, there will be vertices reachable by both walking and driving, some only by walking and some only reachable by driving. The park and ride search does not allow driving after transit, so the vertices around the destination are only reachable by walking. ----CCC--------- ---CBBBC----WWW- ---CBOWCC---WDW- ---CBWWCC---WWW- ----CCCC-------- In a TRANSIT,WALK,CAR_HAIL (transit + TNC) search, there are many more vertices explored while searching from the destination in this current implementation. The preTransitVertices may still look about the same as the above graphic, but the postTransitVertices could look as follows: --------CCCCCCC- ------CCCCCCBBBC -----OCCCC--WDBC ------CCCCC-BWBC -------CCCCCCCCC This heuristic is espeically useful for large graphs, but could be turned off entirely for small graphs.

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 (or driving) 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