A Stochastic User Equilibrium (SUE) algorithm for mass transit networks based on Ant Colony Optimisation (ACO)

In analyses of real dimension networks, it is important that simulation models allow solutions to be obtained swiftly such that it is possible to explore a large number of alternative projects or simulate beforehand consequences of a strategy in terms of future (minutes or hours) network conditions. Hence, in this paper we verify the possibility of developing a meta-heuristic algorithm that allows user flows on the transit system to be calculated more quickly than by using traditional algorithms. In particular, we steered our research into ant-based algorithms. Indeed, these algorithms based on the food source search of ant colonies, have in many cases shown their efficiency in terms of calculation time (an extended overview of ant-based algorithms can be found in Dorigo & Stützle, 2004). In the case of transportation systems, algorithms based on the Ant Colony Optimisation (ACO) approach were proposed by Poorzahedy & Abulghasemi (2005) in the case of network design, by de Oliveira & Bazzan (2006) for traffic control, and by D’Acierno et al. (2006) and Mussone et al. (2007) for traffic assignment. However, almost all ACO traffic assignment algorithms proposed in the literature are based on preventive choice user behaviour which is typical of models for simulating road systems. Instead, in the case of transit systems in an urban context, it is necessary to simulate preventive-adaptive choice behaviours because users are not able to set their itineraries preventively. Indeed, since the physical path depends on the arrival of vehicles at boarding stops, users choose the set of attractive lines beforehand (preventive stage) and the line used according to arrival events (adaptive stage). In this paper we propose an ACO algorithm that allows us to simulate preventive-adaptive user behaviour in the case of transit systems. In particular, we show that the proposed algorithm has an MSA framework and state the perfect equivalence in terms of (hyper-)path choice behaviours between artificial ants (with the proposed approach) and mass transit users (simulated with traditional algorithms). Finally, we show numerically that, in the case of real dimension networks, the proposed algorithm can be adopted to solve equilibrium assignment problems in less time but with the same accuracy compared with traditional algorithms.