Range analysis plugin

[roroettg]

Hello,

I am currently working on a plugin, which should be giving me all ways from a starting point within a given distance. I have worked my way through the code and read about Contraction Hierarchies, but I have still no clue if or how i can implement it.

As far as I know every algorithm already implemented to solve the shortest path problem uses a bidirectional Dijkstra. In my case I think the best way to solve the problem is a normal Dijkstra, but i could not find any information if Contration Hierarchies are able to be used that way.

Any hints or ideas where to start are greatly appreciated.

[daniel-j-h]

Hey hey, dropping a few related resources:

@danpat's osrm-isochrone tool is available in this branch:
https://github.com/Project-OSRM/osrm-backend/tree/isochrone_tool

@TheMarex has an experimental osrm isochrone project here:
https://github.com/mapbox/osrm-isochrone

@emilymdubois can probably tell you more about isochrones:
https://www.mapbox.com/blog/isodistances-part-1/
https://www.mapbox.com/blog/isodistances-travel-times/

[danpat]

@roroettg Take a look at the src/tools/isochrone.cpp for an example of how to do plain Dijkstra with OSRM data.

Unfortunately, you can't perform a simple Dijkstra search on a Contraction Hierarchy - the graph structure is optimized for 1:1 routing, not 1:N.

The isochrone.cpp loads the pre-contracted node-based graph into RAM and uses that for Dijkstra - but I haven't yet worked out if we can include this in the main OSRM routing daemon - it doubles the memory requirements :-( I suspect I'll make it a completely separate tool/daemon.

[roroettg]

Thank you very much.

I will keep this updated, once i have some results to show. :-)

[roroettg]

Hello,

I was able to create a first implementation of an Isochrone-Plugin based on danpats's code for the current version of osrm. As @danpat mentioned the memory increase is significant. Is there a way to reduce the memory or is there any possibility to perform these searches on the contracted graph?

Another issue for me is the testing infrastructure. As far as I understand the tests use the shared memory function of osrm, but right now I am only able the to load the uncontracted graph from a file. Is the uncontracted graph also stored in the shared memory? If so, how can i access it?

As I am new to opensource projects is this a thing I should make a pull request for once i got some tests running?

[danpat]

@roroettg The uncontracted graph is not loaded into memory during normal runtime. The datafiles that my isochrone work loaded were temporary files created during processing, but they're not loaded by osrm-routed. To make this work, you'd either need to:

• create a separate service, like osrm-isocroned that loads different data into RAM, and cannot do routing; people can osrm-routed and osrm-isochroned separately.
• load the node-based-graph into RAM for osrm-routed, and add a new plugin - this would massively increase (double?) memory use, but keep everything under the one API - it would need to be optional

[roroettg]

@danpat Yes, I implemented it as a Plugin and load the graph into RAM.Would a separate service be the better solution?

I think the memory usage does more than double, but i can take a look at that.

[danpat]

@roroettg no, that seems like a sensible approach, but we should definitely make it optional - it's a big bump in memory usage, and not everyone is going to want it.

You should:

• make loading the isochrone plugin optional, and off by default
• if not loaded, no additional data gets loaded

Would you like to start a pull request with your changes? It would be great to see how you've approached this and discuss the impact of the code changes. This would be a great feature to have in the mainline.

[roroettg]

Right now I am using the code below to get the weight of the edges for the dijkstra, but I am still confused about what the weight really is. The weight depends on the profile I am using, so I am guessing the value is not a distance. Is it a time value or does it have no unit?

Since the plugin should be able to have a time and/or distance break condition, is there a way to use the weight for that?

const auto data = graph->GetEdgeData(current_edge);
if (data.real)
{
    int to_distance = distance + data.weight;
    if (to_distance > MAX_DISTANCE)
    {..}
}```

[danpat]

@roroettg currently, weight is basically time. There is some naming confusion in these variables, we're trying to clear it up. No-where in the data is the actual length of an edge saved, we only store the duration.

If you wan to do distance-based routing on the node-based graph, you'll need to fetch the underlying coordinates for the edge, and re-calculate its length on-the-fly.

Note that @TheMarex is working on #77 at the moment, which is going to make this even more complex, as we will store the duration separately from the weight, so that you can route on the weight, but still get accurate ETA values from the duration.

[daniel-j-h]

I'm closing this here as not actionable for us.

Give https://github.com/Project-OSRM/osrm-backend/pull/2399a try for arbitrary edge weights!