Eingabe der Orte per Mausklick oder durch Adresseingabe

Klicken Sie unten auf "Schnellster Rund-Weg" bzw. auf "Schnellster Ein-Weg", so wird die optimale Route, d.h. der schnellste Weg, zwischen den Markierungen in der Karte berechnet und angezeigt. Klicken Sie auf "Ganz neu starten" und fügen Sie Ihre eigenen Orte per Mausklick oder durch Eingabe von Adressen hinzu. Das Ergebnis stellt eine Lösung des "Problems des Handlungsreisenden" ("Traveling Salesman Problem", kurz "TSP") dar.

Eine schöne Vollbild-Version dieses Routenplaners gibts hier.

Adressen hinzufügen:

• Eine einzelne Adresse (postalisch):
  
• Mehrere Adressen (auch Koordinaten sind möglich):

Hinweise:
Um einen Ort hinzuzufügen, klicken Sie einfach auf Stelle in der Karte. Der erste Ort wird als Startpunkt gesetzt, der bei "Schnellster Rund-Weg" gleichzeitig auch der Endpunkt ist. Klicken Sie auf "Schnellster Ein-Weg", so hat der Endpunkt die höchste Zahl. Sie können auch einen Marker löschen: Klicken Sie auf einen blauen Marker und dann im Infofenster auf "Lösche den Wegpunkt". Wenn es keine blauen Marker gibt und Sie einen grünen löschen möchten, dann klicken Sie auf den Button "Marker reaktivieren", wodurch alle grünen Marker sich augenblicklich blau verfärben. Jetzt können Sie den gewünschten blauen (vormals grünen) Marker aus der Route löschen. Sind mehr als 15 Orte markiert, errechnet ein spezieller Ameisenalgorithmus [] eine suboptimale Lösung. Maximal 24 Orte sind möglich. Die Routenfindung kann fehlschlagen, wenn ein Marker zu weit von Straßen oder Wegen entfernt ist.
4. Juli 2013, Update: Jetzt sind maximal 99 Orte möglich. Die Marker 25 - 99 sind dunkler als die ersten vierundzwanzig. An einem PC mit Intel Core 2 Duo, 3GHZ, 2GB RAM , Windows XP ergeben sich folgende Rechenzeiten: 10 Orte: 7 sec, 20 Orte: 34 sec, 30 Orte: 90 sec, 40 Orte: 180 sec, 50 Orte: 390 sec.

Wegbeschreibung

Die Wegbeschreibung erscheint hier nach der Routenberechnung:

Danksagungen

Der Autor bedankt sich bei

• Geir K. Engdahl, der bereits im Jahre 2007 die schöne Webseite "Google Maps Fastest Roundtrip Solver" ins Netz stellte. Seine Seite war Inspiration und Vorlage für diese Seite. Außerdem werden auch Geirs Script-Dateien "tsp.js" (modifiziert) und "BpTspSolver.js" verwendet. Auch die nummerierten Marker stammen von Geirs Website.
• James Tolley, der das Script "BpTspSolver.js" überarbeitete.
• Google für die exzellenten Online-Karten und die brillante "Google Maps-API".

 

Zukunftsmusik: Der Quanten-Routenplaner

• "Saunt-Grod-Maschinen
  konnten ganz hervorragend Probleme lösen, bei denen es darum ging, viele mögliche Lösungen gleichzeitig durchzugehen. Wie zum Beispiel beim Faulen Peregrin." "Das ist doch das, wo ein Fraa auf Wanderschaft mehrere Mathe aufsuchen muss, die willkürlich auf einer Landkarte verteilt sind?" "Ja, und das Problem besteht darin, die kürzeste Route zu finden, die ihn zu sämtlichen Zielen bringt." "Man könnte ein vollständige Liste aller möglichen Routen erstellen..." "Was aber ewig dauern würde", sagte Orolo. "In einer Saunt-Grod-Maschine könnte man eine Art verallgemeinertes Modell der Situation entwerfen und die Maschine so konfigurieren, dass sie tatsächlich alle möglichen Routen gleichzeitig untersuchen würde."
  (Neal Stephenson über Routenoptimierung per Quantencomputer in seinem Roman "Anathem" im Jahre 3690 auf dem Planeten Arbre)
• Zu diesen NP-Problemen
  gehört auch das Problem, das unter dem Namen "Traveling Salesman" bekannt wurde. Dieser steht bekanntlich ratlos vor der Aufgabe, die kürzeste Verbindungsstrecke zwischen einer größeren Anzahl von Städten zu finden, die er jeweils genau ein Mal besuchen muss. Bisher ist er auf die Hilfe rückschrittlicher klassischer Computer angewiesen. Da diese mit ihren Algorithmen mit wachsender Zahl der zu bereisenden Städte exponenziell Rechenzeit konsumieren, liegt die Weltrekordmarke derzeit lediglich bei 3038 Städten. Um zukünftig Handlungsreisenden neue Perspektiven bieten zu können, haben amerikanische Wissenschaftler am Massachusetts Institute of Technology und an der Bostoner Northeastern University jetzt schon Algorithmen für zukünftige Quantencomputer getestet. Auch wenn sie für ihre Simulation auf gestrige Computertechnik von heute zurückgreifen mussten und ihre Ergebnisse ebenso vorläufig wie spekulativ sind, wird ihr Science-Artikel die Softwarehäuser bestimmt zu ihrem übernächsten Produkt animieren: dem Quanten-Routenplaner.
  (heise.de: Der Handlungsreisende mit dem Quantencomputer, 20.04.2001)