🔢 mathematics

Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring

Dit artikel presenteert een hybride quantum-klassiek branch-and-price-algoritme dat quantum-annealing-geïnspireerde methoden gebruikt voor het oplossen van de subproblemen, waarmee het de prestaties van een puur klassieke aanpak verbetert bij het plannen van intra-dag oplaadtijden voor elektrische voertuigen, vooral op grote en complexe schaal.

Oorspronkelijke auteurs: Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang

Gepubliceerd 2026-03-24

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De "Quantum-Verkeersregelaar" voor Elektrische Auto's: Een Simpele Uitleg

Stel je voor dat je een enorme parkeergarage hebt met honderden elektrische auto's. Iedere auto moet vandaag nog even opladen voordat hij weer wegrijdt. Maar er zijn twee grote problemen:

Er zijn maar een beperkt aantal laadpalen (bijvoorbeeld 10).
Niet elke auto kan op elk moment laden; sommige komen later, sommige moeten eerder weg, en de batterij moet op tijd vol zijn.

De uitdaging voor de beheerder is: Hoe plan je dit zo in dat niemand wacht, niemand te laat is, en je de laadpalen optimaal gebruikt?

Dit is wat deze wetenschappers hebben opgelost. Ze hebben een slimme manier bedacht om dit probleem te zien als een puzzel en hebben daarbij een beetje hulp ingeroepen van de "toekomstige" rekenkracht van kwantumcomputers.

Hier is hoe het werkt, stap voor stap:

1. Het Probleem: De "Kleuren" van de Auto's

Stel je voor dat elke auto een eigen kleur heeft. Elke auto heeft een paar mogelijke tijden om te laden (bijvoorbeeld: "Ik kan laden tussen 10:00 en 11:00" of "Tussen 10:30 en 11:30").

In de wereld van de onderzoekers heet dit een Partition Coloring Problem.
De regel: Je moet voor elke auto precies één tijdvak kiezen.
Het conflict: Als twee auto's tegelijkertijd willen laden, maar er is maar één laadpaal vrij, dan "botsen" ze. In de puzzel betekent dit dat je die twee tijden niet tegelijk kunt "verkleuren".

Het is alsof je een gigantisch bordspel speelt waarbij je voor elke speler één kaart moet kiezen, maar je mag nooit twee kaarten kiezen die met elkaar in conflict zijn.

2. De Oplossing: Een Slimme Zoekmachine (Branch-and-Price)

De onderzoekers gebruiken een klassieke methode genaamd Branch-and-Price. Je kunt dit vergelijken met het oplossen van een doolhof:

De Master (De Hoofdplanner): Deze kijkt naar het grote plaatje en probeert een goed plan te maken met de opties die hij al kent.
De Pricing (De Zoeker): Deze zoekt constant naar nieuwe, betere tijden die de Hoofdplanner misschien over het hoofd heeft gezien.

Het probleem is: bij heel veel auto's (bijvoorbeeld 100) zijn er zoveel mogelijke combinaties dat de "Zoeker" (de computer) het hoofd verliest. De klassieke computer (Gurobi) wordt dan traag en geeft soms op voordat hij het perfecte antwoord heeft gevonden.

3. De Quantum-Schakel: De "Magische" Zoeker

Hier komt het spannende deel. De onderzoekers hebben de "Zoeker" vervangen door een hybride kwantum-algoritme.

Ze hebben het zoekprobleem vertaald naar een QUBO-model. Dat klinkt als wiskundig jargon, maar het is eigenlijk een manier om het probleem te vertalen naar een energielandschap.
De Analogie: Stel je voor dat je een bal in een berglandschap moet rollen om het laagste punt (de beste oplossing) te vinden. Een klassieke computer is als een wandelaar die stap voor stap omhoog en omlaag loopt; hij kan vastlopen in een klein dal en denkt dat hij de bottom heeft gevonden.
De Quantum-geïnspireerde algoritmen (BSB en SimCIM) zijn als een geest die door de bergen kan zweven of een bal die door de grond kan tunnelen. Ze kunnen sneller het echte laagste punt vinden, zelfs als het landschap heel complex en vol kuilen is.

Ze gebruiken hiervoor software genaamd MindQuantum, die deze "kwantum-geesten" simuleert op een gewone computer.

4. Wat was het Resultaat?

De onderzoekers hebben dit getest met honderden auto's:

Bij kleine groepen: De klassieke computer en de nieuwe "kwantum-hulp" doen het even goed. Geen verschil.
Bij grote groepen (100+ auto's): Hier wordt het verschil enorm. De klassieke computer raakt in de war, wordt traag en geeft vaak een "ongeveer goed" antwoord (met een foutmarge).
De nieuwe methode: Dankzij de kwantum-hulp vonden ze in veel gevallen het perfecte antwoord (geen foutmarge) en deden ze dat veel sneller.

Samenvatting in één zin

Deze wetenschappers hebben een slimme manier bedacht om de laadplanning voor elektrische auto's te verbeteren door een klassieke zoekmachine te koppelen aan een "kwantum-geest" die sneller door de complexe puzzel van tijden en conflicten kan navigeren, waardoor grote parkeergarages veel efficiënter kunnen worden beheerd.

Het is een voorbode van hoe de toekomstige kracht van kwantumcomputers (of hun simulaties) nu al kan helpen bij het oplossen van echte, dagelijkse problemen zoals het opladen van onze auto's.

Titel en Context

Het paper presenteert een hybride kwantum-klassieke oplossing voor het intra-dag laadschema-probleem voor elektrische voertuigen (EV's). Het probleem ontstaat in drukke laadstations (zoals parkeergarages of vlootoperaties) waar voertuigen binnen een beperkte tijdspanne moeten worden opgeladen, maar waar de capaciteit van de laadpalen beperkt is. De auteurs modelleren dit als een variant van het Partition Coloring Problem (PCP) en lossen het op met een Branch-and-Price algoritme, waarbij de prijsbepalende subproblemen worden opgelost met kwantum-geïnspireerde algoritmen (QAIA).

1. Probleembeschrijving

Het kernprobleem is het toewijzen van laadintervallen aan een vloot van elektrische voertuigen onder de volgende restricties:

Tijdsvensters: Elke voertuig heeft een aankomsttijd, een vertrektijd en een energiebehoefte.
Capaciteit: Er is een beperkt aantal identieke laadpalen ( $C$ ).
Keuze: Elk voertuig moet precies één laadinterval kiezen uit een reeks voorgedefinieerde kandidaat-intervallen.
Conflicten: Twee intervallen kunnen niet tegelijkertijd worden gebruikt als ze:
1. Overlappen in de tijd.
2. Behoren tot hetzelfde voertuig (uiteraard kan een voertuig niet op twee momenten tegelijk laden).
3. De totale belasting op een bepaald tijdstip de capaciteit van de laadpalen overschrijdt.

Het doel is om een haalbaar schema te vinden dat de maximale voltooiingstijd (makespan) minimaliseert.

2. Methodologie

A. Modellering als Partition Coloring Problem (PCP)

De auteurs vertalen het probleem naar een grafentheoretisch model:

Partities: Elk voertuig vormt een partitie ( $P_n$ ) in de grafiek.
Knopen: Elke kandidaat-laadinterval is een knoop ( $v$ ) binnen die partitie.
Randen: Een rand bestaat tussen twee knopen als ze conflicteren (tijdelijke overlapping of hetzelfde voertuig).
Doel: Kies precies één knoop per partitie zodanig dat de geselecteerde knopen een maximaal onafhankelijke verzameling vormen (geen twee geselecteerde knopen hebben een rand) en het aantal benodigde "kleuren" (laadpalen) wordt geminimaliseerd.

B. Hybride Branch-and-Price Algoritme

Het oplosframework combineert klassieke optimalisatie met kwantum-geïnspireerde technieken:

Restricted Master Problem (RMP):
- Dit is een lineaire relaxatie die wordt opgelost met de klassieke MIP-solver Gurobi.
- Het selecteert combinaties van haalbare intervallen (kolommen) om de huidige beste oplossing te verbeteren.
- Het genereert duale informatie om de zoekrichting te sturen.
Pricing Subproblem (Prijsbepaling):
- In plaats van dit subprobleem klassiek op te lossen, wordt het geformuleerd als een Maximum Independent Set probleem.
- Dit wordt omgezet in een QUBO (Quadratic Unconstrained Binary Optimization) model.
- De QUBO wordt opgelost met QAIA (Quantum Annealing Inspired Algorithms) binnen het MindQuantum framework.
- Twee specifieke algoritmen worden getest:
  - BSB (Ballistic Simulated Bifurcation): Een snelle, continue dynamiek-gebaseerde methode.
  - SimCIM (Simulated Coherent Ising Machine): Een methode die de fysica van Ising-machines simuleert.
- De oplossing van het subprobleem genereert nieuwe kolommen (haalbare intervallen) die aan het RMP worden toegevoegd.
Branching Strategie:
- Om integer-oplossingen te garanderen, wordt een vertakkingsstrategie gebruikt die specifiek is ontworpen voor de PCP-structuur (subset-gebaseerd en paar-gebaseerd vertakken).

3. Belangrijkste Bijdragen

Nieuwe Modellering: Het is de eerste systematische formulering van het intra-dag EV-laadschema als een Partition Coloring Problem. Dit maakt conflicten tussen voertuigen en intervallen expliciet en ondersteunt meerdere hulpbronnen.
Hybride Algoritme: Ontwikkeling van een Branch-and-Price framework waarin de zware pricing-subproblemen worden versneld door QAIA, terwijl het master-probleem klassiek wordt opgelost.
Schalbaarheid: Integratie van MindQuantum's QAIA-oplossers (BSB en SimCIM) om de schaalbaarheid voor grote, complexe instanties te verbeteren, waar klassieke methoden vastlopen.

4. Resultaten

De auteurs voerden uitgebreide numerieke experimenten uit op synthetische datasets met variërende grootte (van 10 tot 100 voertuigen). Ze vergeleken drie varianten:

Gurobi (Baseline): Alles klassiek opgelost.
BSB: Pricing subprobleem opgelost met Ballistic Simulated Bifurcation.
SimCIM: Pricing subprobleem opgelost met SimCIM.

Kernbevindingen:

Kleine en Middelgrote Instanties ( $V \le 40$ ): Alle drie de methoden vinden de globale optimum met vergelijkbare rekentijden. De QAIA-methoden presteren hier even goed als de pure Gurobi-baseline.
Grote en Moeilijke Instanties ( $V \ge 80$ ):
- De Gurobi-baseline loopt vaak vast op de tijdslimiet (3600 seconden) met aanzienlijke optimaliteitsgaten (tot 40% bij 100 voertuigen).
- De QAIA-varianten (BSB en SimCIM) sluiten deze gaten en bewijzen vaak de optimaliteit binnen dezelfde tijdslimiet.
- Bijvoorbeeld: Voor een instantie met 100 voertuigen ( $v100c10k10s1$ ) stopte Gurobi na 3600s met een gat van ~35%, terwijl BSB en SimCIM de optimale oplossing vonden in ongeveer 900-1000 seconden.
Efficiëntie: De QAIA-methoden genereren hoogwaardige kolommen in minder pricing-calls, waardoor de Branch-and-Price boom sneller wordt verkend.

5. Significatie en Conclusie

Dit paper demonstreert dat het integreren van kwantum-geïnspireerde algoritmen in klassieke decompositie-methoden (zoals Column Generation) een veelbelovende richting is voor complexe logistieke problemen.

Praktische Impact: Het biedt een haalbare route om grote schaal EV-laadproblemen op te lossen die voorheen onoplosbaar waren binnen redelijke tijdslimieten.
Technologische Vooruitgang: Het bewijst dat hybride frameworks (klassiek + kwantum-geïnspireerd) superieur kunnen zijn aan puur klassieke benaderingen voor specifieke NP-moeilijke problemen, zelfs zonder toegang tot echte kwantumhardware.
Toekomst: De auteurs suggereren dat deze aanpak uitbreidbaar is naar andere resource-toewijzingsproblemen en dat toekomstig werk kan focussen op dynamische scenario's en real-time data-integratie.

Samenvattend toont het onderzoek aan dat het gebruik van BSB en SimCIM voor het oplossen van pricing-subproblemen de schaalbaarheid en robuustheid van EV-laadplanning aanzienlijk verbetert, vooral in scenario's met hoge complexiteit en grote vlootgroottes.