HEURISTIC METHODS FOR SOLVING STOCHASTIC USER EQUILIBRIUM TRAFFIC ASSIGNMENT PROBLEM

Abstract

In this study, a new solution algorithm based on heuristic methods is proposed in order to solve Stochastic User Equilibrium (SUE) traffic assignment problem. Ant Colony Optimization Stochastic Traffic Assignment (ACOSTA) and Harmony search Stochastic Traffic Assignment (HASTA) models which are formed using Ant Colony Optimization and Harmony Search, are used to solve the stochastic traffic assignment problem. In the proposed models, probit route choice model is used to represent driver’s behaviour. SUE assignment is also described as equivalent optimization problem. In order to illustrate applications of the proposed models, test network is used which has one Origin-Destination (O-D) pair, five links and three paths. Monte-Carlo simulation method is used to find probit route choice probabilities. Furthermore, the results of SUE assignment are compared with the Deterministic User Equilibrium (DUE). Numerical example showed that ACOSTA model has more advantages when it is compared with the HASTA model especially in terms of the value of objective function although it requires more CPU time according to HASTA model. Moreover, SUE assignment based probit route choice is more realistic in accordance with DUE assignment and it can be solved using heuristic methods.

Keywords

• Stochastic user equilibrium, Traffic assignment, Ant colony optimization, Harmony search, Probit choice model

STOKASTİK KULLANICI DENGESİ TRAFİK ATAMA PROBLEMİNİN SEZGİSEL METOTLAR KULLANILARAK ÇÖZÜLMESİ

Abstract

Bu çalışmada Stokastik Kullanıcı Dengesi (SKD) trafik atama probleminin çözümü için sezgisel metot tabanlı yeni bir çözüm algoritması önerilmiştir. Karınca Kolonisi Optimizasyonu (KKO) ve Armoni Araştırması Tekniği (AAT) kullanılarak oluşturulan KArınca KOlonisi Stokastik Trafik Atama (KAKOSTA) ve ARmoni Araştırması Stokastik Trafik Atama (ARASTA) modelleri SKD trafik atama probleminin çözümünde kullanılmıştır. Geliştirilen modellerde, sürücülerin güzergah seçim davranışları probit güzergah seçim modeli kullanılarak temsil edilmekte ve SKD problemi, eşdeğer optimizasyon problemi olarak tanımlanmaktadır. Önerilen modellerin test edilmesi için 1 adet Başlangıç-Varış (B-V) çifti, 5 adet bağ ve 3 adet güzergâhtan oluşan ulaşım ağı verilmiştir. Probit güzergah seçim olasılıklarının bulunabilmesi için Monte-Carlo simülasyon tekniğinden faydalanılmıştır. Ayrıca SKD atamasının sonuçları Deterministik Kullanıcı Dengesi (DKD) ataması sonuçları ile karşılaştırılmıştır. Sayısal uygulama sonucunda, SKD probleminin çözümünde ARASTA modeli hesaplama süresi açısından KAKOSTA modeline göre avantajlı olmasına rağmen KAKOSTA modelinin amaç fonksiyonunun en küçüklenmesinde daha başarılı olduğu görülmüştür. Ayrıca probit tabanlı SKD ataması ile elde edilen sonuçların gerçek sürücü davranışlarının modellenmesinde DKD atamasına göre daha gerçekçi olduğu ve probit tabanlı SKD probleminin sezgisel metotlar kullanılarak çözülebildiği görülmektedir

Keywords

• Stokastik kullanıcı dengesi, Trafik atama, Karınca kolonisi optimizasyonu, Armoni araştırması tekniği, Probit seçim model

References

1. Başkan Ö. (2009): “Karınca Kolonisi Optimizasyonu ile Ulaşım Ağ Tasarımı”, Pamukkale Üniversitesi, Fen Bilimleri Enstitüsü, Doktora Tezi, s. 140.
2. Başkan O., Haldenbilen S., Ceylan H., Ceylan H. (2009): “A New Solution Algorithm for Improving Performance of Ant Colony Optimization”, Applied Mathematics and Computation, 211 (1), s. 75-84.
3. Beckmann M. J., McGuire C. B., Winsten C. B. (1956): “Studies in the Economics of Transportation”, Yale University Press, New Haven, Conn.
4. Bell M. G. H., Lida Y. (1997): “Transportation Network Analysis”, John Wiley and Sons, Chichester, UK.
5. Bell M. G. H., Shield, C. M., Busch F., Kruse G. (1997): “A Stochastic User Equilibrium Path Flow Estimator”, Transportation Research Part C, 5, s. 1972-210.
6. Ceylan H. (2008): “Genetik Algoritma ve Oyun Teorisi Yaklaşımları ile Şehir İçi Trafik Yönetimi”, Tübitak Kariyer Projesi (104I119), 7. ara rapor, s. 58.
7. Ceylan H., Ceylan H. (2009): “Şehiriçi Karayolu Ağlarının Ayrık Tasarımında Sezgisel Armoni Araştırması Yöntemi Uygulaması”, İstanbul, 8. Ulaştırma Kongresi, s. 195-208.
8. Ceylan H., Ceylan H., Haldenbilen S., Baskan O. (2008): “Transport Energy Modeling with Meta–Heuristic Harmony Search Algorithm, an Application to Turkey”, Energy Policy 36, s. 2527-2535.

9. Chiou S. W. (2005): “Bilevel Programming for the Continuous Transport Network Design Problem”, Transportation Research Part B, 39, s. 361-383.
10. Colorni A., Dorigo M., Maniezzo V. (1991): “Distributed Optimization by Ant Colonies”, Paris, France, Proceedings of ECAL-European Conference on Artificial Life, s. 134-142.
11. Connors R. D., Sumalee A., Watling D. P. (2007): “Sensitivity Analysis of the Variable Demand Probit Stochastic User Equilibrium with Multiple User-Classes”, Transportation Research Part B, 41, s. 593-615.
12. D’Acierno L., Montella B., De Lucia F. (2006): “A Stochastic Traffic Assignment Algorithm Based on Ant Colony Optimization”, ANTS 2006, LNCS 4150, s. 25-36.
13. Daganzo C., Sheffi Y. (1977): “On Stochastic Models of Traffic Assignment”, Transportation Science, 11,s. 253-274.
14. Davis G. A. (1994): “Exact Local Solution of the Continuous Network Design Problem via Stochastic User Equilibrium Assignment”, Transportation Research Part B, 28, s. 61-75.
15. Denebourg J. L., Pasteels, J. M., Verhaeghe J. C. (1983): “Probabilistic Behavior in Ants: A Strategy of errors?”, Journal of Theoretical Biology, 10, s. 259-271.
16. Dial R. (1971): “A Probabilistic Multipath Traffic Assignment Algorithm which Obviates Path Enumeration”, Transportation Research 5 (2), s. 83–111.
17. Dorigo M., Di Caro G. (1999): “Ant Colony Optimization: A New Meta-Heuristic”, In: Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 2, s. 1470-1477.
18. Dorigo M. (1992): “Optimization, Learning and Natural Algorithms”, PhD Thesis, Politecnico di Milano, Italy.
19. Dorigo M., Stützle T. (2004): “Ant Colony Optimization”, Cambridge, MIT Press.
20. Geem Z. W. (2006): “Optimal Cost Design of Water Distribution Networks Using Harmony Search”, Engineering Optimization 38 (3), s. 259-280.
21. Geem Z. W., Kim J. H., Loganathan G. V. (2001): “A New Heuristic Optimization Algorithm: Harmony Search”, Simulation 76 (2), s. 60-68.
22. Han S. (2007): “A Route-Based Solution Algorithm for Dynamic User Equilibrium Assignments”, Transportation Research Part B, 41, s. 1094-1113.
23. Kim J. H., Geem Z. W., Kim E. S. (2001): “Parameter Estimation of the Nonlinear Muskingum Model using Harmony Search”, Journal of the American Water Resources Association 37 (5), s. 1131-1138.
24. Kuan S. N., Ong H. L., Ng K. M. (2006): “Solving the Feeder Bus Network Design Problem by Genetic Algorithms and Ant Colony Optimization”, Advances in Engineering Software, 37, s. 351-359.
25. Lee K. S., Geem Z. W., Lee S. H., Bae K. W. (2005): “The Harmony Search Heuristic Algorithm for Discrete Structural Optimization”, Engineering Optimization, 37 (7), s. 663-684.
26. Maher M. J., Hughes P. C. (1997): “A Probit-Based Stochastic User Equilibrium Assignment Model”, Transportation Research Part B, 31, s. 341-355.
27. Matteuchi M., Mussone L. (2006): “Ant Colony Optimization Technique for Equilibrium Assignment in Congested Transportation Networks”, Washington, USA, Proceedings of the 8th annual conference on Genetic and evolutionary computation,s. 87-88.
28. Oppenheim N. (1995): “Urban Travel Demand Modeling: From Individual Choices to General Equilibrium”, New York, John Wiley and Sons, Inc.
29. Prashker J. N., Bekhor S. (1998): “Investigation of Stochastic Network Loading Procedures”, Transportation Research Record, 1645, s. 94-102.
30. Poorzahedy H., Abulghsami F. (2005): “Application of Ant System to Network Design Problem”, Transportation, 32, s. 251-273.
31. Saka M. P. (2009): “Optimum Design of Steel Sway Frames to BS5950 Using Harmony Search Algorithm”, J. of Constr. Steel Research 65 (1), s. 36-43.
32. Sheffi Y. (1985): “Urban Transport Networks: Equilibrium Analysis with Mathematical Programming Methods”, New Jersey, USA, Prentice-Hall Inc., Englewood Cliffs.
33. Wardrop J. G. (1952): “Some Theoretical Aspects of Road Traffic Research”, Proceedings of the Institute of Civil Engineers. Part II, 1 (2), s. 325-378.