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

Helder Alves helderalvespt at gmail.com
Wed Dec 16 21:14:58 UTC 2015


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>
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>
>>> 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
>>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>>
>>
>> _______________________________________________
>> OSRM-talk mailing list
>> 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/20151216/63d12978/attachment.html>


More information about the OSRM-talk mailing list