OSRM distance matrix

[sweenzor]

Heyo!

Is there any equivalent (or plans for one) in OSRM to google's distance matrix? I end up just doing loads of http requests to emulate this functionality, which isn't terribly efficient.

Description of the functionality:

The Google Distance Matrix API is a service that provides travel distance and time for a matrix of origins and destinations. The information returned is based on the recommended route between start and end points, as calculated by the Google Maps API, and consists of rows containing duration and distance values for each pair.

[limoges]

There is no such functionality at the moment. I cannot say for future plans, but this could be easily implemented using the plugin interface the project uses.

[DennisOSRM]

I implemented a distance matrix feature already a while back, but did not release the code yet. It is planned, but not yet public. The efficiency is great compared to doing single queries, i.e. 1000x1000 distance tables can be computed in a matter of seconds.

Am 19.12.2012 um 00:07 schrieb Matt Sweeney [email protected]:

Heyo!

Is there any equivalent (or plans for one) in OSRM to google's distance matrix? I end up just doing loads of http requests to emulate this functionality, which isn't terribly efficient.

Description of the functionality:
"""The Google Distance Matrix API is a service that provides travel distance and time for a matrix of origins and destinations. The information returned is based on the recommended route between start and end points, as calculated by the Google Maps API, and consists of rows containing duration and distance values for each pair."""

—
Reply to this email directly or view it on GitHub.

[sweenzor]

@DennisOSRM sounds great! any chance I could have a look at the unreleased work you've done so far?

[grishick]

+1 for me. I would be willing to test and bug-fix. This is an important
feature for my current project as well.
Greg

Sent from a mobile phone. Pls xcuse the spelling.
On Dec 19, 2012 12:33 AM, "Matt Sweeney" [email protected] wrote:

@DennisOSRM https://github.com/DennisOSRM sounds great! any chance I
could have a look at the unreleased work you've done so far?

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/544#issuecomment-11521560.

[sweenzor]

Hi @DennisOSRM, any new developments on this front?

[jacobcroope]

I also am using OSRM for this functionality. A distance matrix would be very helpful. Is there anything that can be done to contribute to this feature?

[DennisOSRM]

There is code for distance matrices, but for the time being, it is closed source.

[keesklopt]

I would be very interested in this feature too. And i'm also willing to lend a hand in development/testing/bugfixing.

[aquavit]

Hello,
In need with our own project, I implemented a really straightforward version of distance-matrix plugin.
The git fork is at https://github.com/aquavit/Project-OSRM.

It only supports JSON format outputs, involving an amount of redundancy
(as I had little time to dive into XXXDescriptors) but it anyway works for at least 100x100 matrices or so.

Feedbacks and suggestions are welcome.

Regards,

[jacobcroope]

Thanks Aquavit, I am currently compiling your fork and testing it against my distance matrix builder. I will comment on your fork further.

[keesklopt]

Aquavit,

Thanks for sharing first of all.

I tried it, and it generates matrices fine (well i tried 20x20)
However it seems it is just an interface implementation on top of single routing ? (Excuse me if i'm wrong)
If you calculate a 100x100 matrice you actually do 10.000 single routing calculations.

I think the solution DennisOSRM is mentioning is built on re-using the result of the last calculation when planning to (or from) the same location.
As i understand contraction hierarchies use a modified Dijkstra algorithm upward from one point and downward from the other, meeting somewhere in the middle.
The circle of evaluated nodes around those points is the same every time, so in theory if you have enough memory to remember all solutions you only needed 100 calculations (..well ok, 200 halves) instead of 10.000.

Anyway that's the solution i'm seeking, ... i need speed.

I would try to implement it myself, but it's lower down on my list (not the coming months).
And i'm still hoping osrm will decide to release it in the mean time.

Greetings Kees

[aquavit]

jtok202, keesklopt,

Thank you for your reply.

However it seems it is just an interface implementation on top of single routing ? (Excuse me if i'm wrong)
If you calculate a 100x100 matrice you actually do 10.000 single routing calculations.

Right. My current implementation is a naive double-loop of single routing.
I was aware of applicability of Dijkstra-variants, but what I needed was a
quick workaround for relatively small instances (up to 100x100, typically quite less.)

So, I admit It's not an ultra-scalable solution (though, I'd like to note it still returns within a second
for 50x50 queries over Japan's road network, which contains about 78M nodes,
the CH's search algorithm performs really awesome!)

I'm, of course, eager to improvements and would like to see if I can make any progress.

[knoepfle]

I'd also be interested in this functionality and glad to help with testing. DennisOSRM, do you intend to integrate your code into OSRM at some point or are you planning to keep it separate?

[ares86]

It would be a great feature! I'm working in a project in my university and it would be a nice feature to have to finally use OSRM in my project.

[keesklopt]

If any of you are interested in a 'times" only matrix implementation you might want to try my version.

https://github.com/keesklopt/matrix

I have made this a month ago, and had some time now to make it somewhat more accessible for others.

Why only times only ? because the weights on which the hierarchy is built are times not distances, and getting the distances means decoding the found path which kills the performance. Since i use it for a subsequent TSP, i have no need for distances until i have calculated the TSP, and i won't need all the distances.

To save memory i delete the heap node index as soon as i'm done with it, probably making retrieval of the distances(or path's) very difficult. If you really need distances, it's probably best to alter osrm-prepare to put distances in all shortcuts as well.

I cloned project-osrm some days ago, put it in my repository and then added my changes so you will see the alterations clearly. I used the interface code from aquavit as a start, but had to alter it at quite some points.

quick-start :

git clone http://github.com/keesklopt/matrix
cd matrix
mkdir build
cd build
cmake ..
make
cd ..
ln -s build/osrm-extract
ln -s build/osrm-prepare
ln -s build/osrm-routed

Usage example for osrm-routed :

http://localhost:5000/matrix?loc=51.4962,4.30823&loc=51.005,5.77311&loc=52.1258,5.21367&loc=51.5355,5.99368&loc=51.6594,5.41607&loc=52.7977,6.93993

And you might need to rebuild your network(s). The interface can't cope with 1000x1000 orders, the returned data seems to be too big. So i only tried 100x100 (1.4seconds).
But it should in theory rise linearly with the number of stops, so 1000x1000 should take around 14 seconds.
The test network was Europe.

Comments are welcome,
Greetings Kees

[knoepfle]

Kees,
Thanks so much for this. I've had success with 500x500 matrices but 600x600 fails. Any sense of what interface limitation results in this limit?

[keesklopt]

I actually don't know, for one i have not had an orderset that large to deal with yet.
But i tried the 1000x1000 matrix and internally it generates ok (and it DOES finish in about 14 seconds) , but somewhere in passing the result it fails.

If no one had reacted i'd leave it at that, but i will look into it later today.
It is probably a buffer overflowing that was never designed for that amount of data.

greetings kees

[keesklopt]

Knoepfle thanx for testing, that number of 500 was very helpful.

I copied aquavit's code too carelessly, it turns out he has built in a limit for the matrix, see :

Plugins/MatrixPlugin.h: 76

    if( 2 > routeParameters.coordinates.size() || 500 < routeParameters.coordinates.size()) 

That explains a lot. 1000x1000 works fine when you remove the second part of this check.

I do not know what happens when you run out of resources, will it be a crash ?
If you fear that you can also keep the limit but enlarge it, i personally want it to go as far as it can.
So i will check it in without the limit.

Greetings Kees.

[knoepfle]

Fantastic, thanks! I can run queries with apparent success up to about 2480 points now (I haven't validated the response data but the queries return full distance matrices). 2500 and up have truncated responses but it could be a problem with my client rather than the server; I'll keep testing and let you know what I find.

[DennisOSRM]

Just a heads-up. A more sophisticated solution (even faster) will arrive at some point.

[keesklopt]

Yes,

I saw some pdf's about transit node routing coming passed in my searches. Also a very nice technique.
That will probably be faster and use less memory.

But i have a fast enough solution for now to wait for that to come out.

Greetings

[keesklopt]

@knoepfle

I did a 100x100 matrix and tested each "cell" with a single ShortestPathRouting, and that matched.
I did not do a bigger test, so i f you find something please let me know.

I also put in a 10.000x10.000 test just to see where it would break, but that just ate up all my memory and went on a swapping adventure. So i had to stop that to get my machine back.

By the way, i implemented a "randomPhantomNode()" function to get testsets like that, if you are interested i will put that in as well.

Greetings Kees

[woodbri]

This would be a great feature for pgRouting integration also. I'm also implementing a call the server N*(N-1) times. In my implementation, I cache the route geometries in the distance so I done have to go and compute them again later. This might be a nice option to include in you implementation.

[ManofWax]

Any news about the upcoming distance matrix feature? It will be very helpful since no other services are providing a good distance matrix API

[woodbri]

I implemented this as a postgresql wrapper function. See https://github.com/woodbri/osrm-tools
I also implemented a php prototype where the PHP just calls the server multiple times.
Ideally this would be more efficient if it were done in OSRM directly, but the wrappers have worked well for us.

[DennisOSRM]

I have a good gut feeling that this feature is going to arrive in Q1/14

[sweenzor]

Excellent! Looking forward to it @DennisOSRM!

[mck-]

+1 Same here :) very much looking forward to this!

[frankvandenbergh]

+1 Me too

[pchtsp]

Awesome @DennisOSRM, I am also looking forward to this very useful addition to this already great software.

[emiltin]

Since impedance and speed cannot yet be specified separately in the lua profiles, the only way to prioritize certain ways over others is to change the speed, which can lead to unrealistic travel times.

[DennisOSRM]

Looks like this is just a matter of dividing by 10 and rounding.

[linux-devil]

Thanks resolved , will try to implement my own version for distance matrix , I want to utilise distances instead of time , will follow above directions.

[DennisOSRM]

@linux-devil check the discussion happening here: #1162

[systemed]

Can confirm it works really well on a 700x700 matrix if the hardcoded limit is changed. POST would be good, especially as Apache has a limit of 8190 characters in a URL (which can't be fixed without recompiling), but I'm getting around that with a small proxy script.

[frodrigo]

I'm running large matrix, too. There is a plan to set or unlimit the max size by command line option ? a sutch patch will be accepted ?

[systemed]

I don't think you need a command-line option to set the max size - just the supporting code that ensures large matrices are plausible (i.e. parsing POST requests).

[frodrigo]

The limit is not in place to protect osrm-routed to do computation on large matrix and so block the process ?

[systemed]

In my experience osrm-routed copes very well with large matrices, even on old hardware - it did 700x700 without breaking sweat on my 2009 Mac mini. POST support is the only blocker, though a binary encoding for the returned matrix might be nice to have.

[DennisOSRM]

the limit is to protect of excessive internet traffic. The size of the result grows quadratically with the number of locations.

[jcoupey]

I've just learned from this thread about the existence of the 100x100 limit and I just re-compiled as suggested before.

Maybe you should consider mentioning the default limit in the API description. I actually spent quite some time before figuring out my problem with big sizes wasn't elsewhere.

Anyway thanks for the amazing work, this table feature is awesome !

[cenzin]

Hi fellows, well i tried to compile the code, manage to do it but it crashes when it comes to extract planet.osm. then i found a precompiled stuff which appears to be working fine. I process the whole planet.osm and setup the server. But a strange thing is happening: viaroute calculation appears to be working. But when i input the distance table example that is on the documentation, which is

http://localhost:5000/table?loc=52.554070,13.160621&loc=52.431272,13.720654&loc=52.554070,13.720654&loc=52.554070,13.160621&z=14

instead of giving me 0 on the diagonal, it'll give me this

{"distance_table":[[922,38499,38901,922],[38675,995,16859,38675],[39212,16818,839,39212],[922,38499,38901,922]]}

I recompile the osrm_routed server from fresh code and it ran giving me the same result. What you guy think could be wrong?

best regards & thanks

[cenzin]

Fellows,

Just as an update. I managed to compile the code following the guidelines on the project page for windows. Then i use a very small dataset taken from geofabrik. The area is Mexico's country. I extracted and prepare the information from a pbf file. then i ran the server and try this query

http://localhost:5000/table?loc=19.43680,-99.12733&loc=19.43984,-99.11718

The response was

{"distance_table":[[1055,2670],[2478,638]]}

Is this ok, Then again the number on the diagonal are wrong. it does not look like the example at all. Did i do something wrong. is the geofabrik info bad? Hope that somebody can give a light on this.

best regards to all

[DennisOSRM]

Do you use the latest release v4.4.0?

[cenzin]

Dear Fellows,

I am using what i think it is the latest code that can be compiled into windows. The current one won't compile or i'm doing something wrong i the making. Anyway yesterday i managed to isolate the difference in the file ManyToManyRouting.h at this piece of code

            if (new_distance >= 0 && new_distance < current_distance)
            {
                (*result_table)[source_id * number_of_locations + target_id] =
                    (source_distance + target_distance);
            }

the original file i had was like this

            if (new_distance >0 && new_distance < current_distance)
            {
                (*result_table)[source_id * number_of_locations + target_id] =
                    (source_distance + target_distance);
            }

I compiled the code and voila, now i got zeroes in the diagonal. Although my finding was good i was wondering if the latest code actually is compatible with vs2013. I follow all the steps in the windows compiling document but there is get the code from a different source than , what i think, is the latest. Any suggestions to compile the latest into windows will be great. I am seeing a lot of improvement which i want to incorporate into my routing.

But appart from that i want to congratulate all for such a excellent development

best regards

[DennisOSRM]

Oh, right. That totally makes sense. Do you want to file a PR for that change?

[cenzin]

Anything to help! How should i do that properly?

[DennisOSRM]

changed with bec585e

[jornedeblaere]

@linux-devil I 'm as well interested for a distance table in meters. Did you found a solution jet?

[kinju]

This kind of needs is very good for routing planification / optimization. It could be a good idea to not have only the times, but also the distances for some reports or I don't know ;)

[pglotov]

So just making sure, no distance in meters so far?

[alecava58]

+1 for the distance in meters.

[zavan]

+1 for the distance in meters.

[pgarin]

+1 for the distance in meters.

[keesklopt]

If you are going to implement meters, could you please make it optional ?
As i fear this could have a significant impact on generation times, network size and most important memory usage.

[cosmin-petrescu]

+1 for the distance in meters.

[rCarto]

+1 for the distance in meters.

[TheMarex]

Locked because of the 👍 noise.