Konstruktion
Cheapest Insertion baut die erste Lösung. Reicht der Tank für den nächsten Halt nicht, fügt der Solver davor die günstigste Nachfüllstation ein.
Open-Source-Projekt
Streamlet
Tourenplanung für Fahrzeuge, deren Tankfüllung nicht für die ganze Tour reicht.
Tank
Streamlet legt die Reihenfolge der Halte fest und plant das Nachfüllen unterwegs gleich mit. Es läuft als eigenständiger Dienst hinter einer HTTP-API.
Entstanden ist Streamlet für Green Ecolution, weil die geprüften Solver dieses Problem nicht abbilden konnten. Heute liegt es in einem eigenen Repository und hat keine Abhängigkeit zu Green Ecolution. Wer dasselbe Planungsproblem hat, kann es unverändert übernehmen.
Das Problem
Reihenfolge und Nachfüllen hängen voneinander ab
Sobald ein Fahrzeug unterwegs nachfüllen muss, hängt die beste Reihenfolge der Halte davon ab, wann und wo nachgefüllt wird. Beides zugleich zu entscheiden, ist der Kern des Problems.
Wer das dem Solver nicht mitgeben kann, hat zwei Möglichkeiten, und beide kosten Lösungsqualität: die Tour ohne das Nachfüllen planen und ein unzulässiges Ergebnis bekommen, oder die Tour von Hand in Teilstücke schneiden und damit die Optimierung über das Ganze aufgeben.
Streamlet plant die Nachfüllstationen im selben Optimierungslauf und rechnet sie nicht hinterher hinein. Bei Green Ecolution lief die Routenoptimierung vorher auf Vroom, das mehrere Nachfüllstationen mitten in der Tour nicht abbilden konnte.
Einsatzfeld
Passt Streamlet zu deinem Problem?
Streamlet ist nicht auf eine Branche zugeschnitten, entscheidend ist die Struktur der Tour. Je mehr dieser Merkmale auf deine Touren zutreffen, desto eher passt es.
- Fahrzeuge mit begrenzter Tankkapazität
- Halte mit Zeitfenstern
- Nachfüllen oder Umladen mitten in der Tour
- Mehrere mögliche Nachfüllstationen
- Rückkehr zum Depot am Schichtende
Unabhängig vom Transportgut
Streamlet kennt Tankkapazität und Bedarf, nicht Bewässerung. Was du transportierst, bleibt offen. Wasser ist der erste Anwendungsfall, die API setzt ihn an keiner Stelle voraus.
Schnittstelle
Ein Aufruf, eine Lösung
Streamlet arbeitet synchron. Du schickst das Problem, du bekommst die Routen zurück, ohne Job-Handling und ohne Polling dazwischen.
- 01
Problem senden
Ein JSON-Body an POST /v1/solve beschreibt die Fahrzeuge mit Tankkapazität und Schichtzeitfenster, die Depots, die Halte mit Bedarf und Zeitfenster sowie die Nachfüllstationen.
- 02
Kosten holen und lösen
Streamlet fragt die Reisezeit- und Distanzmatrix bei der Routing-Engine ab und löst das Problem im Solver.
- 03
Routen erhalten
Die Antwort enthält für jede Route die Reihenfolge der Halte, Distanz, Fahrt- und Wartezeit sowie die Geometrie. Dazu kommt die Liste der Halte, die unbedient bleiben.
- POST/v1/solveProblem lösen und Routen zurückgeben
- GET/healthLiveness-Prüfung
- GET/api-docs/openapi.jsonOpenAPI-Schema der API
Streamlet prüft das Problem schon beim Einlesen. Eine Startladung über der Tankkapazität, ein Zeitfenster, das vor seinem Beginn endet, oder ein Problem ohne Fahrzeug wird mit 422 abgelehnt, statt später im Solver aufzulaufen. Fehlerantworten geben keine internen Details preis, weder Engine-URLs noch fremde Response-Bodies.
Solver
Nachvollziehbar statt zufällig
Der Solver arbeitet in zwei Phasen und ohne Zufall. Solange das Zeitbudget nicht greift, ergibt dieselbe Eingabe dieselbe Ausgabe, das macht Ergebnisse reproduzierbar und Regressionen prüfbar.
Lokale Suche
Eine VND-artige Suche verbessert die Lösung. Zuerst laufen die günstigen Züge innerhalb einer Route, danach die teureren zwischen den Routen. Findet keiner davon mehr etwas, setzt sie alle Nachfüllbesuche neu und verwirft die, die sich nicht mehr lohnen.
Load- und Duration-Segmente. Kapazität und Zeitfenster prüft der Solver über Load- und Duration-Segmente nach Vidal et al. (2014). Sie lassen sich in konstanter Zeit zusammenführen, bewertet wird jeder Zug an der betroffenen Route.
Gemessen an den Solomon-Instanzen
Die Regressionstests lösen bekannte Instanzen des VRPTW, also Tourenplanung mit Zeitfenstern. Sie prüfen, ob die Lösung Kapazität und Zeitfenster einhält und ob sie nah genug am Optimum liegt. Nachfüllstationen enthalten diese Instanzen nicht, gemessen wird also die Grundqualität des Solvers.
- c101
- 3,1 %
- r101
- 1,9 %
- rc101
- 1,5 %
Abstand zur besten bekannten Lösung, Schwelle 5 %
Kartendaten
Das Straßennetz an deine Flotte anpassen
Eine gute Route nützt nichts, wenn das Straßennetz nicht zur Flotte passt. Ein Betriebsfahrzeug darf über Wirtschafts- und Dienstwege fahren, die für den allgemeinen Verkehr gesperrt sind. Eine Standardkarte weiß das nicht und lässt Ziele unerreichbar aussehen, die es nicht sind.
Die Routing-Engine rechnet auf Tiles, die aus einem OSM-Extrakt entstehen. Zum Streamlet-Repository gehört ein CLI, das dieses Extrakt vorher über OSC-Changesets verändert, also über Änderungsdateien im OSM-Format. Damit bildest du ab, was deine Fahrzeuge tatsächlich befahren dürfen.
construction
VerfügbarMarkiert Straßen, die wegen Baustellen gesperrt sind, als access=no. Routen führen dann nicht mehr durch die Sperrung.
allowed-paths
In EntwicklungÖffnet Wege für Kraftfahrzeuge, wenn ein Zielpunkt von keiner befahrbaren Straße aus erreichbar ist. Die Zielpunkte soll der Patcher aus der API von Green Ecolution lesen.
Der Patcher verändert nur dein Extrakt für deine Routing-Instanz. Er beeinflusst, was die Engine für deine Fahrzeuge als befahrbar ansieht. Eine Befahrungserlaubnis erteilt er damit nicht. Wer ihn einbindet, braucht dafür eine eigene Tile-Pipeline.
Betrieb
Einbauen und betreiben
Streamlet ist ein einzelner Dienst neben deiner Anwendung. Jeder Stand von main wird als Container-Image veröffentlicht, konfiguriert wird es über Umgebungsvariablen. Dazu brauchst du eine erreichbare Routing-Engine.
Zustandslos
Keine Datenbank, keine Job-Queue. Beim Herunterfahren laufen offene Anfragen aus, statt abzubrechen.
Engine austauschbar
Die Routing-Engine hängt hinter dem Port-Trait Router. Implementiert ist Valhalla. Eine andere Engine lässt sich dahinter setzen, ohne den Solver zu ändern.
Solver als separate Crate
Der Solver liegt in der Crate streamlet-core, ohne tokio, axum und HTTP-Code. Dazu kommen nur Serialisierung und Fehlertypen.
AGPL-3.0
Der Quellcode steht unter der GNU Affero General Public License, Version 3. Wer Streamlet verändert und als Netzwerkdienst betreibt, muss den geänderten Quellcode dessen Nutzern anbieten.
Stand
Was heute geht und was nicht
Streamlet steht am Anfang und läuft bei Green Ecolution in der Einsatzplanung. Diese Punkte stehen hier, damit niemand sie erst beim Einbauen entdeckt.
- Die Geometrie kommt als kodierte Polyline zurück. Die Option geojson verhält sich derzeit wie polyline.
- Die API nimmt mehrere Depots entgegen, jede Route kehrt aber zum ersten zurück.
- Es gibt keinen GPX-Endpoint und keine eingebettete Routing-Engine.
Mitmachen oder selbst einsetzen
Fragen, Fehlerberichte und Erfahrungen aus anderen Anwendungsfällen sind im Repository willkommen. Wie Streamlet bei Green Ecolution eingebunden ist, beschreibt Release 0.4.0.