Routen automatisiert und kostenlos berechnen?

Allgemeiner Austausch zum Thema Geocaching.

Moderator: jmsanta

Antworten
Benutzeravatar
pen²
Geocacher
Beiträge: 66
Registriert: Sa 9. Apr 2005, 20:31
Wohnort: Bayreuth

Routen automatisiert und kostenlos berechnen?

Beitrag von pen² » Di 18. Apr 2006, 21:39

Hallo Ihrs,

bei goyellow kann man ja z.B. indem man die Koordinaten in eine bestimmte URL einsetzt das entsprechende Luftbild zu der Position anschauen.
Kennt jemand zufällig eine Seite, bei der das auch für Straßenrouten funktioniert, also a'la
http://www.mapschlagmichtot.de/route.ph ... elkoord=...

Konkret brauchen würde ich nur die Länge der kürzesten Route und die Stationen sollten per Koordinaten angegeben werden können.

Hintergrund dazu:
Ich bin in einem Verein, der jährlich einige Open-Airs organisiert, nichts großes, ca. 1000 Besucher/Konzert. Dazu muss natürlich die nähere Umgebung plakatiert werden. Ich habe jetzt GPS-Koordinaten der Plakatsteller und möchte hierfür eine kürzeste Tour planen, soll heißen eigentlich ein Travelling Salesman Problem lösen.
Nur will ich ja nicht auf Luftlinienentfernung optimieren (denn dann könnte ich sofort loslegen, man wählt halt dann ein Kartendatum das kartesische Koordinaten bietet und legt los) sondern die realen Straßenkilometer.
Naja und wenn ich halt jetzt 5 Stationen hab, dann muss ich zur Optimierung diese Entfernungen kennen:
1->2, 1->3, 1->4, 1->5, 2->3, 2->4, 2->5, 3->4, 3->5, 4->5
Aber woher nehmen und nicht stehlen?
(Im konkreten Fall wäre die Größenordnung ca. 150 Stationen - da ich Mathematik studiere und sowieso noch ein Softwarepraktikum machen muss würde sich das anbieten...)
BildBild

Werbung:
Cornix
Geowizard
Beiträge: 1795
Registriert: Di 4. Okt 2005, 18:39
Wohnort: Saarland

Beitrag von Cornix » Mi 19. Apr 2006, 00:44

URL habe ich keine parat, aber mit Microsoft Autoroute kann man Routen nach verschiedenen Kriterien erstellen und sich die Zwischenstationen optimal sortieren lassen. Der Import von Wegpunkten im csv-Format ist ebenfalls möglich.

Cornix

Benutzeravatar
pen²
Geocacher
Beiträge: 66
Registriert: Sa 9. Apr 2005, 20:31
Wohnort: Bayreuth

Beitrag von pen² » Mi 19. Apr 2006, 00:59

hmm wieviele Stationen kann AutoRoute denn verwalten? ich habe gesehen, dass map&guide 11 lediglich 100 Stationen optimieren kann; das 12er kann dann 200. Allerdings werden hier aus Geschwindigkeitsgründen oft Heuristiken eingesetzt, die zwar gute, aber keine optimale Lösung liefern, daher meine Idee, das selbst zu schreiben...
BildBild

Benutzeravatar
Schnüffelstück
Geoguru
Beiträge: 3118
Registriert: Mo 5. Apr 2004, 08:21

Re: Routen automatisiert und kostenlos berechnen?

Beitrag von Schnüffelstück » Mi 19. Apr 2006, 09:02

pen² hat geschrieben:soll heißen eigentlich ein Travelling Salesman Problem lösen

pen² hat geschrieben:1->2, 1->3, 1->4, 1->5, 2->3, 2->4, 2->5, 3->4, 3->5, 4->5

Also Travelling Salesman mit 150 Punkten macht 22.350 Wegstreckeninformationen - au weia! Da die Fahrstrecke A=>B eine andere sein kann als B=>A (ich sag nur Einbahnstraße) wird die Rechnung wirklich lustig. Zusätzlich zu den angegebenen Strecken brauchst Du also noch 2=>1, 3=>1, 3=>2, 4=>1, 4=>2, 4=>3, 5=>1, 5=>2, 5=>3, 5=>4 :-(
Würde mich sehr interessieren, wie Du das programmierst. Ich habe den traditionellen Travelling Salesman mal in Eiffel programmiert, das war ein ekeliges Gefrett und langsam war die Sache *kotz*
Schnüffelstück

Bild

Cornix
Geowizard
Beiträge: 1795
Registriert: Di 4. Okt 2005, 18:39
Wohnort: Saarland

Beitrag von Cornix » Mi 19. Apr 2006, 10:26

pen² hat geschrieben:hmm wieviele Stationen kann AutoRoute denn verwalten?

Gute Frage, für meine Zwecke hat's immer gereicht. Ich kann's aber zuhause mal testen.

Schnüffelstück hat geschrieben:Ich habe den traditionellen Travelling Salesman mal in Eiffel programmiert, das war ein ekeliges Gefrett und langsam war die Sache *kotz*

Ich hab's vor Jahren mal in PROLOG programmiert, damit ging es wegen des eingebauten Backtrackings sogar relativ elegant. Aber schnell war's auch nicht gerade. :wink:

Cornix

Benutzeravatar
Schnüffelstück
Geoguru
Beiträge: 3118
Registriert: Mo 5. Apr 2004, 08:21

Beitrag von Schnüffelstück » Mi 19. Apr 2006, 10:45

Cornix hat geschrieben:Ich hab's vor Jahren mal in PROLOG programmiert, damit ging es wegen des eingebauten Backtrackings sogar relativ elegant. Aber schnell war's auch nicht gerade. :wink:

In der c´t war vor etwa einem Jahr mal ein sehr geiler Artikel über neue Programmieransatze am Beispiel des TSP. Ist vielleicht als Anregung interessant.
Schnüffelstück

Bild

Benutzeravatar
jennergruhle
Geoguru
Beiträge: 4857
Registriert: Mi 29. Jun 2005, 12:14
Ingress: Enlightened
Wohnort: Pierknüppel

Beitrag von jennergruhle » Mi 19. Apr 2006, 10:58

Schnüffelstück hat geschrieben:In der c´t war vor etwa einem Jahr mal ein sehr geiler Artikel über neue Programmieransatze am Beispiel des TSP. Ist vielleicht als Anregung interessant.

War das nicht mit simulierten Ameisenschwärmen realisiert? So nach dem Motto, kürzere Wege werden in gleicher Zeit von mehr Ameisen belaufen, was eine dichte Spur ergibt?
Feierabend- und Urlaubscacher und bekennender DNF-Logger

Benutzeravatar
pen²
Geocacher
Beiträge: 66
Registriert: Sa 9. Apr 2005, 20:31
Wohnort: Bayreuth

Beitrag von pen² » Mi 19. Apr 2006, 11:09

Jepp das mit den Ameisen ist auch ein neuerer Ansatz... aber auch mit anderen Algorithmen hat sich in letzter Zeit ziemlich viel getan; Der Rekord beim normalen TSP liegt aktuell bei einer optimalen Tour durch 24978 schwedische Städte (Luftlinie); das Programm mit dem der "Sieg" berechnet wurde gibts hier http://www.tsp.gatech.edu/
BildBild

Kalli
Geowizard
Beiträge: 1421
Registriert: Sa 19. Mär 2005, 18:56

Beitrag von Kalli » Mi 19. Apr 2006, 18:47

Die Geschichte mit MS Autoroute ist mir auch spontan eingefallen. Zumindest importieren kann MS Autoroute jede Menge (ich hatte da mal alle deutschen Caches drin), wo beim Routen die Grenze ist: keine Ahnung. Vieleicht macht es ja auch aus logistischen Gründen Sinn, mehrere Gebiete im Vorhinein festzulegen (z.B. mehrere Leute die aufstellen), dann reduziert sich das Problem.

Anderer Vorschlag: Mach deine Garage zum Cache, jeder der den Loggen will, muss ein Plakat mitnehmen und aufstellen. :wink:

Antworten

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder