Return distance for table queries #1353
Comments
|
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. |
|
+1 for this feature request! This would be a huge breakthrough for me |
|
Any news/timeframe/estimation for this? |
|
+1, I think there's a lot of value here for routing based on shortest time and displaying the distance. |
|
While we are asking for your patience at this point, please be assured that this is very much on our radar. |
|
cool! i am looking also for the distance in this matrix so I can complete a OD-matrix 👍 |
|
+1 |
|
What is the current status of this issue? |
|
That would be very welcome 😄 |
|
+1 |
|
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 From v4.9.0 (only 1/10 seconds distance values): 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! :-) |
|
@RhinoDevel Thank you very much! |
|
@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. |
|
While @RhinoDevel implementation looks good the implementation increase memory usage dramatically and will not be merged into |
|
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 ( 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 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. |
|
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? |
|
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. 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 |
|
I'm in the process of removing some variables from the EdgeBasedNode ( @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 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 :-( |
|
I've implemented this along the lines of @danpat's Feb 2 suggestion, i.e. by unpacking paths as part of 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 |
|
@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? |
|
+1 any news or update about this feature? |
|
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 |
|
@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 |
|
@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. |
|
+1 for returning distance. |
|
Yet more +1
On Dec 14, 2017 7:29 PM, "Dinesh Weerapurage" <notifications@github.com> 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
<#1353 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/ABCIjB5fruzQAqXQ5pF34S4KbtTQMzkzks5tAVsFgaJpZM4DVPNd>
.
|
|
Hi, |
|
I would also like to vote for this feature to be added. |
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. |
|
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. |
|
@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
There is some work towards (3) happening over in #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 #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. |
|
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. . |
|
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).
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). |
|
heyhey. I am aware this is a super hot topic 😄🔥 @cglacet regarding some of your questions
@danpat basically already answered this question:
So that the is main difference between durations and distances. Unpacking is expensive. 😞
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
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 💪 ❤️ |
|
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. UsageThe 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_pluscoordinates = [ "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 secondEach of these three results are numpy matrices of size (4,4). If you want to understand the technique I'll give all hints you need to do so. Overall strategyThe strategy is to build a route that goes through all (non-ordered) pairs of coordinates in the matrix. For example, if you have n=4 coordinates {c1,c2,c3,c4} you need to build a route in which appear all (non-ordered) pairs of coordinates, ie. a route that contains {c1,c2}, {c1,c3}, {c1,c4}, {c2,c3}, {c2,c4}, {c3,c4}. By non-ordered I mean that if the route contains at some point SolutionThe algorithm has two parts (n is odd and n is even), they both are based on the same principle: using disjoint hamiltonian paths to cover most edges of the graph (all when n is odd). You can find details on the technique for an odd n here. Once you understand that technique (I really suggest you take a bit of time to do so because it's a very nice technique), then the n is even part will be easy as we will build a simpler (but not as nice) version of this strategy. When n is oddIt exists a set of hamiltonian path that cover the graph (the set of edges of our hamiltonian paths is exactly equal to the set of edges of the graph). The stackoverflow post explains a nice way to build hamiltonian paths that can be merged to have an eulerian tour (the idea is to have a fixed node that will serve as a bridge between all paths). When n is evenThe solution can't be optimal (there is no eulerian tour of a graph that contains more than 2 odd degree nodes). In this case we can still find a solution that is easy to build and only have n/2 repetitions (one can probably find a better solution, but I was lazy and this one is particularly simple to implement). The idea is to use the same zig-zaggy path as in the odd solution (first node, last node, second node, penultimate node, ...) but with all nodes in it (no fix point), and then rotate the zig-zag n/2 times to build n/2 hamiltonian paths that are then merged to give the final tour (not eulerian). With this solution, the unnecessary edges are all the edges between the hamiltonian paths, and thus there are n/2 edges that are repeated in the tour. This solution is fine for me right now, but if you find a nicer solution I would be happy to hear it :) (if you are even lazier than I am you could even implement an even version where you simply add a fake coordinate and then build an eulerian tour). Detailed implementation example (python)I added my source for the tour construction here in case someone would like to improve it (I'm not 100% sure it is possible but I have the filling it should be), the code I'll show here directly use the tour generated by import clique_tour, requests, json
import numpy as np
osrm_route_service = "http://router.project-osrm.org/route/v1/driving/"
def main():
test_coordinates = [
"60.70278,31.6386",
"60.92565,33.94732",
"61.28789,32.23765",
"65.90314,37.6431",
"66.9574,34.18027",
"67.5304,31.95617",
"67.63406,33.14132"
]
sample_size = len(test_coordinates)
print("Testing with {} coordinates".format(sample_size))
eulerian_tour = clique_tour.build(sample_size)
fake_route = ";".join([ test_coordinates[i] for i in eulerian_tour ])
address = osrm_route_service + fake_route
print("Requesting osrm at \n\t{}".format(address))
r = requests.get(address, params={'continue_straight':'false'}, timeout=None)
data = json.loads(r.text)
if data['code'] == "Ok":
route = data["routes"][0]
legs = route["legs"]
eulerian_tour_distances = [ leg["distance"] for leg in legs]
eulerian_tour_durations = [ leg["duration"] for leg in legs]
distances = np.zeros((sample_size,sample_size))
durations = np.zeros((sample_size,sample_size))
for i in range(len(eulerian_tour)-1):
u = eulerian_tour[i+1]
v = eulerian_tour[i]
# get distances/durations for all edges and fill the matrix
distances[u,v] = eulerian_tour_distances[i]
distances[v,u] = eulerian_tour_distances[i]
durations[u,v] = eulerian_tour_durations[i]
durations[v,u] = eulerian_tour_durations[i]
print("Distance matrix: \n\t{},\n Duration matrix: \n\t{}".format(distances,durations))
if __name__ == "__main__":
main()This code outputs the following: Testing with 7 coordinates
Requesting osrm at
http://router.project-osrm.org/route/v1/driving/60.70278,31.6386;67.5304,31.95617;60.92565,33.94732;66.9574,34.18027;61.28789,32.23765;65.90314,37.6431;67.63406,33.14132;60.92565,33.94732;60.70278,31.6386;61.28789,32.23765;67.5304,31.95617;65.90314,37.6431;66.9574,34.18027;67.63406,33.14132;61.28789,32.23765;60.92565,33.94732;65.90314,37.6431;60.70278,31.6386;66.9574,34.18027;67.5304,31.95617;67.63406,33.14132;60.70278,31.6386
Distance matrix:
[[ 0. 597848.5 111905.3 1424042.5 1327335.6 908101.5 981078.8]
[ 597848.5 0. 579581.6 938840.5 1397277.6 883615.5 1051166.7]
[ 111905.3 579581.6 0. 1374843.5 1432621.7 916834.9 1084560.8]
[1424042.5 938840.5 1374843.5 0. 902239.6 983268.3 905651.4]
[1327335.6 1397277.6 1432621.7 902239.6 0. 515612. 438002.3]
[ 908101.5 883615.5 916834.9 983268.3 515612. 0. 197313.8]
[ 981078.8 1051166.7 1084560.8 905651.4 438002.3 197313.8 0. ]],
Duration matrix:
[[ 0. 74002.1 14669.4 144092.3 120643. 80559.3 96219.7]
[ 74002.1 0. 71016.5 82867.2 108230.5 63790.4 83739.4]
[ 14669.4 71016.5 0. 132550.5 136620. 87058.8 109406.6]
[144092.3 82867.2 132550.5 0. 85250.8 75562.9 79776. ]
[120643. 108230.5 136620. 85250.8 0. 47162.4 46454.5]
[ 80559.3 63790.4 87058.8 75562.9 47162.4 0. 18105.8]
[ 96219.7 83739.4 109406.6 79776. 46454.5 18105.8 0. ]]Using these two matrices you can check the average speed (km/h): print("Speed matrix (km/h): \n\t{}".format(distances/(durations+np.finfo(np.float32).eps)*((60*60)/1000)))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. ]]For the curious - the two tour functionsAgain, this is more or less what you can find in the PyPi package: # This function is called when n is odd
def eulerian(n):
middle = (n-1)//2
path_shape = [ u for i in range(middle) for u in (i,n-2-i) ]
hamiltonian_paths = []
# Increment the path shape to "rotate" the hamiltonian path (see stackexchange post)
for i in range(middle):
hamiltonian_paths += [ (path_shape[p]+i)%(n-1) for p in range(len(path_shape)) ]
hamiltonian_paths += [n-1] # Everything is rotated, this node is here to make a junction from one hamiltonian path to the next
# Close the tour
hamiltonian_paths += [hamiltonian_paths[0]]
return hamiltonian_paths# 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]] |
|
@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 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. |
|
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. |
|
@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. |
|
Hi Folks, I test this example: and got this erro: {"code":"Error","message":"Unrecognized parameter 'annotations'"} |
|
Any updates on this one? I get the same error as @LeoPovoa |
|
@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 |
|
@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. |
Any updates? ... I still get the same error. |
|
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. |
and others
Would it be possible to add distances along with travel times to the matrix requests?
The text was updated successfully, but these errors were encountered: