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.
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.
Durch das Verschieben von Buchung C kann Buchung N1 akzeptiert werden. Andernfalls hätte sie abgelehnt werden müssen.
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.
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.
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.
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.
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.
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.
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.
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.
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.
