Routen automatisiert und kostenlos berechnen?

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.php?startkoord=...&zielkoord=...

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...)

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

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...

pen² schrieb:

soll heißen eigentlich ein Travelling Salesman Problem lösen

Zum Vergrößern anklicken....

pen² schrieb:

1->2, 1->3, 1->4, 1->5, 2->3, 2->4, 2->5, 3->4, 3->5, 4->5

Zum Vergrößern anklicken....

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*

pen² schrieb:

hmm wieviele Stationen kann AutoRoute denn verwalten?

Zum Vergrößern anklicken....

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

Schnüffelstück schrieb:

Ich habe den traditionellen Travelling Salesman mal in Eiffel programmiert, das war ein ekeliges Gefrett und langsam war die Sache *kotz*

Zum Vergrößern anklicken....

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.

Cornix

Cornix schrieb:

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.

Zum Vergrößern anklicken....

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 schrieb:

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.

Zum Vergrößern anklicken....

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?

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/

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.