Learning-based model predictive control for passenger-oriented train rescheduling with flexible train composition

Sintesi Tecnica: Controllo Predittivo del Modello basato sull'Apprendimento per la Riproprogrammazione dei Treni Orientata ai Passeggeri con Composizione del Treno Flessibile

Enunciato del Problema
I sistemi di trasporto ferroviario urbano affrontano sfide significative nella riprogrammazione in tempo reale a causa delle reti in rapida espansione, della domanda di passeggeri variabile nel tempo e della necessità di bilanciare i costi operativi con la qualità del servizio. Mentre la ricerca esistente affronta la riprogrammazione orientata ai passeggeri, molti approcci sono limitati a composizioni di treni fisse o frequenze di partenza fisse. Inoltre, l'integrazione della composizione flessibile del treno (regolazione del numero di unità ferroviarie per servizio) e della circolazione del materiale rotabile (gestione delle unità ferroviarie tra i depositi) introduce un gran numero di variabili decisionali intere. Ciò trasforma il problema della riprogrammazione in un complesso problema di Programmazione Non Lineare con Variabili Intere Miste (MINLP) o di Programmazione Lineare con Variabili Intere Miste (MILP). Il collo di bottiglia principale per l'applicazione in tempo reale è l'elevato carico computazionale online richiesto per risolvere questi problemi entro i stretti vincoli temporali del Controllo Predittivo del Modello (MPC).

Metodologia
L'articolo propone un framework di Controllo Predittivo del Modello (MPC) basato sull'Apprendimento che integra il deep learning con l'ottimizzazione per affrontare la complessità computazionale della riprogrammazione dei treni in tempo reale. L'approccio è strutturato come segue:

1. Formulazione Matematica: Gli autori estendono un modello di riprogrammazione orientato ai passeggeri per includere la domanda di passeggeri sezionale variabile nel tempo, la composizione flessibile del treno e la circolazione del materiale rotabile. L'obiettivo è minimizzare il tempo totale di attesa dei passeggeri e i costi operativi (energia e costi di variazione della composizione). Il problema è inizialmente formulato come un MINLP, dove le variabili intere rappresentano le composizioni dei treni, l'ordine dei treni e la circolazione del materiale rotabile, mentre le variabili continue rappresentano gli orari di partenza e di arrivo.
2. Tecniche di Presolve: Per ridurre la dimensionalità del problema di ottimizzazione, sono sviluppate quattro tecniche di presolve. Queste tecniche eliminano sottoinsiemi di variabili decisionali intere determinando i loro valori sulla base di vincoli predeterminati e variabili accoppiate (ad esempio, fissando l'ordine dei treni in base a orari predeterminati o fissando la composizione per i treni che sono già partiti).
3. Approccio Ibrido Apprendimento-Ottimizzazione:
   • Addestramento Offline: Reti Long Short-Term Memory (LSTM) vengono addestrate per prevedere i valori ottimali delle restanti variabili intere. Il processo di addestramento utilizza un insieme di reti LSTM per massimizzare il tasso di fattibilità. Le reti sono addestrate su dati generati risolvendo il problema MINLP completo, con una funzione di perdita che minimizza l'errore quadratico tra i valori dell'obiettivo previsti dalla rete e i valori ottimali.
   • Esecuzione Online: Nel ciclo MPC in tempo reale, le reti LSTM addestrate generano le variabili intere (composizioni dei treni e ordini) sulla base dello stato attuale del sistema (conteggio passeggeri, domande e materiale rotabile disponibile). Queste variabili vengono poi fissate.
   • Ottimizzazione Continua: Con le variabili intere fissate, l'originale problema MINLP viene ridotto a un problema di Programmazione Non Lineare (NLP) continua (o un problema di Programmazione Lineare (LP) se la funzione obiettivo viene ulteriormente approssimata). Questo problema ridotto viene risolto efficientemente per determinare l'orario dettagliato (orari di partenza e di arrivo).
4. Garanzia di Fattibilità: Per garantire la fattibilità ricorsiva, viene impiegato un meccanismo di fallback euristico (basato sul Lemma 1). Se la rete LSTM non riesce a generare un insieme di variabili intere fattibili, l'euristica costruisce una soluzione fattibile, assicurando che il ciclo MPC possa sempre procedere.

Principali Contributi
L'articolo elenca tre contributi principali:

1. Modello Esteso: Il modello di riprogrammazione orientato ai passeggeri è esteso per ottimizzare congiuntamente la domanda di passeggeri variabile nel tempo, la composizione flessibile del treno e la circolazione del materiale rotabile, approssimando le domande come funzioni a tratti costanti.
2. Presolve e Riduzione della Dimensionalità: Quattro tecniche di presolve sono sviluppate per ridurre le variabili decisionali intere, restringendo significativamente lo spazio di ricerca per l'algoritmo di apprendimento.
3. Framework MPC basato sull'Apprendimento: Un nuovo approccio MPC basato sul deep learning è sviluppato dove reti LSTM pre-addestrate determinano le variabili intere, e l'ottimizzazione vincolata determina le variabili continue. Questo combina le garanzie di soddisfazione dei vincoli dell'ottimizzazione con la velocità computazionale dell'apprendimento.

Risultati
L'approccio è stato valutato utilizzando dati reali da una rete a tre linee del sistema di trasporto ferroviario urbano di Pechino. Le simulazioni hanno confrontato il proposto MPC basato sull'apprendimento (varianti NLP e LP) rispetto a un Benchmark (MINL con warm-start e tempo esteso), un Warm-start MINLP standard e un approccio MILP.

• Efficienza Computazionale: Gli approcci basati sull'apprendimento hanno dimostrato una drastica riduzione del tempo di soluzione. L'approccio Learning + LP ha raggiunto un tempo di soluzione medio di 0,13 secondi (massimo 0,31s), rispetto ai 96,71 secondi (media) del Warm-start MINLP e ai 51,36 secondi del MILP nei test a ciclo chiuso.
• Ottimalità: I metodi basati sull'apprendimento hanno ottenuto prestazioni comparabili ai benchmark basati sull'ottimizzazione con un compromesso accettabile. Nei test a ciclo chiuso, l'approccio Learning + NLP ha mostrato un gap di ottimalità medio del 4,92%, e Learning + LP del 5,50%, rispetto al benchmark.
• Fattibilità: Il tasso di fattibilità iniziale dell'output grezzo della LSTM era circa il 98,5–98,9%. Tuttavia, con l'applicazione del meccanismo di fallback euristico, il tasso di fattibilità finale ha raggiunto il 100% per tutti gli approcci basati sull'apprendimento nelle simulazioni a ciclo chiuso.
• Qualità dell'Orario: L'analisi visiva degli orari generati ha indicato che gli approcci basati sull'apprendimento hanno adattato con successo le composizioni dei treni ai flussi di passeggeri (ad esempio, utilizzando treni più lunghi durante le ore di punta), sebbene lievi variazioni nella strategia rispetto al benchmark abbiano portato a piccole differenze nei valori della funzione obiettivo.

Significatività e Rivendicazioni
L'articolo sostiene che il framework proposto affronta efficacementmente le sfide di scalabilità e carico computazionale inerenti alla riprogrammazione dei treni in tempo reale con composizione flessibile. Decoupling (decomponendo) il processo decisionale intero (gestito dall'apprendimento) dall'ottimizzazione continua (gestita dai solver), il metodo consente la generazione di orari ottimizzati in tempo reale (sotto 1 secondo per la variante LP), il che è critico per i centri di controllo operativo. Gli autori affermano che questo approccio bilancia la necessità di soluzioni di alta qualità che soddisfino i vincoli con i rigorosi requisiti temporali delle operazioni ferroviarie urbane in tempo reale, offrendo un'alternativa valida ai metodi esatti computazionalmente costosi per reti su larga scala. Il lavoro suggerisce che la ricerca futura potrebbe esplorare l'apprendimento per rinforzo e i sistemi multi-agente per migliorare ulteriormente l'adattabilità e la scalabilità.