pgRouting als Entscheidungshilfe für die französische Feuerwehr und Rettungsdienste

Am 17. Juni nimmt Camptocamp am PG Day France 2021 teil. Bei dem von der französischsprachigen PostgreSQL Community organisierten Treffen, bot sich die Gelegenheit, unsere Arbeit zum Thema Routing (straßenbezogene Berechnungen) vorzustellen. Diese Entwicklung entstand im Auftrag von l’Agence du Numérique de la Sécurité Civile (ANSC und ihrem Projekt NexSIS 18-112.

Wie rettet man ein Leben?

Stellen Sie sich folgendes vor: Ihre Oma ist gerade von einer Leiter gestürzt und liegt bewusstlos auf dem Boden. Ihr Opa ruft sofort die 112 an. Die Einsatzleitstelle fragt nach Details zur Situation. Wie sind die Umstände? Wer ist die verletzte Person? Wo ereignete sich der Unfall? Anhand dieser Angaben wird der Fall dann an die zuständige Organisation (Feuerwehr, Polizei, ...) weitergeleitet, die für das entsprechende Gebiet zuständig sind.

Sobald die Details des Anrufs an die Einsatzkräfte übermittelt wurden, ist es an der Zeit zu entscheiden, welche Personen/Fahrzeuge zum Einsatzort geschickt werden sollen (So macht es z.B. keinen Sinn, ein Feuerwehrauto zu einem Herzinfarkt zu schicken), und wie sie auf dem schnellsten Weg dorthin kommen sollen.

Schnell und seriös

Aus der Historie heraus waren die Einsatzgebiete der Feuerwachen rund um deren Standort über Alarmlisten aufgeteilt. Diese Gebiete waren so politisch wie praktisch. Wenn ein Anruf einging, sollte er je nach Gebiet, aus dem er kam, der ersten Feuerwache auf der Liste zugewiesen werden. Wenn diese Feuerwache nicht verfügbar war, dann würde die Liste auf die zweitnächste Feuerwache verwiesen, bis eine verfügbare Feuerwache gefunden wurde. Diese Listen wurden statisch berechnet, ohne die Entwicklung des Straßennetzes oder die zu einem bestimmten Zeitpunkt verfügbaren Mittel zu berücksichtigen.

Aber zurück zu Oma und Opa: Stellen Sie sich vor, ein Rettungswagen ist nach einem Einsatz auf dem Rückweg zur Feuerwache, genau in dem Moment, indem Ihr Opa seinen Anruf tätigt. Dieser Krankenwagen könnte in nur wenigen Minuten neu disponiert werden. Aber mit den vorgegebene Listen, die absolut unflexibel sind, ist das ohne den manuellen Eingriff eines Mitarbeiters nicht möglich.

Routing-Engine zur Rettung

Um die schnellstmögliche Reaktion zu gewährleisten, benötigt die Leitstelle ein dynamisches System, das die kürzesten Anfahrtswege berechnet. Wenn bereits eine Übersicht mit verfügbaren Fahrzeugen und Feuerwachen in der Nähe des Einsatzortes vorliegt, kann die Zeit berechnet werden, die jedes dieser Fahrzeuge benötigen würde, um dorthin zu gelangen.

Diese Berechnung, die von einer Routing-Engine durchgeführt wird, sollte ebenfalls schnell, aber auch flexibel sein, da Einsatzfahrzeuge nicht den gleichen Verkehrsbeschränkungen unterliegen wie normale Fahrzeuge.

Bei der Suche nach Informationen über Open Source-Routing-Engines, die schnell, aber flexibel sein sollten, mit erweiterten Funktionen und mit einer aktiven Community, kamen drei Kandidaten in die engere Auswahl:

Nach einigen Diskussionen mit Camptocamp-Kollegen und dem Lesen einiger Blogs (gis-ops.com, curiosio.medium.com oder jakobmiksch.eu) stellte sich heraus, dass pgRouting die Routing-Engine war, die benötigt wird, um die größte Flexibilität zu erhalten und gleichzeitig schnell genug zu sein (auf kurzen Strecken).

Wollen Sie etwas Algo? Holen Sie sich etwas Algo!

pgRouting ist eine PostGIS-Erweiterung, PostGIS ist die räumliche Erweiterung von PostgreSQL. Es ist wirklich ein Werkzeugkasten, um mit Graphen, Straßennetzen oder jeder anderen Art zu arbeiten.

Es werden zahlreiche Algorithmen angeboten, aber diejenigen, die den kürzesten Weg von Punkt A nach Punkt B berechnen, sind für unsere Bedürfnisse am relevantesten:

Dijkstra
Das ist DER Algorithmus für den kürzesten Weg. Leider ist er auf einem großen Graphen nicht wirklich effizient.
A*
Dieser Algorithmus wurde ursprünglich entwickelt, um den schnellsten Weg von A nach B zu finden, indem er die Suche entlang der Achse A-B bevorzugt. Auf einem homogenen Graphen (was bei einem Straßennetz nicht der Fall ist, da verschiedene Straßentypen große Unterschiede bei den Geschwindigkeitsbegrenzungen aufweisen können) ist der erste gefundene Pfad auch einer der kürzesten.
Turn Restriction Shortest Path (TRSP)
Er ist fast so schnell wie der A* und kann Abbiegeverbote in Straßennetzen berücksichtigen. Damit dieser Algorithmus sinnvoll genutzt werden kann, müssen diese Einschränkungen genau bekannt sein und vor allem wirklich restriktiv sein, was bei Einsatzfahrzeugen nicht immer der Fall ist.

Somit behalten wir den A*-Algorithmus bei, da er am leistungsfähigsten ist und weitere Optimierungen am Graphen ihn homogen genug machen.

Zum Thema Optimierung

Die wichtigste Optimierung besteht darin, die Anzahl der Straßen/Ecken zu reduzieren, die die Routing-Engine inspizieren muss, um einen Weg von A nach B zu finden. Die effektivste Art, diese Anzahl zu reduzieren, besteht darin, nur die Ecken auszuwählen, die bei der Suche nach dem kürzesten Weg von A nach B am wahrscheinlichsten verwendet werden:

Hauptstraßen mit einer hohen Geschwindigkeitsbegrenzung
Nebenstraßen in der Nähe von A und B

Aber wir sollten darauf achten, so viele Straßen wie möglich zu erfassen, um den kürzesten Weg von A nach B zu finden.

Die Auswahl dieser Straßen sollte ebenfalls optimiert werden, und zwar durch die Verwendung von räumlichen Verzeichnissen.

Zu den weiteren interessanten Optimierungen gehört die Graphen Kontraktion, die einen Graphen von unnötigen Kanten (Sackgassen) oder redundanten Informationen (mehrere Kanten, um von einem Punkt zu einem anderen zu gelangen, wenn eine einzige Kante die gleiche Information transportieren würde) befreien soll. Die Kontraktion ist in unserem Fall besonders interessant, da die Auswahl eines Teilgraphen viele redundante Knoten und Kanten erzeugt (Zwischenknoten zu Nebenstraßen sind nun nutzlos).

Der ursprüngliche Graph

Nach der Durchführung der Sackgassen-Kontraktionsoperation

Nachdem Sie die lineare Kontraktionsoperation mit dem obigen Diagramm durchgeführt haben

Die Knoten 2, 4, 10 und 12 wurden entfernt, da sie keine sinnvollen Informationen bezüglich der Graphenbeziehungen tragen. Es ist z. B. immer noch möglich, von Knoten 3 zu Knoten 5 zu gelangen, indem man die neue Kante -1 nimmt, die die Informationen der alten Knoten 1 und 2 trägt.

Eine weitere Optimierung besteht in der Many-to-One-Implementierung, die einen Teil der für Mehrfachberechnungen notwendigen Ressourcen aufteilt: nur eine Anfrage an die Datenbank, um n kürzeste Wege zu erhalten, und der Graph wird nur einmal in den Speicher geladen.

Schließlich sollten wir die Anforderungen nicht vernachlässigen, um den Algorithmus mit realen Daten nutzbar zu machen (Projektion der Start- und Endpunkte auf die Kanten des Netzes), was ebenfalls auf optimierte Weise geschehen muss (CTE, temporäre Tabellen).

Noch flexibler als Elasti-Girl

Vergessen wir nicht unser anfängliches Bedürfnis: Es soll realistischer und dynamischer sein als Listen von vorsortierten Feuerwachen. In dieser Hinsicht ist eine große Stärke von pgRouting die Fähigkeit, auf PostgreSQL und alle Möglichkeiten seiner SQL-Engine zu setzen. Das Auswählen und Ändern eines Teilgraphen kann so präzise sein, wie es SQL erlaubt. Nichts hindert uns daran, eine Straße aufgrund von Wartungsarbeiten zu sperren (vorhersehbar in einem bestimmten Zeitraum), oder jeden Sonntagmorgen für den Markt (vorhersehbar und wiederkehrend), oder aufgrund einer Überschwemmung (unvorhersehbar). Es könnte auch einen Mechanismus geben, um Geschwindigkeitsbegrenzungen auf bestimmten Straßen zu modulieren (langsamer, wenn bspw. der Straßenbelag in einem schlechtem Zustand ist, oder im Gegenteil schneller, weil sich Einsatzfahrzeuge nicht immer an Geschwindigkeitsbegrenzungen halten). Mit den richtigen Daten wäre sogar eine Verkehrsintegration denkbar.