Riepilogo Tecnico: Avanzamento della Simulazione del Ride-Pooling Dinamico – Un Dispatcher Altamente Scalabile

1. Enunciato del Problema

Il ride-pooling dinamico mira a migliorare l'efficienza delle risorse nei trasporti abbinando viaggiatori con itinerari simili in veicoli condivisi, offrendo una via di mezzo tra la flessibilità delle auto private e l'efficienza del trasporto pubblico. Sebbene considerato un componente fondamentale dei futuri sistemi di trasporto autonomo, la ricerca esistente è spesso limitata dalla scalabilità del dispatcher—l'algoritmo responsabile dell'assegnazione dei viaggiatori ai veicoli in tempo reale.

Le limitazioni attuali includono:

• Scalabilità: La maggior parte dei dispatcher non può gestire milioni di richieste all'ora o flotte di decine di migliaia di veicoli, limitando gli studi a piccole aree urbane o a dimensioni di flotte ridotte.
• Assunzioni Statiche: Molti modelli assumono tempi di percorrenza statici o una conoscenza preventiva di tutte le richieste future, non riuscendo a catturare la vera natura dinamica del problema.
• Ambito del Servizio: Molti studi ignorano il contesto più ampio dei trasporti (ad esempio, la scelta modale tra camminare, guidare e usare il trasporto pubblico) e mancano di funzionalità come punti di incontro ottimizzati, assumendo spesso un servizio rigido porta-a-porta.
• Prestazioni nelle Aree Periferiche: La qualità del servizio e l'efficienza spesso si degradano significativamente nelle aree a bassa densità o periferiche.

2. Metodologia

Gli autori introducono Mt-KaRRi (Multi-threaded Karlsruhe Rapid Ride-pooling), un dispatcher innovativo progettato per elaborare milioni di viaggiatori all'ora. La metodologia integra diverse tecniche algoritmiche avanzate e componenti di simulazione:

2.1 Algoritmo di Dispatching Core

Il sistema è costruito sul dispatcher KaRRi, che utilizza algoritmi di stato dell'arte per il percorso più breve per calcolare le inserzioni al volo.

• Ottimizzazione del Percorso Più Breve: Il sistema impiega Gerarchie di Contrazione (CH) e Gerarchie di Contrazione a Secchiello (BCH) per calcolare in modo efficiente percorsi più brevi da uno-a-molti e da molti-a-molti.
• Potatura Ellittica: Per gestire il carico computazionale delle richieste dinamiche, l'algoritmo utilizza la "potatura ellittica" per limitare lo spazio di ricerca per le deviazioni in base ai vincoli esistenti dei passeggeri, riducendo significativamente l'uso della memoria e il tempo di interrogazione.
• Punti di Incontro: A differenza dei modelli tradizionali porta-a-porta, Mt-KaRRi incorpora punti di incontro. I passeggeri possono percorrere brevi distanze a piedi fino ai punti di prelievo/consegna. Questo è modellato utilizzando una rete pedonale separata ($G_{psg}$) e consente deviazioni minori del veicolo, specialmente in aree con limiti di velocità bassi o griglie stradali complesse.
• Funzione di Costo: Il dispatcher minimizza una funzione di costo lineare che combina il tempo di operazione del veicolo, il tempo di viaggio del passeggero e il tempo di cammino, soggetto a vincoli su capacità, intervalli di servizio, tempi di attesa massimi e deviazioni massime del tempo di viaggio.

2.2 Framework di Simulazione

• Modello di Scelta Modale: La simulazione va oltre la semplice assegnazione integrando un modello di scelta discreta (modello logit). I viaggiatori scelgono tra ride-pooling, auto private, camminata e trasporto pubblico in base a punteggi di utilità derivati da tempi di viaggio, tempi di attesa e tempi di accesso/uscita. Ciò permette al sistema di modellare una domanda realistica in cui i viaggiatori possono rifiutare offerte di ride-pooling se la qualità del servizio peggiora.
• Parallelizzazione (Mt-KaRRi): Per raggiungere la scalabilità, gli autori parallelizzano il dispatcher. Le richieste sono raggruppate in batch (intervalli di tempo fissi, ad esempio 5 secondi). All'interno di un batch, più thread worker calcolano in parallelo le migliori inserzioni per le richieste.
• Risoluzione dei Conflitti: Poiché i thread paralleli possono proporre inserzioni per lo stesso veicolo, viene utilizzato un meccanismo di risoluzione iterativa dei conflitti. Le richieste conflittuali vengono risolte in sequenza all'interno del batch, aggiornando lo stato del percorso e ricalcolando le inserzioni per le richieste posticipate fino a quando tutti i conflitti non sono risolti.

2.3 Setup Sperimentale

Gli autori hanno generato istanze di problemi realistiche utilizzando dati di domanda da Karlsruhe e Stuttgart (Germania) e Los Angeles (USA), derivati da simulazioni basate su agenti (mobiTopp e MATSim).

• Scala: Gli esperimenti hanno variato da migliaia a oltre 25 milioni di viaggi di passeggeri e flotte fino a 500.000 veicoli.
• Geografia: Lo studio ha distinto tra aree urbane e rurali (periferiche) utilizzando la tipologia RegioStaR-2 per analizzare le differenze di prestazione.

3. Contributi Chiave

1. Dispatcher Scalabile: Presentazione del primo dispatcher di ride-pooling dinamico in grado di gestire milioni di richieste all'ora e decine di migliaia di veicoli, rappresentando istanze di problemi di un ordine di grandezza superiore rispetto al lavoro precedente.
2. Strategia di Parallelizzazione: Sviluppo di Mt-KaRRi, una variante multi-thread che ottiene accelerazioni significative (fino a ~37x su 96 core per istanze grandi) mantenendo la qualità della soluzione attraverso l'elaborazione in batch e la risoluzione dei conflitti.
3. Integrazione della Scelta Modale: Combinazione del dispatcher con un modello realistico di scelta modale, consentendo la valutazione del ride-pooling come parte di un sistema di trasporto multimodale piuttosto che come un silo isolato.
4. Modellazione dei Punti di Incontro: Implementazione di un modello dettagliato dei punti di incontro che tiene conto delle velocità e delle distanze di cammino specifiche del passeggero, dimostrando il suo impatto sull'efficienza del sistema.
5. Analisi Empirica su Grande Scala: Esecuzione di simulazioni estese per analizzare gli effetti della dimensione della flotta, della densità della base clienti, dei punti di incontro e dei contesti urbani rispetto a quelli rurali sulla qualità del viaggio e sull'uso delle risorse.

4. Risultati Sperimentali

Gli autori hanno condotto esperimenti estesi per valutare le prestazioni e la qualità della soluzione:

• Scalabilità: Mt-KaRRi ha dimostrato una forte scalabilità debole. Per l'istanza più grande (Los Angeles, 100% della popolazione, 25 milioni di viaggi), il sistema ha raggiunto un'accelerazione di 36,89x rispetto alla versione sequenziale utilizzando 96 thread, con un tempo di risposta medio di **1,84 ms per richiesta**.
• Impatto della Base Clienti:
  • Basi clienti più grandi hanno aumentato il numero totale di passeggeri e il potenziale di pooling (maggiore occupazione e passeggeri condivisi).
  • Tuttavia, se la dimensione della flotta era fissa e piccola rispetto alla domanda, la qualità del viaggio (tempi di attesa, deviazioni) si deteriorava significativamente.
  • L'efficacia del sistema (tempo di veicolo risparmiato rispetto alle auto private) migliorava con basi clienti più grandi, raggiungendo un'efficienza fino a 1,57x per flotte grandi.
• Punti di Incontro: L'uso dei punti di incontro ha migliorato significativamente le prestazioni del sistema:
  • Riduzione dei tempi di attesa medi di 4+ minuti in scenari ad alta domanda.
  • Riduzione dei tempi totali di viaggio dell'8–11%.
  • Aumento del numero medio di passeggeri condivisi e dell'efficacia del sistema.
• Dimensione e Capacità della Flotta:
  • L'aumento della dimensione della flotta ha migliorato la qualità del viaggio (minori deviazioni e tempi di attesa) ma ha infine prodotto rendimenti decrescenti sulla quota modale.
  • Flotte più piccole richiedevano livelli di pooling più elevati (maggiore occupazione) per rimanere efficaci, mentre flotte più grandi operavano più come taxi individuali con tassi di pooling più bassi.
• Urbano vs Periferia:
  • Il ride-pooling era più attraente nei corridoi urbano-rurale e rurale-urbano, dove riduceva la quota modale delle auto private da ~66% a <45%.
  • Sebbene i viaggi periferici avessero deviazioni leggermente più lunghe a causa delle distanze maggiori, la distribuzione dei tempi di attesa e delle deviazioni rimaneva relativamente equa tra le categorie urbane e rurali.

5. Significato e Affermazioni

Il documento posiziona Mt-KaRRi come uno strumento fondamentale per la futura ricerca sul ride-pooling su larga scala. Il suo significato principale risiede nel permettere una scala senza precedenti negli studi di simulazione, consentendo ai ricercatori di:

• Analizzare il comportamento dei sistemi di ride-pooling con decine di migliaia di veicoli e milioni di viaggiatori, ciò che era precedentemente computazionalmente non fattibile.
• Studiare l'interazione tra il ride-pooling e altre modalità di trasporto (camminata, trasporto pubblico, auto private) in un ambiente dinamico realistico.
• Investigare le sfide specifiche delle aree periferiche e i benefici dei punti di incontro nel ridurre lo stress operativo sulle flotte.

Gli autori concludono che, sebbene basi clienti più grandi migliorino l'efficacia del sistema, possono degradare la qualità del viaggio se la capacità della flotta è insufficiente. Suggeriscono che l'uso dei punti di incontro è una leva critica per mantenere la qualità del servizio in condizioni di alta domanda. Il documento non afferma di risolvere tutte le sfide del ride-pooling ma fornisce un motore scalabile per esplorarle, notando che il lavoro futuro potrebbe coinvolgere un accoppiamento più stretto con le simulazioni del traffico, aggiornamenti dinamici dei tempi di viaggio e un routing multimodale più sofisticato.