Approccio Innovativo alla Progettazione della Rete di Trasporti

Le agenzie di trasporto di tutto il mondo stanno affrontando tagli di budget. Per continuare a fornire un buon servizio risparmiando soldi, devono progettare reti di trasporto in modo efficiente. Tuttavia, pianificare le rotte di trasporto pubblico è un lavoro difficile. I migliori metodi finora utilizzano algoritmi per passare in rassegna diverse opzioni apportando piccole modifiche casuali alle rotte. Il modo in cui queste piccole modifiche sono progettate può influenzare notevolmente il risultato finale. In questo lavoro, applichiamo il deep learning con reti neurali grafiche per imparare a fare queste piccole modifiche automaticamente, invece che a mano. Questo nuovo metodo mostra risultati migliori quando testato su città campione con molti nodi, e si comporta eccezionalmente bene nel ridurre i Costi Operativi. Ha anche migliorato una simulazione della rete di trasporto reale a Laval, in Canada, di un ampio percentuale e ha permesso di risparmiare sui costi rispetto al sistema esistente.

#Riconoscimenti

Apprezziamo l'aiuto della Laval Transport Society per aver fornito mappe e dati di trasporto, e dell'agenzia di trasporto metropolitano del Quebec per aver fornito i set di dati necessari. Questi dati sono stati cruciali per i nostri esperimenti. Ringraziamo anche l'agenzia di finanziamento per il supporto. Inoltre, siamo grati a uno dei coinquilini dell'autore per aver condiviso idee e fornito feedback sui nostri progetti.

#Contesto e Sfide

La pandemia di COVID-19 ha causato una diminuzione del numero di persone che utilizzano i trasporti nelle città di tutto il mondo. Questa situazione ha creato una crisi finanziaria per molte agenzie di trasporto, facendole sentire la necessità di ridurre i costi per i servizi di trasporto. Se il taglio dei costi porta a una diminuzione della qualità del servizio, potrebbe far sì che meno persone vogliano usare il trasporto, creando un ciclo di servizio e reddito ridotti. Le agenzie devono fare più lavoro con meno risorse. Questo rende molto importante la disposizione delle reti di trasporto, poiché una buona pianificazione può far risparmiare denaro pur continuando a fornire un servizio decente. Tuttavia, cambiare una rete di trasporto non è una cosa da prendere alla leggera. Per i sistemi ferroviari, potrebbe essere necessario apportare modifiche estese, che possono essere troppo costose. Anche per i sistemi di autobus, riprogettare le rotte può essere costoso e dirompente. Pertanto, è cruciale per le agenzie di trasporto ottenere i loro progetti di rete giusti fin dal primo momento. Buoni algoritmi per la progettazione delle reti di trasporto possono essere molto utili in questo senso.

#Il Problema della Progettazione della Rete di Trasporto

Il Problema della Progettazione della Rete di Trasporto (NDP) riguarda la pianificazione di un insieme di rotte di trasporto per una città che soddisfino obiettivi specifici, come servire tutte le esigenze di viaggio mantenendo bassi i costi operativi. Questo è un problema complesso e impegnativo. A causa della natura delle città reali, che spesso hanno molti punti di fermata potenziali, gli approcci di ottimizzazione tradizionali non sono praticabili. Pertanto, i metodi più riusciti finora per affrontare il NDP sono stati gli algoritmi metaeuristici. Questi algoritmi applicano diverse regole semplici che apportano alterazioni casuali a una rete, guidando la ricerca di reti migliori attraverso molte iterazioni utilizzando un processo simile alla selezione naturale.

Sono stati suggeriti diversi approcci per guidare questa ricerca, e numerose regole semplici, specificamente progettate per la progettazione di reti di trasporto, sono state proposte. Anche se questi algoritmi possono fornire buoni risultati in molti casi, la maggior parte delle reti di trasporto reali è ancora progettata manualmente.

Queste semplici regole cambiano la rete in modi diversi: alcune potrebbero rimuovere a caso fermate da una rotta, mentre altre potrebbero aggiungere una fermata a ciascuna estremità di una rotta, o scambiare due fermate su una rotta. La maggior parte di queste semplici regole è piuttosto casuale, il che significa che non tiene conto di dettagli specifici sulla città o sulla rete quando decide quale cambiamento apportare. Vogliamo determinare se un sistema di machine learning potrebbe agire come una regola più intelligente, imparando a utilizzare informazioni sulla città e sulla rete di trasporto attuale per apportare le migliori modifiche.

In un lavoro precedente, abbiamo addestrato una rete neurale per creare una rete di trasporto da zero, dimostrando che questo metodo ha migliorato la qualità delle reti quando abbinato a due algoritmi metaeuristici. Questo ha comportato la generazione di rotte collegando i percorsi più brevi nella rete stradale di una città e utilizzando la rete neurale per scegliere quale percorso aggiungere successivamente. Facendo questo ripetutamente, potevamo assemblare un'intera rete di trasporto.

Nella ricerca continuativa, abbiamo esplorato se la nostra rete neurale potesse migliorare un algoritmo metaeuristico fungendo da regola semplice appresa. Per testare questo, abbiamo adattato un algoritmo evolutivo esistente sostituendo una delle sue regole standard con una che utilizza la rete neurale per pianificare una nuova rotta.

I risultati hanno mostrato notevoli miglioramenti delle prestazioni per le città con molti nodi (70 o più).

#Espandere i Risultati

In questo lavoro, ci basiamo su questi risultati in diversi modi. Presentiamo nuovi risultati ottenuti con un modello di rete neurale aggiornato e una nuova versione dell'algoritmo evolutivo. Effettuiamo anche studi per valutare l'importanza delle diverse parti del nostro approccio combinato neurale-evolutivo. Alcuni di questi studi coinvolgono una nuova regola semplice non appresa, in cui i percorsi con punti finali comuni sono collegati a caso invece di seguire la guida della rete neurale. Curiosamente, quando ci si concentra esclusivamente sulla minimizzazione del tempo di viaggio dei passeggeri, questa regola non appresa ha superato sia le regole tradizionali che la nostra regola della rete neurale. Tuttavia, nella maggior parte degli altri casi, la nostra regola della rete neurale ha fornito risultati migliori.

Confrontiamo i risultati delle nostre regole apprese e non apprese con altri risultati su città di riferimento standard. Scopriamo che la regola non appresa ottiene risultati simili ai migliori metodi conosciuti quando ci si concentra puramente sulla minimizzazione del tempo di viaggio dei passeggeri, mentre la nostra regola della rete neurale supera i migliori metodi precedenti fino al 13% quando si minimizzano i costi operativi.

Infine, andiamo oltre il nostro lavoro precedente applicando le nostre regole a dati reali di Laval, in Canada, un caso reale significativo. I nostri risultati mostrano che la nostra regola appresa può essere utilizzata per progettare reti di trasporto per Laval che superano il sistema di trasporto attuale della città nelle simulazioni su tre obiettivi di ottimizzazione. Questi risultati indicano che le regole apprese possono consentire alle agenzie di trasporto di fornire un servizio migliore a costi inferiori.

#Contesto e Lavoro Correlato

#Deep Learning e Problemi di Ottimizzazione

Il deep learning coinvolge l'uso di metodi di machine learning che presentano reti neurali artificiali profonde-quelle con più strati nascosti. Quando combinato con il reinforcement learning (RL), un ramo del machine learning in cui un sistema prende decisioni e riceve ricompense numeriche, può massimizzare la ricompensa totale attraverso varie azioni. C'è un notevole aumento di interesse nell'applicare il deep learning, e in particolare il deep RL, a problemi di ottimizzazione combinatoria come il Problema del Commesso Viaggiatore (TSP).

I ricercatori hanno proposto diversi modelli, come i Pointer Networks, addestrati tramite apprendimento supervisionato per risolvere istanze del TSP. Altri studi si sono basati su questi risultati, impiegando modelli di rete neurale simili con algoritmi RL per creare soluzioni per il TSP e altre sfide di ottimizzazione. Alcuni studi recenti hanno addestrato reti neurali ricorrenti per generare popolazioni iniziali di soluzioni per un algoritmo genetico, migliorando ulteriormente il processo di addestramento.

Questi metodi rientrano generalmente nei “metodi di costruzione” che partono da una soluzione vuota e si basano su di essa, mentre i “metodi di miglioramento” modificano soluzioni completate per cercare opzioni migliori. Gli Algoritmi Evolutivi appartengono a questa categoria e possono essere computazionalmente costosi ma spesso producono risultati migliori. Alcuni lavori hanno addestrato reti neurali a selezionare mosse nei metodi di miglioramento, dimostrando prestazioni impressionanti sul TSP e problemi simili. In questo contesto, il nostro lavoro addestra una rete neurale per affrontare il problema della progettazione della rete di trasporto e poi la utilizza per migliorare le soluzioni all'interno di un metodo di miglioramento.

Nella maggior parte di questa ricerca, i modelli di rete neurale utilizzati sono reti neurali grafiche, progettate per lavorare con dati strutturati a grafo. Questi modelli hanno trovato applicazione in diversi campi, inclusa l'analisi di grandi grafi web, la progettazione di circuiti stampati e la previsione delle proprietà molecolari. Dato che il problema della progettazione della rete di trasporto può essere descritto come un problema di grafo, utilizziamo anche modelli di reti neurali grafiche.

#Ottimizzazione del Trasporto Pubblico

Il problema della progettazione della rete di trasporto è NP-completo, il che significa che trovare soluzioni ottimali è impraticabile per la maggior parte dei casi. Sebbene le tecniche di ottimizzazione analitica abbiano funzionato su piccole istanze, spesso faticano a rappresentare realisticamente il problema. Pertanto, gli approcci metaeuristici hanno guadagnato terreno.

Le metaeuristiche ampiamente utilizzate per il NDP includono algoritmi genetici, annealing simulato e ottimizzazione delle colonie di formiche. Lavori recenti hanno mostrato successo con altre metaeuristiche come le iper-euristiche, la ricerca a fasci e i gruppi di particelle. Numerose regole a basso livello sono utilizzate in questi algoritmi metaeuristici, ma la maggior parte seleziona uniformemente casualmente tra le opzioni possibili.

Esiste un'eccezione in cui gli autori hanno progettato un modello semplice per esaminare come ogni cambiamento potrebbe influenzare la qualità. Tuttavia, questo modello semplice ignora i viaggi dei passeggeri che coinvolgono trasferimenti e le preferenze degli utenti. Al contrario, il nostro metodo apprende un modello per valutare questi impatti considerando un insieme più ricco di input.

Sebbene le reti neurali siano state spesso impiegate per problemi predittivi nella mobilità urbana, la loro applicazione al NDP rimane limitata, così come il reinforcement learning. Due esempi recenti hanno utilizzato RL per la progettazione di rotte in una piccola città di riferimento con solo pochi punti di trasporto. Tuttavia, questi metodi non si adattano bene a istanze più ampie. Il nostro approccio può trovare buone soluzioni per casi NDP più grandi, superando i 600 nodi, e può essere utilizzato per istanze non viste.

#Formulazione del Problema

Definiamo il problema della progettazione della rete di trasporto in termini di un grafo della città con una raccolta di nodi e archi. Ogni nodo rappresenta potenziali fermate di trasporto, mentre gli archi li collegano con pesi che indicano i tempi di viaggio. L'obiettivo è offrire una rete di trasporto che soddisfi la domanda di viaggio con un focus sulla minimizzazione dei costi.

La rete deve collegare le coppie di domanda mantenendo un numero definito di rotte, rispettando vincoli come i limiti di fermata e evitando cicli. Ci concentriamo su un NDP simmetrico, il che significa che tutte le domande e le rotte funzionano in modo uguale in entrambe le direzioni.

#Formulazione del Processo Decisionale di Markov

Un Processo Decisionale di Markov (MDP) offre un modo per definire problemi di RL. Un agente interagisce con un ambiente attraverso vari passaggi temporali. In ogni passaggio temporale, l'ambiente è in uno stato particolare e l'agente sceglie azioni che portano a nuovi stati, ricevendo ricompense in base alle azioni intraprese. Nel nostro approccio MDP al NDP, lo stato consiste di rotte completate e una rotta attualmente in fase di progettazione. L'agente alterna tra l'estensione di questa rotta o decidere di fermare la rotta.

#Funzione di Costo

La nostra funzione di costo NDP ha diverse parti. La prima componente rappresenta il tempo medio che i passeggeri trascorrono viaggiando attraverso la rete, mentre la seconda componente tiene conto del tempo totale di guida delle rotte. La terza parte assicura che i vincoli siano rispettati contando la frazione di coppie di domanda che rimangono non collegate. In questo modo, la funzione di costo bilancia i costi per i passeggeri e i costi operativi mentre consente aggiustamenti.

#Imparare a Costruire una Rete

Alleniamo una rete neurale grafica per massimizzare il ritorno cumulativo all'interno della nostra formulazione MDP. Applicando questa politica appresa in una città, possiamo generare reti di trasporto, che chiamiamo "costruzione appresa". Eseguendola più volte, possiamo ottenere diverse reti, permettendoci di scegliere quella con il costo più basso.

La parte centrale della rete politica è una rete di attenzione grafica che tratta la città come un grafo completamente connesso. Ogni nodo e arco contiene informazioni rilevanti sulla posizione, sulla domanda e sulle connessioni di trasporto esistenti. L'output consiste in embedding dei nodi che informano la decisione di scegliere tra estensioni o fermare la costruzione.

L'addestramento della politica coinvolge l'esecuzione di episodi attraverso città sintetiche. Ogni città è generata casualmente, mentre i parametri sono mantenuti costanti durante l'addestramento, permettendo alla rete neurale di apprendere da scenari diversi.

#Algoritmo Evolutivo

Valutiamo se la nostra politica appresa può fungere efficacemente da regola a basso livello all'interno di un algoritmo metaeuristico. L'algoritmo evolutivo di base opera su una popolazione di soluzioni, alternando fasi di mutazione e selezione. Per la fase di mutazione, applichiamo due tipi di mutatori a sottoinsiemi scelti casualmente della popolazione. Se la rete mutata ottiene prestazioni migliori rispetto al suo predecessore, sostituisce la rete genitore.

Il nostro algoritmo evolutivo neurale modifica questo utilizzando la nostra politica appresa al posto di uno dei mutatori standard. Questo approccio consente modifiche più avanzate, incoraggiando soluzioni migliori attraverso la combinazione di euristiche esistenti e apprese.

#Esperimenti e Risultati

Valutiamo il nostro metodo su vari set di dati di riferimento, comprese le città di Mandl e Mumford. Ogni città presenta parametri distinti e ogni esperimento esegue diverse iterazioni per raccogliere risultati robusti. L'algoritmo evolutivo neurale viene confrontato con l'approccio evolutivo di base per determinare la sua efficacia.

#Confronto con l'Algoritmo di Base

Nei nostri esperimenti, l'algoritmo evolutivo neurale ottiene risultati significativamente migliori, in particolare nelle città più grandi. I miglioramenti diventano più pronunciati man mano che le città crescono, con miglioramenti distinti sia nei costi operativi che nei tempi di viaggio dei passeggeri.

#Studi di Ablazione

Per migliorare la nostra comprensione di ogni componente dell'algoritmo, eseguiamo studi di ablation per analizzare l'impatto delle varie parti all'interno del nostro sistema. Questo include il confronto del nostro mutatore neurale con una versione senza di esso, aiutandoci a valutare il suo contributo alle prestazioni complessive.

#Applicazione a Scenari del Mondo Reale

Applichiamo il nostro approccio ai dati di Laval, Canada, per valutare la sua efficacia in un contesto reale. Il grafo stradale deriva da varie fonti, tra cui dati geografici, reti di trasporto esistenti e matrici di domanda. Ognuna di queste componenti informa il nostro progetto, assicurando che la nuova rete colleghi tutti i viaggi necessari dei passeggeri.

#Risultati a Laval

I nostri esperimenti mostrano che la politica appresa può sviluppare reti a Laval che superano il sistema di trasporto esistente, riducendo significativamente i tempi operativi e migliorando l'esperienza dei passeggeri. I risultati indicano potenziali risparmi sui costi per l'agenzia di trasporto, migliorando nel contempo la qualità del servizio.

#Conclusione

Questa ricerca dimostra che utilizzare il deep reinforcement learning per apprendere euristiche può migliorare notevolmente la progettazione delle reti di trasporto rispetto ai metodi tradizionali. L'approccio consente alle agenzie di trasporto di raggiungere un servizio migliore a un costo ridotto, dimostrandosi utile in scenari reali. In futuro, esplorare algoritmi metaeuristici variati e affinare il processo di apprendimento potrebbe portare a ulteriori miglioramenti nella progettazione e nelle prestazioni delle reti.