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 <[email protected]>: > > 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 <[email protected]>: >>> >>> 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 [email protected] >>>> EAN 5798009493149 >>>> >>>> -----Oprindelig meddelelse----- >>>> Fra: Hans Gregers Petersen [mailto:[email protected]] >>>> 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 >>>> [email protected] >>>> -------------------------- >>>> Septima P/S >>>> Frederiksberggade 28, 2. tv. >>>> 1459 København K >>>> www.septima.dk >>>> >>>> _______________________________________________ >>>> 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 >> >> _______________________________________________ >> 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
