Kürzester Weg zwischen 5 Punkten?

Question

Nehmen wir an, ich möchte eine Tour zu meinem Bäcker, zum Metzger, zum Baumarkt, zu einem Freund und meiner Tante machen. Alle Adressen sind bekannt.
Jetzt suche ich den kürzesten Weg um alle 5 Punkte abzufahren; die Reihenfolge ist egal. Gibt es im Internet ein Tool á la Google Maps, mit der man so etwas berechnen kann.

Heanzi · Accepted Answer

Tja, du hast da das "Problem des Handlungsreisendenen" (schau mal unter http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden ist ganz interessant).

Aber um deine eigentlich Frage zu beantworten:

"Ich würde die Map & Guide empfehlen. Ist DAS Programm was den professionellen Bereich abdeckt. Viele große Speditionen verwenden es.
Dort kannst du ohne Probleme die 25 Zwischenstationen eingeben und dann eine Reihenfolgeoptimierung durchführen.
Bei wenigen Zwischenstationen funktioniert das sehr gut. Bei so vielen habe ich es noch nie getestet.

Ist aber nicht für den Privatanwender gedacht da preislich in der Oberliga (~ 2.500,-)"

Alle Möglichkeiten durchprobieren ist beim TSP nicht praktikabel. Ich zitiere hierfür einfach mal Wikipedia zum TSP: "Da es nur endlich viele Rundreisen gibt, ist es theoretisch möglich, alle zu enumerieren und sich die kürzeste herauszusuchen. Praktisch ist dies jedoch nicht durchführbar, [..] und es beispielsweise schon bei nur 15 Städten über 87 Milliarden mögliche Rundreisen gibt."

Um es noch einmal auf den Punkt zu bringen, schmeiß die Lösung in den Routenplaner deiner Wahl und hoffe, dass die Programmierer eine taugliche Heuristik entwickelt haben, die eine annehmbare Lösung bringen.

Kürzester Weg zwischen 5 Punkten?

1 Antwort