EMU circulation planning for Silesian Railways: case study and a quantum approach

Dit artikel presenteert een casestudy over de dagelijkse planning van de circulatie van elektrische treinstellen (EMU) voor de Silesian Railways, waarbij een hoogwaardige klassieke mixed-integer linear programming oplossing wordt vergeleken met quantum- en quantum-geïnspireerde benaderingen om de huidige beperkingen en het potentieel van QUBO-gebaseerde methoden voor realistische spoorwegoptimalisatie aan te tonen.

De kern

Stel je voor dat je de dirigent bent van een enorm, druk orkest, maar in plaats van violen en drums zijn je instrumenten elektrische treinen. Jouw taak is om ervoor te zorgen dat elke trein een bestuurder heeft, genoeg zitplaatsen voor passagiers en genoeg ruimte voor hun fietsen, terwijl je er ook voor zorgt dat de treinen aan het einde van de dag weer terugkeren in hun "garages" (depots), klaar voor de volgende dag.

Dit artikel is een casestudy over het oplossen van deze puzzel voor de Silesian Railways in Polen. De onderzoekers probeerden twee verschillende manieren om dit op te lossen: de ouderwetse, betrouwbare manier (Klassieke Wiskunde) en de futuristische, experimentele manier (Quantum Computing).

Hier is de uitsplitsing van hun reis:

1. Het Probleem: De Treinpuzzel

De spoorwegexploitant moet het dagelijkse schema voor honderden treinen plannen. Het is niet alleen een kwestie van een trein kiezen voor een route; het is een complex spelletje Tetris met extra regels:

• Koppelen: Soms kunnen twee identieke treinen aan elkaar worden gehaakt (zoals treinwagons) om een grotere trein te maken voor drukke routes.
• Fietsen: Ze moeten ervoor zorgen dat er genoeg ruimte is voor de fietsen van passagiers.
• Bestuurders: Ze kunnen niet meer treinen toewijzen dan er op een specifiek moment beschikbare bestuurders zijn.
• Garagebalans: Elke dag moet een bepa certain aantal treinen in specifieke depots beginnen en eindigen.

2. De "Ouderwetse" Oplossing: De Meesterkok (ILP)

Eerst bouwde het team een Klassiek Wiskundig Model (een Integer Linear Program of ILP).

• De Analogie: Denk aan een superintelligente, hypergeorganiseerde chef die een receptenboek heeft voor elke mogelijke manier om de treinen te arrangeren. De chef controleert elke mogelijkheid tegen de regels (bestuurders, fietsen, koppelen) om het perfecte, goedkoopste schema te vinden.
• Het Resultaat: Deze methode werkte vlekkeloos. Zelfs met 404 treinritten en 11 verschillende soorten treinen, loste de computer de volledige dagplanning in minder dan 40 minuten op. Het vond elke keer het beste mogelijke plan.

3. De "Futuristische" Oplossing: De Quantum Dobbelsteenworp (QUBO)

Vervolgens probeerde het team dit probleem te vertalen naar een formaat dat Quantumcomputers (specifiek D-Wave machines) en "Quantum-geïnspireerde" software zouden kunnen begrijpen. Ze veranderden de treinregels in een QUBO (Quadratic Unconstrained Binary Optimization) probleem.

• De Analogie: Stel je voor dat je, in plaats van een chef die één voor één recepten controleert, een magische dobbelsteenwerper hebt die de beste arrangement probeert te vinden door de "energie" van het systeem te "voelen". Als de arrangement slecht is (bijv. niet genoeg ruimte voor fietsen), voelt het "heet" (hoge energie). Als het goed is, voelt het "koud" (lage energie). Het doel is om de koudste staat te vinden.
• De Haken en ogen: Om de quantumcomputer de regels te laten begrijpen, moesten de onderzoekers "straf"-gewichten toevoegen. Dit deed het probleem in omvang exploderen.
  • De "Explosie": Terwijl het klassieke model een beheersbaar aantal variabelen had, moest de quantumversie rekening houden met miljoenen interacties tussen hen. Het was alsof je een hele oceaan in een theekopje probeerde te passen.

4. De Confrontatie: Wie Won Er?

De onderzoekers testten beide methoden met echte gegevens van de spoorwegen.

• De Klassieke Chef (ILP): Won gemakkelijk. Het hanteerde de grote, rommelige, echte schema's snel en vond het perfecte antwoord.
• De Quantum Dobbelsteen (D-Wave): Kon alleen de kleine versies van het probleem oplossen (zoals een speelgoedvoorbeeld met slechts 3 treinen). Toen ze probeerden een middelgroot schema in te voeren, was het geheugen (qubits) van de computer niet groot genoeg om de puzzel te bevatten. Het was alsof je een puzzel van 1.000 stukjes probeert op te lossen met slechts 10 puzzelstukjes.
• De Quantum-Geïnspireerde Solver (VeloxQ): Dit is een klassieke computer die doet alsoos quantum. Het presteerde beter dan de echte quantumcomputer en kon iets grotere problemen oplossen, maar liep nog steeds tegen een muur aan wanneer het probleem te groot werd. Het kon de "kaart" van het probleem niet snel genoeg genereren.

5. De Kern van het Verhaal

Het artikel concludeert dat voor de huidige treinplanning:

• Blijf bij de Klassieke Chef: De traditionele wiskundige methode is snel, betrouwbaar en klaar voor gebruik in de echte wereld.
• Quantum is nog steeds een "Speelgoed": Huidige quantumcomputers zijn te klein en de wiskunde die nodig is om het probleem te vertalen is te zwaar. Ze kunnen alleen zeer kleine, vereenvoudigde versies van de puzzel oplossen.

Het Toekomstige Idee:
De auteurs suggereren een Hybride Aanpak voor de toekomst. Stel je voor dat je de Klassieke Chef gebruikt om de hele dag te plannen, maar vervolgens de Quantum Dobbelsteen gebruikt om snel een paar specifieke, lastige plekken te controleren (zoals een druk station waar treinen moeten koppelen en ontkoppelen) om te zien of er een iets betere manier is om precies die paar treinen te arrangeren.

Kortom: De onderzoekers hebben bewezen dat hoewel quantum computing opwindend is, voor het plannen van treinroosters op dit moment de ouderwetse supercomputer-wiskunde nog steeds de koning is. De quantum-aanpak is een veelbelovende sidekick, maar is nog niet klaar om de leiding te nemen.

Technische samenvatting

Technische Samenvatting: EMU-circulatieplanning voor de Spoorwegen van Silezië

Probleemdefinitie

Het artikel behandelt het dagelijkse rollendmaterieel-circulatieprobleem voor elektrische treinstellen (EMU's) op het regionale passagiersnetwerk van de Spoorwegen van Silezië (Koleje Śląskie) in Polen. Het doel is om beschikbare EMU's toe te wijzen aan een vaste dienstregeling van treinritten, terwijl een complexe set operationele beperkingen wordt nageleefd.

De belangrijkste kenmerken van het probleem zijn:

• Flexibele Samenstellingen: EMU's van hetzelfde type kunnen op een vooraf gedefinieerde subset van ritten in paren worden gekoppeld om de capaciteit te vergroten, terwijl andere ritten door enkelvoudige eenheden moeten worden uitgevoerd.
• Vraaggestuurde Capaciteit: Het model incorporeert expliciet beperkingen voor zowel passagierszitcapaciteit als fietsenopslagcapaciteit, waarbij wordt gewaarborgd dat tekorten de toegestane limieten niet overschrijden.
• Depotbalans: Het plan moet voldoen aan de onder- en bovengrenzen voor het aantal startende en eindigende EMU's van elk type bij specifieke depots, om de operationele reserves te handhaven.
• Beschikbaarheid van Personeel: Geaggregeerde beperkingen beperken het aantal gelijktijdig operationele EMU's op basis van de beschikbaarheid van geschikte bestuurders bij specifieke depots en tijdstippen.
• Acyclische Horizon: De planningshorizon is een enkele dag, wat resulteert in een acyclische circulatiestructuur, in tegenstelling tot cyclische wekelijkse planningsmodellen.

Methodologie

De auteurs stellen een duale methodologie voor, waarbij een klassieke Integer Linear Programming (ILP) formulering wordt vergeleken met een Quadratic Unconstrained Binary Optimization (QUBO) herformulering.

1. Graaf/Hypergraaf Representatie

Het probleem wordt gemodelleerd met behulp van een tijd-geëxpandeerde graaf waarbij:

• Knopen treinritten en hulp-depotdienstgebeurtenissen vertegenwoordigen.
• Bogen de haalbare transities van een enkele EMU tussen ritten vertegenwoordigen.
• Hyperbogen transities vertegenwoordigen die betrekking hebben op gekoppelde EMU's (koppelen, gekoppelde transfer en ontkoppelen).
  Deze hypergraaf-formulering vangt de combinatorische complexiteit van flexibele treincomposities op natuurlijke wijze op.

2. Klassieke ILP Benadering

Het probleem wordt gecodeerd als een Mixed-Integer Linear Program (MILP) en opgelost met de SCIP solver.

• Doelstelling: Minimaliseert een gewogen som van operationele kosten (vaste en afstandsafhankelijke kosten) en het aantal ingezette EMU's (om reservevloten te sparen).
• Beperkingen: Omvat dekking (elke rit wordt precies één keer bediend), flow-balans (continuïteit van rollend materieel), depotbalans, capaciteitslimieten (zitplaatsen/fietsen) en de beschikbaarheid van personeel.
• Schaalbaarheid: Het aantal binaire variabelen schaalt ruwweg met $|T| \cdot |T|^2 \cdot |R|$ in het slechtste geval, waarbij $|T|$ het aantal ritten is en $|R|$ het aantal EMU-typen, hoewel praktische beperkingen dit aanzienlijk verminderen.

3. Quantum en Quantum-geïnspireerde Benadering (QUBO)

De ILP wordt geherformuleerd naar een QUBO-probleem om gebruik te maken van quantum annealing en natuurkundig geïnspireerde heuristieken.

• Transformatie: Beperkingen worden omgezet in straftermen (penalty terms) die worden toegevoegd aan de doelstelling. Slack-variabelen worden geïntroduceerd om ongelijkheidsbeperkingen (bijv. depotlimieten, personeelsbeschikbaarheid) af te handelen.
• Solvers:
  • Quantum Annealing: Uitgevoerd op D-Wave Advantage systemen (zowel Pegasus als Zephyr topologieën).
  • Quantum-geïnspireerd: Uitgevoerd met VeloxQ, een klassieke solver gebaseerd op natuurkundig geïnspireerde heuristieken (simulated bifurcation/energy minimization) die geen quantumhardware vereist.
• Schaalbaarheid: De QUBO-formulering introduceert een aanzienlijke overhead in het aantal kwadratische termen, wat schaalt als $|T|^5$ in het slechtste geval, wat een bottleneck creëert voor modelgeneratie en opslag nog voordat de oplossing begint.

Belangrijkste Bijdragen

1. Praktisch ILP Model: Ontwikkeling van een flexibel, direct oplosbaar ILP-model dat specifieke eisen van de exploitant integreert: parenwijze koppeling beperkt tot vooraf gedefinieerde ritten, expliciete fietscapaciteitsbeperkingen en geaggregeerde personeelslimieten.
2. QUBO Mapping: Een specifieke herformulering van het circulatieprobleem van rollend materieel naar QUBO, inclus\u2019 een analyse van de schaling van variabelen en termen, waarbij de snelle groei van kwadratische interacties wordt benadrukt.
3. Empirische Benchmarking: Een vergelijkende studie met echte data van de Spoorwegen van Silezië (tot 404 ritten en 11 EMU-typen) waarbij wordt geëvalueerd:
   • Klassieke ILP (SCIP).
   • Quantum Annealing (D-Wave hardware).
   • Quantum-geïnspireerde Heuristieken (VeloxQ).
4. Haalbaarheidsanalyse: Identificatie van de huidige praktische grens voor QUBO-gebaseerde methoden in spoorwegplanning, specifiek met betrekking tot de afweging tussen modelexpressiviteit en computationele hanteerbaarheid.

Experimentele Resultaten

Prestaties van de Klassieke ILP

• Schaalbaarheid: De SCIP-solver loste alle instanties succesvol op, inclusief de grootste met ~404 ritten en ~380.000 binaire variabelen.
• Runtime: Optimale of hoogwaardige oplossingen werden verkregen binnen seconden voor middelgrote instanties en tot ongeveer 40 minuten voor de grootste instanties.
• Kwaliteit: Het model produceerde haalbare, praktische circulatieplannen die alle beperkingen respecteerden, inclusief complexe koppelscenario's en capaciteitslimieten.

Prestaties van Quantum en Quantum-geïnspireerde Systemen

• Hardwarebeperkingen: D-Wave quantum annealers waren beperkt tot de kleinste instanties (tot ~50 ritten) vanwege embedding-beperkingen en het aantal beschikbare qubits. Het nieuwere Advantage2-systeem (Zephyr-topologie) loste iets grotere sub-instanties op dan het oudere Pegasus-gebaseerde systeem, maar kon geen instanties aan groter dan grootte 2a.
• QUBO Constructie Bottleneck: De primaire barrière was niet de oplostijd, maar de generatie van de QUBO-matrix. Voor middelgrote instanties (bijv. 78 ritten) bereikte het aantal kwadratische termen ~1,8 miljoen, en voor grotere instanties overschreed het $10^8$, waardoor modelconstructie onmogelijk werd binnen de beschikbare RAM (62 GB).
• Solver Vergelijking:
  • VeloxQ: Presteerde beter dan D-Wave op kleine instanties en vond snel optimale oplossingen. Het werd echter geconfronteerd met dezelfde beperking betreffende de generatie van het QUBO-model voor grotere instanties.
  • Haalbaarheid: Zowel quantum als quantum-geïnspireerde solvers vereisten nabewerking om oplossingen te filteren die soft-constraints (slack-variabelen) schonden, aangezien de penalty-methode niet garandeert dat een oplossing haalbaar is door constructie.

Betekenis en Claims

Het artikel claimt dat voor het specifieke probleem van de dagelijkse EMU-circulatie met de beschreven beperkingen:

• Klassieke ILP is momenteel superieur: De klassieke benadering (SCIP) is de enige methode die in staat is de volledige schaal van real-world regionale spoorweginstanties (honderden ritten) aan te kunnen binnen praktische tijdskaders en daarbij haalbaarheid te garanderen.
• Huidige Staat van Quantum Methoden: QUBO-gebaseerde benaderingen (zowel quantum als quantum-geïnspireerd) zijn momenteel beperkt tot kleine subproblemen of zeer beperkte instanties vanwege de kwadratische expansie van termen en de embedding-overhead. Ze presteren nog niet beter dan klassieke solvers voor end-to-end dagelijkse planning.
• Toekomstige Richting: De resultaten suggereren dat een hybride klassiek-quantum architectuur de meest levensvatbare nabije termijn pad is. In dit kader zou de klassieke solver de globale problemen afhandelen, terwijl QUBO-gebaseerde methoden kunnen worden toegepast op gelokaliseerde, hoog-complexe subproblemen (bijv. specifieke koppelings-"hotspots" of korte termijn herplanningen) waar de omvang van het probleem kleiner is.
• Praktisch Nut: De studie toont aan dat het beperken van het transfertijdvenster ($\Delta$) dient als een effectieve heuristiek om de modelcomplexiteit voor klassieke solvers te verminderen zonder de oplossingskwaliteit significant te verslechteren, een kenmerk dat ook kan helpen bij het verdunnen (sparsifying) van QUBO-formuleringen.

De auteurs concluderen dat hoewel quantummethoden veelbelovend zijn voor het samplen van toestanden met lage energie en het bieden van alternatieve haalbare oplossingen, hun toepassing op grootschalige circulatieplanning voor rollend materiel nog steeds wordt beperkt door hardwarebeperkingen en de wiskundige overhead van de QUBO-herformulering.