2-OPT ALGORİTMASI VE BAŞLANGIÇ ÇÖZÜMÜNÜN ALGORİTMA SONUÇLARI ÜZERİNDEKİ ETKİSİ

Yıl 2016, Cilt: 27 Sayı: 3, 2 - 12, 23.09.2016

Timur Keskintürk , Barış Kiremitci Serap Kiremitci

Öz

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.

Anahtar Kelimeler

2-opt algoritması, gezgin satıcı problemi, sezgisel

2-OPT ALGORITHM AND EFFECTS OF INITIAL SOLUTION ON RESULTS

Öz

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.

Anahtar Kelimeler

2-opt algorithm, travelling salesman problem, heuristic

Kaynakça

• 1. Biggs, N. L., LIyod, E. K., Wilson, R. J. 1976. Graph Theory, Clarendon Press, Oxford.
• 2. Blazinskas, A., Misevicius, A. 2011. “Combining 2-opt, 3-opt And 4-Opt with K-Swap-Kick Perturbations for the Traveling Salesman Problem,” Information Technologies' 2011: Proceedings of the 17th international Conference on Information and Software Technologies, (Eds. R. Butleris, R. Butkiene), 27-29 April 2011, Kaunas, Lithuania, Kaunas University of Technology, Technologija, Kaunas, p. 45-50.
• 3. Croes, G. A. 1958. “A Method for Solving Traveling-Salesman Problems,” Operations Research, vol. 6 (6), p. 791-812.
• 4. Dantzig, G., Fulkerson, R., Johnson, S. 1954. “Solution of a Large-Scale Travelling-Salesman Problem,” Journal of the Operations Research Society of America, vol. 2 (4), p. 393-410.
• 5. Flood, M. 1956. “The Traveling-Salesman Problem,” Operations Research, vol. 4 (1), p. 61-75.
• 6. Fortini, M. 2007. “LP-Based Heuristics for the Traveling Salesman Problem,” Doctoral Dissertation, Bologna University, Bologna.
• 7. Gutin, G., Punnen, A. P. 2002. The Traveling Salesman Problem and its Variations, Springer Science & Business Media, Chicago.
• 8. Jevtic, A. 2014. http://www.mathworks.com/matlabcentral/fileexchange/25542-nearest-neighbor-algorithm-for-the-travelling-salesman-problem/content/nn_tsp.m, son erişim tarihi: 11.09.2015.
• 9. Johnson, D. S., Lyle, A. McGeoch. 1997. "The Traveling Salesman Problem: A Case Study in Local Optimization," Local Search in Combinatorial Optimization, vol. 1, p. 215-310.
• 10. Karayolları Genel Müdürlüğü. 2014. http://www.kgm.gov.tr /SiteCollection Documents/KGMdocuments/Root/Uzakliklar/ ilmesafe.xls, son erişim tarihi: 10.05.2014.
• 11. Karp, R. M. 1972. “Reducibility among Combinatorial Problems,” In Miller, R. E., Thatcher, J. W. (Eds.), Complexity of Computer Computations, Plenum Press, New York.
• 12. Kuzu, S., Önay, O., Şen, U., Tunçer, M., Yıldırım, B. F., Keskintürk, T. 2014. “Gezgin Satıcı Problemlerinin Metasezgiseller ile Çözümü,” İstanbul Üniversitesi İşletme Fakültesi Dergisi, sayı 43 (1), s. 1-27.
• 13. Lin, S. 1965. “Computer Solutions of the Traveling Salesman Problem,” Bell System Technical Journal, vol. 44 (10), p. 2245–2269.
• 14. Nilsson, C. 2003. “Heuristics for the Traveling Salesman Problem,” Tech. Report, Linköping University, Sweden.
• 15. Önder, E., Özdemir, M., Yıldırım, B. F. 2013. “Combinatorial Optimization Using Artificial Bee Colony Algorithm and Particle Swarm Optimization Supported Genetic Algorithm,” Kafkas University, Journal of Economics and Administrative Sciences Faculty, vol. 4 (6).
• 16. Reinelt, G. 1995. “TSPLIB95,” http://www.iwr.uni-heidelberg.de/groups/comopt/software/ TSPLIB95/tsp/, son erişim tarihi: 10.01.2015.
• 17. Verhoeven, M. G., Aarts, E. H., Swinkels, P. C. 1995. “A Parallel 2-opt Algorithm for the Traveling Salesman Problem,” Future Generation Computer Systems, vol. 11 (2), p. 175-182.