Geocaching > Caches & Touren > Problem des Handlungsreisenden Geocachers auf Tour

Problem des Handlungsreisenden Geocachers auf Tour

5. Dezember 200811 KommentareEiner von 546 Beiträgen von aba

Traveling Salesman Problem – Wer häufig auf Dienstreise ist, und dabei nicht nur eine Strecke A => B zurücklegen muß, wird es nur zu gut kennen. A, B, C, D, E und F sind die Ziele der Reise. Und die Route soll so optimal gewählt werden, dass die gesamte Reisestrecke nach Rückkehr zu A möglichst kurz ist.

(Das Problem kennt man übrigens auch, wenn man mit seiner Frau des öfteren in großen Shoppingcentern unterwegs ist. Wobei dann die Ziele in etwa A, B, C, A, B, A, C, D, A, A, A, E, B, B usw sind.)

Auf jeden Fall ist das ganz oben beschrieben Szenario nicht neu und trifft wohl auch dann zu, wenn Geocacher eine Reise planen. Die Cyberberrys beispielsweise dürften hin und wieder mal vor dieser Thematik ins Schwitzen gekommen sein: Wie sammelt man möglichst sinnvoll bei einer Rundreise durch Deutschland möglichst viele Dosen ein? Ohne dabei Umwege und doppelte Strecke zu haben?

Das Problem ist ein mathematisches, sagt uns die große Allwissende. Und zwar schon seit 1930. Kluge Köpfe haben Nächte über Optimierungsmöglichkeiten gebrütet. Gefunden auch. Und das natürlich auch in der Welt 2.0. Nämlich mit : Google Maps Fastest Roundtrip Solver. Ein feines Mashup, das eigentlich auch ganz prima mit vielen anderen neuen Funktionalitäten auf GC.COM eingebunden gehört. Denn das braucht ja nun eigentlich jeder, der “mal so” eine kleine Tour für das Wochenende plant.

Happy rumprobiering!

[ Vielen Dank an rabazzo für den Hinweis! ]

Tags: , ,

11 Kommentare »

  • cyberberry (Stefan) sagt:

    Das werde ich doch bei Gelegenheit mal ausprobieren.

    Aber nach Schwerin finde ich inzwischen sogar ohne Brille, Stock und Blindenhund ;-)

    # 5 Dezember 2008 um 13:41
  • matzotti sagt:

    Hm, aber den Anschein, den mein kleiner Test hinterläßt, ist nicht so berauschend. Es wird die Reihenfolge der Punkte angefahren, die ich eingeben, genauer, das Tool berücksichtigt nicht kürzere Entfernungen des n+2-Punktes gegenüber der distanz zum n+1ten Punktes, oder war mein Testmodell nur einfach klinisch falsch ?

    # 5 Dezember 2008 um 14:19
  • aba (Autor) sagt:

    @matzotti
    hast du denn mal mit anderen punkten probiert? bei mir hats ganz gut funktioniert. habe mal so ein paar stationen schwerin, berlin, münchen eingegeben – und das ergebnis war ok.

    # 5 Dezember 2008 um 14:30
  • AndiOlli sagt:

    Das ist ja mal wieder ein klasse Hilfsmittel. Werde ich mal zu meinem nächsten Besuch in Neu Lüblow (bei Ludwigslust) zu Weihnachten probieren. Denn da sind ja einige neue Caches seit Sommer hinzugekommen, die auf mich warten. Ich hoffe ich finde trotz Weihnachten die Zeit für ein paar Caches :-)
    Mal schauen wie ich am einfachsten und schnellsten alle relevanten Koordinaten von GC in das Tool bekommen, bin ja kein Premium Member. Aber vielleicht gehts ja auch den Waypoint Download.

    # 5 Dezember 2008 um 14:36
  • matzotti sagt:

    na, so ein Schlingelchen. Nummeriert ja nach der Berechnung die Punkte um. Aber selbst dann soll ich zuerst an einem Punkt vorbeifahren, um ihn später als letzten einzufangen. Interessant finde ich ja, dass die Straßenführungen bekannt sind. Bin ja neugierig, ob da auch Einbahnstraßen und Geschwindigkeitsbegrenzungen integriert sind :-p).

    # 5 Dezember 2008 um 15:02
  • 5_pomms sagt:

    Finde ja fetzig, dass die dort Ant Colony Optimization als optimierungsalgorithmus nutzen. Aber ihr habt ja sicher eh mit unter 10 orten getestet oder?

    # 5 Dezember 2008 um 18:42
  • aba (Autor) sagt:

    aehm, welche methode wuerde denn besser das problem loesen? mir ist die aco als jene mit den besten ergebnissen auf das tsp bezogen bekannt. gibts bessere?

    # 5 Dezember 2008 um 20:48
  • 5_pomms sagt:

    nee, nicht das ich wüsste (bin nun auch nicht so die optimierungsexpertin), so meinte ich das auch nicht. Hab mich bisher auch nicht mit aco befasst. Einfach nur eine fetzige (bildliche) vorstellung, dass nun millionen cacher den ameisen folgen.

    # 5 Dezember 2008 um 21:17
  • aba (Autor) sagt:

    ah! ok! ha, ich hatte das jetzt gar nicht uebersetzt.
    stimmt, feldversuche mit ameisen haetten in der tat was ;)

    # 5 Dezember 2008 um 21:26
  • London Rain sagt:

    Dazu fällt mir auch noch das hier ein:

    Planung einer Cachetour 1 von 3 von m.zielinski
    Planung einer Cachetour 2 von 3 von m.zielinski
    Planung einer Cachetour 3 von 3 von m.zielinski

    # 8 Dezember 2008 um 14:10
  • struwwelchen sagt:

    Da passt doch dieser Cache wie die sprichwörtliche Faust auf’s Auge:

    Alles, was zählt
    http://www.geocaching.com/seek/cache_details.aspx?guid=80566ae0-1876-4de8-8c84-e231fa35374b

    # 8 Dezember 2008 um 17:49

Schreib` einen Kommentar.

Kommentiere hier oder in Deinem Blog per Trackback. Du kannst die Kommentare auch als RSS-Feed abonnieren. Es kann passieren, dass ein Kommentar vor der Veröffentlichung von uns freigeschaltet werden muss. Sollten wir dazu zu lange brauchen, hilft eine kleine Mail an podcast bei dosenfischer d e

Be nice. Keep it clean. Stay on topic. No spam. ;)

Du kannst verwenden:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Dosenfischer nutzt Gravatare.