Isochrone Support

[mjjbell]

Interested to gauge demand for isochrone / one-to-all query support in OSRM.

There have been previous proof of concepts that didn't make it to mainline. @danpat it looks like you were involved in these. Perhaps you have some insights into how feasible this is now and whether any of these POCs can be revived?

There are some specialised isochrone algorithms for both MLD and CH style preprocessing, which would be consistent with OSRM's performance characteristics and provide an alternative to the isochrone support provided by other routing engines.

Personally, it's a use-case I'm frequently having. I've been extending RoutingKit to do this as it already uses a PHAST-like graph representation, but it would be nice to combine this with OSRM's extraction flexibility and features.

[danpat]

Sigh, I wish I'd finished my branch. The blockers on my PHAST implementation (https://github.com/Project-OSRM/osrm-backend/pull/3652) were:

1. PHAST requires a way to iterate over the CH nodes in descending order - OSRM does not store nodes in this order, nor is there an index, so the fast "reverse" phase of PHAST cannot be done without fixing that.
2. Deciding on the output format - approximate polygons, or an exact tree format.

I think an isochrone implementation would be very useful.

[frodrigo]

Yes, also for me the isochrone are the big missing thing on OSRM. I already need to write myself a wrapper on to of OSRM using a one-to-may matrix, or using one of the existing POC.

[TimMcCauley]

@danpat do you have a rough idea how much would be missing to enhance PHAST to RPHAST which would speed up the matrix requests by a magitude?

[mvl22]

There is Galton: https://github.com/urbica/galton

However, as noted in https://github.com/urbica/galton/issues/231 this works to 5.17.2 but will need some kind of adjustment for >5.17.2.

Perhaps someone can add a patch to that?

[Skrol29]

This issue should be tagged as « feature request ».

Isochrone is a missing key in OSRM. For now it is usually partially solved by a walk-around using a route-grid, but this is limited and expensive, while Isochrone is a commonly needed feature.

Isochrone !

[guillaume-vignal]

Hello, is there some news on creating isochrone map with OSRM ?

[TheMarex]

I could have sworn that we actually shipped this. Oh well. :sweat_smile:

For what it's worth this is super simple with the MLD graph (one-to-all with proper termination), I would recommend to just not implement it for CH because it is so tricky. I would recommend a polygon output because that is in line with other implementation I've seen.

[danpat]

Nah, I never got it finished. The blocker for CH was the ability to do the reverse order node iteration.

[mjjbell]

I've been making sporadic progress on isochrone support. Here's an update.

I have created OSRM implementations of isoDijkstra and isoMLD, as described in the paper linked in the first post.

One notable feature of the implementation is the planarization of the OSM graph for creating isochrone boundaries. This planar embedding is independent of the OSRM graph, which means it doesn't require reprocessing when the weights are updated, such as via osrm-customize.

See the following example where the reachable boundary follows a path via a planarization node that is not in OSM.

The main problem with implementation is the output is too accurate, it returns a traversal of all the boundary faces of the reachable area. The resultant output has a huge number of lines, which makes visualisation performance very bad.

To explain visually by looking at the debug output, rather than returning the full reachable boundary, we want to instead return the simplest possible polygon between the yellow (reachable) and orange (unreachable) boundaries, intersecting the grey lines (boundary edges).

My plan is to implement one of the strategies suggested in this paper for simplifying the output, but there are still some issues around external boundaries that will need figuring out.

In any case, I'm still a way off from submitting a patch (a lot of tidying up is required), but I thought it would be useful to communicate some progress.

[SiarheiFedartsou]

Likely I don’t know something obvious about OSRM, but I am curious why cannot we just port algorithm from Valhalla(there is also this paragraph in docs)? It looks quite simple and straightforward.

[lgrd]

Hi there, I'm very pleased to discover what has been done here ! @mjjbell do you have some good news to share with us ? :)

[mvl22]

@mjjbell

The main problem with implementation is the output is too accurate, it returns a traversal of all the boundary faces of the reachable area. The resultant output has a huge number of lines, which makes visualisation performance very bad.

Could I suggest that, while that can be an issue, what you have done so far will nonetheless be very useful in some cases. IMO it would be better to publish something that is useful in some cases, with that in the main branch making it easier for others to perfect later, than wait for things to be perfect which might never happen.

[mjjbell]

I did actually make more progress since the last update, to the point where I made a hype video thread showing what it could do.

I was getting stuck on getting it to perform at "scale", as the algorithm was tricky to parallelise on edge-expanded graphs. Then the pandemic ended and I went outside.

In any case, I do have a use-case where even a slowish version would be beneficial, so I'll resurrect this work and start submitting some PRs. But first I need to remind myself how it works...

[lgrd]

@mjjbell thank you for your answer and all this work ! :)

[azarz]

@mjjbell Very nice work, congrats! I would also be very interested if isochrone support makes it into the main OSRM project :grin:

[hannesaddec]

Same here.. would be cool to get in so we can start contributing