Network optimization via Ant Colony Algorithm: il caso della rete di trasporto urbano di Roma

Network Optimization via Ant Colony Algorithm – Il caso della rete di trasporto 
urbano di Roma 
 
  
     7 
 
  
Introduzione 
 
Insetti come pachidermi. Per quanto paradossale, l’obiettivo di questo 
lavoro è quello di utilizzare l’intelligenza delle formiche per riconquistare le 
strade di Roma, più di due millenni dopo il celebre tentativo di Annibale con i 
suoi elefanti. 
Il trasporto pubblico, in un’epoca di crescente attenzione ai temi 
ambientali e di convivenza con un permanente stato di traffico congestionato, 
vede aumentare quotidianamente la propria importanza come mezzo per 
soddisfare la richiesta di mobilità nelle città, soprattutto nelle metropoli. La 
scelta che porta una persona all’utilizzo di un autobus o di una linea di 
metropolitana interrata è legata ad una serie di fattori come la comodità, la 
rapidità, la distanza dalla propria posizione e da quella di arrivo. Dall’altra parte 
del servizio vi sono coloro che il sistema di trasporto lo dirigono e che, nel 
soddisfare al meglio gli utenti, devono cercare un equilibrio con la sostenibilità 
economica e le esigenze pratiche della gestione quotidiana. 
Lo scopo di questa tesi è quello di cercare di ottimizzare la rete di 
trasporto pubblico della maggiore metropoli italiana, Roma. Nello specifico 
s’intende studiare ed applicare un approccio che consenta di ridisegnare le 
linee di trasporto esistenti variandone il percorso per consentire ad un maggior 
numero di persone di utilizzare il trasporto pubblico senza costringerle a 
spostarsi per raggiungere le fermate. Al tempo stesso lo studio si prefigge di 
limitare l’aumento di distanza chilometrica delle linee per evitare da un lato 
l’allungamento dei tempi di viaggio e dall’altro per garantire un bilanciamento 
tra il potenziale incremento di utenza e la variazione dei costi fissi. 
Ridisegnare un sistema di trasporto focalizzandosi sul miglioramento di 
determinati parametri è un’operazione che ricade all’interno di un ampio 
insieme di metodiche e tecniche conosciuto come ottimizzazione di reti. E’ 
infatti di uso comune la denominazione “rete di trasporto pubblico” per 
indicare tutto il complesso sistema di tragitti, mezzi, frequenze. 
L’ottimizzazione di reti è diventata nel corso degli anni uno degli argomenti 
più importanti e su cui ci si è concentrati maggiormente di tutta la ricerca 
operativa, la branca della logica matematica sviluppatasi nella seconda metà del 
secolo scorso sulla scia degli studi di pionieri come Turing
1
, Minsky
2
, Dijkstra
3
. 
Non è un caso che con il termine “problema di routing” con cui oggi si indica 
un generico problema d’instradamento in una rete sia diventato di accezione 
comune: navigatori satellitari che risolvono reti stradali e router informatici che 
risolvono reti di calcolatori sono oggetti con cui quotidianamente abbiamo 
rapporti più o meno diretti a livello professionale, ludico, domestico. 
                                                             
1
 (Turing, 1950) 
2
 (Minsky, 1967) 
3
 (Dijkstra, 1959)
Network Optimization via Ant Colony Algorithm – Il caso della rete di trasporto 
urbano di Roma 
 
  
     8 
 
  
Capire come muoversi in un reticolo di punti come città, stazioni, 
fermate percorrendo percorsi come strade, rotte, sentieri cercando di 
ottimizzare al meglio gli spostamenti è stato fin dagli anni ’50 un tema su cui la 
sensibilità dell’opinione pubblica prima e degli scienziati poi è risultata più 
spiccata soprattutto a causa dell’aumento esponenziale dei trasporti su ruota 
del dopoguerra. 
Gli studi relativi all’ottimizzazione delle reti di trasporto si sono 
focalizzati su due aspetti fondamentali: minimizzare la lunghezza necessaria ad 
uno spostamento e massimizzare il flusso di merci o persone di un tragitto 
commerciale. Gli studi tra gli altri di Dijkstra, Ford-Fulkerson
4
 e più 
recentemente di Orlin
5
 e Ahuja
6
, hanno portato nel tempo alla formulazione 
ed a successivi miglioramenti di algoritmi in grado di ricercare percorsi minimi 
e percorsi di massimo flusso di reti estremamente estese e complesse. Un 
risultato importante è stata la formulazione di procedure per l’ottenimento dei 
cosiddetti percorsi “maximum flow – minimum cost”, quelli ossia in grado di 
garantire a tragitti commerciali un massimo flusso di beni/persone pur con la 
percorrenza di un tragitto il più breve possibile. Principali limiti di tali algoritmi 
sono risultati l’elevata potenza di calcolo richiesta ed i tempi di risoluzione 
proporzionali alla complessità del problema. 
Nell’ultimo quarto del secolo scorso, contemporaneamente alla 
formulazione dell’ultima generazione di algoritmi deterministici di 
ottimizzazione di reti, l’osservazione e lo studio del comportamento sociale di 
alcune specie di insetti ha ispirato il lavoro di alcuni ricercatori come Gerardo 
Beni
7
 e portato alla definizione del concetto di intelligenza di sciame. La 
capacità di comunicare con il resto della propria comunità da parte di soggetti 
fondamentalmente privi della capacità di prendere decisioni complesse si è 
dimostrata la base grazie alla quale specie come le termiti sono in grado di 
costruire nidi dalla struttura estremamente elaborata, alti decine di metri. Il 
processo con il quale la banale scelta del singolo elemento dello sciame diventa 
il tramite con cui si produce e si sviluppa un comportamento di comunità 
molto più complesso parte dall’utilizzo dello spazio come mezzo di 
comunicazione. Un insieme di segnali volatili emessi da ogni individuo in base 
alla scelta elementare fatta (che potrebbe essere, per esempio, quella di passare 
sopra o sotto un ostacolo) condiziona le decisioni degli altri appartenenti allo 
sciame che si comportano di conseguenza, portando l’intero gruppo a seguire 
solo la scelta più favorevole, lasciando che i segnali degli individui che si 
perdono o muoiono scompaiano nel tempo. Insetti, uccelli, pesci sono solo 
alcuni esempi di specie specializzate in forme di stigmergia, la capacità di 
prendere decisioni in base ai segni presenti nell’ambiente, presenti in natura. 
                                                             
4
 (Ford, 1962) 
5
 (Orlin, 2013, Jun) 
6
 (Ahuja, 1988) 
7
 (Beni, 1993)
Network Optimization via Ant Colony Algorithm – Il caso della rete di trasporto 
urbano di Roma 
 
  
     9 
 
  
Sulla base di questi studi, Marco Dorigo
8
 nei primi anni ’90 ha sviluppato 
un algoritmo basato sull’intelligenza di sciame ed in grado di risolvere 
problemi di ottimizzazione di reti. Nello specifico l’algoritmo si riferisce al 
comportamento delle formiche ed è stato chiamato Ant Colony Optimization, 
algoritmo di ottimizzazione basato sulle colonie di formiche. La ricerca di 
questa dissertazione si basa sull’applicazione di questo algoritmo, nello 
specifico dell’evoluzione denominata ACS o Ant Colony System, al caso reale 
della rete di trasporto di Roma. 
Se è vero che ACO prima ed ACS poi sono inizialmente stati scritti per 
risolvere prevalentemente problemi di percorso minimo (o shortest path), la 
loro formulazione ha ispirato il lavoro di questa tesi grazie alla loro generalità. 
L’algoritmo si basa sull’idea che le formiche seguano, nel medio-lungo termine, 
il percorso più conveniente per raggiungere la loro meta che sia cibo o sia 
l’ingresso del nido. Le formiche che intraprendono un percorso non ottimale 
vedono la loro scelta scartata in breve tempo grazie ad un meccanismo di 
volatilità dei messaggi ormonali con cui gli insetti comunicano e questo 
garantisce la convergenza verso una soluzione ottima in breve tempo. Il 
percorso che la formulazione originale dell’algoritmo ricerca è il più breve in 
grado di connettere i punti di partenza ed arrivo. 
Lo scopo della nostra ottimizzazione è quello di ottenere percorsi in 
grado di mantenere la loro brevità pur raccogliendo un maggior numero di 
passeggeri. E di farlo basandosi su dati reali applicando l’algoritmo ACS alla 
rete di trasporto pubblico di Roma. Per fare questo, le nostre formiche virtuali 
devono potere viaggiare ed andare a caccia di cibo in un ambiente che pur 
mantenendo rigide formulazioni matematiche possa rappresentare la 
situazione reale delle linee in essere e della richiesta di mobilità. Innanzitutto la 
città deve essere trasformata in una grande scacchiera in cui all’interno delle 
sue celle ricadono aree predeterminate della città, come se sulla città fosse 
adagiata una griglia di dimensioni predefinite. Poi le linee esistenti del trasporto 
pubblico devono essere ridisegnate sopra a questa rete e gli spostamenti 
relativi ai percorsi devono trasformarsi in transizioni tra le celle che 
compongono questa scacchiera. A questo punto, conoscendo i nidi 
rappresentati dai capolinea possiamo fare viaggiare le nostre formiche alla 
ricerca dei migliori percorsi, non prima di avere distribuito nelle celle 
l’informazione, sotto forma di ormone virtuale, relativa alla richiesta di 
mobilità nelle varie aree della città. In questo modo, l’algoritmo viene settato 
per ricercare un percorso che colleghi sorgente e destinazione transitando su 
zone la cui desiderabilità è proporzionale alla richiesta di mobilità dell’utenza.  
Una volta ottenuta una rete con nuovi percorsi, è necessario testarne le 
performance con un adeguato algoritmo per valutare il grado di ottimizzazione 
sia dal punto di vista del gestore della rete che dell’utente. Un’evoluzione che 
simuli un utilizzo più ampio del sistema di trasporto è un’ipotesi che deve 
                                                             
8
 (Dorigo M. , 1992)
Network Optimization via Ant Colony Algorithm – Il caso della rete di trasporto 
urbano di Roma 
 
  
     10 
 
  
essere presa in considerazione non solo per valutare la sostenibilità 
dell’ottimizzazione con un bacino d’utenza aumentato ma soprattutto 
nell’ottica di un progressivo interesse verso il trasporto modale per 
motivazioni pratiche, sociali e soprattutto ambientali. 
La struttura della dissertazione che ha lo scopo d’illustrare le basi 
teoriche e la realizzazione pratica di quanto detto prevede: un primo capitolo 
nel quale si discutono gli approcci tradizionali agli algoritmi di routing; un 
secondo capitolo nel quale s’illustra in dettaglio l’algoritmo Ant Colony System; 
un terzo capitolo nel quale viene analizzata la situazione attuale del trasporto 
pubblico della città di Roma e la sua traduzione in una forma sfruttabile per 
l’ottimizzazione della rete di trasporto; un quarto capitolo centrato 
sull’implementazione pratica dell’algoritmo in linguaggio informatico; un 
quinto capitolo con i risultati della simulazione di un giorno d’esercizio delle 
linee tradizionali confrontate con le linee frutto dell’implementazione 
dell’algoritmo ACS. 
La tesi che con questo lavoro ci si accinge a dimostrare è che utilizzando 
l’algoritmo Ant Colony System sia possibile ottimizzare la rete di trasporto 
pubblico della città di Roma, migliorando il rapporto passeggeri trasportati su 
km di rete in condizioni normali e di aumentato bacino d’utenza.
Network Optimization via Ant Colony Algorithm – Il caso della rete di trasporto 
urbano di Roma 
 
  
     11 
 
  
1. Ottimizzazione di reti 
 
1.1 Reti di trasporto 
Con il termine rete ci si riferisce ad un insieme estremamente vasto ed 
eterogeneo di entità, integrate nelle più disparate realtà. Reti di computer, reti 
sociali, reti di aziende e molte altre. Le reti di trasporto urbano rappresentano 
un caso particolarmente comune e vicino al quotidiano del cittadino, in modo 
particolare di coloro che vivono in realtà metropolitane nelle quali l’utilizzo di 
mezzi di trasporto pubblico rappresenta la scelta primaria per la fruizione della 
mobilità. 
A differenza di reti come quelle delle telecomunicazioni o di quelle 
neurali, la rete di trasporto urbano è soggetta alle perturbazioni di un 
significativo numero di variabili: la frequenza delle corse, la variabilità della 
domanda in base a condizioni meteorologiche o di orario, la possibilità di 
multi-hop trips
9
, la congestione del traffico e molte altre. Ciò rende l’obiettivo 
dell’ottimizzazione della rete affrontabile sotto diversi piani e punti di vista. Si 
può quindi puntare ad ottimizzare la quantità di persone trasportate in un 
determinato lasso di tempo, migliorare il livello di riempimento dei mezzi, 
diminuire il tempo di attesa alle fermate o quello di viaggio, diminuire i costi 
sia dal lato utente che da quello del gestore del servizio. Allo stesso tempo si 
può agire focalizzandosi sulla revisione delle tabelle orarie delle varie linee 
urbane o progettando un nuovo layout delle linee stesse. 
Già intuitivamente si coglie quanto sia diverso analizzare la situazione 
puntando a tempi di passaggio o disegno delle linee come obiettivo principale 
del lavoro di ottimizzazione. Altrettanto complesso può essere decidere se 
optare su trasporto su gomma o su rotaia perché oltre a dovere prendere in 
considerazione quale aspetto il nuovo disegno potrebbe puntare a migliorare, 
si dovrebbe anche tenere conto di limitazioni logistiche ed economiche nel 
caso di nuovi o modificati tratti di metropolitana (interrata o di superficie che 
sia). Sotto questo punto di vista si può sottolineare come diversi studi e 
valutazioni dimostrino come ottimizzare un aspetto (p.e. layout) comporti 
inevitabilmente un miglioramento anche nell’altro (p.e. miglioramento nella 
frequenza di passaggio) e come la scelta tra rotaia e gomma sia stata enfatizzata 
in passato rispetto a quanto fattibile nel presente soprattutto grazie 
all’introduzione di metodologie come il BRT
10
 in grado di mimare con bus 
prestazioni e comportamenti di metropolitane interrate
11
. 
                                                             
9
 Viaggi in cui è previsto il cambio di vettura in uno o più punti del percorso 
10
 Bus Rapid Transit: linee di autobus che grazie a temporizzazione semaforica, segregazione delle 
linee e stazioni ad hoc di fatto riducono tempi di viaggio e di attesa. 
11
 (Nielsen, 2008)