Mappare gli ingorghi Analisi del traffico utilizzando la teoria dei grafi

Analisi ingorghi traffico con teoria dei grafi

Scopri come trovare i punti critici potenziali nell’infrastruttura della tua città utilizzando la teoria dei grafi

La teoria dei grafi ha molte applicazioni in problemi reali come reti sociali, biologia molecolare o dati geospaziali. Oggi, presenterò l’ultima di queste, analizzando la disposizione delle strade della città per prevedere le strade critiche, gli incroci e come i cambiamenti all’infrastruttura possono influenzarla. Ma prima, iniziamo con le basi.

Grafici e le loro misure di centralità

I grafici sono insiemi di vertici e archi:

Dove gli archi rappresentano le connessioni tra i nodi. Se gli archi non hanno direzioni, chiamiamo il grafico non orientato. Un esempio di grafico non orientato nella vita reale può essere una molecola chimica, dove i vertici sono gli atomi e i legami sono rappresentati come archi.

Tuttavia, a volte abbiamo bisogno di informazioni su se l’arco va da u a v, da v a u o in entrambi i modi. Ad esempio, se Mark piace ad Alice, non significa necessariamente che sia reciproco ( ☹ ). In queste situazioni, possiamo definire l’arco come una tupla ordinata anziché non ordinata.

• Nuovo modello di testo-immagine di Metas – Spiegazione del paper CM3leon
• Il Chief Scientist di NVIDIA, Bill Dally, terrà il discorso principale a Hot Chips
• Il viaggio di 50 anni della Teoria della Complessità ai limiti della conoscenza

Utilizzando la struttura del grafico, possiamo definire una misura di centralità. È una metrica utilizzata per rispondere alla domanda:

Quanto è importante questo vertice/arco in un grafico?”

E ci sono molti modi per rispondere.

Diversi metodi per valutare l’importanza dei componenti del grafico

A seconda del compito, possiamo partire da un punto diverso valutando la centralità. Una delle metriche più comuni sono: Grado, Vicinanza e Intermedio. Le discuteremo utilizzando il grafico del Karate Club di Zachary [maggiori informazioni]. Puoi trovare il codice utilizzato per generare le immagini qui di seguito.

Centralità del grado

La centralità più basilare. È definita solo per i vertici ed è uguale al grado del vertice (che è il numero dei vertici vicini). Come esempio, possiamo tornare al grafico delle relazioni umane e nel caso delle amicizie tra le persone questa metrica risponderebbe alla domanda

Quanto è popolare questa persona?”

Percorsi nel grafo

Per le due prossime centralità, dobbiamo introdurre alcuni concetti nella nostra conoscenza della teoria dei grafi. Tutti sono molto intuitivi, a partire dai pesi degli archi. Possiamo aggiungere pesi ai nostri archi per segnare la differenza tra di loro. Ad esempio, questo può essere la lunghezza della strada nel caso di un grafo del traffico.

Nei grafi possiamo definire dei percorsi, che sono liste di vertici che dobbiamo attraversare per andare da A a B. I vertici consecutivi nel percorso sono vicini, il primo vertice è A e l’ultimo è B. La distanza del percorso è la somma dei pesi degli archi lungo di esso. Il percorso più breve tra A e B è il percorso con la distanza più piccola.

Centralità di vicinanza

­­­Avendo tutte queste nuove conoscenze, possiamo tornare alle nostre metriche. La prossima è la centralità di vicinanza, che ci dice quanto un nodo è vicino al resto del grafo. È definita per un vertice specifico come l’inverso della media dei percorsi più brevi verso tutti gli altri vertici nel grafo. In questo modo, un percorso medio più breve si traduce in una centralità di vicinanza più alta.

Centralità di intermediazione

La centralità di intermediazione ci fornisce informazioni su quali nodi di un grafo sono cruciali per il traffico che lo attraversa. Immaginate una città con una vasta rete stradale, dove ogni incrocio è un nodo. Alcuni di questi servono come connettori chiave per i pendolari quotidiani, mentre altri possono essere vicoli ciechi con un impatto quasi nullo sul flusso del traffico. I primi hanno punteggi di centralità di intermediazione elevati, calcolati come la proporzione dei percorsi più brevi che attraversano l’intersezione.

Piano della città come un grafo

Ora, avendo gli strumenti per descrivere ed analizzare un grafo, possiamo iniziare a trasformare il piano della città in una forma di grafo. Per farlo possiamo utilizzare Open Street Maps (OSM), per importarlo in Python come grafo NX utilizzando la libreria osmnx. Inizieremo con un esempio più piccolo per discutere quale processo aggiuntivo dobbiamo applicare al fine di migliorare il tempo e l’efficienza del nostro lavoro.

Grzegórzki è uno dei diciotto distretti della città di Cracovia, con due rotonde complesse – Mogilskie e Grzegórzeckie – e molti incroci. Pertanto, saremo in grado di vedere la maggior parte dei potenziali problemi con l’ingegneria dei dati.

Confini amministrativi di Grzegórzki. [©Google]

Iniziamo importando i dati dal repository OSM in un grafo Python e visualizzando i risultati:

C’è qualcosa di sbagliato in questo grafo – riesci a capire cosa è?

Otteniamo molteplici archi per sezioni singole di strade, risultando in un grafo con quasi 3.000 “giunzioni”. Questo non fornisce una rappresentazione adeguata (non possiamo fare inversione a U nel mezzo di una strada e ogni nodo causa un calcolo più lento). Per risolvere questa situazione, eseguiremo una semplificazione della topologia del grafo rimuovendo tutti i nodi sulla strada tra due giunzioni. In OSMnx, abbiamo una funzione chiamata ox.simplify_graph() per fare ciò.

C’è un’altra complicazione – come puoi vedere, abbiamo due archi per la maggior parte delle strade, uno per ogni senso di marcia. A causa di ciò, abbiamo nodi multipli per ogni incrocio, il che comporta un comportamento indesiderato. Immagina di essere su un incrocio, stai svoltando a sinistra e non c’è una corsia separata per la svolta a sinistra (o è già piena). Finché non saremo in grado di fare la svolta, le altre auto saranno bloccate. Nel nostro grafo attuale, questo non è vero. La svolta a sinistra è composta da 2 nodi separati, uno per svoltare a sinistra e l’altro per attraversare la corsia opposta. Questo indicherebbe che sono due operazioni indipendenti, mentre non lo sono.

Ecco perché uniremo gli incroci, cioè combineremo più nodi vicini tra loro in uno solo. Sceglieremo un raggio di consolidamento sufficientemente grande per consolidare più parti degli incroci in uno solo, ma d’altra parte manterremo le rotatorie come strutture a nodi multipli, poiché possono essere bloccate solo parzialmente. Per fare ciò, useremo la funzione ox.consolidate_intersections() di osmnx.

Dopo queste operazioni, siamo quasi pronti per l’analisi. L’ultima complicazione sono i confini del comune di Cracovia – poiché molte persone viaggiano dalle città vicine e l’analisi del grafo include solo i dati all’interno del grafo, dobbiamo includere queste aree. Nel prossimo capitolo presenterò le implicazioni di non farlo. Ecco il nostro grafo:

Puoi trovare il codice sorgente utilizzato per generare questa mappa, così come tutte le immagini utilizzate nel prossimo capitolo, in questo notebook Jupyter.

Centralità di intermediazione del layout stradale

In questo caso di studio ci concentreremo solo sulla misurazione della centralità di intermediazione per stimare il traffico stradale. In futuro, questo potrebbe essere esteso ad altre tecniche della teoria dei grafi, inclusa l’uso di GNN (Graph Neural Networks).

Inizieremo calcolando la misurazione della centralità di intermediazione per tutti i nodi e gli archi in una rappresentazione del layout stradale. Per questo useremo la libreria NetworkX.

A causa di un elevato numero di strade in un grafo, è difficile vedere quali componenti hanno la più alta probabilità di essere critiche per il traffico. Diamo un’occhiata alla distribuzione delle misure di centralità per il grafo.

Possiamo utilizzare queste distribuzioni per filtrare i giunzioni e le strade meno importanti. Selezioneremo il 2% superiore di ciascuno, dove i valori di soglia sono:

• 0,047 per i nodi,
• 0,021 per gli archi.

Possiamo vedere che i segmenti stradali più importanti per betweenness sono:

• La superstrada A4 e la S7 che costituiscono la tangenziale di Cracovia (nota che Cracovia non ha una parte settentrionale della tangenziale),
• La parte occidentale della seconda tangenziale e il suo collegamento con la A4,
• La parte settentrionale della terza tangenziale (che sostituisce la parte settentrionale mancante della tangenziale),
• La strada Nowohucka che collega la seconda tangenziale con la parte nord-orientale della città,
• La strada Wielicka che porta dal centro città alla parte sud-orientale dell’autostrada.

Confrontiamo queste informazioni con una mappa del traffico di Cracovia in tempo reale di Google Maps:

Possiamo vedere che le nostre intuizioni corrispondono ai risultati del radar del traffico. Il meccanismo dietro questo è piuttosto semplice: le componenti con una elevata centralità di betweenness sono quelle utilizzate per percorrere la maggior parte dei percorsi più brevi nel grafo. Se gli automobilisti selezionano i migliori percorsi per i loro tragitti, le strade e gli incroci con i più alti volumi di traffico saranno quelli con la più alta centralità di betweenness.

Torniamo all’ultima parte dell’ingegneria del grafo: l’estensione dei confini del grafo. Possiamo verificare cosa succederebbe se prendessimo in considerazione solo i confini della città per la nostra analisi:

La superstrada A4, che è uno dei componenti più importanti per la sua natura di tangenziale, ha una delle misure di centralità più basse dell’intero grafo! Questo accade perché l’A4 si trova ai margini della città e la maggior parte del traffico proviene dall’esterno, quindi non possiamo includere questo fattore nella centralità di betweenness.

Come utilizzare la centralità di betweenness per analizzare gli effetti dei cambiamenti nella disposizione sul traffico

Diamo un’occhiata a uno scenario diverso per l’analisi del grafo. Supponiamo di voler prevedere come la chiusura di una strada (ad esempio a causa di un incidente) influisce sul traffico. Possiamo utilizzare le misure di centralità per confrontare le differenze tra due grafi e quindi esaminare i cambiamenti nella centralità.

In questo studio, simuleremo un incidente stradale sul segmento dell’autostrada A4-7, che è un evento comune. L’incidente causerà la chiusura completa del segmento.

Inizieremo creando una nuova rete stradale rimuovendo il segmento A4-7 dal grafo e ricalcolando la misura di centralità.

Diamo un’occhiata alla distribuzione di centralità:

Possiamo vedere che è ancora molto simile a quello originale. Per analizzare le modifiche nelle misurazioni di centralità calcoleremo un grafo residuale, in cui le misurazioni di centralità sono la differenza tra il layout stradale originale e quello successivo all’incidente. I valori positivi indicheranno una maggiore centralità dopo l’incidente. I nodi e le giunzioni mancanti in uno dei grafi (come A4-7) non saranno inclusi nel grafo residuale. Di seguito è riportata la distribuzione delle misurazioni dei residui:

Di nuovo, filtreremo il 2% superiore di strade e nodi interessati. I valori soglia questa volta sono:

• 0.018 per i nodi,
• 0.017 per gli archi.

Possiamo vedere aumenti nelle strade che collegano le parti separate della circonvallazione al centro della città, dove si trova la seconda tangenziale. La maggiore variazione si può osservare nella seconda tangenziale che contiene uno dei due ponti rimasti sul fiume Vistola sul lato occidentale della città.

Cosa l’analisi di centralità del grafo non può fare su una rete stradale

Ci sono alcune cose che non possiamo prendere in considerazione durante l’analisi del grafo. Le due più importanti, che abbiamo potuto osservare in questa analisi, sono:

• L’analisi di centralità del grafo assume una distribuzione uniforme del traffico tra i nodi.

Che è falso nella maggior parte dei casi, poiché i villaggi e le città hanno densità di popolazione diverse. Tuttavia, ci sono altri effetti che possono ridurre questo, ad esempio un numero maggiore di persone che vivono nei villaggi limitrofi sceglieranno l’auto come opzione di trasporto rispetto alle persone che vivono nel centro della città.

• L’analisi del grafo tiene conto solo delle cose presenti all’interno del grafo.

Questo è più difficile da vedere negli esempi forniti, soprattutto per chi è fuori da Cracovia. Diamo un’occhiata a Zakopianka. È una importante arteria stradale tra il centro della città e la maggior parte dei comuni a sud di Cracovia, ed è anche parte della DK7 (strada nazionale n. 7) che attraversa tutto il paese.

Se confrontiamo il traffico tipico su DK7 a Cracovia con le nostre misurazioni di centralità, sono completamente diverse. La centralità di intermediazione media è di circa 0,01, che è un valore due volte più piccolo della soglia del 2% superiore. Mentre in realtà, è una delle sezioni più bloccate.

In conclusione

La teoria dei grafi e la sua analisi hanno applicazioni in diversi scenari, come l’analisi del traffico presentata in questo studio. Utilizzando operazioni di base e metriche sui grafi, possiamo ottenere preziose intuizioni in tempi molto più brevi rispetto alla costruzione di un modello di simulazione completo.

Tutta questa analisi può essere eseguita utilizzando diverse dozzine di righe di codice Python e non è limitata a un solo layout stradale. Possiamo anche passare molto facilmente ad altri strumenti di analisi della teoria dei grafi.

Come tutte le cose, anche questo metodo ha i suoi svantaggi. I principali sono le supposizioni sulla distribuzione uniforme del traffico e il limite di scopo alla struttura del grafo.

Il repository di Github contenente il codice utilizzato in questo studio può essere trovato qui.