IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v217y2012i2p459-469.html
   My bibliography  Save this article

An Ant Colony Optimisation algorithm for solving the asymmetric traffic assignment problem

Author

Listed:
  • D’Acierno, Luca
  • Gallo, Mariano
  • Montella, Bruno

Abstract

In this paper we propose an Ant Colony Optimisation (ACO) algorithm for defining the signal settings on urban networks following a local approach. This consists in optimising the signal settings of each intersection of an urban network as a function only of traffic flows at the accesses to the same intersection, taking account of the effects of signal settings on costs and on user route choices. This problem, also known as Local Optimisation of Signal Settings (LOSS), has been widely studied in the literature and can be formulated as an asymmetric assignment problem. The proposed ACO algorithm is based on 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 real-scale networks show that the proposed approach allows the solution to be obtained in less time but with the same accuracy as in traditional MSA (Method of Successive Averages) approaches.

Suggested Citation

  • D’Acierno, Luca & Gallo, Mariano & Montella, Bruno, 2012. "An Ant Colony Optimisation algorithm for solving the asymmetric traffic assignment problem," European Journal of Operational Research, Elsevier, vol. 217(2), pages 459-469.
    • Handle: RePEc:eee:ejores:v:217:y:2012:i:2:p:459-469
    DOI: 10.1016/j.ejor.2011.09.035
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711008630
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.09.035?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yang, Hai & Yagar, Sam, 1995. "Traffic assignment and signal control in saturated road networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 29(2), pages 125-139, March.
    2. Han, Bin, 1996. "Optimising traffic signal settings for periods of time-varying demand," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(3), pages 207-230, May.
    3. Carlos F. Daganzo, 1983. "Stochastic Network Equilibrium with Multiple Vehicle Types and Asymmetric, Indefinite Link Cost Jacobians," Transportation Science, INFORMS, vol. 17(3), pages 282-300, August.
    4. Ennio Cascetta, 2009. "Transportation Systems Analysis," Springer Optimization and Its Applications, Springer, number 978-0-387-75857-2, September.
    5. Wong, S. C. & Yang, Hai, 1997. "Reserve capacity of a signal-controlled road network," Transportation Research Part B: Methodological, Elsevier, vol. 31(5), pages 397-402, October.
    6. Abu-Lebdeh, Ghassan & Benekohal, Rahim F., 2003. "Design and evaluation of dynamic traffic management strategies for congested conditions," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(2), pages 109-127, February.
    7. M. J. Smith & T. van Vuren, 1993. "Traffic Equilibrium with Responsive Traffic Control," Transportation Science, INFORMS, vol. 27(2), pages 118-132, May.
    8. Stella Dafermos, 1980. "Traffic Equilibrium and Variational Inequalities," Transportation Science, INFORMS, vol. 14(1), pages 42-54, February.
    9. Hossain Poorzahedy & Farhad Abulghasemi, 2005. "Application of Ant System to network design problem," Transportation, Springer, vol. 32(3), pages 251-273, May.
    10. Smith, M. J., 1981. "Properties of a traffic control policy which ensure the existence of a traffic equilibrium consistent with the policy," Transportation Research Part B: Methodological, Elsevier, vol. 15(6), pages 453-462, December.
    11. Giulio Erberto Cantarella, 1997. "A General Fixed-Point Approach to Multimode Multi-User Equilibrium Assignment with Elastic Demand," Transportation Science, INFORMS, vol. 31(2), pages 107-128, May.
    12. Patrice Marcotte, 1983. "Network Optimization with Continuous Control Parameters," Transportation Science, INFORMS, vol. 17(2), pages 181-197, May.
    13. Sheffi, Yosef & Powell, Warren, 1981. "A comparison of stochastic and deterministic traffic assignment over congested networks," Transportation Research Part B: Methodological, Elsevier, vol. 15(1), pages 53-64, February.
    14. Lo, Hong K. & Chang, Elbert & Chan, Yiu Cho, 2001. "Dynamic network traffic control," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(8), pages 721-744, September.
    15. Florian, Michael & Spiess, Heinz, 1982. "The convergence of diagonalization algorithms for asymmetric network equilibrium problems," Transportation Research Part B: Methodological, Elsevier, vol. 16(6), pages 477-483, December.
    16. Chang, Tang-Hsien & Lin, Jen-Ting, 2000. "Optimal signal timing for an oversaturated intersection," Transportation Research Part B: Methodological, Elsevier, vol. 34(6), pages 471-491, August.
    17. Gallo, Mariano & D'Acierno, Luca & Montella, Bruno, 2010. "A meta-heuristic approach for solving the Urban Network Design Problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 144-157, February.
    18. Wong, C. K. & Wong, S. C., 2003. "Lane-based optimization of signal timings for isolated junctions," Transportation Research Part B: Methodological, Elsevier, vol. 37(1), pages 63-84, January.
    19. Suh-Wen Chiou, 1999. "Optimization of Area Traffic Control for Equilibrium Network Flows," Transportation Science, INFORMS, vol. 33(3), pages 279-289, August.
    20. Pillai, Rekha S. & Rathi*, Ajay K. & L. Cohen, Stephen, 1998. "A restricted branch-and-bound approach for generating maximum bandwidth signal timing plans for traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 517-529, November.
    21. Stella Dafermos, 1982. "Relaxation Algorithms for the General Asymmetric Traffic Equilibrium Problem," Transportation Science, INFORMS, vol. 16(2), pages 231-240, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Castillo González, Rodrigo & Clempner, Julio B. & Poznyak, Alexander S., 2019. "Solving traffic queues at controlled-signalized intersections in continuous-time Markov games," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 166(C), pages 283-297.
    2. Qiuchi Xue & Xin Yang & Jianjun Wu & Huijun Sun & Haodong Yin & Yunchao Qu, 2019. "Urban Rail Timetable Optimization to Improve Operational Efficiency with Flexible Routing Plans: A Nonlinear Integer Programming Model," Sustainability, MDPI, vol. 11(13), pages 1-26, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ennio Cascetta & Mariano Gallo & Bruno Montella, 2006. "Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment models," Annals of Operations Research, Springer, vol. 144(1), pages 301-328, April.
    2. Castillo González, Rodrigo & Clempner, Julio B. & Poznyak, Alexander S., 2019. "Solving traffic queues at controlled-signalized intersections in continuous-time Markov games," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 166(C), pages 283-297.
    3. Evers, Ruth & Proost, Stef, 2015. "Optimizing intersections," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 100-119.
    4. Meneguzzer, Claudio, 1995. "An equilibrium route choice model with explicit treatment of the effect of intersections," Transportation Research Part B: Methodological, Elsevier, vol. 29(5), pages 329-356, October.
    5. Guo, Jianhua & Kong, Ye & Li, Zongzhi & Huang, Wei & Cao, Jinde & Wei, Yun, 2019. "A model and genetic algorithm for area-wide intersection signal optimization under user equilibrium traffic," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 155(C), pages 92-104.
    6. Gallo, Mariano & D'Acierno, Luca & Montella, Bruno, 2010. "A meta-heuristic approach for solving the Urban Network Design Problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 144-157, February.
    7. D E Boyce, 1984. "Urban Transportation Network-Equilibrium and Design Models: Recent Achievements and Future Prospects," Environment and Planning A, , vol. 16(11), pages 1445-1474, November.
    8. Elnaz Miandoabchi & Reza Farahani & Wout Dullaert & W. Szeto, 2012. "Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks," Networks and Spatial Economics, Springer, vol. 12(3), pages 441-480, September.
    9. Liu, Ronghui & Smith, Mike, 2015. "Route choice and traffic signal control: A study of the stability and instability of a new dynamical model of route choice and traffic signal control," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 123-145.
    10. Smith, Mike & Mounce, Richard, 2011. "A splitting rate model of traffic re-routeing and traffic control," Transportation Research Part B: Methodological, Elsevier, vol. 45(9), pages 1389-1409.
    11. Lee, Seunghyeon & Wong, S.C. & Varaiya, Pravin, 2017. "Group-based hierarchical adaptive traffic-signal control part I: Formulation," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 1-18.
    12. Lee, Seunghyeon & Wong, S.C., 2017. "Group-based approach to predictive delay model based on incremental queue accumulations for adaptive traffic control systems," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 1-20.
    13. Elnaz Miandoabchi & Reza Farahani & W. Szeto, 2012. "Bi-objective bimodal urban road network design using hybrid metaheuristics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(4), pages 583-621, December.
    14. Khooban, Zohreh & Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y., 2015. "Mixed network design using hybrid scatter search," European Journal of Operational Research, Elsevier, vol. 247(3), pages 699-710.
    15. Massimo Gangi & Giulio E. Cantarella & Antonino Vitetta, 2019. "Solving stochastic frequency-based assignment to transit networks with pre-trip/en-route path choice," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 661-681, December.
    16. Simone Baldi & Iakovos Michailidis & Vasiliki Ntampasi & Elias Kosmatopoulos & Ioannis Papamichail & Markos Papageorgiou, 2019. "A Simulation-Based Traffic Signal Control for Congested Urban Traffic Networks," Service Science, INFORMS, vol. 53(1), pages 6-20, February.
    17. Gao, Ziyou & Sun, Huijun & Shan, Lian Long, 2004. "A continuous equilibrium network design model and algorithm for transit systems," Transportation Research Part B: Methodological, Elsevier, vol. 38(3), pages 235-250, March.
    18. Les Foulds & Daniel Duarte & Hugo Nascimento & Humberto Longo & Bryon Hall, 2014. "Turning restriction design in traffic networks with a budget constraint," Journal of Global Optimization, Springer, vol. 60(2), pages 351-371, October.
    19. Fan, Yinchao & Ding, Jianxun & Liu, Haoxiang & Wang, Yu & Long, Jiancheng, 2022. "Large-scale multimodal transportation network models and algorithms-Part I: The combined mode split and traffic assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    20. Connors, Richard D. & Sumalee, Agachai & Watling, David P., 2007. "Sensitivity analysis of the variable demand probit stochastic user equilibrium with multiple user-classes," Transportation Research Part B: Methodological, Elsevier, vol. 41(6), pages 593-615, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:217:y:2012:i:2:p:459-469. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.