[OSRM-talk] Shortest route given start and end point

Kieran Caplice kieran.caplice at temetra.com
Thu Dec 17 08:50:48 UTC 2015


Hi Helder,

Of course - I meant to include a link in my previous email! We'll more 
than likely be going with VROOM (https://github.com/jcoupey/vroom), 
which runs on top of OSRM. I've made it web-accessible with a simple 
Java Spring Boot app.

Kind regards,
Kieran Caplice

On 16/12/15 21:14, Helder Alves wrote:
>
> Dear Kieran,
>
> Do you want to share that solution with the list? :-)
>
> --
> Helder Alves
>
> Em 16/12/2015 3:13 da tarde, "Kieran Caplice" 
> <kieran.caplice at temetra.com <mailto:kieran.caplice at temetra.com>> escreveu:
>
>     Hi all,
>
>     Thanks for the replies. I think we have found a solution.
>
>     Kind regards,
>     Kieran Caplice
>
>     On 09/12/15 21:37, Daniel Patterson wrote:
>
>         Hi Kieran,
>
>            You're correct, OSRM doesn't currently implement the query
>         you want.  All the data you need to answer the question is in
>         the response of the `/table` API.
>
>            In theory, supporting this exact situation (fixed start/end
>         nodes) should be a fairly simple change to the trip plugin. 
>         With the addition of a URL parameter to indicate that it's not
>         a round-trip, we could insert a dummy node between the
>         start/end points with 0 weight, and this should find a path
>         with the properties you want, once we discard the dummy node
>         at the end.  Changes here should be mostly limited to the
>         `plugins/trip.cpp` file, adding some entries to the distance
>         table before performing the TSP search.
>
>            Even without this feature, you could test OSRM with a
>         couple of thousand points for a full round-trip. Performance
>         for the query would be roughly the same, and I have no idea
>         how it would handle 1000's.  It's absolutely unfeasible for a
>         brute-force search, that is limited to 10 nodes inside OSRM,
>         so it would use the Farthest Insertion algorithm, which we've
>         had good results with with 10's to 100's of points, but I
>         don't know if it's been tested to 1000's.  I suspect it's
>         probably still going to be slow, you're asking some pretty
>         computationally expensive questions here.
>
>         daniel
>
>             On Dec 9, 2015, at 2:38 AM, Kieran Caplice
>             <kieran.caplice at temetra.com
>             <mailto:kieran.caplice at temetra.com>> wrote:
>
>             Hello,
>
>             At the moment we're using the MapQuest Optimize Route API
>             (http://www.mapquestapi.com/directions/#optimized), which
>             given a list of points, computes the shortest route, using
>             the first point as the start and the last point as the
>             end. This is the exactly the functionality we're looking
>             for, but MapQuest is quite expensive, slow, and doesn't
>             support large batches (we need to support a couple of
>             thousand points).
>
>              From what I've been told, OSRM doesn't support this - it
>             only supports travelling salesman (trip), using the same
>             start and end point, or viaroute, which doesn't do any
>             optimisation. I'm wondering how easy/possible would it be
>             to implement in OSRM, or is there any pre/post processing
>             that we can do to achieve this?
>
>             Thanks in advance.
>
>             Kind regards,
>             Kieran Caplice
>
>
>             _______________________________________________
>             OSRM-talk mailing list
>             OSRM-talk at openstreetmap.org
>             <mailto:OSRM-talk at openstreetmap.org>
>             https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>         _______________________________________________
>         OSRM-talk mailing list
>         OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
>         https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
>     _______________________________________________
>     OSRM-talk mailing list
>     OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
>     https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20151217/1faa588b/attachment-0001.html>


More information about the OSRM-talk mailing list