Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Dieses Paper präsentiert ein hybrides Divide-and-Conquer-Framework, das die Rollmaterialplanung als Problem des maximalgewichtigen unabhängigen Knotens (Maximum-Weight Independent Set) umformuliert und den Quantum Approximate Optimization Algorithm (QAOA) sowohl auf klassischen Simulatoren als auch auf dem IQM Emerald Quantengerät evaluiert, wobei demonstriert wird, dass die Erhöhung der Subgraph-Größen innerhalb dieses Ansatzes effektiv die Lücke zwischen approximativen und exakten Lösungsmethoden schließt.

Das Wesentliche

Stellen Sie sich vor, Sie sind der Leiter eines riesigen Eisenbahnunternehmens. Sie haben einen Fahrplan mit 190 spezifischen Zugfahrten, die über zwei Tage stattfinden müssen. Ihre Aufgabe ist es, herauszufinden, welcher physische Zug welche Fahrt übernimmt.

Aber es gibt Regeln:

1. Wartung: Jeder Zug muss alle paar tausend Kilometer an einem bestimmten Bahnhof (wie zum Beispiel Hamburg) für eine zweistündige Überprüfung anhalten.
2. Kontinuität: Ein Zug kann nicht einfach magisch teleportieren; er muss eine Fahrt beenden und die nächste vom selben Bahnhof aus beginnen.
3. Kosten: Wenn ein Zug ohne Passagiere fahren muss (eine Leerfahrt), um zu seinem nächsten Einsatzort zu gelangen, kostet das Geld (Kraftstoff, Verschleiß). Sie wollen diese Leerkilometer minimieren.

Dies ist das Problem der Rollmaterialplanung. Es ist ein riesiges Puzzle, bei dem Sie Zugfahrten zu Kreisläufen (sogenannten „Cycles“) zusammenfügen müssen, die am selben Ort beginnen und enden, die Wartungsregeln einhalten und die geringsten Kosten verursachen.

Das Problem: Zu viele Möglichkeiten

Die Anzahl der Möglichkeiten, diese Züge anzuordnen, ist astronomisch groß. Es ist, als würde man versuchen, ein Sudoku-Rätsel zu lösen, bei dem das Spielfeld so groß wie ein Fußballfeld ist und sich die Regeln ständig ändern. Selbst die schnellsten Supercomputer haben Schwierigkeiten, eine perfekte Anordnung für einen so großen Fahrplan zu finden.

Die Lösung: Eine hybride „Teile-und-Herrsche“-Strategie

Die Autoren schlagen einen cleveren Trick vor. Anstatt zu versuchen, das ganze riesige Puzzle auf einmal zu lösen, zerlegen sie es in kleinere, handhabbare Stücke.

Stellen Sie sich vor, Sie organisieren eine riesige Bibliothek. Anstatt zu versuchen, alle Bücher der Welt auf einmal ins Regal zu stellen, gehen Sie so vor:

1. Sie wählen einen kleinen Abschnitt der Bibliothek aus.
2. Sie sortieren diese Bücher perfekt.
3. Sie stellen sie ins Regal.
4. Sie gehen zum nächsten Abschnitt über.

Sie nennen dies einen Divide-and-Conquer-Algorithmus (Teile-und-Herrsche-Algorithmus). Sie nehmen das große Problem, schneiden ein kleines Stück heraus (einen „Subgraphen“), lösen dieses Stück und machen dann weiter.

Die Geheimwaffe: Quantencomputer

Hier wird es Science-Fiction. Um diese kleinen Teile zu lösen, nutzen sie eine Mischung aus klassischen Computern und einer neuen Art von Computer, einem Quantencomputer.

• Der klassische Computer: Er ist wie ein sehr schneller, logischer Bibliothekar. Er kann kleine Rätsel schnell lösen, stößt aber bei riesigen Aufgaben an seine Grenzen.
• Der Quantencomputer (QAOA): Denken Sie an ihn als einen „super-intuitiven“ Bibliothekar. Er betrachtet nicht nur einen Pfad nach dem anderen; er erforscht viele Möglichkeiten gleichzeitig. Er verwendet eine Methode namens Quantum Approximate Optimization Algorithm (QAOA).

Die Forscher haben diesen Quanten-Bibliothekar auf einer echten Quantenmaschine (genannt IQM Emerald) getestet und ihn auch auf einem klassischen Computer simuliert.

Wie sie es getestet haben

Die Forscher verglichen drei Wege, um diese kleinen Puzzleteile zu lösen:

1. Der Greedy-Ansatz (Gieriger Ansatz): Eine einfache, schnelle Methode, die die im Moment am besten aussehende Option wählt, ohne vorauszuschauen. (Wie das Auswählen des nächstgelegenen Buches, ohne zu prüfen, ob es zum Genre passt).
2. Der exakte Solver (Exact Solver): Eine langsame, perfekte Methode, die jede einzelne Möglichkeit prüft, um die absolut beste Antwort zu finden.
3. Der Quanten-Solver (QAOA): Der „intuitive“ Ansatz, der versucht, sehr schnell eine sehr gute Antwort zu finden.

Was sie herausgefunden haben

1. Größere Stücke sind besser: Wenn sie die „kleinen Teile“ des Puzzles größer machten, wurde die Gesamtlösung besser. Es ist so, als würde man einen ganzen Gang an Büchern auf einmal organisieren statt nur eines einzelnen Regals – man kann das große Ganze besser sehen und klügere Entscheidungen treffen.
2. Quanten sind vielversprechend: Der Quanten-Solver (QAOA) schnitt fast so gut ab wie der perfekte, langsame „Exact Solver“, aber viel schneller. Obwohl der Quantencomputer noch klein und nicht perfekt ist, zeigte er, dass er qualitativ hochwertige Lösungen finden kann, die den bestmöglichen Antworten sehr nahe kommen.
3. Der „Pruning“-Schritt (Beschneidung): Manchmal liefert der Quantencomputer eine unordentliche Antwort (wie etwa den Vorschlag, dass zwei Züge gleichzeitig an denselben Ort fahren). Die Autoren nutzen ein „Pruning“-Werkzeug, um diese Fehler zu bereinigen und die Konflikte zu entfernen, um eine gültige Lösung zu erhalten.

Das Fazenz

Dieses Paper behauptet nicht, dass Quantencomputer die Eisenbahnprobleme der Welt bereits gelöst haben. Stattdessen zeigt es einen Fahrplan.

Sie haben bewiesen, dass man durch das Zerlegen eines massiven, unlösbaren Problems in kleinere Teile und die Nutzung eines Quantencomputers zur Lösung dieser Teile sehr gute Ergebnisse erzielen kann. Es ist eine Brücke zwischen den langsamen, perfekten Methoden der Vergangenheit und den schnellen, leistungsstarken Methoden der Zukunft.

Kurz gesagt: Sie haben einen riesigen, chaotischen Fahrplan genommen, ihn in Stücke geschnitten, einen Quantencomputer genutzt, um die kleinen Teile aufzuräumen, und gezeigt, dass dieser hybride Ansatz besser funktioniert als bloßes Raten oder die Verwendung von ausschließlich klassischen Computern.

Technische Zusammenfassung

Technisches Resümee: Rolling-Stock-Planung unter Verwendung des Quantum Approximate Optimization Algorithm

Problemdefinition
Die Arbeit befasst sich mit dem Problem der Rolling-Stock-Planung (Rollmaterialplanung), einer komplexen Optimierungsherausforderung im Eisenbahnmanagement. Das Ziel ist die Zuweisung physischer Züge zu einem geplanten Fahrplan von Fahrten unter Minimierung der Betriebskosten, die spezifisch als „Leerkilometer“ (ohne Fahrgäste zurückgelegte Distanz) definiert sind. Die betrachtete Probleminstanz umfasst 190 Fahrten über zwei Tage an fünf Stationen unter Einhaltung strenger Randbedingungen:

• Zyklischer Betrieb: Jeder Zug muss einen Zyklus abschließen, der ihn zur Ausgangsstation zurückführt.
• Wartung: Jeder Zyklus muss einen obligatorischen Wartungsstopp an einer bestimmten Station für eine feste Dauer enthalten.
• Distanzbeschränkungen: Zyklen dürfen vor der erforderlichen Wartung keine maximale Distanz ($l_{max}$) überschreiten.
• Leerfahrten: Züge dürfen „Leerfahrten“ (nicht geplante Bewegungen) absolvieren, um geplante Fahrten miteinander zu verbinden oder Wartungsstationen zu erreichen, was Kosten verursacht, aber die Durchführbarkeit sicherstellt.

Die Autoren merken an, dass das Problem zwar beschränkt ist, sie jedoch keine Kapazitätsbeschränkungen des Netzwerks (z. B. Parkplatzkapazitäten an Stationen oder Routenüberlastung) modellieren, da sie für den Umfang dieser Studie von einer unbegrenzten Kapazität ausgehen.

Methodik
Die Autoren schlagen einen hybriden quanten-klassischen Divide-and-Conquer-Algorithmus vor, um die rechnerische Komplexität des Problems anzugehen, die exponentiell mit der Anzahl der Fahrten skaliert.

1. Abbildung auf das Maximum-Weight Independent Set (MWIS):
   Das Problem wird zunächst als MWIS-Problem auf einem Graphen umformuliert.

• Knoten: Repräsentieren zulässige Zugzyklen, die aus dem Fahrplan generiert wurden.
• Kanten: Verbinden Knoten, wenn die entsprechenden Zyklen gegenseitig inkompatibel sind (d. h. beide dieselbe geplante Fahrt bedienen).
• Gewichte: Werden den Knoten basierend auf einer heuristischen Zielfunktion ($w_i = 2d_{full} - d_{empty}$) zugewiesen, wobei die Abdeckung von Fahrgastfahrten gegenüber der reinen Kostenreduktion priorisiert wird.
• Ziel: Ein unbelebtes Set (eine Menge nicht-konfliktierender Zyklen) mit dem maximalen Gesamtgewicht zu finden.

2. Strategie zur Zyklengenerierung:
   Um die Explosion der möglichen Zyklen zu bewältigen, verwenden die Autoren einen zweimodigen Generierungsprozess:

• Modus 1: Generiert Zyklen ausschließlich unter Verwendung geplanter Fahrten (keine Leerfahrten).
• Modus 2: Wird aktiviert, wenn die Anzahl der unbedienten Fahrten unter einen Schwellenwert (40 Fahrten) fällt oder keine weiteren Modus-1-Zyklen mehr gebildet werden können. Dieser Modus erlaubt Leerfahrten, wodurch der Lösungsraum signifikant erweitert wird, um sicherzustellen, dass alle verbleibenden Fahrten abgedeckt werden können.

3. Hybrider Divide-and-Conquer-Rahmen:
   Da der vollständige MWIS-Graph zu groß für aktuelle Solver ist, löst der Algorithmus iterativ kleinere Teilgraphen:

• Auswahl des Teilgraphen: Eine Heuristik wählt einen Teilgraphen der Größe $k$ (z. B. 20 bis 300 Knoten). Die Auswahlstrategie priorisiert Zyklen, die die höchste Anzahl an vollen Fahrten bedienen, um die Lösungsqualität mit der Diversität in Einklang zu bringen.
• Lösen des Teilgraphen: Das MWIS-Problem auf dem ausgewählten Teilgraphen wird mit verschiedenen Methoden gelöst:
  • Klassischer exakter Solver: Wird als Baseline verwendet.
  • Greedy-Algorithmus: Eine klassische Baseline, die Knoten basierend auf dem Verhältnis von Gewicht zu Grad auswählt.
  • QAOA (Quantum Approximate Optimization Algorithm): Implementiert mit Tiefe $p=1$ und $p=5$. Das Problem wird auf einen diagonalen Spin-Glass-Hamiltonian mit einem Strafterm für Kantenviolationen abgebildet.
• Pruning (Beschneidung): Da QAOA und Random Sampling potenziell ungültige Mengen (die verbundene Knoten enthalten) erzeugen können, entfernt ein Pruning-Verfahren Knoten mit den niedrigsten Gewicht-zu-Grad-Verhältnissen, bis eine gültige unabhängige Menge gebildet ist.
• Globale Aktualisierung: Ausgewählte Zyklen werden der globalen Lösung hinzugefügt und konfliktierende Knoten werden aus dem globalen Graphen entfernt. Der Prozess wiederholt sich, bis alle Fahrten bedient sind.

Wichtigste Ergebnisse
Die Autoren evaluierten den Algorithmus mittels klassischer Simulation und der Ausführung auf dem IQM Emerald Quantencomputer.

• Solver-Vergleich (Feste Teilgraphgröße): Bei einer kleinen Teilgraphgröße ($k=20$) war der Leistungsunterschied zwischen dem Greedy-Algorithmus, klassischen exakten Solvern und QAOA ($p=1, p=5$) vernachachlässigbar. Die Ergebnisse zeigten jedoch, dass eine höhere QAOA-Tiefe ($p=5$) dazu neigte, die Lösungsqualität des exakten Solvers zu erreichen, obwohl es sich um einen Algorithmus mit Polynomialzeit im Vergleich zum exponentiellen Zeitaufwand des exakten Solvers handelt.
• Einfluss der Teilgraphgröße: Eine entscheidende Erkenntnis war die positive Korrelation zwischen der Teilgraphgröße und der Lösungsqualität. Mit zunehmender Teilgraphgröße (bis zu 300 Knoten) sank die Anzahl der Leerkilometer signifikant (negativer Steigungswert mit $p \approx 10^{-9}$). Dies deutet darauf hin, dass das Lösen größerer Teilprobleme bessere globale Lösungen liefert, selbst wenn der Teilgraph-Solver selbst nur approximativ ist.
• Quantenausführung: Die Arbeit berichtet über Ergebnisse der Ausführung von $p=1$ QAOA auf dem IQM Emerald Quantencomputer und demonstriert die Machbarkeit der Ausführung des Algorithmus auf aktueller Hardware, wenngleich die Lösungsqualität für die getesteten Parameter mit der klassischen Simulation und dem Random Sampling vergleichbar war.

Bedeutung und Behauptungen
Die Arbeit positioniert ihre Arbeit als praktischen Weg, um near-term Quantencomputer auf realistische industrielle Optimierungsprobleme anzuwenden, bevor die Hardware in der Lage ist, das vollständige Problem direkt zu lösen.

• Überbrückung der Lücke: Der hybride Rahmen überbrückt effektiv die Lücke zwischen schnellen, approximativen Polynomialzeit-Solvern (wie Greedy-Algorithmen) und langsamen, exakten Exponentialzeit-Methoden.
• Skalierbarkeit: Die Autoren argumentieren, dass ihr Ansatz es ermöglicht, Quantenalgorithmen auf Teilprobleme anzuwenden, die mit den aktuellen Hardwarebeschränkungen kompatibel sind, während eine klassische äußere Schleife die Gesamtoptimierung steuert.
• Potenzial für Quantenvorteile: Die Ergebnisse deuten auf ein Szenario hin, in dem die Tiefe des QAOA-Algorithmus ($p$) nur polynomial mit der Teilgraphgröße wachsen muss, um annähernd optimale Lösungen zu erreichen, was einen potenziellen Quantenvorteil gegenüber exakten klassischen Methoden für groß angelegte Instanzen bietet.
• Bescheidenheit: Die Autoren räumen Einschränkungen ein und merken an, dass der aktuelle Schritt der Zyklengenerierung ein Engpass für größere Fahrpläne ist und dass die Effektivität des Pruning-Verfahrens mit zunehmender Teilgraphgröße abnehmen kann. Sie behaupten nicht, dass QAOA derzeit exakte klassische Solver für das gesamte Problem übertrifft, sondern dass die hybride Architektur die Exploration größerer Lösungsräume ermöglicht, als dies mit reinen Quantenressourcen möglich wäre.