Planned improvement : batch routing

[chourmo]

The documentation mentions a planned improvement of "Batch (multi-threaded) routing between a large number of pairs of nodes in the network".

Is this still planned ?

[smmaurer]

We'd still love to have that functionality, but unfortunately I don't think we have the development capacity to tackle it any time soon.

The NetworkX package has some tools for this, though:

https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.shortest_paths.html

And I've heard that the sp package is very fast for calculating many-to-many shortest paths (although it doesn't look like there's much documentation):

https://github.com/cb-cities/sp

[knaaptime]

you might also check out https://github.com/GeoDaCenter/spatial_access

[tomalrussell]

I'm interested in this too, in the context of batch routing for transport simulations on regional/national networks. I wondered if anyone had any initial thoughts on a suitable approach?

Looking around:

• PHAST (Delling et al 2013) https://doi.org/10.1016/j.jpdc.2012.02.007 seems to describe an approach to building one or many single-source shortest paths trees that makes good use of the contraction hierarchies
• There has been some work on a similar approach in OSRM, towards implementing an isochrone service https://github.com/Project-OSRM/osrm-backend/pull/3652/
• openrouteservice uses something similar for many-to-many routing (in Java) RPHASTAlgorithm.java
• RoutingKit looks like it uses the forwards/backwards scan described in the PHAST paper contraction_hierarchy.cpp

Reading the docs for shortest_paths this looks like almost the API I would like. With this, if I pass sources=[a,b,c], targets=[d,e,f], I would get routes [a-d, b-e, c-f]. For full many-to-many, I would like to get [a-d, a-e, a-f, b-d, b-e, b-f, c-d, c-e, c-f]. (Note that I could construct a longer list of sources and targets to pass to the current API and get exactly that.)

Looking at Accessibility::Routes the approach is to find one route between source-target pairs at a time (or in parallel). I would expect (? needs testing) it to be faster to look for shortest paths from a single source to all targets at the same time.