Optimierte Fahrzeugbelegung im Carsharing

Heutzutage sind umweltfreundlichere und günstigere Transportlösungen gefragt. Eine Idee ist, Fahrräder, Fahrzeuge und andere Transportmittel zu teilen. Unser Projektpartner cambio bietet dies in Form von Carsharing an. Man hat die Möglichkeit, Fahrzeuge für bestimmte Zeiträume an unterschiedlichen Standorten zu reservieren. Sollten alle Reservierungen im Vorfeld bekannt sein, wäre es leicht ein optimales Ergebnis hinsichtlich der Verteilung der Buchungen zu erzielen. Unsere Aufgabe besteht darin eingehende Anfragen zu behandeln, ohne zukünftige Buchungen zu kennen und dabei das bestmögliche Ergebnis zu erzielen.

Ausgangslage

Die neue Buchung N1 passt nicht auf Anhieb, daher muss umarrangiert werden. Buchung B und C sind kompatibel - heißt sie überlappen sich nicht - daher kann Buchung C verschoben werden.

Endergebnis

Durch das Verschieben von Buchung C kann Buchung N1 akzeptiert werden. Andernfalls hätte sie abgelehnt werden müssen.

Online-Problem

Bei dem Online-Problem muss sofort entschieden werden, ob ein Buchungswunsch angenommen werden kann oder nicht. Der darauffolgende Buchungswunsch ist noch unbekannt und wird bei der Entscheidung nicht berücksichtigt.

Offline-Problem

Bei dem Offline-Problem sind alle Buchungswünsche bereits bekannt. Das System kann nun anhand bestimmter Kriterien einen optimalen Buchungsplan erstellen. Dabei kann z. B. nach dem Kriterium Max. Buchungsanzahl optimiert werden, bei welchem möglichst viele Buchungen akzeptiert werden.

Architektur

Die Software basiert auf dem Entwicklungsmuster Model View Controller. Das Model umfasst die interne Anwendungslogik. Die View stellt die Funktionalitäten der Visualisierung bereit. Der Controller stellt das Steuerelement zwischen dem Model und der View dar. Das Programm stellt eine Sever-Client-Architektur dar. Der Client dient zur Visualisierung und zur Interaktion des Benutzers. Der Server führt die entwickelten Algorithmen aus und ist manipuliert die Datenbank.

Algorithmen

Es wurden verschiedene Ansätze zur Lösung des Problems gefunden. Diese lassen sich grob in Greedy-, Best-Fit-, und Weighted Algorithmen unterscheiden. Während der Greedy-Ansatz in jedem Schritt aufs Neue versucht eine Buchung durch Sortieren und Einfügen zu buchen versucht der Best-Fit-Ansatz Lücken in der bestehenden Buchungskonfiguration zu finden. Der gewichtete Ansatz priorisiert Buchungen mit möglichst hohem Gewicht und versucht anhand dessen eine neue Buchung zu akzeptieren. Als Benchmark für die Algorithmen wurden zwei ILP`s (Integer Linear Programming) entwickelt, die jeweils eine optimale Lösung zur Maximierung der Gesamtbuchungszeit oder zur Maximierung der Buchungsanzahl ausgeben.

Vergleichbarkeit

Es musste sichergestellt werden, dass sowohl Eingangs- als auch Ausgangsdaten bei jedem Algorithmus die gleiche Form haben. Das wurde durch vereinheitlichte Eingabemethoden, eine standardisierte Ausgabemaske und einheitliche Zeitintervalle gewährleistet.

Datenbasis

Die der Eingabemethode zugrunde liegenden Daten basieren einerseits auf realen Buchungen der Carsharing Dienstleister Cambio und Flinkster und andererseits auf künstlich erzeugten randomisierten Daten.

Visualisierung

Um die fertigen Buchungspläne visuell darzustellen, wurde im Projekt eine grafische Anwendung entwickelt. Mit dieser lässt sich der komplette Buchungsablauf der verschiedenen Algorithmen grafisch nachvollziehen. Zudem kann man sich schnell einen Überblick darüber verschaffen, wie viele Buchungen auf welches Auto gebucht wurden.

Screenshot von GUI

Außerdem verfügt die grafische Anwendung auch über eine Auswertungsfunktion, die nützliche Statistiken generiert. Dabei kann man erfahren, wie viele Buchungen die verschiedenen Algorithmen angenommen haben und wie hoch die Auslastung einzelner Autos ist.

Screenshot von GUI Statistik

Evaluation

Die Ergebnisse der verschiedenen Algorithmen wurden zum Projektende ausgewertet und verglichen. In einem Liniendiagramm wurden die Endergebnisse gegenübergestellt. Dabei ist der Input die Gesamtanzahl aller Buchungswünsche, welche gestellt wurden. Das Ergebnis ILPMaxBuchungen (Zielfunktion: maximale Buchungsanzahl) stellt die höchste Anzahl von Buchungen dar.

Liniendiagramm Buchungsanzahl

Potential

Um das Problem noch weiter der Realität anzunähern, gibt es hinreichende Möglichkeiten:
  • Implementierung verschiedener Wagenklassen und Wagenausstattung (z. B. Navigationssystem, Freisprecheinrichtung etc.)
  • Wechselnde Anzahl verfügbarer Fahrzeuge an einer Station
  • Berücksichtigung weiterer Nebenbedingungen beim Buchen (z. B. Fahrzeug defekt, noch nicht zurückgegeben)
  • Kombination verschiedener Algorithmen zur weiteren Prüfung, ob Buchungen berücksichtigt werden können
  • Ausweichmöglichkeit auf benachbarte Stationen
Projektteilnehmer: Marcel Brannahl • Christian Klapproth • Anita Klassen • Matthias Köhne • Kai Krause • Patrick Lewandowski • Yeliz Sandici