Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Sintesi Tecnica: Pianificazione del Materiale Rotabile Utilizzando l'Algoritmo di Ottimizzazione Approssimata Quantistica

Definizione del Problema
Il documento affronta il problema della Pianificazione del Materiale Rotabile (Rolling Stock Planning), una complessa sfida di ottimizzazione nella gestione ferroviaria. L'obiettivo è assegnare treni fisici a un orario di corse programmato, minimizzando i costi operativi, definiti specificamente come "chilometri a vuoto" (distanza percorsa senza passeggeri). L'istanza del problema considerata coinvolge 190 corse nell'arco di due giorni attraverso cinque stazioni, soggetta a vincoli rigorosi:

• Operatività Ciclica: Ogni treno deve completare un ciclo che lo riporti alla stazione di partenza.
• Manutenzione: Ogni ciclo deve includere una sosta di manutenzione obbligatoria in una stazione designata per una durata fissa.
• Limiti di Distanza: I cicli non possono superare una distanza massima ($l_{max}$) prima che sia richiesta la manutenzione.
• Viaggi a Vuoto: I treni possono percorrere "viaggi a vuoto" (movimenti non programmati) per collegare le corse programmate o raggiungere le stazioni di manutenzione, incorrendo in costi ma garantendo la fattibilità.

Gli autori osservano che, sebbene il problema sia vincolato, non modellano i vincoli di capacità della rete (ad esempio, limiti di parcheggio nelle stazioni o congestione delle tratte), assumendo una capacità illimitata per lo scopo di questo studio.

Metodologia
Gli autori propongono un algoritmo ibrido quantistico-classico "divide et impera" per affrontare la complessità computazionale del problema, che scala esponenzialmente con il numero di corse.

1. Mappatura nel Problema dell'Insieme Indipendente a Peso Massimo (MWIS):
   Il problema viene prima riformulato come un problema MWIS su un grafo.

• Nodi: Rappresentano cicli di treni fattibili generati dall'orario.
• Archi: Collegano i nodi se i corrispondenti cicli sono mutuamente incompatibili (ovvero, servono entrambi la stessa corsa programmata).
• Pesi: Assegnati ai nodi in base a una funzione obiettivo euristica ($w_i = 2d_{full} - d_{empty}$), dando priorità alla copertura delle corse con passeggeri rispetto alla pura riduzione dei costi.
• Obiettivo: Trovare un insieme indipendente (un insieme di cicli non conflittuali) con il peso totale massimo.

2. Strategia di Generazione dei Cicli:
   Per gestire l'esplosione di possibili cicli, gli autori impiegano un processo di generazione a due modalità:

• Modalità 1: Genera cicli utilizzando solo corse programmate (senza viaggi a vuoto).
• Modalità 2: Attivata quando il numero di corse non servite scende sotto una soglia (40 corse) o quando non è più possibile formare cicli in Modalità 1. Questa modalità consente i viaggi a vuoto, espandendo significativamente lo spazio delle soluzioni per garantire che tutte le corse rimanenti possano essere coperte.

3. Framework Ibrido Divide-and-Conquer:
   Poiché l'intero grafo MWIS è troppo grande per gli attuali risolutori, l'algoritmo risolve iterativamente sottografi più piccoli:

• Selezione del Sottografo: Un'euristica seleziona un sottografo di dimensione $k$ (ad esempio, da 20 a 300 nodi). La strategia di selezione dà priorità ai cicli che servono il maggior numero di corse complete, bilanciando la qualità della soluzione con la diversità.
• Risoluzione del Sottografo: Il problema MWIS sul sottografo selezionato viene risolto utilizzando vari metodi:
  • Risolutore Classico Esatto: Utilizzato come baseline.
  • Algoritmo Greedy: Un baseline classico che seleziona i nodi in base al rapporto peso-grado.
  • QAOA (Algoritmo di Ottimizzazione Approssimata Quantistica): Implementato con profondità $p=1$ e $p=5$. Il problema viene mappato su un Hamiltoniano di tipo spin-glass diagonale con un termine di penalità per le violazioni degli archi.
• Pruning (Potatura): Poiché QAOA e il campionamento casuale possono produrre insiemi non validi (contenenti nodi connessi), una procedura di pruning rimuove i nodi con i rapporti peso-grado più bassi finché non si forma un insieme indipendente valido.
• Aggiornamento Globale: I cicli selezionati vengono aggiunti alla soluzione globale e i nodi conflittuali vengono rimossi dal grafo globale. Il processo si ripete fino a quando tutte le corse sono servite.

Risultati Chiave
Gli autori hanno valutato l'algoritmo utilizzando la simulazione classica ed l'esecuzione sul dispositivo quantistico IQM Emerald.

• Confronto tra i Risolutori (Dimensione del Sottografo Fissa): Con una piccola dimensione del sottografo ($k=20$), la differenza di prestazioni tra l'algoritmo greedy, i risolutori classici esatti e il QAOA ($p=1, p=5$) era trascurabile. Tuttavia, i risultati hanno mostrato che un QAOA a maggiore profondità ($p=5$) tendeva ad avvicinarsi alla qualità della soluzione del risolutore esatto, nonostante sia un algoritmo a tempo polinomiale rispetto al risolutore esatto a tempo esponenziale.
• Impatto della Dimensione del Sottografo: Un risultato critico è stata la correlazione positiva tra la dimensione del sottografo e la qualità della soluzione. Man mano che la dimensione del sottografo aumentava (fino a 300 nodi), i chilometri a vuoto diminuivano significativamente (pendenza negativa con $p \approx 10^{-9}$). Ciò suggerisce che risolvere sottoproblemi più grandi produce soluzioni globali migliori, anche se il risolutore del sottografo stesso è approssimativo.
• Esecuzione Quantistica: Il documento riporta i risultati dell'esecuzione di QAOA $p=1$ sul computer quantistico IQM Emerald, dimostrando la fattibilità dell'esecuzione dell'algoritmo sull'hardware attuale, sebbene la qualità della soluzione fosse comparabile alla simulazione classica e al campionamento casuale per i parametri testati.

Significatività e Rivendicazioni
Il lavoro si posiziona come un percorso pratico per l'applicazione di computer quantistici a breve termine a problemi di ottimizzazione industriali realistici, prima che l'hardware sia in grado di risolvere direttamente l'intero problema.

• Colmare il Divario: Il framework ibrido colma efficacemente il divario tra risolutori veloci e approssimativi a tempo polinomiale (come gli algoritmi greedy) e metodi esatti a tempo esponenziale lenti.
• Scalabilità: Gli autori sostengono che il loro approccio permette agli algoritmi quantistici di essere applicati a sottoproblemi compatibili con i limiti dell'hardware attuale, mentre un ciclo esterno classico orchestra l'ottimizzazione complessiva.
• Potenziale di Vantaggio Quantistico: I risultati suggeriscono uno scenario in cui la profondità dell'algoritmo QAOA ($p$) deve solo crescere polinomialmente con la dimensione del sottografo per ottenere soluzioni approssimativamente ottimali, offrendo un potenziale vantaggio quantistico rispetto ai metodi classici esatti per istanze su larga scala.
• Modestia: Gli autori riconoscono le limitazioni, notando che l'attuale fase di generazione dei cicli è un collo di bottiglia per orari più grandi e che l'efficacia della procedura di pruning può degradare all'aumentare delle dimensioni dei sottografi. Non affermano che il QAOA superi attualmente i risolutori classici esatti sul problema completo, ma piuttosto che l'architettura ibrida consente l'esplorazione di spazi di soluzione più ampi di quanto precedentemente possibile con sole risorse quantistiche.