[OSRM-talk] Shortest route given start and end point
daniel at mapbox.com
Wed Dec 9 21:37:46 UTC 2015
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.
> On Dec 9, 2015, at 2:38 AM, Kieran Caplice <kieran.caplice at temetra.com> wrote:
> 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
More information about the OSRM-talk