[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