Emil,
See this for a good explanation of the various algorithms:
http://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP003__.HTM
Click the right arrow at the bottom of the page to see more algorithms.
The heuristics for the traveling salesman problem fall into the following
classes:
Tour construction algorithms (creating an initial sub-tour and / or
inserting remaining points if necessary)
Tour improvement algorithms (improving the existing tour)
Most of the time, a combination of algorithms from both of these classes is
used. These are called composite procedures.
The farthest insertion is a Tour construction algorithm and it could
benefit from adding a simulated annealing of a tabu search optimizer to
improve the initial tour construction.
-Steve
On 7/6/2015 4:16 PM, Emil Tin wrote:
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
_______________________________________________
OSRM-talk mailing list
[email protected]
https://lists.openstreetmap.org/listinfo/osrm-talk
