Osrm-backend: Return distance for table queries

[mantesat]

Would it be possible to add distances along with travel times to the matrix requests?

[TheMarex]

Adding the distance should be doable in doable in the near future. The current M2M implementation needs some work however for this to be supported.
Note: This is not routing bases on shortest distance! Until we can support that it is still some time off.

[jornedeblaere]

+1 for this feature request! This would be a huge breakthrough for me

[mantesat]

Any news/timeframe/estimation for this?

[mattkrick]

+1, I think there's a lot of value here for routing based on shortest time and displaying the distance.

[DennisOSRM]

While we are asking for your patience at this point, please be assured that this is very much on our radar.

[deRightDirection]

cool! i am looking also for the distance in this matrix so I can complete a OD-matrix :+1:

[rCarto]

+1

[jellevictoor]

What is the current status of this issue?

[zavan]

That would be very welcome :smile:

[faheemmughal]

+1

[RhinoDevel]

You can find a v4.9.0-based branch including additional distances in meters here.

Please take a look at the changes made.

The table service response's .distance_table is changed this way (sample):

From v4.9.0 (only 1/10 seconds distance values): [ [ 0, 24302 ], [ 25352, 0 ] ]
To v4.9.0-meters (1/10 seconds and meters distance sub-arrays): [ [ [ ​0, ​0 ], [ ​24302, 45281 ] ], [ [ ​25352, ​47483 ], [ ​0, 0 ] ] ]

The solution writes distances in meters during preparation into the OSRM data files. This should lead to better performance as the calculations done in [NOT READY] General Many-To-Many plugin #1452 during each table request.

Currently these distances in meters from data files are just used by table service, but they might be useful to improve performance of other services, too (viaroute, etc.).

Please let me know, if something is not right or a pull request is appreciated.

Enjoy! :-)

[zavan]

@RhinoDevel Thank you very much!
Gonna give it a try today!

[alf]

@TheMarex As far as I can understand the changes made by @RhinoDevel, it should now be possible to add distance tables with shortest path as weight without too much difficulty.

Is this feature on your radar? I can't find an issue for that.

[TheMarex]

While @RhinoDevel implementation looks good the implementation increase memory usage dramatically and will not be merged into develop.
Not a priority for me at all right now, sorry.

[danpat]

The distances could be calculated on the fly, but it would impact the query table performance a bit. The approach that @RhinoDevel took was to pre-calculate distances, so there is relatively little runtime cost, but there is quite significant extra memory required.

The rough approach would be to add route unpacking to the ManyToMany routing plugin (include/engine/routing_algorithms/many_to_many.hpp). Currently, it just accumulates the total weight and returns that.

During each routings step, the edges should be added to a stack. Once a route is found, that stack can be unwound, turned into geometry, and then distances can be calculated.

This is how routing works in all the other plugins: not only is the duration found, but the actual route is returned. The ManyToMany plugin doesn't do this because it doesn't need to, but if it also tracked the route, the logic from include/engine/routing_algorithms/routing_base.hpp could be copied/reused to unpack the path, get the coordinates and then calculate the route length.

This would necessarily slow down the table, as we'd be calculating great-circle lengths for every segment in each route. It should be doable to make this a query-time flag and not pay this penalty if distances aren't required.

[jellevictoor]

Thanks for your take on this matter @danpat, I'm just curious how it would affect tables of 7000_7000 or even 10000_10000. I like the @RhinoDevel solution since it's all precalced and it is fine for us. Could this be a prepare flag?
--table = time (default)
--table = timedist (@RhinoDevel implementation)

[RhinoDevel]

Instead of using a commandline flag adding or not adding the distances in meters could be decided during compile time, e.g. by a DEFINE.
All binaries (-extract, -prepare, -routed) would be automatically on the same page then.
Some work is necessary for that.

But for people in need of big distance tables containing meters (like @jellevictoor and me) there should be a (speed) advantage - in addition to the fact that the option @danpat wrote about is not implemented, yet.

I also wouldn't have to merge my "meters-mod" with every new official OSRM release version.. ;-)

Anyway this would add some complexity to the source code the OSRM team maintains
and I don't know how many people actually are in need of big distance tables containing meters.

[danpat]

I'm in the process of removing some variables from the EdgeBasedNode (forward/reverse_offset, forward/reverse_weight). This is going to free up some memory that we might be able to use for this feature. _Maybe_.

@jellevictoor The main problem is that it can't really be a runtime flag - the pre-calculated values are baked into the data structure and that's fixed at compile-time. @RhinoDevel 's suggestion of a compile-time #define would work, but I worry about having those sprinkled all throughout the code, it gets kind of messy.

In an ideal world, we'd have distance, time and "routing weight" all separate (we want to separate time and routing weight so that we can arbitarily penalize edges without affecting calculated ETAs), but getting that all to fit in reasonable amounts of memory is difficult :-(

[systemed]

I've implemented this along the lines of @danpat's Feb 2 suggestion, i.e. by unpacking paths as part of many_to_many.hpp. It provides a new parameter to the table service (distances=true) which, when supplied, adds a metres_table matrix to the JSON output. It seems to work well; I've briefly sanity-tested the resulting distances against the output from viaroute and they appear to be what I'd expect.

I'm running on 4.9.x so can't send it as a pull request against develop. And my C++ isn't great so you probably wouldn't want to merge it unthinkingly anyway. ;) But I can put the new version of many_to_many.hpp in a gist, explain the changes there, and also list the (very few) changes elsewhere in the code. It's not too complex - I'd estimate it'd probably take a core OSRM developer half an hour to integrate, if that. Would that be helpful?

[RhinoDevel]

@systemed That is good news, thanks! But I am still very interested in an official solution that does not need on-the-fly distance calculation. @danpat Any success in freeing up memory to store meters as mentioned?

[risinglf]

What is the current status of this issue?
@RhinoDevel and @danpat please give us good news!

[danpat]

@risinglf patches are welcome :-) AFAIK, nobody is working on it directly right now.

[systemed]

Like I say, I'm happy to provide a gist which calculates on-the-fly, but it's coded against 4.9 so (given the changes in the API grammar, in particular) it would need someone to integrate it into 5.x.

[RhinoDevel]

@danpat As there already are systemed's "low-memory/high-CPU" and my "high-memory/low-CPU" solutions available - what kind of patches would help?

[danpat]

@RhinoDevel oh, that's easy - low-memory, low-CPU :-)

@systemed Have you measured the performance cost of your patch?

[RhinoDevel]

@danpat :-) Is there still hope for freeing up some space in EdgeBasedNode that could be used for precalculated meters (see your comment from Feb 3 to really get to such a low-memory, low-CPU solution?

[danpat]

@RhinoDevel I was mistaken about how much memory that would save. It reduces the size of the data in the RTree (on disk), but doesn't have a significant memory effect.

[systemed]

@danpat With a square table of 33 locations (cities in Colorado, custom bike profile), a call to localhost:5000/table goes up from 0.164s to 1.177s. That's overstating it slightly because I have some additional stuff patched in there, but not by much. The patch is, of course, an optional flag (&destinations=true).

[josefcs]

Just a general thought, please correct me if I'm wrong:
Shouldn't the implementation of distances take at most twice the time and memory to make sense?
Because if the trick from #1831 can be applied (create a profile with only one speed), one gets the distances via this way.
So two calls with 0.2ms each are way better than one call with > 1s.

[danpat]

@josefcs The problem is that the fast graph structure OSRM uses (contraction hierarchies) is optimized for a single metric - it can _only_ route using a single metric decided on at pre-processing time.

You cannot do both shortest time and shortest distance calculations on the same CH. We would need to create a second CH duplicating a bunch of data and optimizing it for shortest distance routing. This would probably add multiple GB of additional RAM for large scale graphs.

[danpat]

Wow, my previous answer is a bit random. It's late, I'll blame the beer.

@josefcs What you're suggesting is what @RhinoDevel made - more memory, very fast results. The problem is that this extra memory use doesn't have much purpose elsewhere. It's a good solution if you need this, but a bit of a resource hog if you don't, and most people don't (we think).

[frodrigo]

I'm doing this too, currently be recompute the distance matrix on by on using the via route. Add distance on matrix is useful for me too, but for sure this need to be an option.

[valeriob]

I'm computing the matrix with distance and time with viaroute as well, but i recognize that doubling the amount of memory needed by osrm would be a no-go.

[josefcs]

@danpat The reason asking was because I took a look at systemed's preliminary benchmark (https://github.com/Project-OSRM/osrm-backend/issues/1353#issuecomment-220254749) with 0.164s vs 1.177s and came to the conclusion, that might be two runs for distance and speed (for distance: only one speed with 3.6m/s, the rest is the same in the profile) is better than to change a lot of internal structure in osrm.

This way, the memory structure of osrm stays the same and people that need both results (like me) can get them with nearly double the time (two api calls).

[frodrigo]

@josefcs no, you miss one point. Compute the distance of the fastest route is not the shorter distance.

[josefcs]

@frodrigo Yes, you are right. I mixed that one up. For my case, it is ideal to have the shortest distance and fastest travel time (different routes). The other request/patches seem to be the fastest travel time and its distance (same route).

[PlassJ]

+1

[shikharkhattar]

+1

[niemeier-PSI]

A fully functional version of the table service with distance support is available here: https://github.com/Project-OSRM/osrm-backend/pull/2764
The general approach is quite similar to what RhinoDevel did, but this one is based on _master_.
For more details the the description in that pull request.

[narzero]

+1

[glifchits]

Hey OSRM team, we think this feature would be useful as well. I'm wondering if returning distances in the table API are on the roadmap, given that there hasn't been a lot of recent activity on this issue.

[sandeepgadhwal]

I just need distance not duration here can anyone help

I am currently getting table response here by this query
http://localhost:5000/table/v1/driving/-118.307399,34.090134;-118.306342,34.082808;-118.306342,34.0829?sources=0

which is : {"code":"Ok","durations":[[0,139.2,136.8]],"destinations":[{"hint":"woYAgLVmGYA0AAAAXQAAAAAAAAAAAAAANAAAAF0AAAAAAAAAAAAAAFkDAAC6xfL41SsIArnF8viWLAgCAACfBU9TUk0=","name":"Sierra Vista Avenue","location":[-118.307398,34.089941]},{"hint":"D2MZgBFjGYBWAgAAfwEAAAAAAAAAAAAAKwEAAMAAAAAAAAAAAAAAAFkDAAC5yfL4-A8IAtrJ8vj4DwgCAAB_Fk9TUk0=","name":"","location":[-118.306375,34.082808]},{"hint":"D2MZgBFjGYCHAgAATgEAAAAAAAAAAAAAQwEAAKgAAAAAAAAAAAAAAFkDAAC4yfL4VBAIAtrJ8vhUEAgCAAB_Fk9TUk0=","name":"","location":[-118.306376,34.0829]}],"sources":[{"hint":"woYAgLVmGYA0AAAAXQAAAAAAAAAAAAAANAAAAF0AAAAAAAAAAAAAAFkDAAC6xfL41SsIArnF8viWLAgCAACfBU9TUk0=","name":"Sierra Vista Avenue","location":[-118.307398,34.089941]}]}

I want distance instead of duration in the matrix what should i do.

[RhinoDevel]

@sandeepgadhwal, this is not supported by OSRM, but you can use this: https://github.com/Project-OSRM/osrm-backend/pull/2764

[nicolo-paganin]

+1 any news or update about this feature?

[sandeepgadhwal]

I do not need the duration i just need distance matrix can somebody help me to get distance by this query http://localhost:5000/table/v1/driving/-118.307399,34.090134;-118.306342,34.082808;-118.306342,34.0829?sources=0

[frodrigo]

@sandeepgadhwal No you can't with the actual code of OSRM until some change will be made. Nevertheless, you can use this pull request #2764. Or change a profile to deals with distance in place of time. I made this here: https://github.com/Project-OSRM/osrm-profiles-contrib/tree/master/5/5

[sandeepgadhwal]

@frodrigo what changes can i make in my https://github.com/sandeepgadhwal/osrm-backend/blob/master/profiles/car.lua profile i just need distance in place of duration can we keep speed constant at 1 meter per second so that i get seconds = meters in duration table. Any suggestion that we can determine distance instead of duration.

[xydinesh]

+1 for returning distance.

[sashakh]

Yet more +1

On Dec 14, 2017 7:29 PM, "Dinesh Weerapurage" [e-mail]
wrote:

+1 for returning distance.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/Project-OSRM/osrm-backend/issues/1353#issuecomment-351780742,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABCIjB5fruzQAqXQ5pF34S4KbtTQMzkzks5tAVsFgaJpZM4DVPNd
.

[hopewise]

Hi,
As I will be using table service to feed an algorithm that solves vehicle routing problem, I will only need the durations without destinations, is this possible? to exclude destinations in result as its not needed in my case?

[jgabriels]

I would also like to vote for this feature to be added.
I also would honestly like to know what the use case even is for a table with durations but no distances.
To me, if you were going to include only one, only returning distances makes a lot more sense.

[systemed]

I also would honestly like to know what the use case even is for a table with durations but no distances.

Most VRP applications, which optimise deliveries within time constraints. Typically you'll take a duration matrix and feed it into a solver such as jsprit or something built with Google's OR Tools. Distance is additionally useful here if you have a fuel constraint, but duration is the main use case.

[dskrvk]

There are different classes of VRP problems. Quite often the cost function includes both time and distance (perhaps with different weights).

It's just weird that a mapping API which internally keeps track of distances between points doesn't expose this information to the callers.

[danpat]

@dskrvk The reason that OSRM currently isn't returning this data is because it doesn't keep track of distances between points - the routing graph only stores time (and/or weight), and in order to return distances, the full path between points currently needs to be unpacked and distances re-calculated.

One of the reasons that the table plugin is so fast is that it does not need to unpack paths in order to return the time between points. There are basically three options to make it happen:

1. Unpack paths and calculate distances - this will make the table request much slower.
2. Store the distances alongside the paths - this will make OSRM use a lot more memory.
3. Implement a caching scheme for path unpacking that will hopefully make (1) reasonably performant.

There is some work towards (3) happening over in https://github.com/Project-OSRM/osrm-backend/pull/4876 - we hope to get this into the mainline soon-ish. The results look promising, caching of path unpacking is quite effective with CH/MLD.

If you prefer the additional memory usage approach, you can follow the work done in https://github.com/Project-OSRM/osrm-backend/pull/2764 - I don't think we'll mainline this yet, unless we can figure out a good way to make it a runtime configuration option.

[jmarca]

For my use case---sourcing an all-to-all distance and duration matrix for feeding into Google OR-tools pdptw solver---I'm willing to pay the cost of getting duration and distance using individual queries, because the solver takes so long to run compared to getting the data one OD pair at a time. At the same time, it is so tantalizing to know that I can get half the data I need from the many-to-many query in much less time. I took a look at the #4876 branch, but to be honest my C++ is pretty darn rusty and I can't really contribute much right now. So I'm just a cheerleader waving my pompoms and saying Go Team right now, but getting distance and duration from the Table API would be super awesome. .

[cglacet]

I'm not sure to understand how this is really different from durations, both metrics behave the same.

It seems to me that it might not even need supplementary work depending on what users want. For example, if I just want to retrieve the distance associated with the shortest path in the duration graph, then you can use the exact same protocol to answer both distance and duration request (as both metrics rely on the same graph and come from same shortest path).

I don't know what technique you are currently using for durations requests, but let say you use a landmark cover. If you want to have both duration and distance working, then you still keep your current cover and simply add a second metric to your graph (all edges will have a distance and a duration), your landmarks will only cover the duration (same as before). When you have a new request for nodes (u,v), you do the same landmark search as before. Let suppose that landmark w is found to be on the path u->v (w has been selected as u->w->v is contained in a shortest path from u to v). You then return duration(u,w)+duration(w,v) (just as you did before) and/or distance(u,w)+distance(w,v).

• It is not harder than before to build your landmark cover (the cover is the same set as before).
• There is a factor 2 overhead in the preprocessing as you still do a BFS but now with two metrics.
• For query response time you have no overhead (as you only select a single landmark in the same set as before and just return two values)

On the other hand, if the user want to have both the shortest path in terms of distance and duration, then you simply duplicate everything and you therefore have two distinct graphs (distance/duration), with two landmark covers and you run two distinct BFS to get your landmark distances. Answering a request will probably takes twice longer as before unless the landmark cover for distances is significantly larger than the one for durations. Overall the overhead probably is a factor 2 on preprocessing time/memory usage and query time (if the user query both services), there is no overhead for query time if the user only request the duration.

Unless you are using a very strange/convoluted technique to query durations I really feel like this is a question of days to implement this (at least for the first version I explained).

[chaupow]

heyhey. I am aware this is a super hot topic 😄🔥

@cglacet regarding some of your questions

I'm not sure to understand how this is really different from durations, both metrics behave the same.

@danpat basically already answered this question:

@dskrvk The reason that OSRM currently isn't returning this data is because it doesn't keep track of distances between points - the routing graph only stores time (and/or weight), and in order to return distances, the full path between points currently needs to be unpacked and distances re-calculated.

So that the is main difference between durations and distances. Unpacking is expensive. 😞

Overall the overhead probably is a factor 2 on preprocessing time/memory usage and query time

OSRM can probably do a factor 2 on query time, but a factor 2 on preprocessing time / memory is something we'd need to consider well. OSRM already consumes a lot of memory and people struggle getting the right hardware to run OSRM. Preprocessing can take up to 6h for a continent. So resulting in 12h is not something we can just do.

If memory is no problem, there is a working branch by @niemeier-PSI that computes distances in the matrix https://github.com/Project-OSRM/osrm-backend/issues/1353#issuecomment-239397980

Unless you are using a very strange/convoluted technique to query durations I really feel like this is a question of days to implement this (at least for the first version I explained).

We're (and especially @ghoshkaj ) are working on this to get it right with preserving query time, preproc time and memory as best as possible. Please give her and us time to do this right 🙂 Coding is hard, there are many pitfalls and we're doing our best 💪 ❤️

[cglacet]

If you are interested, I found a way to cheat a little bit. You can use the route service (which returns distances and durations) to simulate a table matrix. It's a bit awkward, but it works.

Usage

The solution I currently use allow to retrieve matrices (distances and durations) for 15 coordinates at most in a single request to OSRM (maybe 16 if you don't need high precision coordinates). The technique mostly comes from this great stackexchange post.

pip install osrm_plus

coordinates = [ "60.70278,31.6386", "60.92565,33.94732", "61.28789,32.23765", "65.90314,37.6431"]
result = distances_and_durations(coordinates, include_speed=True)
distances = result['distances']  # meters
durations = result['durations']  # seconds
speeds = result['speeds']        # meters per second



md5-cb82904d57fae250f2ba0b20ad3d4e50




This code outputs the following:



md5-d52ca6d6323a3d9436ce5856ebfbf27f




Using these two matrices you can check the average speed (km/h):



md5-e82f9eb1798152cf9037af94e410f22d



```bash
Speed matrix (km/h):
    [[ 0.         29.08369623 27.46254634 35.5782578  39.60783598 40.58085654
  36.70645072]
 [29.08369623  0.         29.38040817 40.7860504  46.47672657 49.86668519
  45.19019859]
 [27.46254634 29.38040817  0.         37.34000699 37.7502424  37.91237228
  35.68723346]
 [35.5782578  40.7860504  37.34000699  0.         38.100083   46.84528883
  40.86874544]
 [39.60783598 46.47672657 37.7502424  38.100083    0.         39.35769164
  33.94306852]
 [40.58085654 49.86668519 37.91237228 46.84528883 39.35769164  0.
  39.23216185]
 [36.70645072 45.19019859 35.68723346 40.86874544 33.94306852 39.23216185
   0.        ]]



md5-93b3c57fb4edfbaeb2cf41cd3f069ade



```python
# This function is called when n is even (more or less the same code)
def almost_eulerian(n):
    path_shape = [ u for i in range(n//2) for u in (i,n-1-i) ]
    hamiltonian_paths = []
    for i in range(n//2):
        path = [ (path_shape[p]+i)%n for p in range(len(path_shape)) ]
        hamiltonian_paths += path
    hamiltonian_paths += [hamiltonian_paths[0]]

[danpat]

@cglacet Thanks for the write-up. This does seem like a reasonably efficient way to fetch distances using the current API interface.

You'll probably need to add the &continue_straight=false parameter to the request - if you don't do this, the paths selected by the /route service will never enter/exit waypoints on the same edge, so you can't guarantee that the distances between will necessarily be the shortest.

The implementation being done by @ghoshkaj ultimately will make client-side work like this unnecessary - the difficulty with the implementation is simply getting the distance labels for edges without significant memory use or significantly impacting matrix calculation time.

[cglacet]

Ah ok, thanks for the remark, I'll add that option tomorrow. If you need some help with a specific graph problem I might be able to help (on the algorithmic side). Don't hesitate to send me an email.

[danpat]

@cglacet This is an open-source project - pull requests are always welcome, and if you have the time and inclination to contribute to the implementation of this feature, feel free.

There is very little (i.e. no) change to the actual graph traversal side here, rather, the implementation problem is more around data packing and cache invalidation.

Work is happening over in https://github.com/Project-OSRM/osrm-backend/pull/4876, and https://github.com/Project-OSRM/osrm-backend/pull/4990

[TheMarex]

This is now possible by passing &annotations=duration,distance to the table service. The computation will be much slower for coordinate pairs that are far apart, which could be improved with https://github.com/Project-OSRM/osrm-backend/pull/4989. Thanks @ghoshkaj @chaupow @oxidase for working so hard on this. :-)

[LeoPovoa]

Hi Folks,

I test this example:

http://router.project-osrm.org/table/v1/driving/13.388860,52.517037;13.397634,52.529407;13.428555,52.523219?annotations=distance

and got this erro:

{"code":"Error","message":"Unrecognized parameter 'annotations'"}

[russelltrafford]

Any updates on this one? I get the same error as @LeoPovoa

[xydinesh]

@LeoPovoa @russelltrafford annotations enabled/added in 5.18.0, please check version of the OSRM you are using. Most likely you are using a version older than 5.18.0

https://github.com/Project-OSRM/osrm-backend/blob/master/CHANGELOG.md

[danpat]

@xydinesh No, the problem is that the OSRM demoserver hasn't exposed those new options yet. It's on my todo list, but I simply haven't got around to it yet.

[isaac0821]

Hi Folks,

I test this example:

http://router.project-osrm.org/table/v1/driving/13.388860,52.517037;13.397634,52.529407;13.428555,52.523219?annotations=distance

and got this erro:

{"code":"Error","message":"Unrecognized parameter 'annotations'"}

Any updates? ... I still get the same error.

[danpat]

No updates - I don't see myself having a chance to get this upgrade done any time in the near future. If you need the distance annotation urgently, you should consider running your own server.