Diese Projektarbeit befasst sich mit Chläusen, die Familien besuchen. Familien haben gewisse Zeiten, an denen sie nicht besucht werden können und gewisse Wunschzeiten, an denen sie vorzugsweise besucht werden wollen. Es kommen mehrere Chläuse zum Einsatz, die an mehreren Tagen unterwegs sind. 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 besucht werden sollen, sodass die Kosten minimal werden. Das Problem wird in der Fachliteratur Vehicle Routing Problem with Time Windows genannt.
Im Rahmen dieser Projektarbeit wurden 4 neue Algorithmen implementiert und miteinander verglichen.
VRPTW, MILP, ILP, LocalSolver, Genetic Algorithm, Google OR Routing, C#
Das Optimierungsproblem für den Kunden zu lösen, sowie die Evaluation über die verschiedenen Lösungsansätze.
In einem Vorgängerprojekt wurde bereits eine Applikation entwickelt, die solche Routen für die Chläuse erstellen kann. Bei diesem Vorgängerprojekt kam ein Algorithmus zum Einsatz, der auf ganzzahliger linearer Programmierung basiert.
Aus der Evaluation geht hervor, dass, gemessen an der Zielfunktion, die neu entwickelten Ansätze bessere Routenpläne erzeugen als die von Hand erstellten. Die Erkenntnisse aus dieser Arbeit ermöglichen es der Chlausgesellschaft Kosten zu sparen. Es können der Arbeitsaufwand für die Planung und die Kosten für die Besuche reduziert werden. Es wird gezeigt, dass mittels optimierter Routen in den Jahren 2017 und 2018 insgesamt Einsparungen von 230 CHF hätten erzielt werden können, was 15.6% der Gesamtkosten der Besuche entspricht.
Jungwacht Niederwil, jw-niederwil.ch
Pascal Lüscher, Janik Meyer
