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

Yıl 2024, , 519 - 527, 27.09.2024

Mustafa Orçun Uslu , Kazım Erdoğdu

https://doi.org/10.21205/deufmd.2024267820

Öz

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.

Anahtar Kelimeler

Traveling Salesman Problem, Ant Colony Optimization, Beam-ACO, 2-Opt, Swarm Intelligence Optimization, Traffic Congestion

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

Öz

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.

Anahtar Kelimeler

Gezgin Satıcı Problemi, Karınca Kolonisi Optimizasyonu, Beam-KKO, 2-Opt, Sürü Zekası Optimizasyonu, Trafik Sıkışıklığı

Kaynakça

• [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.