Logo

RecyclRoute - Dokumentation RecyclRoute

Erklärung der Funktionen von RecyclRoute

In diesem Abschnitt werden die Funktionen und Interaktionen des RecyclRoute-Planner beschrieben.

Funktionen Planner:

Nach der Wahl der Planer-Page auf der Startpage wird man auf die in Grüntönen gehaltene Planner-Page weitergeleitet. Auf dieser Seite können die Standartfunktionen “Aktuelle Position”, “ nach Norden ausrichten” und “Layer-Manager” (Punkte eines Projektes anzeigen), ebenfalls genutzt werden. Die Hauptfunktion ist jedoch das Erstellen und Bearbeiten von Projekten und dem dazugehörigen Erstellen von Routen sowie dem Navigieren durch die Route.

Startseite Planer

Projektmanager

Um den Projektmanager aufrufen zu können, muss auf den Button in der Fusszeile unten rechts geklickt werden und es öffnet sich ein neues Popup-Fenster. Hier sieht man alle Projekte, welche in der Datenbank gespeichert sind. Durch Klicken auf ein bestimmtes Projekt öffnet sich ein neues Popup, in dem man die einzelnen Funktionen im ausgewählten Projekt ausführen kann. Insgesamt hat es vier Buttons, die jeweils folgende Funktionen ausführen:

Projektmanager

Neues Projekt erstellen

Im Projektmanager ganz unten gibt es den Button Neues Projekt erstellen. Hier kann ein neues Projekt erstellt werden. Es erscheint ein neues Popup, in welchem man den Projektnamen, die Gemeinde, sowie ein Sammeldatum eingeben kann. Man kann nur zum nächsten Schritt weitergeleitet werden, wenn man alle Felder ausgefüllt hat. Mit dem Klick auf “Weiter” werden die eingegebenen Werte gespeichert und man wird zur Definition des Polygons (Gebiet der Sammlung) weitergeleitet und die Karte zoomt zur eingegebenen Gemeinde.

neues Projekt

Polygon definieren & Startpunkt setzen

Nun muss auf der Karte ein Polygon gezeichnet werden, welches das ganze gewünschte Gebiet komplett umschliesst. Mit Doppelklick oder Klick auf den Button Perimeter speichern bestätigt man die Eingabe und man wird nach Eingabe des Startpunktes für die Route gefragt. Der Startpunkt muss zwingend innerhalb des Polygons definiert werden. Mit Klick auf die Karte wird der Startpunkt direkt gesetzt und die Route wird im Hintergrund berechnet. Während der Berechnung erscheint ein Popup, welches bei erfolgreichem Berechnen verschwindet.

Polygon_definieren

Nachfolgend ist ein Kurzvideo, welches den kompletten Ablauf der Erstellung eines neuen Projekts aufzeigt.

Berechnung_alles

Nach der Berechnung kommt man auf die Navigationseite, auf welcher man durch die Navigation der berechneten Route geführt wird. Dabei wird man Schritt für Schritt durch die Navigation geleitet.

Geplant ist auch, dass die Abschnitte nach Status (erledigt, aktueller Abschnitt, als nächster folgend, als übernächster folgend) unterschiedlich eingefärbt werden, damit der Benutzer möglichst einfach durch die Route geführt wird.

Navigation

Routing- und Optimierungs-Tool für vollständige Wegenetzbefahrung

Das Tool ist in einem Python-Skript aufgebaut und berechnet automatisiert eine optimale Route durch ein definiertes Strassennetz. Ziel ist es, alle relevanten Strassen in einem Gebiet möglichst effizient und ohne doppelte Befahrung abzufahren – ähnlich wie das sogenannte Chinese Postman Problem.

Eingaben

Für die Ausführung des Skripts werden folgende Daten benötigt:

Ausgaben

Das Skript erzeugt verschiedene Dateien, die direkt verwendet werden können oder für zukünftige Anwendungen vorgesehen sind:

Verwendete Module

Kategorie Bibliotheken/Technologien Verwendungszweck
Geodaten geopandas, shapely, pyproj Geometrieoperationen, Koordinatentransformation
Graphentheorie networkx, scipy.spatial.cKDTree Netzwerkaufbau, Knotenanalyse
Optimierung ortools (Google OR-Tools) TSP-Lösung, Matching-Algorithmen
Routing requests, Valhalla (lokal) Routing-Anfragen
Allgemein numpy, json, os Datenverarbeitung, Dateioperationen

Ablauf und Theoretische Grundlagen

  1. Datenvorbereitung und Koordinatentransformation
    Die Startkoordinaten werden von EPSG:3857 (Standard von MapLibre) ins Schweizer Landeskoordinatensystem EPSG:2056 transformiert (translate_start_coord(coord_3857)). Das Strassennetz im Zielgebiet wird aufbereitet, indem der GeoPackage-Layer eingelesen und irrelevante Strassen gefiltert werden (filter_street_data(gdf)).
    Ausgeschlossen werden u.a.:
    • Objektarten wie Ausfahrt, Einfahrt, Autobahn, Raststätte, Zufahrt, Dienstzufahrt, Autozug, Fähre, Autostrasse, Klettersteig, Provisorium
    • Wanderwegtypen wie Wanderweg, Bergwanderweg, Alpinwanderweg
    • Verkehrsbeschränkungen wie Allgemeines Fahrverbot, Fussweg, Fussgängerzone, Radweg, Reitweg, Panzerpiste, Teststrecke, Gesperrt
    • Belagsarten wie Natur

  2. Netzwerkaufbau und -bereinigung
    Die Liniengeometrien der verbleibenden Strassen werden analysiert. Punkte entlang der Linien werden mittels Punkt-Snapping (Toleranz 0.5m) zusammengeführt. Gerade Strassenabschnitte mit einem Winkel von mehr als 170° zwischen den Segmenten werden automatisch zusammengeführt (merge_straight_segments(graph)).
    Aus den Segmenten entsteht ein ungerichteter Multigraph (Knoten = Punkte, Kanten = Strassenabschnitte). Zu kleine oder isolierte Komponenten (<3 Knoten) werden entfernt (remove_disconnected_components(graph)).

  3. Routenoptimierung
    Das Chinese Postman Problem wird gelöst:
    • Knoten mit ungeradem Grad werden identifiziert und so gepaart, dass die zusätzlichen Verbindungen eine minimale Gesamtlänge haben (gewichtetes Matching).
    • Der resultierende Graph enthält nur noch gerade Knotengrade und ist somit eulerisierbar – ein Eulerkreis kann gefunden werden (generate_chinese_postman_coordinates(graph, start_node_coord)), berechnet mit dem Hierholzer-Algorithmus.
    • Optional kann die Koordinatenfolge gefiltert werden, um Punkte mit zu geringem Abstand zu entfernen (deaktiviert).
  4. Weitere Optimierung und Routing
    • Eine Distanzmatrix mit realen Wegstrecken (über Valhalla, nicht Luftlinie) wird erstellt (build_dist_matrix(coords, batch_size=50, max_workers=25)). Das Skript erkennt automatisch, ob Auto- oder Fuss-Routing verwendet werden muss.
    • Mit dieser Matrix wird das Travelling Salesman Problem (TSP) gelöst (solve_tsp(dist_matrix)), um die Reihenfolge der Punkte mit minimaler Gesamtreiselänge zu bestimmen (Google OR-Tools, PATH_CHEAPEST_ARC).
    • Die optimierten Koordinaten werden in Teilblöcke unterteilt und jeweils bei Valhalla angefragt (get_valhalla_route_chunked), um turn-by-turn Navigation zu erhalten. Pro Block werden JSON- und GeoJSON-Dateien erzeugt, die zu einer Gesamtroute zusammengefügt werden. Parallel werden detaillierte Navigationsanweisungen ausgegeben.

Inhaltsverzeichnis Funktionsdokumentation

Funktionsdokumentation

translate_start_coord(coord_3857)

Zweck:
Transformiert eine Koordinate vom Web-Mercator-Projektionssystem (EPSG:3857, z.B. aus einer Webkarte) ins Schweizer Landeskoordinatensystem LV95 (EPSG:2056).

Funktionsweise:
Verwendet pyproj.Transformer, um die Koordinate exakt umzuwandeln.

Input:
Tupel (x, y) in EPSG:3857

Output:
Tupel (x, y) in EPSG:2056

prepare_graph(input_json, input_gpkg)

Zweck:
Erzeugt aus einem Polygon (vom Webfrontend) und einem Strassenlayer (SwissTLM3D) ein bereinigtes, routingfähiges Strassennetzwerk.

Funktionsweise:

Input:

Output:
Netzwerkgraph als networkx.MultiGraph

filter_street_data(gdf)

Zweck:
Entfernt Strassen, die für die Routenplanung ungeeignet sind (z.B. Fusswege, Zufahrten).

Funktionsweise:
Prüft relevante Attribute (z.B. objektart, wanderweg, belagsart) und filtert alle Objekte, die in Ausschlusslisten enthalten sind.

Input:
GeoDataFrame mit Strassenattributen

Output:
Gefilterter GeoDataFrame

create_graph(gdf, polygon)

Zweck:
Schneidet den Strassenlayer mit dem Polygon und baut daraus einen Netzwerkgraphen.

Funktionsweise:

Input:

Output:
Netzwerkgraph

build_graph(roads)

Zweck:
Wandelt Liniengeometrien in einen Netzwerkgraphen um und sorgt dafür, dass nahe beieinanderliegende Punkte zusammengefasst werden.

Funktionsweise:

Input:
GeoDataFrame mit Linien

Output:
networkx.MultiGraph

clean_graph(graph)

Zweck:
Bereinigt das Netzwerk, indem kleine isolierte Komponenten entfernt und geradlinige Segmente zusammengeführt werden.

Funktionsweise:

Input:
networkx.MultiGraph

Output:
Bereinigter networkx.MultiGraph

remove_disconnected_components(graph, min_nodes=3)

Zweck:
Entfernt kleine, isolierte Teilgraphen mit weniger als min_nodes Knoten.

Funktionsweise:

Input:
networkx.MultiGraph, min_nodes (Standard: 3)

Output:
Bereinigter Graph

merge_straight_segments(graph)

Zweck:
Führt fast geradlinige Strassenabschnitte zu einer Kante zusammen, um die Komplexität des Netzwerks zu reduzieren.

Funktionsweise:

Input:
networkx.MultiGraph

Output:
Modifizierter Graph

Hinweis:
Das Verfahren basiert auf der Winkelberechnung zwischen Vektoren. Siehe Wikipedia: Line Simplification für mathematische Hintergründe.

calculate_angle(p1, p2, p3)

Zweck:
Berechnet den Winkel zwischen zwei Liniensegmenten, die sich in p2 treffen.

Funktionsweise:

Input:
p1, p2, p3 als (x, y)-Tupel

Output:
Winkel in Grad (0°–180°)

Mathematischer Hintergrund:
Siehe Wikipedia: Skalarprodukt und Winkel zwischen Vektoren.

vector(a, b)

Zweck:
Berechnet den Richtungsvektor von Punkt a zu Punkt b.

Funktionsweise:

Input:
a, b als (x, y)-Tupel

Output:
(dx, dy) als Richtungsvektor

generate_chinese_postman_coordinates(graph, start_node_coord)

Zweck:
Berechnet eine Route, die alle Kanten mindestens einmal abfährt (Chinese Postman Problem).

Funktionsweise:

Input:

Output:
Liste von [lon, lat]-Koordinaten (EPSG:4326)

Theoretischer Hintergrund:
Das Chinese Postman Problem ist ein klassisches Optimierungsproblem der Graphentheorie. Siehe Wikipedia: Chinese Postman Problem.

chinese_postman(graph, start_node=None)

Zweck:
Löst das Chinese Postman Problem auf dem Netzwerkgraphen.

Funktionsweise:

Input:
networkx.MultiGraph, optionaler Startknoten

Output:
Liste von Knoten in Eulerkreis-Reihenfolge

try_sources_to_targets(sources, targets, last_costing)

Zweck:
Fragt Entfernungen zwischen mehreren Punkten bei der Valhalla-API ab, mit Fallback auf ein alternatives Routingprofil bei Fehlern.

Funktionsweise:

Input:

Output:
Antwort der Valhalla-API (JSON)

build_dist_matrix(coords, batch_size=50, max_workers=25)

Zweck:
Erstellt eine Distanzmatrix zwischen allen Koordinatenpunkten für das TSP.

Funktionsweise:

Input:
Liste von [lon, lat]-Koordinaten

Output:
2D-Numpy-Matrix mit Distanzen in Metern

fetch_distances(i)

Zweck:
Hilfsfunktion für build_dist_matrix, berechnet eine Zeile der Distanzmatrix.

Input:
Index i (Zeile)

Output:
Liste von Distanzen für Zeile i

solve_tsp(dist_matrix)

Zweck:
Bestimmt eine optimale Besuchsreihenfolge für die Koordinatenpunkte (Travelling Salesman Problem).

Funktionsweise:

Input:
Distanzmatrix

Output:
Liste von Indexpositionen (optimale Reihenfolge)

Theoretischer Hintergrund:
Das TSP ist ein NP-schweres Problem. Siehe Wikipedia: Travelling Salesman Problem.

distance_callback(from_idx, to_idx)

Zweck:
Callback-Funktion für die Distanzberechnung im TSP-Löser.

Input:
from_idx, to_idx: Indizes

Output:
Distanzwert

decode_polyline6(encoded)

Zweck:
Dekodiert eine Valhalla-Polyline (mit 6 Dezimalstellen) in eine Liste von GPS-Koordinaten.

Funktionsweise:

Input:
encoded: String

Output:
Liste von [lon, lat]-Koordinaten

get_valhalla_route_chunked(coords, order, chunk_size=100, output_dir=”output”)

Zweck:
Ruft bei Valhalla segmentierte Routenabfragen ab und speichert die Ergebnisse je Teilroute.

Funktionsweise:

Input:

Output:
Routenblöcke als .json und .geojson

save_geojson(valhalla_json, filename=”route.geojson”)

Zweck:
Speichert die Liniengeometrie aus einer Valhalla-Route als GeoJSON-Datei.

Input:

Output:
GeoJSON-Datei

save_route_with_directions(valhalla_routes, filename=”navigation.geojson”)

Zweck:
Speichert alle Fahranweisungen als GeoJSON mit Schrittinformationen aus den Valhalla-Maneuvern.

Input:

Output:
GeoJSON mit Navigationsanweisungen

save_navigation_geojson_from_shape_indices(valhalla_routes, filename=”navigation.geojson”)

Zweck:
Exportiert Manöver auf Basis der shape_indices (Indexbereiche im Linienzug) als GeoJSON.

Input:

Output:
GeoJSON-Datei

save_trace_route_json(valhalla_routes, filename=”trace_route.json”)

Zweck:
Speichert alle Anweisungen und Geometrien als JSON-Liste (kein GeoJSON).

Input:

Output:
JSON-Datei

merge_geojson_parts(part_filenames, output_file=”route_full.geojson”)

Zweck:
Fasst mehrere GeoJSON-Dateien zu einer Gesamtdatei zusammen.

Input:

Output:
Gesamte GeoJSON-Datei

run_routing(input_json, input_gpkg, start_node_coord_3857, output_dir=”output”)

Zweck:
Steuert den gesamten Routing-Workflow von der Eingabe bis zur Ausgabe.

Funktionsweise:

Input:

Output:
Alle Routing- und Navigationsdaten als Dateien im Output-Ordner

↑ Zurück zum Beginn der Webseite

← Einleitung
Funktionen Report →