AI Summary & Key Takeaways
AI InsightSince this algorithm has not yet been studied in the Turkish literature this study will fill a gap on this topic.
📌 3 Key Takeaways
Abstract
In this study the 2-opt heuristic algorithm which was proposed by Croes (1958) for the travelling salesman problem is presented and the effect of the initial solutions produced by constructive heuristics on the performance of the algorithm is analyzed. The algorithm is based on a local search that works with the logic of removing two edges from the current solution and merging the two parts in a different way. After trying all possible changes the result is considered a 2-optimal solution. The initial tour could be either a randomly created tour or a result of any other heuristics. In this work the best initial tour by the heuristics has also been studied. The algorithm has been tested on different benchmark problems and these results have been analyzed. Since this algorithm has not yet been studied in the Turkish literature this study will fill a gap on this topic.
Özet
Bu çalışmada, gezgin satıcı problemlerinin çözümü için Croes (1958) tarafından önerilen 2-opt algoritması tanıtılmış ve tur oluşturan sezgisellerle üretilen başlangıç çözümlerinin, algoritmanın performansı üzerindeki etkileri incelenmiştir. Yerel arama mantığı ile çalışan algoritma, turdaki iki kenarın turdan çıkarılması ve kalan kısımların farklı şekilde birbirlerine bağlanması şeklinde iyileştirmeler yapmaktadır. Tüm mümkün değişikliklerin yapılmasından sonra elde edilen çözüm, 2-optimal olarak adlandırılmaktadır. Başlangıç çözümü tesadüfi olarak üretilen bir tur olabileceği gibi, farklı sezgisellerin ürettiği turlar da kullanılabilir. Çalışmada ayrıca, hangi başlangıç çözümünün 2-opt algoritmasının sonuçlarını iyileştirdiği de araştırılmıştır. Algoritma, farklı problemler üzerinde denenmiş, elde edilen sonuçlar da karşılaştırmalı olarak raporlanmıştır. Türkçe literatürde daha önce ele alınmamış olan algoritmanın detaylı anlatımıyla, anadili Türkçe olan araştırmacılar için bir boşluğu doldurması umulmuştur.