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 <[email protected]> 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
[email protected]
https://lists.openstreetmap.org/listinfo/osrm-talk
_______________________________________________
OSRM-talk mailing list
[email protected]
https://lists.openstreetmap.org/listinfo/osrm-talk
_______________________________________________
OSRM-talk mailing list
[email protected]
https://lists.openstreetmap.org/listinfo/osrm-talk
