Differential Evolution Algorithm Based Solution Approaches for Solving Transportation Network Design Problems

Abstract

Differential Evolution algorithm has effectively been used to solve engineering optimization problems recently. The Differential Evolution algorithm, which uses similar principles with Genetic Algorithms, is more robust on obtaining optimal solution than many other heuristic algorithms with its simpler structure. In this study, Differential Evolution algorithm is applied to the transportation network design problems and its effectiveness on the solution is investigated. In this context, Differential Evolution based models are developed using bi-level programming approach for the solution of the transportation network design problem and determination of the on-street parking places in urban road networks. In these models, optimal investment and parking strategies are investigated on the upper level. On the lower level, deterministic traffic assignment problem, which represents drivers' responses, is solved using Frank-Wolfe algorithm and VISUM traffic modeling software. In order to determine the effectiveness of the proposed models, numerical applications are carried out on Sioux-Falls test network. Results showed that the Differential Evolution algorithm may effectively been used for the solution of transportation network design problems.

Keywords

• Differential evolution, Transportation network design, Bi-level programming.

Ulaşım Ağ Tasarımı Problemlerinin Çözümünde Diferansiyel Gelişim Algoritması Tabanlı Çözüm Yaklaşımları

Öz

Diferansiyel Gelişim Algoritması son yıllarda mühendislik optimizasyon problemlerinin çözümünde etkin olarak kullanılan bir yöntem olarak karşımıza çıkmaktadır. Temel olarak Genetik Algoritma tekniğine benzer çalışma prensibine sahip olan Diferansiyel Gelişim algoritması, diğer sezgisel algoritmalara oranla yapısal olarak daha basit olmasına karşın optimum değerlere ulaşmada daha kararlı bir yöntemdir. Bu çalışmada, Diferansiyel Gelişim Algoritması ulaşım ağ tasarımı problemlerine uygulanmakta ve çözüm üzerindeki etkinliği incelenmektedir. Bu kapsamda, Birleştirilmiş Ulaşım Ağ Tasarımı ve kentiçi karayolu ağlarındaki yol kenarı park yerlerinin belirlenmesi problemlerinin çözümü için iki seviyeli programlama yaklaşımı altında DG algoritması tabanlı modeller geliştirilmiştir. Bu modellerde, üst seviyede optimum yatırım ve parklanma stratejileri araştırılırken, alt seviyede sürücü reaksiyonlarını temsil eden Deterministik Trafik Atama problemi Frank-Wolfe algoritması ve VISUM trafik modelleme yazılımı kullanılarak çözülmüştür. Önerilen modellerin etkinliklerinin belirlenmesi amacıyla Sioux-Falls test ağı üzerinde sayısal uygulamalar gerçekleştirilmiştir. Elde edilen sonuçlar Diferansiyel Gelişim Algoritmasının ulaşım ağ tasarımı problemlerinin çözümünde etkin şekilde kullanılabileceğini göstermiştir. 

Anahtar Kelimeler

• Diferansiyel gelişim, Ulaşım ağ tasarımı, İki seviyeli programlama.

Kaynakça

1. Poorzahedy H, Turnquist MA. “Approximate Algorithm for the Discrete Network Design Problem”. Transportation Research Part B, 16(1), 45-55, 1982.
2. Heragu SS. Facilities Design. Boston, USA, PWS Publishing Company, 1997.
3. Pinedo ML. Scheduling Theory. Algorithms and Systems. 3rd ed. New York, USA, Springer Verlag LLC, 2008.
4. Poorzahedy H, Abulghasemi F. “Application of Ant System to 32, 251-273, 2005. Problem”. Transportation,
5. Poorzahedy H, Rouhani OM. “Hybrid Meta-Heuristic Algorithms for Solving Network Design Problem”. European Journal of Operational Research, 182, 578-596, 2007.
6. Luathep P, Sumalee A, William HKL, Li ZC, Lo HK. “Global Optimization Method for Mixed Transportation Network Design Problem: A Mixed-İnteger Linear Programming Approach”. Transportation Research Part B, 45(5), 808-827, 2011.
7. Ceylan H, Ceylan H. “A Hybrid Harmony Search and TRANSYT Hill Climbing Algorithm for Signalized Stochastic Transportation Research Part-C, 25, 152-167, 2012.
8. Ceylan H, “Optimal Design of Signal Controlled Road Networks Using Differential Evolution Optimization Algorithm”, Mathematical Problems in Engineering, 2013, 1-11, 2013.

9. Dell’Orco M, Baskan O, Marinelli M. “A Harmony Search Algorithm Approach for Optimizing Traffic Signal Timings”. Promet Traffic&Transportation, 25(4), 349-358, 2013.
10. Baskan O. “Determining
11. Optimal Link Capacity
12. Expansions in Road Networks Using Cuckoo Search
13. Algorithm with Levy Flights”. Journal of Applied
14. Mathematics, 2013, 1-11, 2013.
15. Baskan O. “Harmony Search Algorithm for Continuous Network Design Problem with Link Capacity Expansions”. KSCE Journal of Civil Engineering, 18(1), 273-283, 2014.
16. Shoup DC. “The Ideal Source of Public Revenue”. Regional Science and Urban Economics, 34(6), 753-784, 2004.
17. Yousif S, Purnawan. “Traffic Operations at On-Street Parking Facilities”. Proceedings of the Institution of Civil Engineers-Transport, 157(3), 189-194, 2004.
18. Portilla AI, Orena BA, Berodia JLM, Diaz FJR. “Using M/M/∞ Queuing Model in On-Street Parking Maneuvers”. Journal of Transportation Engineering, 135(8), 527-535, 2009.
19. Bruynooghe M. “An Optimal Method of Choice of Investments in a Transport Network”. Presentation, Planning&Transport Research & Computation Seminars on Urban Traffic Model Research, London, England, 1972.
20. LeBlanc LJ. “An Algorithm for the Discrete Network Design Problem”. Transportation Science, 9(3), 183-199, 1975.
21. Gao ZY, Wu JJ, Sun HJ. “Solution Algorithm for the Bi-Level Discrete Network Design Problem”. Transportation Research Part B, 39(6), 479-495, 2005.
22. Duthie J, Waller ST. “Incorporating Environmental Justice Measures into Equilibrium-Based Network Design”. Journal of the Transportation Research Board, 2089, 58-65, 2008.
23. Ceylan H, Ceylan H. “Şehiriçi Karayolu Ağlarının Sezgisel Harmoni Araştırması Optimizasyon Yöntemi ile Ayrık Tasarımı”. İMO Teknik Dergi, 24(1), 6211-6231, 2013.
24. Frank M, Wolfe P. “An Algorithm for Quadratic Programming”. Naval Research Logistics Quaterly, 3(1-2), 95-110, 1956.
25. Storn R, Price K. “Differential Evolution: A Simple and Efficient Adaptive Scheme for Global Optimization Over Continuous Spaces”. ICSI, USA, Technical Report, TR-95- 012, 1995.
26. Liu H, Cai Z, Wang Y. “Hybridizing Particle Swarm Optimization With Differential Evolution for Constrained Numerical and Engineering Optimization”. Applied Soft Computing, 10(2), 629-640, 2010.
27. Suwansirikul C, Friesz TL, Tobin RL. “Equilibrium Decomposed Optimisation: A Heuristic for the Continuous Equilibrium Network Design Problem”. Transportation Science, 21(4), 254-263, 1987.
28. Bureau of Public Roads. “Traffic Assignment Manual”. Department of Commerce, Washington DC, USA, 1964.