Transit facility allocation: Hybrid quantum-classical optimization

Technische Samenvatting: Allocatie van Transitfaciliteiten via Hybride Quantum-Klassieke Optimalisatie

Probleemstelling
Stedelijke transitplanning staat voor een fundamentele afweging tussen de dienstverlenende toegankelijkheid (hoe gemakkelijk vraagknooppunten, zoals stedelijke gebieden, faciliteiten kunnen bereiken) en efficiëntie (de afstand die een route kan afleggen binnen een specifieke tijdvenster). Het verhogen van het aantal faciliteiten verbetert over het algemeen de toegankelijkheid, maar vermindert de efficiëntie door toegenomen stilstandtijden en reisafstanden. Omgekeerd vermindert het reduceren van faciliteiten de efficiëntie, maar brengt dit risico's met zich mee voor de toegankelijkheid. Het artikel behandelt het Transit Facility Redundancy Problem: het bepalen van de optimale allocatie van een beperkt aantal faciliteiten ($p$) langs een route om de toegankelijkheid te maximaliseren en redundantie te minimaliseren zonder de dekking in gevaar te brengen. De studie richt zich op de B20 northbound busroute in Vancouver, British Columbia, gebruikmakend van Geographic Information Systems (GIS) data.

Methodologie
De auteurs stellen een end-to-end optimalisatieframework voor dat GIS-data, multi-criteria besluitvorming en hybride quantum-klassieke computing integreert.

1. Wiskundige Formulering:

   • Het probleem wordt gemodelleerd met behulp van een nieuwe Spatial Interaction Coverage (SIC) aanpak, die niet-lineaire interacties tussen faciliteiten en vraagknooppunten, afstandsderving (distance decay) en inter-facilitaire competitie vastlegt.
   • Het model wordt geformuleerd als een Quadratic Unconstrained Binary Optimization (QUBO) probleem. De doelfunctie maximaliseert een gewogen som van de populatievraag, gedempt door afstand, terwijl er een straf wordt opgelegd voor het selecteren van faciliteiten die te dicht bij elkaar liggen (competitie).
   • Een beperking die vereist dat exact $p$ faciliteiten actief zijn, wordt geïntegreerd als een kwadratische strafterm. Om de complexiteit te verminderen, partitioneren de auteurs deze globale beperking in kleinere lokale beperkingen, waardoor de probleemgraf van een dichte volledige graaf naar een ijle (sparse) netwerk wordt getransformeerd.

2. Gewichtsschatting (TOPSIS):
   * Om de belangrijkheid (gewichten) van elke faciliteit te bepalen, gebruiken de auteurs TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), een methode voor multi-criteria besluitvorming.
   * Drie attributen worden voor elke faciliteit geëvalueerd: maandelijkse vraag, verbondenheid met andere diensten en nabijheid van oriëntatiepunten (bijv. ziekenhuizen, scholen). TOPSIS synthetiseert deze tot een rangorde die wordt gebruikt om de faciliteiten in het QUBO-model te wegen.

3. Hybride Solver:

   • De optimalisatie wordt opgelost met behulp van een hybride quantum-klassieke solver gebouwd op het open-source dwave-hybrid framework.
   • De solver voert drie parallelle takken uit:
     • Klassieke Heuristieken: Simulated Annealing (SA) en Tabu Search (TS) voeren hill-climbing uit op het volledige probleem.
     • Quantum Annealing (QA): Werkt op kleinere subproblemen die variabelen met een "hoge energie-impact" bevatten, waarbij gebruik wordt gemaakt van quantum tunneling om lokale minima te vermijden waar klassieke hill-climbing methoden in vastlopen.
   • Het systeem combineert iteratief de beste oplossingen uit alle takken.

4. Theoretische Eigenschappen:

   • De auteurs demonstreren dat onder milde omstandigheden (specifiek wanneer de ratio van behouden faciliteiten tot het totaal aantal faciliteiten $>0,5$ is en competitie beperkt is), de matrix die het QUBO-probleem beheerst positief definiet is.
   • Dit impliceert dat zelfs als de integriteitsbeperkingen worden versoepeld (waarbij continue variabelen $x_j \in [0, 1]$ zijn toegestaan), de optimale oplossing van nature convergeert naar binaire waarden ($0$ of $1$).
   • Een theoretische bovengrens voor de optimale doelwaarde wordt afgeleid met behulp van de Schur-Horn stelling, berekend als de som van de $p$ grootste eigenwaarden van de interactiematrix.

Belangrijkste Bijdragen

• Nieuw Wiskundig Model: Een QUBO-gebaseerd model dat van nature integrale oplossingen oplevert zonder expliciete integer-beperkingen en complexe niet-lineaire factoren zoals afstandsderving en facilitaire competitie vastlegt.
• Quantum-Ready Formulering: Het model is expliciet ontworpen om gebruik te maken van quantum-effecten (superpositie en tunneling) via Ising spin glass equivalentie, waardoor het oplosbaar is op quantum annealers, digitale annealers en gate-gebaseerde quantumcomputers.
• Hybride Solver Implementatie: Een robuuste solver die klassieke hill-climbing combineert met quantum tunneling om complexe optimalisatielandschappen te navigeren.
• Theoretische Grenzen: De afleiding van een nauwe, in polynomiale tijd berekenbare bovengrens om de kwaliteit van de oplossing te beoordelen.
• GIS Integratie: Een flexibele workflow die censusgegevens en TOPSIS integreert voor datagedreven facilitaire weging.

Resultaten
Het framework werd toegepast op de Vancouver B20 busroute (49 haltes):

• Faciliteitsreductie: Het model slaagde erin het aantal bushaltes met 40% te verminderen (van 49 naar ~30) terwijl de volledige dekking van alle disseminatiegebieden (vraagknooppunten) behouden bleef.
• Efficiëntiewinst: De reductie in haltes resulteerde in een geschatte reistijdverkorting van 7 minuten (ongeveer 13% van de oorspronkelijke reistijd) tijdens werkuren.
• Oplossingskwaliteit: De beste gevonden waarden van de doelfunctie lagen binnen 95% van de theoretische bovengrens (specifiek bij $p=45$).
• Vergelijkbare Prestaties: In experimenten op 30 synthetische datasets presteerde de voorgestelde hybride solver statistisch beter dan een standaard SIC-model opgelost met de klassieke APOPT solver in termen van vraagdekking over verschillende niveaus van faciliteitsbehoud.
• Redundantieanalyse: De studie identificeerde dat tot 40% van de haltes redundant was (meerdere haltes binnen loopafstand van dezelfde vraagknooppunten) zonder de toegankelijkheid significant te beïnvloeden.

Betekenis en Claims
Het artikel claimt dat dit framework een significante vooruitgang biedt in transitplanning door een kosteneffectieve methode te bieden om de dienstverlening te verbeteren via strategische consolidatie van faciliteiten. De primaire betekenis ligt in:

1. Bruggen slaan tussen Klassieke en Quantum Computing: Het biedt een praktische, real-world toepassing voor opkomende quantumhardware, en demonstreert hoe transportplanners quantum-effecten naast klassieke tools kunnen gebruiken.
2. Model Robuustheid: Het vermogen om van nature binaire oplossingen te genereren en nauwe bovengrenzen te berekenen, biedt een niveau van theoretische zekerheid en flexibiliteit die niet aanwezig is in traditionele modellen zoals LSCP of p-median.
3. Schaalbaarheid: De hybride aanpak adresseert de beperkingen van huidige quantumhardware (ruis en foutpercentages) door klassieke solvers te gebruiken voor redundantie en globale zoekopdrachten, terwijl quantum tunneling wordt ingezet voor lokale optimalisatie.

De auteurs concluderen dat hoewel de aanpak beperkingen heeft met betrekking tot niet-binaire integer variabelen en ongelijkheidsbeperkingen, het succesvol aantoont dat quantum-geïnspireerde optimalisatie effectief de concurrerende doelen van toegankelijkheid en efficiëntie in complexe stedelijke transitnetwerken kan balanceren.