"Problem des Handlungsreisenden"

Haben Sie Vorschläge, Kommentare, Ideen...?

Moderators: Miles66, Licht & Feuer

Post Reply
User avatar
haemoglobin
Euro-Master
Euro-Master
Posts: 1414
Joined: Sat Apr 12, 2003 11:26 pm
Location: Oldenburg, Germany
Contact:

"Problem des Handlungsreisenden"

Post by 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... ;)
User avatar
helloggs
Euro-Master
Euro-Master
Posts: 1340
Joined: Sat Oct 02, 2004 1:17 pm
Location: Berlin, Germany
Contact:

Re: "Problem des Handlungsreisenden"

Post by helloggs »

Wikipedia wrote: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. :P
User avatar
taucher
Euro-Master
Euro-Master
Posts: 1572
Joined: Thu Jun 30, 2005 10:57 pm
Location: Frankfurt am Main, Germany

Re: "Problem des Handlungsreisenden"

Post by taucher »

helloggs wrote:Also wirds fuer deine Touren bestimmt 35 Jahre dauern. :P
Und wenn Jenni noch die Schuhgeschäfte mitnimmt, bestimmt 45 Jahre :mrgreen:
infinity is a great place to start

10.08.2010 | 360° Frankfurt

we're one, but we're not the same
doiknow
Euro-Master in Training
Euro-Master in Training
Posts: 766
Joined: Sun May 20, 2007 4:04 pm
Location: Hannover, Germany

Re: "Problem des Handlungsreisenden"

Post by 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 :wink:
One Currency, one Union, one Eurobilltracker...
My dots are of the same order as 10.
User avatar
androl
Euro-Master
Euro-Master
Posts: 4318
Joined: Sun Feb 08, 2004 1:20 pm
Location: München (Myeenack, Mjuncken), Deutschland (Chairmany, Djutschländ)
Contact:

Re: "Problem des Handlungsreisenden"

Post by androl »

taucher wrote:
helloggs wrote:Also wirds fuer deine Touren bestimmt 35 Jahre dauern. :P
Und wenn Jenni noch die Schuhgeschäfte mitnimmt, bestimmt 45 Jahre :mrgreen:
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 :lol:

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?
Joshu, a Chinese Zen master, asked a cow:
"Do you have Buddha-nature or not?"
The cow answered: "Moo."
User avatar
DkL
Euro-Regular in Training
Euro-Regular in Training
Posts: 50
Joined: Sun Oct 19, 2008 8:46 pm
Location: Krefeld

Re: "Problem des Handlungsreisenden"

Post by 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
User avatar
Volker W
Euro-Expert in Training
Euro-Expert in Training
Posts: 431
Joined: Fri Mar 18, 2005 8:52 pm
Location: Berlin

Re: "Problem des Handlungsreisenden"

Post by 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
User avatar
haemoglobin
Euro-Master
Euro-Master
Posts: 1414
Joined: Sat Apr 12, 2003 11:26 pm
Location: Oldenburg, Germany
Contact:

Re: "Problem des Handlungsreisenden"

Post by 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 :(

Image
User avatar
Tombola
Euro-Master
Euro-Master
Posts: 1155
Joined: Fri Feb 20, 2004 5:16 pm
Location: Salzburg, Austria

Re: "Problem des Handlungsreisenden"

Post by 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.
Tombola & Hias: Klasse statt Masse!

86/98 Bezirke of Austria
681/2358 "Gemeinden” of Austria
85/443 Kreise of Germany
114/114 Dots in Austria
314 Eu Dots
15 W Dots
User avatar
haemoglobin
Euro-Master
Euro-Master
Posts: 1414
Joined: Sat Apr 12, 2003 11:26 pm
Location: Oldenburg, Germany
Contact:

Re: "Problem des Handlungsreisenden"

Post by 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
Euro-Regular in Training
Euro-Regular in Training
Posts: 80
Joined: Tue May 30, 2006 9:58 am

Re: "Problem des Handlungsreisenden"

Post by Kurzschluss »

haemoglobin wrote: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
User avatar
lmviterbo
Euro-Master
Euro-Master
Posts: 6529
Joined: Thu Aug 21, 2003 5:23 pm
Location: Lisboa, Portugal
Contact:

Re: "Problem des Handlungsreisenden"

Post by 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
Euro-Master
Euro-Master
Posts: 2038
Joined: Mon Jul 15, 2002 11:52 am
Location: Helden, The Netherlands
Contact:

Re: "Problem des Handlungsreisenden"

Post by MDeen »

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

Return to “Diskussionen zur Site und zum Euro-Tracking (Deutsch)”