Solution of Traveling Salesman Problem on Traffic Congestion with Ant Colony Optimization and Beam Ant Colony Optimization Algorithms

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 from logistics routes to microchip manufacturing. Also, it can be used on DNA sequencing with slight modification as a sub-problem. In this thesis, 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.

Gezgin Satıcı Problemi (GSP), çeşitli endüstrilerde çeşitli etkileri olan, iyi bilinen bir kombinatoryal optimizasyon problemidir. GSP'nin en saf formülasyonunun bile lojistik yollardan mikroçip üretimine kadar birçok uygulaması vardır. Beklenmedik bir şekilde DNA dizilemesinde, ufak bir modifikasyonla alt problem olarak kullanılabilmektedir. Bu yazıda GSP'nin iki versiyonu incelenmiştir; klasik TSP ve trafik sıkışıklığı verilerini içeren GSP. Karınca Kolonisi Optimizasyonu (KKO) ve Beam-ACO olmak üzere son teknoloji ürünü iki çözüm yöntemi kullanıldı. Bu algoritmalar 2-Opt yerel aramayla hibritleştirildi ve performansları aynı kıyaslama örnekleriyle karşılaştırıldı. Deneysel sonuçlar Beam-ACO'nun KKO'ya kıyasla verimliliğini göstermektedir.