SpeedDating: Fallstudie Matching+Scheduling

Wird bearbeitet von: Ben Strasser
Betreuung durch: Prof. Dr. Bastian Katz, Dr. Ignaz Rutter

Zu Speed-Dating-Events werden üblicherweise nur so viele Teilnehmer (bis etwa 2×10 oder 1×10 für gemischt/gleichgeschlechtliche Paarungen) eingeladen, dass in der geplanten Anzahl Runden jeder Teilnehmer mit jedem potentiellen Partner ein „Date“ hat. Bei einer neuartigen Form des Speed-Dating sollen dagegen eine deutlich größere Zahl an Teilnehmern zugelassen werden, und aus der Menge der Möglichen Dates eine möglichst gute ausgewählt werden. Dazu müssen sich alle Teilnehmer vorab anmelden; alle möglichen Paarungen werden dann (ebenfalls vorab) bewertet, einige sogar völlig ausgeschlossen. Um dann beim Event eine vorgegebene Menge von Zeitslots optimal auszunutzen, soll auf Basis der vorab erhobenen Bewertungsmatrix für die erschienenen Teilnehmer ein möglichst guter Zeitplan für eine vorgegebene Anzahl T von Zeitslots erstellt werden.

Die Kriterien für einen guten Zeitplan sind die folgenden:

1. Der Zeitplan ist gültig: In jedem Slot hat jeder Teilnehmer maximal ein Date.
2. Es finden nur Dates statt, die nicht ausgeschlossen wurden, und jedes Date findet maximal einmal statt.
3. Sofern möglich weicht die Anzahl der Dates pro Teilnehmer um weniger als 1 von der idealen Zahl ab, d. h. bei gemischtgeschlechtlichen Events mit $m$ Männern und $f$ Frauen mit oBdA $f\leq m$ hat jede Frau $T$ Dates und jeder Mann zwischen $\lfloor T\cdot f/m\rfloor$ und $\lceil T\cdot f/m\rceil$. Bei gleichgeschlechtlichen Events mit $n$ Teilnehmern hat jeder Teilnehmer bei ungeradem $n$ zwischen $T$ und $T-1$ Dates, bei gerader Anzahl genau $T$ Dates. Falls das nicht möglich ist, gibt es nur Abweichungen nach unten, und die sind minimal (in der Summe oder in der größten Abweichung).
4. Die Summe der Bewertungen der eingeplanten Dates wird unter Berücksichtigung der Kriterien 1 und 2 maximiert.

In einem solchen Zeitplan sollte auch der berücksichtigt werden, an welchem Tisch welches Date stattfinden soll. Dabei kann davon ausgegangen werden, dass bei gemischtgeschlechtlichen Paarungen mindestens so viele Tische wie Frauen zur Verfügung stehen und bei gleichgeschlechtlichen Paarungen mindestens halb so viele Tische wie Teilnehmer. Kriterien an eine Zuordnung der Dates sind folgende:

1. An jedem Tisch findet zu jedem Zeitpunkt maximal ein Date statt.
2. Bei gemischtgeschlechtlichen Events sollen die Frauen einen festen Tisch zugewiesen bekommen.

Zusätzlich steht eine Entfernungsmatrix der Tische zur Verfügung, damit ein Zeitplan anhand der nötigen Laufwege bewertet werden kann.

Entwurf und Implementierung einer effizienten Zeitplanerstellung für gemischt- und gleichgeschlechtliche Dating-Events in C++, zum Teil auf Basis vorhandener und quelloffener Bibliotheken. Die Zeitpläne müssen alle obigen Kriterien berücksichtigen. Laufwege sollten ausgewertet, müssen aber nicht optimiert werden. Die Implementierung kann Heuristiken zur Minimierung der Laufwege enthalten. Die Implementierung muss unter der GPL veröffentlicht werden. Im Rahmen der Studienarbeit sollten die verwendeten Modellierungen, Reduktionen und Algorithmen dokumentiert, sowie das tatsächliche Laufzeitverhalten evaluiert werden. Sofern nötig sollten dafür einfache Modelle für die Generierung von Eingabewerten beschrieben werden.

Optional kann die Qualität nicht-optimaler Lösungen mit Lösungen aus ILP-Modellierungen verglichen werden. Optional können verschiedene Heuristiken zur Verbesserung der Laufwege evaluiert werden.