Einführung in die Welt der Tourenoptimierung – Echte Routen und realistischere Nebenbedingungen (3/3)

In diesem Artikel möchte ich euch mit einem Python Jupyter Notebook  zeigen, wie ihr Anwendungsfälle der Tourenoptimierung inklusive Nebenbedingungen lösen und visualisieren könnt. Außerdem zeige ich euch, wie ihr mit OpenStreetMaps die Route zwischen zwei Punkten für verschiedene Transportmodi berechnen lassen könnt. Dieser Artikel gehört zu meiner dreiteiligen Tourenoptimierungs-Blogreihe und baut auf dem zweiten Blogbeitrag  auf, in dem ich gezeigt habe, wie wir ein einfaches Traveling Salesman Problem (TSP) praktisch lösen und visualisieren können. Schaut euch den Artikel am besten vorher an, da ich stark auf dem vorherigen aufbauen werde.

Von der Luftlinie zu echten Routen

Ihr wollt also gerne sehen wie man die Routen zwischen zwei Zielpunkten berechnet, damit die bisherige Planung nicht nur für fliegende Fahrräder funktioniert?

Auch hierfür setze ich, wie bereits im ersten Teil der Umsetzung, auf OpenStreetMaps. Die pyroutelib3 Library bietet eine ganze Reihe verschiedener Transportmodi: Auto, Fahrrad, Bahn und sogar Pferd. Ich nehme passend zum Anwendungsfall und, um dem Ruf der Stadt Münster gerecht zu werden, das Rad. Zum Speichern der Routen verwende ich eine verschachtelte Liste.

Auf der ersten Ebene liegt die einzelne Tour bzw. das einzelne Fahrzeug, da ich aktuell in dem Grundproblem nur jeweils ein Fahrzeug betrachte. Auf der zweiten Ebene liegt dann die Route von einem Zielpunkt zum nächsten (z. B. vom Ausgangslager zum ersten Kunden) und auf der dritten Ebene findet sich eine Liste aus Tupeln mit den einzelnen Geokloordinaten für jeden Pfad. Mit der findNode-Methode suchen wir für den aktuell betrachteten Punkt der nächsten Knoten. Anschließend ermitteln wir mit der doRoute-Methode die kürzeste Route zwischen Start- und Endknoten.

Um das besser zu verdeutlichen, visualisiere ich das Ergebnis im nächsten Schritt. Dazu iteriere ich über die verschachtelte Liste und zeichne für jede Verbindung von einem Knoten zum Folgeknoten eine gerade Linie. Das erreiche ich durch eine kleine Anpassung beim Erstellen der Karte.

Das Ergebnis sieht dann wie folgt aus:

Wer sich in Münster gut auskennt, erkennt schnell, dass ein Teil der Route auf der Münsteraner Promenade liegt, auf der lediglich Radfahrer zugelassen sind. Das Ergebnis kann sich also sehen lassen.

Erweiterung – Mehrere Fahrer und begrenzte Kapazitäten

Als nächstes möchte ich euch noch zeigen, wie durch ein paar kleine Anpassungen der Ansatz um gängige Nebenbedingungen wie mehrere Fahrzeuge oder Kapazitätsbeschränkungen erweitern werden kann. Kapazitätsbeschränkungen können dabei z. B. ein maximales Volumen oder Gewicht pro Fahrzeug darstellen. Im Folgenden erweitere ich den Demo Case um die Annahme, dass es drei Fahrer gibt, wobei eines der Fahrräder ein Lastenrad mit größerem Volumen ist. Außerdem ergänze ich das Volumen der Produkte, die unsere verschiedenen Kunden erwarten. Darüber hinaus muss ich beim IndexManager berücksichtigen, dass mehrere Transportmittel zur Verfügung stehen. Der darauf folgende Teil bleibt gleich und muss nicht geändert werden. Zusätzlich müssen wir jetzt aber noch ein Demand Callback hinzufügen, um die Kapazitätsbeschränkungen einzubauen. Dieses Callback gibt zu jedem Zielpunkt das zugehörige Nachfragevolumen zurück. Anschließend muss das Demand Callback lediglich noch mit unserem RoutingModel verknüpft werden. Auch dies funktioniert, ähnlich wie beim Demand Callback, mit der RegisterUnaryTransitCallback Methode. Auch hier gibt es eine ganze Reihe an Einstellungsmöglichkeiten. So können beispielsweise Warte-, bzw. Servicezeiten berücksichtigen, was bei anderen Dimensionen sinnvoll sein kann, wir hier aber nicht wollen.

Abschließend wird die Lösung berechnet. Für die anschließende Visualisierung möchte ich die verschiedenen Touren farblich unterscheidbar darstellen. Dafür lasse ich mir eine Liste der verfügbaren Farben ausgeben. Diese Liste nutze ich dann beim Erstellen der Marker für die unterschiedlichen Touren. Aus Gründen der Übersichtlichkeit nutze ich anstatt der tatsächlichen Routen erneut gerade Linien zur Darstellung.

Auf diese Art und Weise können mit vergleichsweise geringem Aufwand bereits etwas realistischere Tourenptimierungsprobleme gelöst werden.

Fazit

In der Praxis gibt es weit mehr Nebenbedingungen, die beachtet werden müssen, wie z.B. Lieferzeitfenster, Priorisierung von Zielpunkten, verschiedene Fahrzeugtypen, die unterschiedlich gut für bestimmte Produkte geeignet sind, und so weiter. Erfahrenen Anwendern fallen hier wahrscheinlich sofort eine ganze Liste an weiteren Anforderungen ein, die eine Tourenplanungslösung für ihren Anwendungsfall abdecken sollte. Zum Abschluss möchte ich noch einmal auf den zu Beginn der Blogreihe beschriebenen Praxisfall zurückkommen:

Ein Logistikanbieter, der auf das Fahrrad als Transportmittel setzt, hatte beim Einsatz von Tourenplanungs-SaaS-Produkten Probleme, da Standardlösungen häufig Schwierigkeitenmit der Transportvariante Rad haben. 

Insbesondere die Zeitplanung, also einzuschätzen zu welchem Zeitpunkt sich welcher Fahrer wo befindet, kann Probleme bereiten. Das ist unter anderem auf die unterschiedlichen Fahrgeschwindigkeiten bei den Fahrern zurückzuführen. Selbstverständlich gibt es diese je nach Verkehrsaufkommen auch im Autoverkehr. Aber gerade bei längeren Fahrwegen gibt es bei Fahrradkurieren, im Gegensatz zu motorisierten Lieferdiensten, eine deutlich größere Varianz bei der Ausliefergeschwindigkeit, welche u. a. auf den Fahrradtyp aber auch auf die Erfahrung und Sportlichkeit des Fahrers zurückzuführen ist. All diese beeinflussenden Faktoren sind in der Regel bekannt, können jedoch häufig in Standard-One-Size-fits-All-Lösungen nicht berücksichtigt werden. Dieses Problem ist daher ein gutes Beispiel, warum insgesamt der Trend wieder vermehrt zu Individuallösungen geht. Individuallösung muss dabei übrigens nicht heißen, dass eine Anwendung von Null auf neu gebaut wird. Ein Baukastenprinzip ermöglicht es, verschiedene Grundmodule, die sehr gängige Komponenten beinhalten, miteinander zu verbinden, um sich dann auf die spezielleren Anforderungen zu konzentrieren. Wenn ihr eigene Erfahrungen oder Fragen und Anmerkungen habt, dann freue ich mich auf eine Diskussion in den Kommentaren.