Traffic Flow Estimation Using Ant Colony Optimization Algorithms

• Antonio Bolufé-Röhler ^[1] ; Juan Manuel Otero Pereira ^[1] ; Sonia Fiol-González ^[1]
  1. [1] Universidad de La Habana

     Universidad de La Habana

     Cuba

     
• Localización: Computación y Sistemas (CyS), ISSN 1405-5546, ISSN-e 2007-9737, Vol. 18, Nº. 1, 2014, págs. 37-50
• Idioma: inglés
• DOI: 10.13053/CyS-18-1-2014-017
• Títulos paralelos:
  • Algoritmos de optimización basados en colonias de hormigas para la estimación de flujos de tráfico
• Enlaces
  • Texto completo
• Resumen
  • español

    La estimación de flujos de tráfico permite implementar buenas estrategias de desarrollo, a la vez que ayuda en el proceso de toma de decisiones cuando se controlan y distribuyen recursos claves como el transporte masivo. La distribución de tráfico puede ser modelada como un problema de Flujo de Costo Mínimo para Múltiples Bienes. Para su solución, la Optimización de Colonia de Hormigas provee un marco de trabajo prometedor. En la presente investigación se presentan dos nuevos algoritmos basados en Colonias de Hormigas, los mismos se aplican a instancias reales del problema de estimación de flujo en Ciudad de La Habana. Los resultados alcanzados se comparan con los provistos por algoritmos clásicos, mostrando la efectividad del método propuesto.

  • English

    Simulation and optimization of traffic flows in a city or province allow the implementation of correct developing strategies and help the decision making process when using and distributing resources such as mass transit. This estimation can be modeled as a bifurcated multi-commodity network flow problem, where the general flow distribution is dictated by Wardrop's principles. In this paper two different Ant Colony Optimization algorithms are presented for solving this problem. The proposed algorithms are tested with real-life traffic demand in the Havana city. The obtained results are compared to those provided by classical algorithms, showing that the new ant colony algorithms provide good results as well as low running times.

• Referencias bibliográficas
  • Wardrop, J.G.. (1952). Some theoretical aspects of road traffic research. Institution of Civil Engineers. Palo Alto.
  • Fratta, L.,Gerla, M.,Kleinrock, L.. (1973). The flow deviation method: An approach to store-and-forward communication network design. Networks....
  • Goffin, J.,Gondzio, J.,Vial, R.. (1997). Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Mathematical...
  • Gabrel, V.,Knippel, A.,Minoux, M.. (1999). Exact Solution of Multicommodity Network Optimization Problems with General Step Cost Functions....
  • Boschetti, M.A.,Maniezzo, V.,Roffilli, M.,Röhler, A.B.. (2009). Matheuristics: Optimization, Simulation and Control. Hybrid Metaheuristics....
  • Garlick, R.M.,Barr, R.S.. (2002). Dynamic wavelength routing in WDM networks via ant colony optimization. Ant Algorithms, Lecture Notes in...
  • Walkowiak, K.. (2005). Ant algorithm for flow assignment in connection-oriented networks. International Journal on Applied Mathematics and...
  • Maniezzo, V.,Roffilli, M.,Gabrielli, R.,Guidazzi, A.,Otero, M.,Trujillo, R.. (2008). Regional Traffic Assignment by ACO. Ant Colony Optimization...
  • Mohan, C.,Baskaran, R.. (2010). Improving network performance using ACO based redundant link avoidance algorithm. International Journal of...
  • Sawadogo, M.,Anciaux, D.. (2012). Sustainable supply chain by intermodal itinerary planning: a multiobjective ant colony approach. International...
  • Dorigo, M.,Gambardella, L.M.. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transaction...
  • Maniezzo, V.. (1999). Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS Journal...
  • Eppstein, D.. (1998). Finding the k Shortest Paths. SIAM Journal on Computing. 28. 652-673
  • Awerbuch, B.,Leighton, T.. (1993). A Simple local-control approximation algorithm for multicommodity flow. 34th Annual Symposium on Foundations...
  • Di Caro, G.,Dorigo, M.. (1998). AntNet: distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research....
  • Burke, E.,Kendall, G.,Newall, J.,Hart, E.,Ross, P.,Schulenburg, S.. (2003). Hyper-heuristics: An emerging direction in modern search technology....
  • Goldberg, D.E.. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Pub. Co. Reading^eMass. Mass..
  • COIN-OR Foundation.
  • Stützle, T.,Hoos, H.H.. (2000). MAX-MIN Ant System. Future Generation Computer Systems. 16. 88-914
  • Fernández, C.A.,Bolufé-Röhler, A.. (2011). XXV JCJuvenil. ICIMAF.