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

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.

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.