Kombinatorische Optimierungsaufgabenstellungen sind durch eine Vielzahl von möglichen Lösungskombinationen charakterisiert und tauchen im Berufsalltag an vielseitigen Stellen auf.

Einerseits gibt es allgemeine Herausforderungen wie die Urlaubsplanung im Betrieb oder das Ausliefern von Waren, andererseits auch spezialisiertere Themen wie die optimalen Netzauslastung von Stromnetzen oder der effizienteste Produktionsablauf zur Herstellung von Waren. Durch mathematische Optimierung können dabei Kosten minimiert, die Effizienz gesteigert, und nicht zuletzt die Umwelt geschont werden, indem ressourcenschonend gearbeitet wird.

Urlaubszeiten-Berechnung für Kommunale Abfallwirtschaft
Nehmen wir dazu ein konkretes Beispiel, die Urlaubszeiten-Berechnung für eine kommunale Abfallwirtschaft. Ein Projekt, das wir bei Math.Tec realisiert haben.

Sie arbeiten in einem Unternehmen für kommunale Abfallwirtschaft einer mittleren Großstadt. Ihre Aufgabe ist, eine Urlaubsplanung für alle Mitarbeitenden im Außendienst zu erstellen. Sehr rasch bemerken Sie, dass diese Aufgabe aufgrund von einer großen Menge an limitierenden Faktoren zunehmend komplex wird. Die Urlaubsplanung soll dabei so erfolgen, dass immer eine funktionierende Einsatzgruppe erstellt werden kann: Die Mitarbeitenden im Außendienst sind entweder Fahrer:innen oder Aufleger:innen mit unterschiedlichen Quakifikationen. Zwei Fahrer:innen in eine Partie einzuteilen wäre nicht sinnvoll, ebenso wenig wie drei Aufleger:innen, die keinen LKW-Führerschein besitzen.
Womöglich sind noch weitere unterschiedliche Vorgaben zu berücksichtigen, maximale Urlaubszeiten lt. Vertrag, Schulferien etc. Wie schafft man es nun, die Komplexität in den Griff zu bekommen und bewertbare Ergebnisse zu erhalten?

Durch mathematische Optimierung …
Was ist Optimierung? Mathematisch gesehen ist es die Suche nach einem Minimum oder einem Maximum. Den schnellsten Weg finden (Problem des Handlungsreisenden) entspricht der Aufgabe, ein Minimum zu finden. Die meisten Artikel auf einer Palette zu verladen wiederum entspricht der Aufgabe, ein Maximum zu finden. Aus mathematischer Sicht steht dahinter jeweils eine Funktion, die einer Kurve entspricht, aus der sich ein gewünschtes Ergebnis ablesen lässt – man sucht bildlich gesprochen nach dem größten Funktionswert der Kurve, dem Maximum (Gipfel) oder dem kleinsten, dem Minimum (Tal).

… die Wirklichkeit mathematisch beschreiben
Die Herausforderung von Optimierungsprojekten in der Praxis besteht darin, die Wirklichkeit mit mathematischen Werkzeugen so nah wie möglich zu beschreiben. Wie kommt man aber zu einem mathematischen Abbild der Wirklichkeit?

Der Ablauf eines typischen Optimierungsprojekts gliedert sich in folgende Phasen:

1. Aufgabenstellung definieren
2. Rahmenbedingungen klären
3. Zieldefinition (Zielfunktion) vereinbaren
4. Math. Modellbildung durchführen
5. Geeignete Optimierungsalgorithmen auswählen
6. Optimale Lösung

Üblicherweise ist dies ein linearer Prozess – sollten sich im Laufe des Projekts die Parameter ändern (etwa: weitere limitierenden Faktoren werden ergänzt), ist der Ablauf iterativ.

Kombinatorische Optimierung in der Praxis
Kombinatorische Aufgabenstellungen wie das Problem des Handlungsreisenden sind durch eine große Anzahl von zulässigen Lösungen charakterisiert – Mathematiker sprechen von einem großen Lösungsraum, dem Zulässigkeitsbereich. Die Herausforderung besteht nun darin, ein spezielles, das „beste“ Ergebnis zu erhalten, z.B. den kürzesten oder schnellsten Weg zu finden, möglichst treibstoffsparend von A über B nach C zu gelangen.

Weitere beispielhafte Themenstellungen aus der Praxis:
– Travelling Salesman (Logistik, Lagerhaltung)
– Rucksack-Problem (Palettenbau, Rollcontainer)
– Produktionsoptimierung (Ressourcen-Zuweisung, Prozess-Sequenzierung)
– Scheduling (Einsatzplanung von Servicetechnikern)
– Betten-Belegung (Heime, Kliniken, Hotels)
– Stundenpläne (Schulen)
– Urlaubsplanung (Betriebe)

Kombinatorik und Quantencomputer
Der Quantencomputer hat bei kombinatorischen Problemen einen Vorteil: er kann alle Möglichkeiten parallel darstellen und Rechnungen auf ihnen gleichzeitig ausführen. Bei einem klassischen Computer ist das so nicht möglich – selbst die größten Supercomputer hätten nicht genug Speicherplatz um alle Möglichkeiten zu speichern. Die Schwierigkeit bei Quantencomputern ist es dabei jedoch, die richtige Lösung auszulesen.

Quantenoptimierungs-Algorithmen
Künftig könnten statt klassischer Optimierungsalgorithmen auch Quantencomputing Optimierungsalgorithmen, ausgeführt auf Quantencomputer in Verbindung mit klassischen Hochleistungsrechnern zum Einsatz kommen. Ein hybrider Ansatz also.

Interessante Quantencomputing-Optimierungsalgorithmen:

Hybrid bedeutet, beide Welten zu vereinigen – klassische Hochleistungsrechner und Quantencomputer. Diese Synergie bietet eine Vielzahl an Möglichkeiten: Der klassische Rechner kann zum Beispiel schwierige Teile einer größeren Rechnung zur Gänze an den Quantencomputer übergeben. Andererseits gibt es auch hybride Algorithmen (wie den QAOA und VQE), bei der der klassische Rechner und der Quantencomputer intensiv miteinander kommunizieren um eine Lösung zu berechnen.

Die Erforschung der Lösung von kombinatorischen Problemen auf Quantencomputern ist ein relativ neues Betätigungssfeld, das sich schnell weiterentwickelt. Wir sind mit dabei und bleiben dran. Rechnen Sie mit uns.