[pgrouting-dev] [OSRM-talk] Making progress on dumping pgRouting tables to OSRM

Stephen_Woodbridge1 · November 13, 2013, 7:00pm

On 11/13/2013 12:27 PM, Emil Tin wrote:

Hi Stephen, Sound like very interesting work, conencting pgRouting
and OSRM. I'm afraid I can't help you with your current problem, but
I'm sure Dennis can.

Emil

Hi Emil, Dennis,

Sorry, cross-posted to pgRouting-dev

So this is kind of my rough plan. I have looked into how to do the various pieces and now it is just a matter of find some time to do the code and testing.

1. build a pgr2osrm tool that will dump a pgRouting topology into an OSRM intermediate file that can be built with osrm-prepare. This is the piece that I'm working on at the moment.

2. setup a local osrm-routed (should be trivial)

3. code postgresql stored procedures to talk to osrm-routed using libcurl

4. write stored procedures like:
point = osrm_locate(point)
point = osrm_nearest(point)

    jsontext = osrm_viaroute(point, alt, instruction, zoom)
    status = osrm_getRouteStatus(jsontext);
    polyline = osrm_getRouteGeometry(jsontext, alt)
    instructions = osrm_getRouteInstructions(jsontext, alt)

distancematrix = osrm_dmatrix(points)
distancerow = osrm_one2many(point, points

To support this, it would be great if Dennis had time to add two methods to osrm-routed like:

http://server:5000/dmatrix?lat=<lat>&lon=<lon>&\.\.\.
http://server:5000/one2many?slat=<start\_lat>&slon=<start\_lon>&lat=<lat>&lon=<lon>&\.\.\.

where the list of points are the arguments. And if the we supply say 10 point, then we get back a 10 x 10 matrix. I can simulate this by making multiple calls to the server and trying to manage all the hints, but it would be far more efficient to just pass the array of points and let the server optimize caching internally. This would also decrease the number of requests to the server and the overall processing time, improving overall performance. Obviously you might not want this turned on on your public server, so maybe it is a compile time option, but clearly doing this efficiently on a local server would be ideal.

We have two major use cases for the distance matrix functionality.

1. TSP solutions for route optimization

2. We have new Vehicle Routing Problem (VRP) solver that needs to create large distance matrices for example doing single depot, multiple vehicle package delivery and pickup. In this case we need to compute the distance matrix between all the pickup, delivery and depot locations.

All this code will get packaged up in the pgRouting project, but I would like to OSRM routed changes to stay in your repository.

We also have a lot of users that are using OSM data with pgRouting so building closer ties with you makes sense to better service our joint users.

The other thing that got me thinking about this is that I was playing with the Google Gmaps API, and it exposes similar functionality. I thought it would be great if some project could come up with an OpenSource replacement for the Gmaps API, but a gating item would be to provide the server tools to support that and this would be one of the key pieces.

Right now this is all getting done without funding based on my ability to work on it between contract work. Any funding from users is always appreciated and would help accelerate my progress.

So that is the idea and my plan

-Steve

On 13 Nov 2013, at 18:04 , Stephen Woodbridge
<woodbri@swoodbridge.com> wrote:

Hi Dennis, Emil,

I have made some progress reverse engineering the current file
formats and have been able to successfully extract a pgRouting
topology into the "current" OSRM normalized data files and run
osrm-prepare on that.

That said, I have not tried to run routes on this which I will do
at some point.

I am still not clear on how restrictions are defined. The only
description that I can find is the out dated description in:

https://github.com/DennisOSRM/Project-OSRM/wiki/OSRM-normalized-file-format

Can someone please help me with the restrictions definition:

If I have the following graph:

nodes: a, b, c, d edges: ab, bc, db

a----b-----c | | d

ab, bc, and db are all two way and there is no right turn from db
to bc

Then, should the restriction as defined in the file be:

b, d, c, forbidden, 7F 00 00

where:

b is the via-node d is the from-node c is the to-node

and the records should then be sorted by edge_id of EDGE[via-node,
to-node].

Is this correct?

I'm happy to create an updated reference page for the normalized
file format once I get this all sortted out and working.

Thanks, -Steve

_______________________________________________ OSRM-talk mailing
list OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

_______________________________________________ OSRM-talk mailing
list OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

dkastl · November 14, 2013, 2:01am

4. write stored procedures like:
   point = osrm_locate(point)
   point = osrm_nearest(point)

   jsontext = osrm_viaroute(point, alt, instruction, zoom)
   status = osrm_getRouteStatus(jsontext);
   polyline = osrm_getRouteGeometry(jsontext, alt)
   instructions = osrm_getRouteInstructions(jsontext, alt)

   distancematrix = osrm_dmatrix(points)
   distancerow = osrm_one2many(point, points

To support this, it would be great if Dennis had time to add two methods
to osrm-routed like:

http://server:5000/dmatrix?lat=<lat>&lon=<lon>&\.\.\.
http://server:5000/one2many?slat=<start\_lat>&slon=<start\_
lon>&lat=<lat>&lon=<lon>&...

Hi Steve, Dennis and Emil,

To be able to use the route for further processing, it would be also nice,
if OSRM would return a list of original network link ID's instead of a more
or less simplified route geometry and a few via points.

This is not an issue for distance matrices, where you only need to total
distance or cost, but too much generalized routes was the reason, why I
couldn't make use of OSRM once. And especially if the OSRM routing result
could be later used again in PostgreSQL/PostGIS, having the original road
network ID's would be very helpful.

So far I couldn't find anything else than this JSON output format:
https://github.com/DennisOSRM/Project-OSRM/wiki/Output-json

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_Woodbridge1 · November 15, 2013, 2:25am

Antonio,

Thank you for the feedback on CURL, and the other references.

I kind of look at the development path as get it working then figure out how to make it fast. Get it working allows use to validate the approach, but having feedback like this is great so we can avoid the same issues others have already discovered.

I'll have to read up on the apache httpclient stuff. I have never seen that before.

Did you write a wrapper for your requests to OSRM via httpclient? Can you share that?

Thanks,
-Steve

On 11/13/2013 4:03 PM, Antonio Moratilla Ocaña wrote:

Hi Stephen

Only two notes that may help you with your plan:
I've been working on using OSRM from a web service, and i've learned
OSRM doesn't perform so good when queried with curl (Ok, it's not OSRM
problem, but curl: it need to setup a route and connection to the
server, and it takes time, and usually you don't go concurrent here). In
my problem, i've been using apache commons httpclient in a concurrent
fashion (http://hc.apache.org/httpcomponents-client-4.3.x/index.html ,
http://hc.apache.org/httpcomponents-client-4.3.x/httpclient/examples/org/apache/http/examples/client/ClientMultiThreadedExecution.java),
so connections didn't get released: I was able to reach up to 700
request por second to my test server, but when used with curl (called
from java), I couldn't go above 20 request per second.

On the distance matrix topic, I remember Dennis talking about it some
time ago, and, if i'm correct, he said he had implemented a really
efficient method for matrix calculation using some clever ideas with
OSRM internal data representation. He said that code was not open source
(maybe some project/contract source code?. Later on, he said he had
matrix calculation on target to be included on OSRM soon (maybe another
source code version)
https://github.com/DennisOSRM/Project-OSRM/issues/544, so it would be
great if that feature could be added. You can also try Klopt
(https://code.google.com/p/klopt/wiki/introduction ,
https://github.com/keesklopt/matrix)

Good luck!!!

Antonio Moratilla Ocaña - antonio.moratilla@uah.es
<mailto:antonio.moratilla@uah.es> - Despacho N334

Profesor del Dpto. Ciencias de la Computación - http://www.cc.uah.es
Escuela Politécnica - Informática - http://www.etsii.uah.es
Universidad de Alcalá - http://www.uah.es

2013/11/13 Stephen Woodbridge <woodbri@swoodbridge.com
<mailto:woodbri@swoodbridge.com>>

    On 11/13/2013 12:27 PM, Emil Tin wrote:

        Hi Stephen, Sound like very interesting work, conencting pgRouting
        and OSRM. I'm afraid I can't help you with your current problem, but
        I'm sure Dennis can.

        Emil

    Hi Emil, Dennis,

    Sorry, cross-posted to pgRouting-dev

    So this is kind of my rough plan. I have looked into how to do the
    various pieces and now it is just a matter of find some time to do
    the code and testing.

    1. build a pgr2osrm tool that will dump a pgRouting topology into an
    OSRM intermediate file that can be built with osrm-prepare. This is
    the piece that I'm working on at the moment.

    2. setup a local osrm-routed (should be trivial)

    3. code postgresql stored procedures to talk to osrm-routed using
    libcurl

    4. write stored procedures like:
        point = osrm_locate(point)
        point = osrm_nearest(point)

        jsontext = osrm_viaroute(point, alt, instruction, zoom)
        status = osrm_getRouteStatus(jsontext);
        polyline = osrm_getRouteGeometry(__jsontext, alt)
        instructions = osrm_getRouteInstructions(__jsontext, alt)

        distancematrix = osrm_dmatrix(points)
        distancerow = osrm_one2many(point, points

    To support this, it would be great if Dennis had time to add two
    methods to osrm-routed like:

    http://server:5000/dmatrix?__lat=
    <http://server:5000/dmatrix?lat=><lat>&lon=<lon>&\.\.\.
    http://server:5000/one2many?__slat=
    <http://server:5000/one2many?slat=><start\_lat>&slon=<start\_\_\_lon>&lat=<lat>&lon=<lon>&\.\.\.

    where the list of points are the arguments. And if the we supply say
    10 point, then we get back a 10 x 10 matrix. I can simulate this by
    making multiple calls to the server and trying to manage all the
    hints, but it would be far more efficient to just pass the array of
    points and let the server optimize caching internally. This would
    also decrease the number of requests to the server and the overall
    processing time, improving overall performance. Obviously you might
    not want this turned on on your public server, so maybe it is a
    compile time option, but clearly doing this efficiently on a local
    server would be ideal.

    We have two major use cases for the distance matrix functionality.

    1. TSP solutions for route optimization

    2. We have new Vehicle Routing Problem (VRP) solver that needs to
    create large distance matrices for example doing single depot,
    multiple vehicle package delivery and pickup. In this case we need
    to compute the distance matrix between all the pickup, delivery and
    depot locations.

    All this code will get packaged up in the pgRouting project, but I
    would like to OSRM routed changes to stay in your repository.

    We also have a lot of users that are using OSM data with pgRouting
    so building closer ties with you makes sense to better service our
    joint users.

    The other thing that got me thinking about this is that I was
    playing with the Google Gmaps API, and it exposes similar
    functionality. I thought it would be great if some project could
    come up with an OpenSource replacement for the Gmaps API, but a
    gating item would be to provide the server tools to support that and
    this would be one of the key pieces.

    Right now this is all getting done without funding based on my
    ability to work on it between contract work. Any funding from users
    is always appreciated and would help accelerate my progress.

    So that is the idea and my plan

    -Steve

        On 13 Nov 2013, at 18:04 , Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

            Hi Dennis, Emil,

            I have made some progress reverse engineering the current file
            formats and have been able to successfully extract a pgRouting
            topology into the "current" OSRM normalized data files and run
            osrm-prepare on that.

            That said, I have not tried to run routes on this which I
            will do
            at some point.

            I am still not clear on how restrictions are defined. The only
            description that I can find is the out dated description in:

            https://github.com/DennisOSRM/__Project-OSRM/wiki/OSRM-__normalized-file-format
            <https://github.com/DennisOSRM/Project-OSRM/wiki/OSRM-normalized-file-format>

    Can someone please help me with the restrictions definition:

            If I have the following graph:

            nodes: a, b, c, d edges: ab, bc, db

            a----b-----c | | d

            ab, bc, and db are all two way and there is no right turn
            from db
            to bc

            Then, should the restriction as defined in the file be:

            b, d, c, forbidden, 7F 00 00

            where:

            b is the via-node d is the from-node c is the to-node

            and the records should then be sorted by edge_id of
            EDGE[via-node,
            to-node].

            Is this correct?

            I'm happy to create an updated reference page for the normalized
            file format once I get this all sortted out and working.

            Thanks, -Steve

            _________________________________________________ OSRM-talk
            mailing
            list OSRM-talk@openstreetmap.org
            <mailto:OSRM-talk@openstreetmap.org>
            https://lists.openstreetmap.__org/listinfo/osrm-talk
            <https://lists.openstreetmap.org/listinfo/osrm-talk>

        _________________________________________________ OSRM-talk mailing
        list OSRM-talk@openstreetmap.org
        <mailto:OSRM-talk@openstreetmap.org>
        https://lists.openstreetmap.__org/listinfo/osrm-talk
        <https://lists.openstreetmap.org/listinfo/osrm-talk>

    _________________________________________________
    OSRM-talk mailing list
    OSRM-talk@openstreetmap.org <mailto:OSRM-talk@openstreetmap.org>
    https://lists.openstreetmap.__org/listinfo/osrm-talk
    <https://lists.openstreetmap.org/listinfo/osrm-talk>

dkastl · November 15, 2013, 2:55am

On Fri, Nov 15, 2013 at 11:25 AM, Stephen Woodbridge <
woodbri@swoodbridge.com> wrote:

Antonio,

Thank you for the feedback on CURL, and the other references.

I kind of look at the development path as get it working then figure out
how to make it fast. Get it working allows use to validate the approach,
but having feedback like this is great so we can avoid the same issues
others have already discovered.

I'll have to read up on the apache httpclient stuff. I have never seen
that before.

Did you write a wrapper for your requests to OSRM via httpclient? Can you
share that?

Hi Steve,

I just remember Paul's HTTP client for PostgreSQL:
https://github.com/pramsey/pgsql-http
So here is some use case now

But it seems it uses curl.

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de