SavedAdd your journal

Journals / Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi / 2024 / Cilt: 26 Sayı: 78

Ant Colony Optimization and Beam-Ant Colony Optimization on Traveling Salesman Problem with Traffic Congestion

Trafik Sıkışıklığı Olan Gezgin Satıcı Probleminde Karınca Kolonisi Optimizasyonu ve Işın-Karınca Kolonisi Optimizasyonu

Mustafa Orçun Uslu(Yasar University)0009-0004-8579-6833
Kazım Erdoğdu(YASAR UNIVERSITY)0000-0001-6256-3114
Pages
519–527
Publication Date
2024-09-27
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The experimental results show the efficiency of Beam-ACO compared to ACO.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem that has various implications in a variety of industries.
📊
Key Findings & Data:These algorithms were hybridized with 2-Opt local search and their performances compared on the same benchmark instances.
💡
Conclusion & Impact:The experimental results show the efficiency of Beam-ACO compared to ACO.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Gezgin Satıcı Problemi · Karınca Kolonisi Optimizasyonu · Beam-KKO

Abstract

The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem that has various implications in a variety of industries. Even the purest formulation of TSP has applications on from logistics routes to microchip manufacturing, unexpectedly, it can be used on DNA sequencing with slight modification as a sub-problem. In this paper, two versions of TSP were studied, a classical TSP and the TSP containing traffic congestion data. Two state-of-the-art solution methods were used, Ant Colony Optimization (ACO) and Beam-ACO. These algorithms were hybridized with 2-Opt local search and their performances compared on the same benchmark instances. The experimental results show the efficiency of Beam-ACO compared to ACO.

Özet

Gezgin Satıcı Problemi (GSP), çeşitli endüstrilerde çeşitli etkileri olan, iyi bilinen bir kombinatoryal optimizasyon problemidir. GSP'nin en saf formülasyonu bile lojistik yollardan mikroçip üretimine kadar çeşitli uygulamalara sahiptir. Beklenmedik bir şekilde, bir alt problem olarak DNA dizilimi için küçük değişikliklerle kullanılabilir. Bu yazıda GSP'nin iki versiyonu incelenmiştir: klasik bir TSP ve trafik sıkışıklığı verilerini içeren GSP. Son teknoloji ürünü iki çözüm yöntemi kullanıldı: Karınca Kolonisi Optimizasyonu (KKO) ve Işın-KKO. Bu algoritmalar 2-Opt yerel arama ile hibritleştirildi ve performansları aynı kıyaslama örnekleriyle karşılaştırıldı. Deney sonuçları Işın-KKO'nun KKO'ya kıyasla verimliliğini göstermektedir.

🔖

Cite This Article

Uslu, M. O., Erdoğdu, K. (2024). Ant Colony Optimization and Beam-Ant Colony Optimization on Traveling Salesman Problem with Traffic Congestion. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi, Cilt: 26 Sayı: 78, 519–527. https://doi.org/10.21205/deufmd.2024267820

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (25)

  1. G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, no. 2, pp. 231–247, Jun. 1992, doi: 10.1016/0377-2217(92)90138-Y.
  2. S. H. Rubin, T. Bouabana-Tebibel, Y. Hoadjli, and Z. Ghalem, “Reusing the NP-Hard Traveling-Salesman Problem to Demonstrate That P~NP (Invited Paper),” in 2016 IEEE 17th International Conference on Information Reuse and Integration (IRI), Pittsburgh, PA, USA: IEEE, Jul. 2016, pp. 574–581. doi: 10.1109/IRI.2016.84.
  3. Y. S. Chang and H. J. Lee, “Optimal delivery routing with wider drone-delivery areas along a shorter truck-route,” Expert Systems with Applications, vol. 104, pp. 307–317, Aug. 2018, doi: 10.1016/j.eswa.2018.03.032.
  4. C. H. Cheng, Y. P. Gupta, W. H. Lee, and K. F. Wong, “A TSP-based heuristic for forming machine groups and part families,” International Journal of Production Research, vol. 36, no. 5, pp. 1325–1337, May 1998, doi: 10.1080/002075498193345.
  5. V. Shinkarenko, S. Nezdoyminov, S. Galasyuk, and L. Shynkarenko, “Optimization of the tourist route by solving the problem of a salesman,” Journ. Geol., Geogr., and Geoec., vol. 29, no. 3, pp. 572–579, Oct. 2020, doi: 10.15421/112052.
  6. E. Duman, M. H. Ozcelik, and A. N. Ceranoglu, “A TSP (1,2) application arising in cable assembly shops,” Journal of the Operational Research Society, vol. 56, no. 6, pp. 642–648, Jun. 2005, doi: 10.1057/palgrave.jors.2601850.
  7. A. Meijer, M. A. J. Huijbregts, E. Hertwich, and L. Reijnders, “Including human health damages due to road traffic in life cycle assessment of dwellings,” Int. J. Life Cycle Assess., vol. 11, pp. 64–71, Apr. 2006, doi: 10.1065/lca2006.04.013.
  8. A. Colorni, M. Dorigo, and V. Maniezzo, “An Investigation of Some Properties of an Ant Algorithm,” in PARALLEL PROBLEM SOLVING FROM NATURE, 2, R. Manner and B. Manderick, Eds., Amsterdam: Elsevier Science Publ B V, 1992, pp. 509–520. Accessed: Nov. 20, 2023. [Online]. Available: https://www.webofscience.com/wos/woscc/full-record/WOS:A1992BX92H00051(overlay:export/exp)
  9. A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed Optimization by Ant Colonies,” in TOWARD A PRACTICE OF AUTONOMOUS SYSTEMS: PROCEEDINGS OF THE FIRST EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, F. Varela and P. Bourgine, Eds., Cambridge: M I T Press, 1992, pp. 134–142. Accessed: Nov. 20, 2023. [Online]. Available: https://www.webofscience.com/wos/woscc/full-record/WOS:A1992BW87V00017
  10. M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, Apr. 1997, doi: 10.1109/4235.585892.
  11. “MAX–MIN Ant System - ScienceDirect.” Accessed: Nov. 20, 2023. [Online]. Available: https://www.sciencedirect.com/science/article/abs/pii/S0167739X00000431?via%3Dihub
  12. S.-C. Chu, J. F. Roddick, and J.-S. Pan, “Ant colony system with communication strategies,” Information Sciences, vol. 167, no. 1, pp. 63–76, Dec. 2004, doi: 10.1016/j.ins.2003.10.013.
  13. X.-M. Hu, J. Zhang, and Y. Li, “Orthogonal Methods Based Ant Colony Search for Solving Continuous Optimization Problems,” J. Comput. Sci. Technol., vol. 23, no. 1, pp. 2–18, Jan. 2008, doi: 10.1007/s11390-008-9111-5.
  14. D. K. Gupta, Y. Arora, U. K. Singh, and J. P. Gupta, “Recursive Ant Colony Optimization for estimation of parameters of a function,” in 2012 1st International Conference on Recent Advances in Information Technology (RAIT), Mar. 2012, pp. 448–454. doi: 10.1109/RAIT.2012.6194620.
  15. “Speech Understanding Systems. Summary of Results of the Five-Year Research Effort at Carnegie-Mellon University.” Accessed: Dec. 21, 2023. [Online]. Available: https://apps.dtic.mil/sti/citations/ADA049288
  16. R. Bisiani, “Beam search,” Encyclopedia of Artificial Intelligence. Wiley & Sons, pp. 56–58, 1987.
  17. C. Blum, “Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling,” Computers & Operations Research, vol. 32, no. 6, pp. 1565–1591, Jun. 2005, doi: 10.1016/j.cor.2003.11.018.
  18. J. L. Caldeira, R. C. Azevedo, C. A. Silva, and J. M. C. Sousa, “Supply-Chain Management Using ACO and Beam-ACO Algorithms,” in 2007 IEEE International Fuzzy Systems Conference, Jul. 2007, pp. 1–6. doi: 10.1109/FUZZY.2007.4295615.
  19. C. Blum, “Beam-ACO for Simple Assembly Line Balancing,” INFORMS J. Comput., vol. 20, no. 4, pp. 618–627, FAL 2008, doi: 10.1287/ijoc.1080.0271.
  20. M. Lopez-Ibanez, C. Blum, D. Thiruvady, A. T. Ernst, and B. Meyer, “Beam-ACO Based on Stochastic Sampling for Makespan Optimization Concerning the TSP with Time Windows,” in EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, PROCEEDINGS, C. Cotta and P. Crowling, Eds., Berlin: Springer-Verlag Berlin, 2009, pp. 97-+. Accessed: Nov. 20, 2023. [Online]. Available: https://www.webofscience.com/wos/woscc/full-record/WOS:000265680900009
  21. M. López-Ibáñez and C. Blum, “Beam-ACO for the travelling salesman problem with time windows,” Computers & Operations Research, vol. 37, no. 9, pp. 1570–1583, Sep. 2010, doi: 10.1016/j.cor.2009.11.015.
  22. L. F. Simões, D. Izzo, E. Haasdijk, and A. E. Eiben, “Multi-rendezvous Spacecraft Trajectory Optimization with Beam P-ACO,” in Evolutionary Computation in Combinatorial Optimization, B. Hu and M. López-Ibáñez, Eds., in Lecture Notes in Computer Science. Cham: Springer International Publishing, 2017, pp. 141–156. doi: 10.1007/978-3-319-55453-2_10.
  23. [T. Fei et al., “Research on improved ant colony optimization for traveling salesman problem,” MBE, vol. 19, no. 8, pp. 8152–8186, 2022, doi: 10.3934/mbe.2022381.
  24. G. A. Croes, “A Method for Solving Traveling-Salesman Problems,” Operations Research, vol. 6, no. 6, pp. 791–812, Dec. 1958, doi: 10.1287/opre.6.6.791.
  25. V. Shinkarenko, S. Nezdoyminov, S. Galasyuk, and L. Shynkarenko, “Optimization of the tourist route by solving the problem of a salesman,” Journ. Geol., Geogr., and Geoec., vol. 29, no. 3, pp. 572–579, Oct. 2020, doi: 10.15421/112052.