Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Dit artikel presenteert een hybride divide-and-conquer-raamwerk dat de planning van rollend materieel herformuleert als een Maximum-Weight Independent Set-probleem en evalueert hoe het Quantum Approximate Optimization Algorithm (QAOA) presteert op zowel klassieke simulators als de IQM Emerald quantum device, waarbij wordt aangetoond dat het vergroten van de subgrafengrootte binnen deze aanpak effectief de kloof tussen benaderende en exacte oplossingsmethoden overbrugt.

De kern

Stel je voor dat je de conducteur bent van een enorm spoorwegbedrijf. Je hebt een dienstregeling met 190 specifieke treinritten die in twee dagen moeten plaatsvinden. Jouw taak is om uit te zoeken welke fysieke trein op welke rit rijdt.

Maar er zijn regels:

1. Onderhoud: Elke trein moet stoppen bij een specifkel station (zoals Hamburg) voor een controle van 2 uur om de paar duizend kilometer.
2. Continuïteit: Een trein kan niet magisch teleporteren; hij moet de ene rit voltooien en de volgende rit starten vanaf dezelfde locatie.
3. Kosten: Als een trein zonder passagiers moet rijden (een "lege rit") om bij zijn volgende opdracht te komen, kost dat geld (brandstof, slijtage). Je wilt deze lege kilometers minimaliseren.

Dit is het Rolling Stock Planning-probleem (planning van het rollend materieel). Het is een gigantische puzzel waarbij je treinen in lussen (cycli) moet passen die in dezelfde plaats beginnen en eindigen, waarbij aan de onderhoudsregels wordt voldaan en de kosten zo laag mogelijk blijven.

Het Probleem: Te Veel Mogelijkheden

Het aantal manieren waarop je deze treinen kunt arrangeren is astronomisch groot. Het is alsoruik een Sudoku-puzzel proberen op te lossen waarbij het rooster zo groot is als een voetbalveld en de regels constant veranderen. Zelfs de snelste supercomputers worstelen om een perfecte ordening te vinden voor een dienstregeling van deze omvang.

De Oplossing: Een Hybride "Verdeel en Heers"-Strategie

De auteurs stellen een slimme truc voor. In plaats van te proberen de hele enorme puzzel in één keer op te lossen, breken ze het op in kleinere, beheersbare stukken.

Denk aan het organiseren van een enorme bibliotheek. In plaats van te proberen elk boek ter wereld in één keer in de kast te zetten, doe je het volgende:

1. Kies een klein gedeelte van de bibliotheek.
2. Sorteer die boeken perfect.
3. Zet ze op de plank.
4. Ga naar het volgende gedeelte.

Ze noemen dit een Divide-and-Conquer-algoritme (verdeel-en-heers). Ze nemen het grote probleem, snijden er een klein stukje uit (een "subgraaf"), lossen dat stukje op en gaan dan verder.

Het Geheime Wapen: Quantumcomputers

Hier wordt het sciencefiction. Om die kleine stukjes op te lossen, gebruiken ze een combinatie van klassieke computers en een nieuw type computer genaamd een Quantumcomputer.

• De Klassieke Computer: Dit is als een zeer snelle, logische bibliothecaris. Hij kan kleine puzzels snel oplossen, maar loopt vast op enorme problemen.
• De Quantumcomputer (QAOA): Denk aan dit als een "super-intuïtieve" bibliothecaris. Hij kijkt niet slechts naar één pad tegelijk; hij verkent vele mogelijkheden tegelijkertijd. Hiervoor gebruikt hij een methode genaamd het Quantum Approximate Optimization Algorithm (QAOA).

De onderzoekers testten deze quantum-bibliothecaris op een echte quantummachine (genaamd IQM Emerald) en simuleerden het ook op een klassieke computer.

Hoe ze het hebben getest

De onderzoekers vergeleken drie manieren om die kleine puzzelstukjes op te lossen:

1. De Greedy Approach (Greedy-methode): Een eenvoudige, snelle methode die direct de "beste" optie kiest zonder vooruit te kijken. (Zoals de dichtstbijzijnde boeken kiezen zonder te controleren of ze wel in het juiste genre passen).
2. De Exact Solver (Exacte oplosser): Een trage, perfecte methode die elke mogelijke combinatie controleert om de absoluut beste oplossing te vinden.
3. De Quantum Solver (QAOA): De "intuïtieve" benadering die probeert om heel snel een zeer goede oplossing te vinden.

Wat zij ontdekten

1. Grotere stukken zijn beter: Wanneer ze de "kleine stukken" van de puzzel groter maakten, werd de algehele oplossing beter. Het is alsof je een hele gang met boeken tegelijk organiseert in plaats van alleen één plank; je ziet dan het grotere plaatje en kunt slimmere keuzes maken.
2. Quantum is veelbelovend: De quantum-oplosser (QAOA) presteerde bijna net zo goed als de trage, perfecte "Exact Solver", maar dan veel sneller. Hoewel de quantumcomputer nog klein en niet perfect is, liet het zien dat het in staat is om kwalitatief hoogwaardige oplossingen te vinden die zeer dicht bij de best mogelijke resultaten liggen.
3. De "Pruning"-stap: Soms geeft de quantumcomputer een rommelig antwoord (zoals suggereren dat twee treinen naar dezelfde plek gaan op hetzelfde moment). De auteurs gebruiken een "pruning"-tool (snoeien) om deze fouten op te schonen, waarbij ze de conflicten verwijderen om een geldige oplossing te maken.

De Kern van het Verhaal

Dit paper beweert niet dat quantumcomputers de wereldwijde spoorwegproblemen al hebben opgelost. In plaats daarvan tonen ze een routekaart.

Ze hebben bewezen dat door een massaal, onmogelijk probleem op te delen in kleinere stukken en vervolgens een quantumcomputer te gebruiken om die stukjes op te lossen, je zeer goede resultaten kunt behalen. Het is een brug tussen de trage, perfecte methoden uit het verleden en de snelle, krachtige methoden van de toekomst.

Kortom: ze namen een enorme, rommelige treinplanning, hakten deze in stukken, gebruikten een quantumcomputer om die kleine stukjes op te ruimen, en lieten zien dat deze hybride aanpak beter werkt dan simpelweg gokken of alleen klassieke computers gebruiken.

Technische samenvatting

Technische Samenvatting: Rolling Stock Planning met het Quantum Approximate Optimization Algorithm

Probleemdefinitie
Het artikel behandelt het Rolling Stock Planning probleem (planning van rollend materieel), een complexe optimalisatieuitdaging binnen het spoorwegbeheer. Het doel is om fysieke treinen toe te wijzen aan een geplande dienstregeling van ritten, waarbij operationele kosten, specifiek gedefinieerd als "lege kilometers" (afstand afgelegd zonder passagiers), worden geminimaliseerd. De overwogen probleeminstantie omvat 190 ritten over twee dagen verspreid over vijf stations, onderworpen aan strikte beperkingen:

• Cyclische Operatie: Elke trein moet een cyclus voltooien die terugkeert naar de startlocatie.
• Onderhoud: Elke cyclus moet een verplichte onderhoudsstop bevatten op een aangewezen station voor een vaste duur.
• Afstandslimieten: Cycli mogen een maximale afstand ($l_{max}$) niet overschrijden voordat onderhoud vereist is.
• Lege Ritten: Treinen mogen "lege ritten" (niet-geplande bewegingen) uitvoeren om geplande ritten te verbinden of onderhoudsstations te bereiken, wat kosten met zich meebrengt maar de haalbaarheid waarborgt.

De auteurs merken op dat hoewel het probleem beperkt is, zij geen netwerkcapaciteitsbeperkingen modelleren (zoals stationparkeerlimieten of routecongestie), uitgaande van onbeperkte capaciteit voor de omvang van deze studie.

Methodologie
De auteurs stellen een hybride quantum-klassiek divide-and-conquer algoritme voor om de computationele complexiteit van het probleem aan te pakken, die exponentieel schaalt met het aantal ritten.

1. Mapping naar Maximum-Weight Independent Set (MWIS):
   Het probleem wordt eerst geherformuleerd als een MWIS-probleem op een graaf.

• Knopen (Nodes): Vertegenwoordigen haalbare trein-cycli gegenereerd uit de dienstregeling.
• Randen (Edges): Verbinden knopen als de bijbehorende cycli wederzijds incompatibel zijn (bijv. ze bedienen beide dezelfde geplande rit).
• Gewichten (Weights): Toegewezen aan knopen op basis van een heuristische objectieve functie ($w_i = 2d_{full} - d_{empty}$), waarbij prioriteit wordt gegeven aan de dekking van passagiersritten boven pure kostenreductie.
• Doel: Vind een onafhankelijke verzameling (een set van niet-conflicterende cycli) met het maximale totale gewicht.

2. Strategie voor Cyclusgeneratie:
   Om de explosie van mogelijke cycli te beheersen, maken de auteurs gebruik van een tweemodus generatieproces:

• Modus 1: Genereert cycli met alleen geplande ritten (geen lege ritten).
• Modus 2: Geactiveerd wanneer het aantal niet-bediende ritten onder een drempelwaarde valt (40 ritten) of wanneer er geen verdere Modus 1-cycli gevormd kunnen worden. Deze modus staat lege ritten toe, wat de oplossingsruimte aanzienlijk vergroot om ervoor te zorgen dat alle resterende ritten gedekt kunnen worden.

3. Hybride Divide-and-Conquer Framework:
   Omdat de volledige MWIS-graaf te groot is voor huidige solvers, lost het algoritme iteratief kleinere subgrafen op:

• Selectie van Subgraaf: Een heuristiek selecteert een subgraaf van grootte $k$ (bijv. 20 tot 300 knopen). De selectiestrategie geeft prioriteit aan cycli die het hoogste aantal volledige ritten bedienen, waarbij een balans wordt gezocht tussen de kwaliteit van de oplossing en diversiteit.
• Oplossen van Subgraaf: Het MWIS-probleem op de geselecteerde subgraaf wordt opgelost met diverse methoden:
  • Klassieke Exacte Solver: Gebruikt als baseline.
  • Greedy Algoritme: Een klassieke baseline die knopen selecteert op basis van de gewicht-tot-graad ratio.
  • QAOA (Quantum Approximate Optimization Algorithm): Geïmplementeerd met diepte $p=1$ en $p=5$. Het probleem wordt gemapt naar een diagonale spin-glass Hamiltonian met een strafterm voor randovertredingen.
• Pruning (Snoeien): Omdat QAOA en random sampling ongeldige verzamelingen kunnen produceren (bevatten verbonden knopen), voert een pruning-procedure het proces uit waarbij knopen met de laagste gewicht-tot-graad ratio worden verwijderd totdat een geldige onafhankelijke verzameling is gevormd.
• Globale Update: Geselecteerde cycli worden toegevoegd aan de globale oplossing en conflicterende knopen worden verwijderd uit de globale graaf. Het proces herhaalt zich totdat alle ritten bediend zijn.

Belangrijkste Resultaten
De auteurs evalueerden het algoritme met behulp van klassieke simulatie en uitvoering op de IQM Emerald quantum device.

• Solver Vergelijking (Vaste Subgraafgrootte): Bij een kleine subgraafgrootte ($k=20$) was het prestatieverschil tussen het greedy algoritme, klassieke exacte solvers en QAOA ($p=1, p=5$) verwaarloosbaar. Echter, de resultaten toonden aan dat een hogere diepte QAOA ($p=5$) de neiging had om de kwaliteit van de oplossing van de exacte solver te benaderen, ondanks dat het een polynomiale-tijd algoritme is vergeleken met de exponentiële-tijd exacte solver.
• Impact van Subgraafgrootte: Een cruciale bevinding was de positieve correlatie tussen subgraafgrootte en oplossingkwaliteit. Naarmate de subgraafgrootte toenam (tot 300 knopen), nam het aantal lege kilometers significant af (negatieve helling met $p \approx 10^{-9}$). Dit suggereert dat het oplossen van grotere subproblemen leidt tot betere globale oplossingen, zelfs als de subgraaf-solver zelf benaderend is.
• Quantum Executie: Het artikel rapporteert resultaten van het draaien van $p=1$ QAOA op de IQM Emerald quantum computer, wat de haalbaarheid demonstreert van het uitvoeren van het algoritme op huidige hardware, hoewel de oplossingkwaliteit vergelijkbaar was met klassieke simulatie en random sampling voor de geteste parameters.

Betekenis en Claims
Het artikel positioneert het werk als een praktische route voor het toepassen van nabije-toekomst quantumcomputers op realistische industriële optimalisatieproblemen, voordat hardware in staat is de volledige problemen direct op te lossen.

• Overbruggen van de Kloof: Het hybride framework overbrugt effectief de kloof tussen snelle, benaderende polynomiale-tijd solvers (zoals greedy algoritmen) en trage, exacte exponentiële-tijd methoden.
• Schaalbaarheid: De auteurs stellen dat hun aanpak het mogelijk maakt om quantumalgoritmen toe te passen op subproblemen die compatibel zijn met de huidige hardwarebeperkingen, terwijl een klassieke buitenste lus de algehele optimalisatie regisseert.
• Potentieel voor Quantumvoordeel: De resultaten suggereren een scenario waarin de diepte van het QAOA-algoritme ($p$) slechts polynomiaal hoeft te groeien met de subgraafgrootte om ongeveer optimale oplossingen te bereiken, wat een potentieel quantumvoordeel biedt ten opzien van exacte klassieke methoden voor grootschalige instanties.
• Bescheidenheid: De auteurs erkennen beperkingen en merken op dat de huidige stap van cyclusgeneratie een bottleneck vormt voor grotere dienstregelingen en dat de effectiviteit van de pruning-procedure kan afnemen naarmate de subgraafgroottes toenemen. Zij beweren niet dat QAOA momenteel klassieke exacte solvers op het volledige probleem overtreft, maar dat de hybride architectuur het verkennen van grotere oplossingsruimtes mogelijk maakt dan voorheen mogelijk was met enkel quantumbronnen.