QGIS: “Traveling Salesman”-Routing mit den ORS Tools

Im Umfeld von OpenStreetMap kommt es immer wieder mal vor, dass man eine Reihe von Objekten erkunden möchte, z.B. alle seit Jahren nicht mehr überprüften Geschäfte einer Stadt. Es ist recht einfach, solche Objekte aus der OSM-Datenbank zu extrahieren. Einen GPX-Track zu erstellen, mit dem man alle gefundenen Objekte auf optimale Weise abfahren kann, ist dagegen recht mühsam. Diese Aufgabenstellung, also den optimalen Weg zu ermitteln, auf dem eine Menge von geografischen Punkten besucht werden kann, wird Traveling Salesman Problem genannt, auf deutsch Problem des Handlungsreisenden. Das Problem kann im Prinzip nur durch Ausprobieren aller Möglichkeiten gelöst werden, so dass der Aufwand mit der Zahl der Punkte exponentiell ansteigt. Die meisten verfügbaren Lösungen sind daher nicht perfekt, aber für den Hausgebrauch ausreichend. Neben OsmAnd und QMapShack bietet openrouteservice.org über sein API ein Traveling-Salesman-Routing an. Dieses kann auch über das QGis-Plugin ORS Tools genutzt werden.

Installation und Konfiguration der ORS Tools

Um das OpenRouteService-API nutzen zu können, benötigt man einen API-Schlüssel. Dafür muss man sich auf openrouteservice.org registrieren und den Schlüssel erstellen. Nachdem das ORS-Tools-Plugin über die Plugin-Verwaltung von QGis installiert wurde, trägt man den Schlüssel in den Provider Settings des Plugins ein^[1]:

Routing mit den ORS Tools

Wenn die anzufahrenden Punkte als Wegpunkte in einer GPX-Datei vorliegen, zieht man diese einfach in das QGis-Fenster oder lädt sie mit dem Menüpunkt Layer>Layer hinzufügen>Vektorlayer hinzufügen.

Anschließend ruft man die ORS Tools auf (Web>ORS Tools>ORS Tools) und wählt unter Directions die Funktion Points (1 Layer). Im Eingabefenster dieser Funktion setzt man den Eingabelayer auf den Layer mit den GPX-Wegpunkten und wählt einen der Traveling-Salesman-Modi aus. Ein Klick auf Starte startet das Routing.

Ist dieses erfolgreich, schließt man die ORS-Fenster und sieht einen neu angelegten Layer mit der Bezeichnung Directions_Layer_.... Nach ein wenig QGis-Styling sieht man die berechnete Strecke auf der Karte.

Anschließend kann man den Layer als GPX-Track exportieren. Im Export-Dialog löscht man alle Export-Felder und erzwingt mit FORCE_GPX_TRACK=YES, dass der Layer als Track und nicht als Route gespeichert wird: