Milchmannproblem

[cache7]

Hallo,

wie löst man am besten folgendes Problem: ich habe sagen wir 10 Cache die ich machen will. Die Frage ist nun, in welcher Reihenfolge sind diese zu nehmen? Sprich: welches ist mit dem Auto die beste Route?

Habt ihr nen Tipp?

cache7

 

[Anonymous]

...
Habt ihr nen Tipp? ...
cache7

ja.
1. forumsuche, oder
2. passenden garmin verwenden (SP 7200 und einige nüvis beherrschen das).
3. forumsuche, oder
4. das ganze tourgelumpe in ms autoroute planen, in gsak reimportieren, anhand der usort-reihung tour manuell zusammenstellen (in mapsource oder auf dem gps-gerät)
5. forumsuche, oder mal bei geocaching-hh nachsehen.

frohes jagen

 

[London Rain]

http://geocaching-hamburg.de/2007/10/08/planung-einer-cachetour-mit-gsak-und-autoroute-teil-1-von-3/
http://geocaching-hamburg.de/2007/10/28/planung-einer-cachetour-mit-gsak-und-autoroute-teil-2-von-3/
http://geocaching-hamburg.de/2007/11/06/planung-einer-cachetour-mit-gsak-und-autoroute-teil-3-von-3/

Das ist super.

 

[hendyp]

Traveling Salesman Problem / Problem des Handlungsreisenden

Kurz und knapp: wirklich auf die beste Lösung zu kommen, ist extrem aufwändig.

Ich hatte das mal "schnell" für 15 Caches gemacht:

• Programmierung: ca. 1h
• Sammeln der benötigten Daten (Abstand in Raum (km) und Zeit (min) für alle Kombinationen): ca. 2h
• Durchlauf: ca. 1h

Die Zeit für den zweiten Punkt wächst quadratisch, d.h. doppelte Anzahl an Caches = vierfache Zeit. Der letzte Punkt ist noch schlimmer (Fakultät); wenn ein 16. Cache dazu kommt, dauert es 16x so lange... Durch sog. Heuristiken kann man die Zeit noch etwas herunterdrehen, wenn man auch mit einem schlechteren Ergebnis zufrieden ist.

Programme wie das in der von London Rain verlinkten Beschreibung genannte AutoRoute machen den zweiten Schritt natürlich automatisch und werden beim Optimieren wohl auch etwas schummeln; ansonsten würde es spätestens ab etwa 20 Caches länger zur Berechnung brauchen als ein Cacher, der 20 gleichmäßig über die Erde verteilte Caches ansteuert...

Im Endeffekt bin ich von 15 Caches an einem Tag auch nur zu sechs gekommen und muss die restlichen ein anderes Mal (dann mit neuer Route) machen.

Die Methode des Hinschauens hat bei mir bisher schneller zu Ergebnissen geführt ; also Caches in Karte eintragen (z.B. Google Earth) und sich dann was überlegen. AutoRoute besitze ich nicht und habe es auch noch nicht ausprobiert...

Gruß,
Hendy

 

[Anonymous]

Traveling Salesman Problem / Problem des Handlungsreisenden

Kurz und knapp: wirklich auf die beste Lösung zu kommen, ist extrem aufwändig.
.... AutoRoute besitze ich nicht und habe es auch noch nicht ausprobiert...

Gruß,
Hendy

das ist überhaupt nicht aufwendig.
von der grobfilterung in gsak, über die feinfilterung (optisch) in autoroute, dem reimport nach gsak und der ausgabe auf gpsr und ausdruck von tourkarte und gsak-tourliste mit hint, vergehen 10-15 minuten. das ist für eine 10 bis 30-caches-tagestour typisch.

frohes jagen

 

[eigengott]

http://www.gebweb.net/optimap/

Als "Adresse" kann man auch Koordinaten eingeben, copy & paste aus der Cachebeschreibung reicht.

 

[Anonymous]

http://www.gebweb.net/optimap/

Als "Adresse" kann man auch Koordinaten eingeben, copy & paste aus der Cachebeschreibung reicht.

bei der methode dürfte die milch relativ schnell sauer werden.

happy planning