[OSRM-talk] Route Optimizing

[Emil Tin]

Seems it the farthest insertion algorithm although i'm not familiar with it.

Sendt fra min iPhone

> Den 06/07/2015 kl. 21.40 skrev Stephen Woodbridge <woodbri at swoodbridge.com>:
> 
> I have not looked at the round_trip feature code, but if it is solving a TSP problem it really need to solve it for an asymmetric matrix and not a symmetric matrix. Most of the algorithms you find around the web solve the symmetric case, but because we are dealing with oneway streets and turn restrictions, etc there can be some big differences in cost based on the direction of travel between nodes.
> 
> There is a way to convert an asymmetric matrix into a symmetric matrix that might be an option. Or if you are only looking for an approximate optimization solution then the symmetric matrix might be good enough.
> 
> You can look at pgRouting and see what we have done there.
> 
> -Steve
> 
>> On 7/6/2015 2:03 PM, Jonas Plass wrote:
>> Thank you guys for the Inspiration. I will have a Look at it tomorrow.
>> 
>> 
>> 
>> 
>>> Am 06.07.2015 um 18:03 schrieb Stephen Woodbridge <woodbri at swoodbridge.com>:
>>> 
>>> A simple trick if you want to do start-via-via-...-via-end optimization like TSP is to use TSP and artificially set the distance between end and start locations to zero and this will keep those two city bound together. Then in the result just remove that link.
>>> 
>>> This will allow the same code that solves TSP round trip to also optimize the vis points between a start and end trip.
>>> 
>>> -Steve
>>> 
>>>> On 7/6/2015 10:02 AM, Emil Tin wrote:
>>>> 
>>>> 
>>>> The OSRM team is working on a new API call to compute a round-trip that visits a list of point:
>>>> 
>>>> https://github.com/Project-OSRM/osrm-backend/tree/feature/round_trip
>>>> 
>>>> 
>>>> Med venlig hilsen
>>>> 
>>>> Emil Tin
>>>> IT- og Processpecialist
>>>> Trafik
>>>> _______________________________
>>>> KØBENHAVNS KOMMUNE
>>>> Teknik- og Miljøforvaltningen
>>>> Byens Anvendelse
>>>> 
>>>> Njalsgade 13, 1035
>>>> Postboks 380
>>>> 2300 København S
>>>> 
>>>> Direkte 2369 5986
>>>> Mobil 2369 5986
>>>> Email zf0f at tmf.kk.dk
>>>> EAN 5798009493149
>>>> 
>>>> -----Oprindelig meddelelse-----
>>>> Fra: Hans Gregers Petersen [mailto:gregers at septima.dk]
>>>> Sendt: 6. juli 2015 15:55
>>>> Til: Mailing list to discuss Project OSRM
>>>> Emne: Re: [OSRM-talk] Route Optimizing
>>>> 
>>>> Hi Jonas,
>>>> 
>>>> 
>>>>> Are there any ambitions to create something like an optimization for route stops?
>>>>> And when not do you know any other way to do this via rest request?
>>>> 
>>>> 
>>>> If you are thinking of the TSP -
>>>> https://en.wikipedia.org/wiki/Travelling_salesman_problem - then it is a simple problem of "I need to visit X places after each other, please optimize the order to visit those places in". The solution is well-described in the WikiPedia link. You can write a little JavaScript, Python or whatever - and optimize on either distance or time. It is fairly simple, and all you use OSRM for is getting the costs. If you want as few calls to the OSRM-server as possible, then have a look at the "table"-service  ( https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#available-services
>>>> )
>>>> 
>>>> Best regards,
>>>> 
>>>> Greg
>>>> 
>>>> 
>>>> Hans Gregers Petersen
>>>> Partner, Seniorkonsulent
>>>> gregers at septima.dk
>>>> --------------------------
>>>> Septima P/S
>>>> Frederiksberggade 28, 2. tv.
>>>> 1459 København K
>>>> www.septima.dk
>>>> 
>>>> _______________________________________________
>>>> 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
>> 
>> _______________________________________________
>> 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