How to find n nearest OSM nodes of a specific type "along" a route?

[HaukeP]

Hi! I’ve just started using GraphHopper as a library (i.e. not through the web API, so I can access the low-level API).

Short version of my question: I’d like to implement basically Google Maps’ “Search along route” functionality for OSM nodes with specific attributes (e.g. finding the nearest waste basket along a route). How would I do this with GraphHopper?

Longer version with example:

• Assume I have calculated a route for a walking profile.
• Now I want search for waste baskets “along” the route, i.e. I want to retrieve a list of n alternative routes that “come closest” to a waste basket, ordered by either added walking distance or walking time (or both).
• A waste basket should be identified by being an OSM node with either waste_basket=yes or amenity=waste_basket.
• How would I implement this with GraphHopper?

I’ve made some initial thoughts on this before posting:

1. To make waste baskets (or any other OSM node of a specific type) “known” to GraphHopper, I assume that I’ll have to enhance the importer. Despite the topic “OSM Data in GraphHopper 3.0” being about a somewhat different use case, it might give me a hint where to start adding functionality to the import process to also capture waste baskets (or other OSM nodes of interest).

2. As most likely no waste basket will be part of a way but basically always be placed next to a way, I expect some preprocessing to be required: I would either need to virtually snap the waste basket onto the respective closest way (most likely the easier option) - or I would need to add a virtual edge from the basket to its nearest way (most likely the option that captures the costs of the detour a little more accurately).

3. Now to the hard part: actually searching along the route. As a naive approach, I could simply loop through ALL waste baskets, calculate the route from start to end via the respective waste basket, and then select the n best baskets. With there currently being more than 7000 waste_basket=yes and more than 500000 amenity=waste_basket nodes, this would however be computationally way too much effort. So I was wondering: Would it somehow be possible to reduce the search area to the nearest few subnetworks or the likes? And ist there existing GraphHopper functionality that would help me here?

All the best
Hauke

[easbar]

So your start and target points are fixed and you want to adjust the route such that it comes close to any (just one) waste bucket? Can you not filter all waste buckets by an approximate distance and then calculate the exact detour for remaining waste buckets? Or find all waste buckets that are closest to your start/destination points using Dijkstra?

You can read the OSM file using OSMInputFile and just keep all OSM nodes with the waste_bucket tags. You can then query these points with LocationIndex to find the closest edge for each waste bucket and use this for your via-point route requests.

[HaukeP]

Thanks for your response.

So your start and target points are fixed and you want to adjust the route such that it comes close to any (just one) waste bucket?

Basically yes: Start and destination are fixed. I’d like to show to the user not only the one “best” waste basket along the way but the three “best” waste baskets (where “best” means that the detour costs would be minimized).

Think of it like this: You’re in a car on an optimal route to your destination. You know that you will need to fuel up within the next few hours. Now you wonder: What fuel stations are close to your route that would minimize the required time for your detour?

You can read the OSM file using OSMInputFile and just keep all OSM nodes with the waste_bucket tags. You can then query these points with LocationIndex to find the closest edge for each waste bucket and use this for your via-point route requests.

That’s basically what I’ve been doing so far. I’ve been going through the OSM file another time and collecting all relevant nodes in a list (not indexed yet as I’m still in prototyping mode).

And for the routing: Instead of explicitly finding the closest edge myself, I’ve let GraphHopper do that for me - so I’ve only been passing the lat/lon of the respective waste basket to the routing algorithm.

Can you not filter all waste buckets by an approximate distance and then calculate the exact detour for remaining waste buckets? Or find all waste buckets that are closest to your start/destination points using Dijkstra?

Yes, “testing” each waste basket within a circle of some radius around the start point was also my first approach for prototyping purposes.

However, the identification of sensible candidate waste baskets is where things get difficult: Using a circle around only the start/destination points as search area will not “work” for longer routes: If the route exceeds the size of the search area, relevant waste baskets that are in the “middle” of the route may not be found. And if you make the search area too large, you have to test way too many waste baskets.

So that’s why I was hoping that GraphHopper would have something to make this more efficient. As examples how the performance might be improved:

• When visiting edges during route calculation, it might be possible to “remember” edges that have been identified as being “close to” a waste basket. This way, you might not even need to run the routing algorithm for every waste basket but only the ones on edges that have not been visited in the first run.
• Or maybe there’s the possibility of calculating the isochrones not only for a single point but for a whole route - and then use this isochrone area as the search area for waste baskets.
• Or maybe there’s some other clever trick with using the spatial index to more efficiently find candidate waste baskets along the way when calculating the route.

Is there any capability of GraphHopper that would help here?

[easbar]

@HaukeP

not only the one “best” waste basket along the way but the three “best” waste baskets

Ok, but that should not be any harder than finding just the best one.

@HaukeP

Instead of explicitly finding the closest edge myself, I’ve let GraphHopper do that for me - so I’ve only been passing the lat/lon of the respective waste basket to the routing algorithm.

Not sure why you are using a routing algorithm for this. All you really need is something like locationIndex.findClosest(lat, lon, filter). When you use e.g. GraphHopper#route this is done internally, but you don’t really need to run the routing algorithm to find the closest edge. But anyway, let’s assume for a moment that we can associate an edge for each waste bucket as this should be rather easy to achieve.

@HaukeP

Using a circle around only the start/destination points as search area will not “work” for longer routes: If the route exceeds the size of the search area, relevant waste baskets that are in the “middle” of the route may not be found. And if you make the search area too large, you have to test way too many waste baskets.

Instead of using a circle you could run a BFS (or Dijkstra) search starting at the start/destination points (and maybe additionally from a few more points in between). Run the search until you found a certain number of waste buckets and stop at a certain number of visited nodes. Note that you could even do this with a single search that uses multiple start points. Another option would be storing all the edges that you associated with the waste buckets in LineIntIndex and then use lineIntIndex.query(BBox, visitor) to find all waste buckets in a given area.

@HaukeP

When visiting edges during route calculation, it might be possible to “remember” edges that have been identified as being “close to” a waste basket. This way, you might not even need to run the routing algorithm for every waste basket but only the ones on edges that have not been visited in the first run.

Yes, the BFS or Dijkstra search I proposed above would be one-to-many searches, so you only start the search once (like at the start or destination point), but find all waste buckets that are nearby one after the other (starting with the closest).

Or maybe there’s the possibility of calculating the isochrones not only for a single point but for a whole route - and then use this isochrone area as the search area for waste baskets.

This is not supported currently, but I don’t think you need the exact isochrone area. Basically this is the same as I proposed above without calculating the exact contour lines of the isochrone area. Moreover once you calculated the search tree/isochrone there is no need to search any area anymore because you can just discover the waste buckets while building the search tree.

@HaukeP

Or maybe there’s some other clever trick with using the spatial index to more efficiently find candidate waste baskets along the way when calculating the route.

Yes, like I said, you could use LineIntIndex to efficiently query edge IDs by their location.

[easbar]

I would try this:

1. Run the standard GraphHopper import.
2. Scan OSM file → You’ll get a list of waste bucket node coordinates. If you want to speed this up a bit you could also hook into the GraphHopper OSM import to read the OSM files already there (saves you one scan of the OSM file)
3. Query the location index (hopper.getLocationIndex()) using all the waste bucket coordinates. This will give you the closest edge for each waste bucket. You might need to setup the edge filter parameter correctly such that edges that are not accessible for the vehicle you are using are skipped. Instead of keeping the edge you could also just keep one of the edge’s nodes (it probably does not matter which one).
4. Calculate your route using the low level API such that you get the internal node IDs of the route.
5. Implement a Dijkstra search that simply uses all the nodes of the calculated route as starting points. Using multiple start nodes is not included currently so you need to adopt the code in Dijkstra.java for example. In each iteration of the search check if the node you are exploring is one of the nodes that are close to a waste bucket. You will find the waste buckets sorted by their distance to the corresponding closest point of the route! Once you found enough (three?) waste buckets you stop the search. You can also add some cutoff rule such that the search stops at some point when no waste buckets were found.
6. Once you found the closest buckets calculate the via-routes to obtain the detour for each waste bucket.

[HaukeP]

Thank for your the comprehensive response.

Implement a Dijkstra search that simply uses all the nodes of the calculated route as starting points.

Thanks - that sounds very reasonable.

When following up with this idea, I was hoping I could somehow “hook” into GraphHopper in such a way that the same edges/nodes would not need to be visited twice - first by GraphHopper’s algorithm (Dijkstra / A*) and then again by my own Dijkstra. Instead, I was hoping to be able to register some kind of callback to my own code with GraphHopper that would be called whenever GraphHopper visits an edge/node.

With this in mind, I’ve now done some deeper digging into GraphHopper’s source code. Besides directly modifying GraphHopper’s source code, I have not found any “nice” way to register a callback to my code.

Therefore just to confirm I have not overlooked anything: Is there a “better” (i.e. architecturally more “clean”) way to implement the search for potentially intermediary route stops (waste baskets in my example) so that it would not need to be executed completely separate from GraphHopper’s algorithms?

[easbar]

You have a few options to ‘hook’ into the GraphHopper algorithms by overriding some of the methods like updateBestPath, finished etc.

But actually it is not clear to me how this is supposed to work. The waste bucket search is fundamentally different to the shortest path search. The latter searches for the shortest path between the start point and all other points, but the waste bucket search needs to find the closest buckets to any of the shortest path’s nodes.

[HaukeP]

Thanks.

My thinking is: In the end, both types of searches are fundamentally only about visiting nodes/edges and storing cost information about them. And I’m expecting that the shortest (or rather: “cheapest”) path search will already visit several nodes/edges that I would need to also visit in my “waste bucket search”.

So for example: Assuming the “classic” path search algorithm is a Dijkstra.

Assume it “happens” to visit a “waste basket edge” (i.e. an edge that was identified to be closest to a waste basket). Then I could already remember a “candidate path” from the start node to the waste basket. And when the Dijkstra search is complete in the end, I could check if the final path has an edge that is also part of all the found “waste bucket candidate paths”. If they do, I could already get some kind of indication what detours must be rather cheap from the candidate path.

But maybe you’re right and this is not thought through enough yet. I’ll hopefully start implementing a prototype soon - maybe I can then report about my lessons learned.