A Swarm Approach to Public Transit Using On-demand Routing in a Slime-Mold-Inspired Framework

Sintesi Tecnica: Un approccio a sciame per il trasporto pubblico mediante instradamento on-demand in un framework ispirato alla muffa vischiosa

Definizione del problema
I sistemi di trasporto a chiamata (DRT - Demand-responsive transit) offrono un'alternativa flessibile al tradizionale trasporto di massa a rotte fisse, particolarmente nelle comunità suburbane e rurali a bassa densità dove le rotte fisse spesso non riescono a garantire un accesso adeguato. Tuttavia, le attuali implementazioni DRT soffrono frequentemente di elevati costi operativi, bassa affidabilità e alti tassi di fallimento. Gli attuali approcci di instradamento si basano tipicamente sulla pianificazione centralizzata utilizzando algoritmi di percorso minimo (ad esempio, basati su Dijkstra) o meta-euristiche (ad esempio, algoritmi genetici e ottimizzazione a colonia di formiche). Questi metodi faticano a gestire la scala e l'imprevedibilità della domanda in tempo reale, dove i percorsi pre-pianificati diventano rapidamente sub-ottimali. Inoltre, i sistemi centralizzati affrontano carichi computazionali e di comunicazione che diventano impraticabili per reti di grandi dimensioni sotto un uso intensivo. La sfida principale consiste nel progettare un meccanismo di instradamento distribuito e scalabile che si adatti dinamicamente alla domanda dei passeggeri, minimizzi le distanze di percorrenza a piedi e ottimizzi l'utilizzo dei veicoli senza fare affidamento su un controllo centralizzato.

Metodologia
Gli autori propongono un nuovo sistema di trasporto distribuito guidato dall'algoritmo RAPID, un metodo di instradamento bio-ispirato modellato sui comportamenti efficienti di ricerca del percorso della muffa vischiosa Physarum polycephalum. Il sistema opera senza controllo centralizzato, utilizzando la comunicazione locale della rete per creare e mantenere gradienti di domanda attraverso la rete stradale.

La metodologia è strutturata attorno a tre componenti:

1. Meccanismo di offerta (Bidding Mechanism): Quando un passeggero richiede un viaggio, i veicoli candidati generano offerte basate su una funzione di ricompensa. Il valore dell'offerta ($B_{i,p}$) per il veicolo $i$ che preleva il passeggero $p$ è calcolato utilizzando il tempo di attesa normalizzato, la distanza del percorso minimo e il carico attuale dei passeggeri, pesati da parametri regolabili ($\alpha, \beta, \gamma, \delta, \sigma, \epsilon$). Al veicolo con il massimo valore di offerta viene assegnato il passeggero.
2. Instradamento ispirato alla muffa vischiosa (RAPID): Invece di calcolare percorsi fissi, i veicoli navigano basandosi su gradienti di domanda locali. Ogni nodo della rete mantiene un valore di domanda ($d_{p,n}$) e un valore di riferimento ($r_{p,n}$), dove i valori di riferimento sono impostati a 10 nei punti di prelievo e rilascio e a 0 altrove. La domanda si propaga tra i nodi vicini in base a parametri di diffusione, rilassamento e inerzia ($\zeta, \eta, \mu$). La domanda cumulativa in un nodo è pesata dal tempo di attesa del passeggero. I veicoli decidono localmente la loro mossa successiva dirigendosi verso il nodo adiacente con il valore di domanda più elevato, permettendo al sistema di reagire in tempo reale alle condizioni variabili.
3. Trasferimenti dinamici: Per ottimizzare ulteriormente l'efficienza, il sistema consente ai passeggeri di effettuare trasferimenti tra veicoli se ciò riduce il loro tempo di viaggio previsto. Un trasferimento viene avviato solo se il miglioramento cumulativo dei valori di offerta per i passeggeri coinvolti supera una soglia ($\theta$) e se il passeggero non ha superato un limite massimo di trasferimenti ($\tau$).

Framework di simulazione
Gli autori hanno implementato una simulazione basata su agenti utilizzando reti stradali reali derivate da OpenStreetMap per tre ambienti distinti: la zona suburbana di Rutherford, NJ; l'area urbana di Newark, NJ; e la zona semi-rurale di Wayne, NJ. La simulazione confronta l'approccio basato su RAPID con un benchmark di trasporto a rotta fissa derivato dai dati di NJ Transit.

• Agenti: Passeggeri (che tracciano posizione, destinazione, trasferimenti e timestamp) e Veicoli (che tracciano posizione e passeggeri assegnati).
• Parametri: Un algoritmo genetico è stato utilizzato per ottimizzare i parametri della funzione di offerta e le soglie di trasferimento, con una funzione di fitness che bilancia il tempo medio di consegna e la deviazione standard dei tempi di consegna.
• Condizioni: Le simulazioni sono state eseguite per 100 minuti con una flotta di 10 veicoli (capacità di 30 passeggeri ciascuno) nello scenario di base, con test aggiuntivi che variano la dimensione della flotta e la capacità dei veicoli mantenendo costante la capacità totale di 300 passeggeri.

Risultati chiave
I risultati della simulazione indicano che l'approccio basato su RAPID supera significativamente il sistema a rotta fissa in tutti gli ambienti testati:

• Tassi di consegna dei passeggeri: Il sistema RAPID ha aumentato il numero di passeggeri consegnati rispetto all'approccio a rotta fissa del 28,2% a Rutherford (suburbana), del 49,0% a Newark (urbana) e del 101,4% a Wayne (semi-rurale).
• Tempo di percorrenza a piedi: Il sistema ha ridotto il tempo medio di percorrenza a piedi per i passeggeri di oltre il 75% in tutti gli scenari (85,5% a Rutherford, 84,7% a Newark e 76,8% a Wayne).
• Configurazione della flotta: Il sistema ha dimostrato flessibilità nella composizione della flotta, mostrando che le configurazioni con molti veicoli più piccoli spesso portavano a tempi di consegna più rapidi rispetto a pochi veicoli più grandi, a parità di capacità totale.

Significato e rivendicazioni
Il documento sostiene che l'approccio proposto basato su RAPID offre una soluzione scalabile e decentralizzata ai limiti degli attuali sistemi DRT. Mimando il processo decisionale decentralizzato della muffa vischiosa, il sistema raggiunge un'elevata efficienza e affidabilità senza l'onere computazionale della pianificazione centralizzata. Gli autori affermano che questo approccio è particolarmente adatto agli ambienti rurali e suburbani dove il trasporto a rotta fissa è spesso inefficace.

Il lavoro contribuisce con:

1. La progettazione di un nuovo algoritmo di instradamento per il trasporto pubblico bio-ispirato.
2. Lo sviluppo di un framework di simulazione flessibile che incorpora dati stradali reali.
3. Le prime prove empiriche che suggeriscono come l'instradamento on-demand guidato da sciami possa migliorare significamente la capacità di transito e l'accessibilità (specificamente riducendo le distanze percorse a piedi) rispetto alle reti tradizionali a rotta fissa.

Gli autori riconoscono i limiti, tra cui l'assenza di modellazione della congestione del traffico, l'uso di una domanda di passeggeri generata casualmente anziché pattern di pendolarismo reali e la mancanza di un'analisi dei costi. Notano che il lavoro futuro si concentrerà sulla validazione del sistema con simulazioni su scala maggiore, l'integrazione della dinamica del traffico e la valutazione della convenienza economica.