Unser Kunde organisiert im Rahmen von Veranstaltungen Meetings zwischen zwei Personengruppen, Investoren und Firmen. Typischerweise fragen Investoren Meetings mit Firmen an. Diese bestätigen dann die Anfrage und das Meeting kann geplant werden.
Herausforderung
Auf den ersten Blick wirkt das Problem einfach zu lösen:
- Ein Investor kann sich eine für ihn passende Zeit für das Meeting aussuchen. Wenn das Meeting dann freigegeben ist, wird es fixiert. In der Praxis ist es nicht so einfach: Nicht jedes Meeting wird akzeptiert. (Im Durchschnitt wird jedes zweite Meeting abgelehnt.) Das passiert nicht sofort, sondern oft erst Tage nachdem es angefragt wurde. Bis dahin müsste die Zeit für die Anfrage aber freigehalten werden.
- Wenn der Investor die Zeit für das Meeting frei wählen kann, dann bleiben oft unbequeme Randzeiten frei. Für Firmen bedeutet dass deutlich weniger Meetings als eigentlich möglich.
- Oft gibt es nicht so viele Räumen wie Firmen, somit müssen auch Räume geblockt werden, bis Anfragen akzeptiert würden.
Ziel ist es also, für die Firmen möglichst viele Meetings zu organisieren und so deren Zeit so effizient wie möglich zu nutzen. Auch die vorhandenen Räume sollten möglichst gut genutzt werden.
Lösung
Wir haben deshalb mit dem Kunden zusammen folgende Lösung erarbeitet:
- Statt dass direkt Zeiten für Meetings festgelegt werden, können Firmen und Investoren Zeiten definieren, zu denen sie verfügbar sind.
- Anfragen werden erfasst und von Firmen bestätigt oder abgelehnt.
- Erst nach Bestätigung der Anfragen werden entweder sofort, einmal täglich, oder auch manuell für die Anfragen mögliche Zeiten und verfügbare Räume ausgewählt und diese als Meetings festgeschrieben. Dieser Prozess findet asynchron statt, es müssen also weder Firmen noch Investoren darauf warten. Somit sind auch komplexe Berechnungen möglich.
Für die Meeting-Planung wird ein genetischer Algorithmus verwendet. Dieser beginnt mit zufällig gewählten Zeiten und Räumen und verbessert diese in Iterationen. Die Qualität eines Plans wird beispielsweise von folgenden Faktoren beeinflusst:
- Offensichtlich dürfen Firmen und Investoren keine parallelen Meetings haben und der gewählte Raum darf nicht belegt sein.
- Ebenso muss die gewählte Zeit in der Verfügbarkeit des Investors und der Firma liegen.
- Firmen sollten zwischen zwei Meetings nach Möglichkeit den Raum nicht wechseln müssen.
- Für Firmen sollten zwischen zwei Meetings definierte Pausen (oder auch nach Möglichkeit keine Pause) haben. Es sollten Meetings möglichst ohne Leerlauf geplant werden.
Im Lauf der Zeit haben sich noch mehr Optimierungsmöglichkeiten gezeigt, die ohne Probleme auch berücksichtigt werden können.
Technische Umsetzung
Die Software für Firmen, Investoren, und auch die Administrationsoberfläche sind als Webanwendungen mit PHP und MySQL umgesetzt worden. Für den genetischen Algorithmus, den Kern der Meeting-Planung, haben wir keine passende Bibliothek für PHP gefunden und haben deshalb unsere eigene Implementierung geschrieben.
Unsere Bibliothek folgt natürlich den Prinzipien der objektorientierten Programmierung. Aktuell ist für die eigentliche Optimierung ein Algorithmus, der sich an NSGA-II orientiert, implementiert. Er kann entweder eine oder mehrere Zielfunktionen (Objectives) berücksichtigen. Als Beispiele wurde eine Wegesuche mit Hindernissen und ein offline-Aktien-Broker implementiert.
Sehr gerne helfen wir Ihnen bei Ihrem (mehrdimensionalen) Optimierungsproblem. Wir verfügen über die notwendige Erfahrung, um mit Ihnen schnell zu effizienten und zufriedenstellenden Lösungen zu kommen.