Unser Projekt befasst sich mit Chläusen, die Familien besuchen. Familien haben gewisse Tage, an denen sie nicht besucht werden können und gewisse Wunschzeiten, an denen sie bevorzugt besucht werden wollen. Es kommen mehrere Chläuse zum Einsatz. Jeder Chlaus hat pro Tag nur eine beschränkte Kapazität. Die Frage ist, wann und in welcher Reihenfolge die Familien von den Chläusen optimal besucht wird. Das Problem wird in der Fachliteratur Vehicle Routing Problem with Time Windows genannt.
Im Rahmen unserer Arbeit lösen wird das oben genannte Problem mit ganzzahliger linearer Programmierung. Der ganze Algorithmus ist dabei in zwei Teile getrennt. Zuerst wird ein Clustering gemacht und anschliessend werden die einzelnen Cluster mit dem Scheduling geplant.
ILP, VRPTW, Samichlaus
Entwicklung einer Webapplikation welche:
Die Jungwacht Niederwil sorgt jedes Jahr dafür, dass in Niederwil und Nesselnbach der Samichlaus kommt. Die Familien können sich entweder auf der Webseite oder via schriftlichem Formular anmelden. Bei der Anmeldung können Terminwünsche geäussert werden. Nach Anmeldeschluss treffen sich die Organisatoren der Chlausgesellschaft und planen einen Abend lang. Dabei werden alle Anmeldungen nach bestem Wissen den Chläusen zugeteilt. Die Chläuse erstellen dann eine individuelle Routenplanung. Diese Aufteilung und Routenplanung wird aber je länger je komplizierter. Grund dafür sind die steigenden Anmeldungen und die zunehmend fehlende Flexibilität der Familien. Zusätzlich verlangt es den Chläusen viel Wissen und Erfahrung ab, ihre Routen zu planen.
Das oben beschriebene Problem ist in der Fachliteratur unter dem Namen Vehicle Routing Problem with Time Windows (kurz VRPTW) bekannt. Das Vehicle Routing Problem with Time Windows ist eine Erweiterung des Vehicle Routing Problem (kurz VRP). Einfach gesagt befasst sich das VRP mit einer Flotte von Fahrzeugen, welche Güter aus einem zentralen Depot zu Kunde liefern soll. Bei der Erweiterung mit Time Windows besteht die Einschränkung darin, dass Kunden nur in einem bestimmten Zeitfenster besucht werden dürfen. Die Kunden sind in unserem Fall die Familien, welche von einem Chlaus besucht werden. Dementsprechend wird die Fahrzeugflotte durch die Chläuse repräsentiert. Beide genannten Probleme gehören zur Klasse der NP-schweren Probleme.
Das Ergebnis unserer Arbeit ist eine Webapplikation, welche zur Erfassung der Besuchsdaten und zum starten des Algorithmus verwendet wird. Der Algorithmus optimiert auf drei verschiedene Kennzahlen und gibt Routen aus. Diese Routen können mittels Vergleichsfunktion auf der Webseite von einem Menschen verglichen werden. So wird zum Schluss eine Entscheidung von einem Menschen nötig, um auszuwählen welche Route man tatsächlich läuft. Die Routen des Algorithmus können mit der manuell erstellten Route aus der Vergangenheit mithalten. Die automatisch erstellten Routen sind nicht generell schlechter oder besser. Es ist vielmehr so, dass die berechneten Routen in ihren zu optimierenden Kennzahlen besser sind und in den anderen tendenziell schlechter.
Projektdauer: Frühlingsemester 2018
Aufwand: 360 Personenstunden
Teamgrösse: 2
Jungwacht Niederwil, jw-niederwil.ch
Pascal Lüscher, Janik Meyer
