Timeout in initialization of goal direction heuristic for park and ride

[mattwigway]

When doing a CAR,TRANSIT search, I see these messages:

12:10:06.455 WARN (AStar.java:120) Timeout during initialization of goal direction heuristic.
12:10:06.455 WARN (GraphPathFinder.java:167) SPT was null.

and no results are returned. Noted on commit d9f66ab4f8f18c82a66a2918f0b7ab64dce28df2 , will verify with master.

[mattwigway]

Per comment from @buma, looks like park+ride only works on arrive-by searches.

[buma]

Strange thing is that arrive-by is IMHO harder to write the code for graph search since everything needs to happen backwards.

In depart search ParkAndRideLinkEdge didn't even came into consideration. (This it the edge from street vertices to P+R vertex). I first thought that maybe it is not the best path for some reason but according to AStar it doesn't even find it even though it is found on same query without a problem on arrive-by. I'm working on bisect now to see when it stopped working.

EDIT: I also checked and P+R are definitely connected to the graph correctly.

[buma]

Problem seems to be in InterleavedBidirectionalHeuristic since on depart search each ParkAndRideVertex has remaining weight -1 and is ignored for that reason in AStar:195 and subsequently each ParkAndRideLinkEdge is ignored for that reason. Because ParkAndRideLinkEdge is never put into the heap Shortest path algorithm can never find shortest path with ParkAndRide in it.

On arrive by searches heuristic gets weight (455 in one vertex) for ParkAndRideVertex, remaining weight is > 0 and ParkAndRideLinkEdges are considered.

[buma]

And the funny thing is that tests for P+R and B+R are testing depart only mode. And they work. But fail on arrive by mode :).

OK that makes sense since the heuristic function is different: EuclideanRemainingWeightHeuristic.

[buma]

It seems that P+R broke on switch from normal mode to long distance mode. Since in commit 40efb5652b698f179cf816478e which is before the switch I can route correctly with arriveby and depart from with P+R/B+R/K+R. But if I enable long distance mode I can't route in either direction. In February long distance mode became the default. More in #1723. There was also talk about this on mailing list: https://groups.google.com/forum/#!msg/opentripplanner-dev/32XP6zxTzG4/lD-uekkruxUJ It seems that some work was done to support P+R (since it works in one direction) but it probably wasn't tested fully.

[buma]

@laurentg: Any ideas how to fix this since I think you implemented P+R?

[laurentg]

@buma So you mean arrive by P+R / B+R work before 40efb5652b698f179cf816478e and not after? No idea, seems a bit cryptic to me, I did not had the time to look at the whole picture.

[buma]

It seems that P+R and other *+R modes worked correctly in arrive by and depart from modes in 40efb56 and before. But even on that commit they didn't work in Long distance mode. On linked mailing list discussion you said that it needs to be made sure that P+R and the rest of the modes would work in long distance mode which now became the default. Some work seems that it was made since it now works only in arrive by searches. But not on depart from. (because all the P+R vertices get weight -1 in interlievedBidirectionalHeuristic). I just thought that you would now better what could be the problem since you implemented it.

[buma]

"Quickfix" seems to be in InterleavedBidirectionalHeuristic.java line 312.

if (!fromTarget) {

needs to be replaced with:

if (!fromTarget && ! (v instanceof ParkAndRideVertex || v instanceof BikeParkVertex )) {

This makes arriveBy and departFrom P+R, B+R work again. But the question still remains why .

Currently in arriveBy search in InterleavedBidirectionalHeuristic.initialize streetSearch is called twice. First with fromTarget false for foreward search. This search doesn't traverse any ParkRideLinkEdges. Next is same search but with fromTarget true. This seems to be backward street search. If fromTarget is true arriveBy is set to negative of what it is in streetSearch so to false in this case. This search traverses ParRideLinkEdges weights for ParkRideVertices are saved in binHeap and also adds ParRideVertices to weights map with correct weight. Up until now all ParkRideEdges were traversed with arriveBy false (even though this is arriveBy =true search). Now Astar start searching with arriveBy true. Estimated remaining weight for ParkRideVertices are corect since they are correctly inserted into weight map. And best path is found. The only thing I don't know is why Astar search is called 3 times.

For depart from search in InterleavedBidirectionalHeuristic.initialize streetSearch is also called twice. The difference is that in foreward search (fromTarget = false) ParkRideLinkEdges are traversed weights for ParkRideVertices are saved in binHeap but newer saved in weights map since fromTarget is false.

In backward street search (fromTarget=true) no ParkRideLinkEdges are traversed and no ParkRideVertices are saved into weights map.

In Astar search Estimated remaining weight for each ParkRideVertex is -1 (since correct weight was newer saved) and for that reason no ParkRideLinkEdge is never even considered in AStar search. Astar is called only 1.

backward, forward and Astar search is made with arriveBy=false.

If I change the line with fromTarget. Weights are correctly saved in foreward search and Astar is run 3 times. But this change can't be fix for the bug.

IMHO arriveBy and departFrom searches should be somehow symmetric. But now depart from makes all searches with ariveby=False and arriveBy search foreward and backward is with arriveBy false and only AStar searches are with arriveBy =true.