Design and implementation of an ant colony optimization algorithm for traffic assignment

Swarm Intelligence (SI) is a concept used by artificial intelligence to solve decision making problems. A peculiar trait of SI algorithms is the use of multiple agents that interact locally and use simple rules to find a globally valid solution. There is no centralized control and the agents have only a limited knowledge of the entire system. In this work we develop and implement a software in Java that extends the basic Ant Colony System (ACS) algorithm, a particular algorithm of the SI family, to model traffic distribution over transportation networks. The objective is to have a software that can work on networks with separable and non-separable cost link functions, searching for a deterministic or stochastic user equilibrium. The flow assignment process is possible over large and real networks with multiple flow origins and destinations, vehicle categories, and limited traffic zones. To achieve this, careful development is done to have an efficient memory consumption, a critical aspect in every software written in Java that uses large amount of data, while maintaining a good computational speed. The software is optimized to work on many threads in parallel, giving a huge increment in performance on multi-core systems. Finally, the software performance and solutions quality is confronted with other commercial software used to solve this type of problems.

La swarm intelligence (SI, traducibile come: teoria dello sciame intelligente) è un concetto usato in intelligenza artificiale per risolvere problemi di decisione. Un tratto di questa famiglia di algoritmi è l'uso di agenti multipli che interagiscono localmente e usano delle semplici regole per trovare una soluzione globalmente valida. Non c'è alcun controllo centralizzato e gli agenti hanno solo una conoscenza limitata dell'intero sistema in cui si muovono e agiscono. In questo lavoro viene sviluppato e implementato un software in Java che estende l'algoritmo chiamato Ant Colony System (ACS), un particolare algoritmo della famiglia degli SI, per modellare da distribuzione del traffico su diverse reti. L'obiettivo è avere un software che può lavorare su diverse reti, con funzioni di costo degli archi dipendenti sia dal traffico sullo stesso arco che su archi incidenti, cercando una soluzione con un equilibrio deterministico o non deterministico. La ricerca di equilibrio è possibile su grandi reti prese dal mondo reale, con diverse origini e destinazioni per il traffico, categorie di veicoli e zone a traffico limitato. Si è data molta attenzione sia alla velocità di esecuzione sia al consumo di memoria, che deve rimanere il più efficiente possibile sopratutto in considerazione del fatto che il software è scritto in Java e lavora su grandi quantità di dati. Il software è ottimizzato per lavorare in parallelo usando diversi processi indipendenti, in modo da avere un ottimo incremento di prestazioni su sistemi multi processore.