An Ant Colony Optimisation (ACO) algorithm for solving the Local Optimisation of Signal Settings (LOSS) problem on real-scale networks

In this paper we propose an Ant Colony Optimisation (ACO) algorithm for solving the problem of optimising the signal settings on urban networks following a local approach. This problem, also known as LOSS (Local Optimisation of Signal Settings), has been widely studied in the literature and can be formulated as an asymmetric assignment problem (see Cascetta et al., 2006, for an extensive analysis of the problem and a literature review). The problem consists in optimising the signal settings of each intersection of an urban network as a function only of traffic flows at the accesses of the same intersection, taking account of the effects of signal settings on costs and on user route choices. This can be formulated as a fixed-point problem since there is a circular dependence between flows, costs and signal settings. In Cascetta et al. (2006) the theoretical properties about existence and uniqueness of the fixed-point solution are studied and some MSA-based algorithms are proposed for solving the problem. In this paper we propose to solve the problem with an ACO algorithm in order to reduce the computation times on real-scale networks. Indeed, the solution of the asymmetric assignment problem requires more computing time than a classic assignment problem, since the signal settings have to be updated at each iteration and there is a double circular dependence (local optimal signal settings depend on flows that depend on costs that depend on both flows and signal settings). Generally, ACO algorithms applied to (symmetric) stochastic assignment require less computing time than MSA algorithms (as shown by D'Acierno et al., 2006). Therefore in this paper we modify the ACO algorithm proposed by D'Acierno et al. (2006) for solving the LOSS problem on real-scale networks, where reducing computing times is an important task. In particular, in the proposed ACO algorithm we can identify two kinds of behaviour of artificial ants which allow the LOSS problem to be solved: traditional behaviour based on the response to pheromones for simulating user route choice and innovative behaviour based on the pressure of an ant stream for solving the signal setting definition problem. Our results on a real-scale network show that the proposed approach allows the solution to be obtained in less time but with the same accuracy as in classic MSA approaches. References Cascetta E., Gallo M., Montella B. (2006) Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment. Annals of Operations Research 144, pp. 301-328. D'Acierno L., Montella B., De Lucia F. (2006) A stochastic traffic assignment algorithm based on Ant Colony Optimisation. In 'Ant Colony Optimization and Swarm Intelligence' (Editors: M. Dorigo, L.M. Gambardella, M. Bittari, A. Martinoli, R. Poli and T. Stützle), Lecture Notes in Computer Science, vol. 4150, Springer-Verlag, Berlin, Germany, pp. 25-36.