Algorithmen die innerhalb weniger Minuten Planungen liefern
C#, SCIP, K-Means, 2-Opt, NearestNeighbour, Priority Queue
Innerhalb von maximal fünf Minuten erstellen unsere Algorithmen und Heuristiken aus den gegebenen Daten eine Tourenplanung, welche als Notfallplanung und nach Möglichkeit als Basis für die bereits bestehenden Algorithmen des Auftraggebers verwendet werden können. Die Algorithmen und Heuristiken müssen auch für Tage nach den Black Friday, an dem ein massiv höheres Paketvolumen besteht, innerhalb der fünf Minuten ein Resultat liefern. Das Resultat wird anhand der vom Auftraggeber gestellten Zielfunktion bewertet. Dabei geht es darum, dass möglichst viele Pakete in möglichst kurzer Arbeitszeit und gefahrener Distanz ausgeliefert werden. Mindestens ein Ansatz wird mit einem solver-basierten Ansatz umgesetzt.
Das Softwareunternehmen "Maison du Software" ist verantwortlich für die tägliche Generierung von Routenplänen zur Paketzustellung im Auftrag eines Logistikunternehmens. Eine Notfallplanung gibt es noch nicht, obwohl sie eine gewisse Planungssicherheit bieten würde, da bei Ausfall der bestehenden Systeme die Zustellung der Pakete ungewiss ist. Aufgrund der rapiden Zunahme des Paketvolumens ist eine Manuelle Planung nicht vorstellbar. Eine Möglichkeit schnell Planungen zu generieren gibt es bisher auch nicht.
Zur Bewältigung dieser Aufgabe wird die erforderliche Codebasis mit Beispieldaten von Szenarien zur Verfügung gestellt. Die Input-Daten werden aufbereitet und es wird eine Distanzmatrix der Zustellpunkte errechnet. Für die als Output definierte Tour kann ein Score (berechnet durch eine Ziel-funktion), diverse Kennzahlen und eine textuelle Übersicht ausgegeben werden.
Eine geografische Aufteilung des Problems in mehrere kleine Probleme mittels K-Means Algorithmus und einer anschliessenden Routenberechnung mittels einer Nearest Neighbour Heursitik hat über alle Probleme gesehen die besten Planungen errechnet. Für kleinere Probleme mit weniger als 3000 Paketen war eine Kombination der Nearest Neighbour Heursitik und anschliessender Optimierung der Routen mittels 2-Opt-Verfahren am geeignetsten.
Visualisierung einer Routenplaung:
Projekt 5, 2er Team
360 Personenstunden
20.02.2024 bis 16.08.2024
Maison du Software
Hardstrasse 223
CH-8005 Zürich
Lukas Wegmüller, Patrik Messerli
Simon Felix simon.felix@fhnw.ch
