Un algoritmo di assegnazione stocastica alle reti stradali basato sull'Ant Colony Optimisation

Nell'analisi e nella progettazione delle reti di grandi dimensioni, è necessario disporre di modelli di assegnazione che consentano di stimare i flussi di traffico in tempi rapidi, così da poter valutare un elevato numero di alternative progettuali o prevedere in tempo reale le condizioni di funzionamento di una rete per effetto di strategie di controllo del traffico. In questa nota si propone un algoritmo meta-euristico che consente di calcolare i flussi su rete in maniera più rapida rispetto agli algoritmi di assegnazione tradizionalmente proposti in letteratura. In particolare, le ricerche sono state indirizzate verso gli algoritmi di Ant Colony Optimisation (ACO). Infatti, tali algoritmi, sviluppati circa un decennio fa (i primi lavori furono proposti da Colorni et al., 1992a, 1992b; e Dorigo, 1992), basati sulle strategie di ricerca del cibo da parte delle colonie di formiche, hanno dimostrato una elevata efficienza computazionale, come nel caso dei problemi del commesso viaggiatore, dei problemi di localizzazione e dei problemi di programmazione degli orari di apertura/chiusura degli esercizi commerciali. Un esteso stato dell'arte sugli algoritmi ACO è riportato nel lavoro di Dorigo e Stützle (2004). Nell'ambito dei sistemi di trasporto, un algoritmo basato sull'Ant Colony per risolvere un problema di progetto di rete è stato proposto da Poorzahedy e Abulghasemi (2005). Inoltre, Mussone et al. (2005) ha proposto un algoritmo di assegnazione basato sull'ACO che tende a caricare maggiormente i percorsi di minimo costo (approccio deterministico). Gli stessi autori, inoltre, confrontano le prestazioni dell'algoritmo proposto con quelle dell'algoritmo di Frank e Wolfe (1956), mostrando l'efficienza degli algoritmi ACO anche nei problemi di simulazione.Un importante aspetto riguardante lo sviluppo degli algoritmi risolutivi è la dimostrazione della convergenza. Nonostante ciò, molti dei lavori proposti in letteratura analizzano le proprietà di convergenza solo da un punto di vista numerico. Comunque, in un lavoro recente, la convergenza è dimostrata da Dorigo e Blum (2005) per alcune classi di algoritmi ACO. In tale contesto, l'obiettivo di questa nota è sviluppare un algoritmo ACO per risolvere il problema dell'equilibrio stocastico dell'utente e provare la sua convergenza ed efficienza.