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
