ZoBaRoute Webapplikation
Von der Bestellliste zur fertigen Lieferroute – eine Webapplikation für den Cevi Seuzach
Der Verein Cevi Seuzach organisiert jährlich traditionell eine Zopfbackaktion. Dabei backt der Verein mehrere hundert Zöpfe und liefert diese an einem einzigen Vormittag aus. Die Routen dafür entstanden bisher von Hand: Hunderte von Adressen mussten in sinnvolle Touren aufgeteilt werden. Die ZoBaRoute Webapplikation nimmt dem Organisationskomitee diese Arbeit ab: Bestellliste hochladen, Anzahl Teams und die Verteil-Zentrale festlegen und fertige Routen in den Formaten PDF und GPX herunterladen.
Ausgangslage
Die Zopfbackaktion ist der grösste Anlass des Vereins. Dabei werben Vereinsmitglieder von Tür zu Tür für einen frischen Sonntagszopf, der anschliessend an einem fixen Datum produziert und ausgeliefert wird.
Die grösste Herausforderung liegt aber nicht im Anwerben, sondern in der darauffolgenden Planungsphase. Aktuell müssen Hunderte von Bestellungen manuell in sinnvolle Routen gruppiert werden. Das kostet viel Zeit und ist ein mühsamer Prozess. Um die Ressourcen des Vereins zu entlasten und die Effizienz der Logistik zu steigern, wurde ZoBaRoute entwickelt.
Lösung
ZoBaRoute führt den Benutzer in fünf Schritten zum Ziel: Die Bestellliste wird als Excel-Datei aus einem Umfragetool, das der Verein bereits nutzt, bezogen. Die Applikation prüft die importierten Daten, meldet fehlerhafte Zeilen und lässt den Benutzer diese direkt in der Webapplikation korrigieren. Anschliessend werden die Adressdaten in Koordinaten umgewandelt. Dies ist nötig, damit sie später geografisch auf die gewünschte Anzahl Verteil-Teams aufgeteilt werden können und für jedes Team eine möglichst kurze Reihenfolge der einzelnen Stopps berechnet werden kann. Zum Schluss können zwei Dateien für jedes Team heruntergeladen werden: eine PDF-Lieferliste zum Ausdrucken, mit allen Stopps in der korrekten Reihenfolge inklusive Bestellmengen und Bemerkungen, und eine GPX-Datei, die sich in diversen Navigationsapps öffnen lässt.
Rahmenbedingungen
Die Applikation ist über eine öffentliche Adresse aufrufbar. Die Bestelldaten enthalten Namen und Adressen von Haushalten. Sie lassen sich nach dem Vorgang auf Knopfdruck vollständig löschen und bleiben nie im Browser zurück. Zusätzlich verursacht die Applikation keine laufenden Kosten, weil der Verein kein Budget dafür aufwenden möchte.
Kennzahlen
Getestet wurde die Applikation mit 200 Bestellungen. 99.5% dieser Adressen wurden korrekt in Koordinaten umgewandelt. Daraus entstanden vier verschiedene Routen mit 40, 53, 53 und 44 Stopps. Dies liegt innerhalb der konfigurierten Toleranz von 10%. Die Berechnung dauert dabei weniger als eine Sekunde.
Vier Phasen des Algorithmus
Der Algorithmus arbeitet in vier Phasen. Zuerst werden mit dem k-Means Verfahren alle Stopps geografisch auf die gegebene Anzahl Verteil-Teams aufgeteilt. Dabei entstehen verschiedene Gebiete, sogenannte Cluster. Weil diese Cluster aber verschieden gross ausfallen können, werden in der nächsten Phase die Randstopps so lange umverteilt, bis die verschiedenen Teams annähernd gleich ausgelastet sind. Danach wird für jedes Gebiet mit dem Nearest-Neighbor Verfahren eine erste Reihenfolge der Stopps berechnet. Das 2-opt Verfahren verkürzt diese danach weiter, indem es Teilstücke der Strecke umdreht und prüft, ob die Gesamtstrecke dadurch sinkt.
Die exakt kürzeste Route lässt sich jedoch nicht berechnen: Schon bei nur 25 Stopps gibt es mehr mögliche Reihenfolgen als Sterne im Weltall.
Technische Basis
Die Applikation ist als Fullstack-Webapplikation umgesetzt: React im Frontend, Node.js und Express im Backend und PostgreSQL als Datenbank. Die Adressen werden durch die Schnittstelle von geo.admin.ch in Koordinaten umgewandelt, für die Berechnung der Routen werden von der Schnittstelle OpenRouteService die Fahrdistanzen zwischen den Positionen bezogen. Betrieben wird die Applikation auf Render, die Datenbank auf Neon, beide in Frankfurt im kostenlosen Tarif. Die Architektur folgt einem Vier-Schichten-Modell.
Ausblick
Die Applikation ist funktionsfähig und öffentlich erreichbar. Der erste echte Einsatz an einer Zopfbackaktion steht erst noch bevor: Im Frühling 2027 wird sie zum ersten Mal produktiv genutzt.
Applikation: zobaroute.onrender.com
Quellcode: github.com/furrer-stefan/zobaroute
