"Problem des Handlungsreisenden"

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

Moderators: Miles66, Licht & Feuer

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

"Problem des Handlungsreisenden"

Postby haemoglobin » Fri May 15, 2009 10:14 am

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: 1339
Joined: Sat Oct 02, 2004 1:17 pm
Location: Berlin, Germany
Contact:

Re: "Problem des Handlungsreisenden"

Postby helloggs » Fri May 15, 2009 10:43 am

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: 1526
Joined: Thu Jun 30, 2005 10:57 pm
Location: Frankfurt am Main, Germany

Re: "Problem des Handlungsreisenden"

Postby taucher » Fri May 15, 2009 11:19 am

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"

Postby doiknow » Fri May 15, 2009 2:54 pm

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: 4313
Joined: Sun Feb 08, 2004 1:20 pm
Location: Myeenack, Chairmany
Contact:

Re: "Problem des Handlungsreisenden"

Postby androl » Fri May 15, 2009 10:04 pm

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-Newbie
Euro-Newbie
Posts: 48
Joined: Sun Oct 19, 2008 8:46 pm
Location: Krefeld

Re: "Problem des Handlungsreisenden"

Postby DkL » Sun May 17, 2009 9:56 pm

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: 428
Joined: Fri Mar 18, 2005 8:52 pm
Location: Berlin

Re: "Problem des Handlungsreisenden"

Postby Volker W » Sun May 17, 2009 11:42 pm

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"

Postby haemoglobin » Mon May 18, 2009 8:12 am

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"

Postby Tombola » Mon May 18, 2009 12:30 pm

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"

Postby haemoglobin » Tue May 19, 2009 8:52 pm

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: 59
Joined: Tue May 30, 2006 9:58 am

Re: "Problem des Handlungsreisenden"

Postby Kurzschluss » Mon Jun 27, 2016 3:24 pm

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: 3808
Joined: Thu Aug 21, 2003 5:23 pm
Location: Lisboa, Portugal
Contact:

Re: "Problem des Handlungsreisenden"

Postby lmviterbo » Thu Jun 30, 2016 2:28 am

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: 1740
Joined: Mon Jul 15, 2002 11:52 am
Location: Helden, The Netherlands
Contact:

Re: "Problem des Handlungsreisenden"

Postby MDeen » Wed Jul 06, 2016 9:48 am

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


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

Who is online

Users browsing this forum: No registered users and 1 guest