- Routenplanung
-
Routenplaner (Streckenplaner, Wegplaner, von französisch: route = Weg) sind Computerprogramme, mit deren Hilfe ein Weg zwischen einem Start- und einem Zielort gefunden werden kann. Meistens können auch ein oder mehrere Orte dazwischen ("via") angegeben werden. Es können meistens Wünsche angegeben werden, ob die schnellste, die kürzeste, die wirtschaftlichste (ökonomischste) oder manchmal auch die schönste Route gesucht werden soll.
Routenplaner gibt es entweder offline für PC oder für eingebaute GPS-Navigationssysteme in Fahrzeugen oder im Internet wie z. B. map24 oder Google Maps. Für Radfahrer gibt es spezielle Routenplaner, die bei der Streckenermittlung bevorzugt Radwege auswählen.
Daten
Die Geodaten (routingfähige Straßennetzdaten, geokodierte Hausnummern, Points of Interest) der verschiedenen Routenplaner kommen von nur wenigen Firmen. Aktuelle europaweite Straßendaten werden von den Firmen Navteq und Tele Atlas erstellt.
Im Aufbau befindet sich momentan OpenStreetMap, ein freies Projekt mit dem Ziel, weltweit Geodaten zu sammeln, die jedermann kostenlos zur Verfügung stehen. Im städtischen Gebiet sind die Daten meist annähernd vollständig, in der Fläche sind aber oft nur Durchgangsstraßen verfügbar.
Lösungsstrategien
Lösungen lassen sich mit Hilfe der Graphentheorie finden; für eine Optimale Lösung zum Beispiel mit dem Dijkstra-Algorithmus. Um für Routenplaner mit großem Straßennetzwerk hinreichend schnell zu einer dem Optimum nahen Lösung zu kommen, müssen allerdings Heuristiken angewandt werden. Ein Spezialfall der Routenplanung ist das Problem des Handlungsreisenden.
Weblinks
Wikimedia Foundation.
