"Problem des Handlungsreisenden"

[haemoglobin]

an unsere Mathematik- und Informatiknerds....

Ich sitze grad mal wieder über Google Earth und trage noch zu trackende Locations ein. Bei der Menge der Locations ist eine vernünftige Tourplanung mehr als angebracht.
Da gibt es doch das schöne Problem des Handlungsreisenden

Gibt es vielleicht irgendwo in den Weiten des Netzes eine versteckte Seite oder spezielle Routenplaner die dieses Problem angehen?

man könnte sich dann so manchen km sparen...

[helloggs]

Komplexitätstheoretisch gehört das TSP zur Klasse der NP-äquivalenten Probleme. Es wird daher sehr stark angenommen, dass die Worst-case-Laufzeit jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, im besten Fall exponentiell von der Anzahl der Städte abhängt. Schon für wenige Städte kann die benötigte Laufzeit eines solchen Algorithmus also unpraktikabel viel Zeit beanspruchen.

Also wirds fuer deine Touren bestimmt 35 Jahre dauern.

[taucher]

Also wirds fuer deine Touren bestimmt 35 Jahre dauern.

Und wenn Jenni noch die Schuhgeschäfte mitnimmt, bestimmt 45 Jahre

[doiknow]

Versuchs mal damit (ich habe es nicht getestet, aber anscheinend gibts den Quellcode auf der Seite und das Programm).
http://www.lalena.com/AI/Tsp/

So nebenbei würde ich mal auf 42 Jahre tippen

[androl]

Also wirds fuer deine Touren bestimmt 35 Jahre dauern.

Und wenn Jenni noch die Schuhgeschäfte mitnimmt, bestimmt 45 Jahre

du hast das mit der exponentiellen Zeit nicht verstanden.
Wenn Jenny ein Schuhgeschäft mitnummt, braucht das Programm 100 Jahre. Bei zwei Schuhgeschäften 300 Jahre. Bei drei Stück 1000 Jahre.

Schuhgeschäfte gibt es aber noch viel mehr

Hämo: Ich glaube, gehört zu haben, dass es einen polynomiellen Algorithmus gibt, der das Problem mit einer bestimmten Fehlerschwelle löst, also der einen Weg findet, wo es keinen anderen Weg gibt, der mehr als 20 Prozent kürzer ist. Reicht dir das?

[DkL]

hab da mal google gewälzt und was gefunden, klein, relativ schnell (im vergleich zu den oben genannten zeitspannen 0o) und auf basis von googlemaps

http://gebweb.net/optimap/

ich habs ausprobiert.. bei ca 30 locations geschätze 30-60 sekunden ladezeit

[Volker W]

Toll DkL, danke für den link..

Große Klasse, das geht ja auch für Fußgänger/Radfahrer

Habe das gerade auch ausprobiert und festgestellt, dass meine 15 Lieblingsbanken hier in Berlin schon in 5:15 h zu Fuß oder die 24 km mit dem Fahrrad in 2-3 Stunden zu erreichen wären. Statt in 2-5 Tagen wie jetzt.

Dass das in der Praxis natürlich bedeutend mehr Zeit beanspruchen wird ist schon klar aber nett ist das Teil auf jeden Fall.
Wir können also auch als nicht Bahn/Autofahrer uns schöne Rundgänge errechnen lassen.

Ob es nun unserem Haemo hilft weiß ich nicht, aber mir und anderen wird es gefallen.

Danke und freundliche Grüße
Volker

[haemoglobin]

DAS ist genau das wonach ich gesucht habe
mal schauen wie es sich in der praxis bewährt

leider bleibt dann auch mehr zeit für schuhgeschäfte

[Tombola]

Ganz netter Link!
Aber ich finde: Eine EBT Tour ohne eigener Planung ist nur der halbe Spaß! Gerade das lange Brüten über der Karte lässt die Vorfreude und Neugierde auf bisher unbekanntes Land so richtig wachsen.

[haemoglobin]

hab das tsp-tool mal an unseren partner für den probentransport in unserem labor weitergeleitet. vielleicht kann der ja die touren dadurch etwas optimieren und ich hab früher feierabend..

btw: es werden leider "nur" 24 locations berechnet, aber trotzdem immer noch super

[Kurzschluss]

Gibt es vielleicht irgendwo in den Weiten des Netzes eine versteckte Seite oder spezielle Routenplaner die dieses Problem angehen?

Auch wenn das Thema schon älter ist, hier mal zwei Kommentare:

1. Mein Navigationssystem (Garmin, Typ "ich saug mich an der Scheibe fest") hat einen Menüpunkt für Routen. Man kann grundsätzlich alle Ziele eingeben und das Navi dann arbeiten lassen.

2. Ich halte trotz allem nicht viel von vollautomatischer Planung, da so ein vollautomatisches Programm meist Probleme mit "Sonderbedingungen" hat. Beispiel: Ich nehme demnächst an einer Veranstaltung teil und reise mit dem PKW an. Ich möchte bei der Gelegenheit "Mühlenweg 10,39517 Lüderitz" besuchen, nur ist zu beachten, dass der Geldautomat der Sparkasse in der Nacht geschlossen hat (Geld gibt's dort nur von 05:00 bis 23:00 Uhr). Also muss ich mir überlegen, ob ich später los fahre und ggf. etwas später bei der Veranstaltung erscheine oder ob ich den Ort nicht in der kilometermäßig angesagten Reihenfolge anfahre oder ob ich noch was anderes mache (denkbar wäre es auch die STAR-Tankstelle in Dolle anzufahren, die hat laut I-Net immer offen). -> Da hilft nur "manuelle" Planung.

Gruß Kurzschluss

[lmviterbo]

https://www.routexl.nl/?lang=de

"RouteXL ist ein Routenplaner mit mehreren Zielorten. Auf einfache Weise finden Sie hier die schnellste Route entlang mehrerer Zwischenstationen. RouteXL bringt die Zieladressen in optimierter Reihenfolge. Für bis zu 20 Adressen können Sie RouteXL gratis benutzen. Möchten Sie bis zu 100 Adressen abrufen dan bieten wir Sie um einen kleine Beitrag."

[MDeen]

Da gibt es auch noch http://gebweb.net/optimap/