Gezgin satıcı  problemlerinin metasezgiseller ile çözümü

YILDIRIM, Bahadır Fatih; KESKİNTÜRK, Timur; Önay, Onur; ŞEN, Uğur; TUNCER, Mustafa; KUZU YILDIRIM, SULTAN

Gezgin satıcı problemlerinin metasezgiseller ile çözümü

SULTAN KUZU YILDIRIM, (İstanbul Üniversitesi)

Onur ÖNAY, (İstanbul Üniversitesi)

Uğur ŞEN, (İstanbul Üniversitesi)

Mustafa TUNCER, (İstanbul Üniversitesi)

Bahadır Fatih YILDIRIM, (İstanbul Üniversitesi)

Timur KESKİNTÜRK (İstanbul Üniversitesi)

İstanbul Üniversitesi İşletme Fakültesi Dergisi

6 2

Yıl: 2014 Cilt: 43 Sayı: 1 Sayfa Aralığı: 1 - 27 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

Gezgin satıcı problemlerinin metasezgiseller ile çözümü

Öz:

Bu çalışmada, NP-zor problem sınıfından olan gezgin satıcı probleminin (GSP), stokastik optimizasyon tekniklerinin en genel sınıfı olan metasezgisel yöntemlerle çözümü ele alınmıştır. Klasik matematiksel yöntemlerle çözümü zor ve belli bir boyuttan sonra imkânsız olan problemler için metasezgisel yöntemler etkin bir çözüm alternatifidir. Uluslararası literatürde sıklıkla kullanılan metasezgisel yöntemlerin GSP problemlerine uygulanması konusunda genel bakış içeren çalışmaya, ulusal literatürde rastlanmamıştır. Bu amaçla yaygın kullanıma sahip 8 metasezgisel yöntem tanıtılarak bu yöntemler literatürden alınan farklı boyutlarda problemlere uygulanmıştır. Sonuçlar raporlanmış ve farklı açılardan yorumlanmıştır

Anahtar Kelime:

Solving travelling salesman problems with metaheuristics

Öz:

This study deals with the travelling salesman problem (TSP) with metaheuristics which is the most general class of the stochastic optimization techniques. The TSP is a NP-hard problem in optimization studied in both operations research and computer science. Metaheuristics are efficient alternative techniques for NP-hard and greater dimensional problems and are impossible to solve by classic mathematical techniques. Although widespread uses of metaheuristics exist in international literature, in a study of Turkish literature there were none encountered that contain a general view of them and their applications to the TSP. For this reason, 8 metaheuristic techniques are introduced and applied to different dimensional benchmark problems which are taken from the literature. Results are reported and commented in different ways

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[1] E. Ateş, Karınca Kolonisi Optimizasyonu Algoritmaları İle Gezgin Satıcı Probleminin Çözümü Ve 3 Boyutlu Benzetimi, Basılmamış Lisans Tezi, Ege Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, İzmir, 2012.
[2] V. V. Nabiyev, Yapay Zeka - İnsan Bilgisayar Etkileşimi, Seçkin Yayıncılık, Ankara, 2007.
[3] E. Önder, M. Özdemir, B.F. Yıldırım, Combinatorial Optimization Using Artificial Bee Colony Algorithm And Particle Swarm Optimization. Kafkas Üniversitesi İktisadi ve İdari Bilimler Fakültesi (KAUİİBF) Dergisi, 4, 6, 59-70 (2013).
[4] C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Mineola, NY: Dover, 308-309, 1998.
[5] İ. Kara, T. Derya, E. Demir, T. Bektaş, “Genelleştirilmiş Gezgin Satıcı Probleminin Tamsayılı Doğrusal Karar Modeli”, Yöneylem Araştırması / Endüstri Mühendisliği 25. Ulusal Kongresi, Koç Üniversitesi, 4-6 Temmuz, İstanbul, 2005.
[6] R. Matai, S.P. Singh, M.L. Mittal, “Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches” in Traveling Salesman Problem, Theory and Applications Donald Davendra (Ed.), InTech, Croatia, 2010, 1- 24.
[7] P. Mattsson, The Asymmetric Traveling Salesman Problem, Uppsala Universitet, 2010
[8] N. Aras, B. Boyacı, D. Koşucuoğlu, D. Aksen, Karlı Gezgin Satıcı Problemi için Sezgisel Yöntemler, Yöneylem Araştırması / Endüstri Mühendisliği 27. Ulusal Kongresi, İzmir, 2007.
[9] Ö.N. Koç, Zaman Pencereli Gezgin Satıcı Problemi İçin Yeni Karar Modelleri, Başkent Üniversitesi, Fen Bilimleri Enstitüsü, Basılmamış Yüksek Lisans Tezi, 2012.
[10] B. Zhang, J. Peng, “Uncertain Traveling Salesman Problem”. Erişim linki: http://orsc.edu.cn/online/110731.pdf, 24 Ocak 2014 .
[11] S. Yadlapalli, S.Rathinam, S. Darbha, 3-Approximation Algorithm for a Two Depot, Heterogeneous Traveling Salesman Problem. Optimization Letters, 6, 1, 141-152 (2012).
[12] B.W. Haskell, A. Toriello, M. Poremba, D.J. Epstein, A Dynamic Traveling Salesman Problem with Stochastic Arc Costs Department of Industrial and Systems Engineering University of Southern California Los Angeles, California (2013).
[13] İ. Kara, E. Demir, Genelleştirilmiş Gezgin Satıcı Poblemi İçin Yeni Tamsayılı Karar Modelleri, Yöneylem Araştırması / Endüstri Mühendisliği 26. Ulusal Kongresi, Kocaeli Üniversitesi, 3-5 Temmuz, Kocaeli, 2006.
[14] C.S. Helvig, G. Robins, A. Zelikovsky, The Moving-Target Traveling Salesman Problem Volition Inc. Journal of Algorithms, 153-174 (1998).
[15] M. Diaby, The Traveling Salesman Problem: A Linear Programming Formulation. WSEAS Transactions on Mathematics, 6, 6, 745–754 (2007).
[16] C. Malandraki, RB. Dial, A Restricted Dynamic Programming Heuristic Algorithm for Time Dependent Traveling Salesman Problem. European Journal of Operations Research, 90, 1, 45–55 (1996).
[17] M.Padherg, R. Rinaldi, Optimization of a 532-City Symmetric Travelling Salesman Problem by Branch and Cut. Operations Research Letters, 6, 1, 1-7 (1987).
[18] M. Padberg, G. Rinaldi, Branch-and-Cut Approach to a Variant of the Traveling Salesman Problem. Journal of Guidance, Control, and Dynamics, 11, 5, 436–440 (1988).
[19] S.Lin, B. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 21, 2, 498-516 (1973).
[20] A. Punnen, F. Margot, S.Kabadi, TSP Heuristics: Domination Analysis and Complexity. Algorithmica, 35, 111–127 (2003).
[21] O. Martin, S. Otto, E. Felten, Large-step markov chains for the traveling salesman problem. Complex Systems, 5, 3, 299-326 (1991).
[22] S. Kirkpatrick, C. D. Gelatt, M. P. Vechi, Optimization by Simulated Annealing. Science, 220, 4598, 671-680 (1983).
[23] S. Kirkpatrik, Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics, 34, 1984, 975-986 (1984).
[24] JB. Wu, SW. Xiong, N. Xu, Simulated Annealing Algorithm Based on Controllable Temperature for Solving TSP. Application Research of Computers, 24, 5, 66–89 (2007).
[25] M.Dam, M. Zachariasen, Tabu Search on the geometric travelling salesman problem. Meta-heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, 571-587, 1996.
[26] Y. Wu, X. Zhou, Meliorative Tabu Search Algorithm for TSP Problem. Journal of Computer Engineering and Applications, 44, 1, 57–59 (2008).
[27] C.A. Hurkens, G.J. Woeginger, On the Nearest Neighbor Rule for the Traveling Salesman Problem. Operations Research Letters, 32, 1, 1-4 (2004).
[28] M. Dry, K. Preiss, J. Wagemans, Clustering, Randomness, and Regularity: Spatial Distributions and Human Performance on the Traveling Salesperson Problem and Minimum Spanning Tree Problem. The Journal of Problem Solving, 4, 1, 2 (2012)
[29] S.Akyol, B. Alataş, Güncel Sürü Zekası Optamizasyon Algoritmaları. Nevşehir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 1, 1, 36-50 (2012).
[30] M.B. Fogel, The Genetic Algorithm for TSP. IEEE Transaction on systems, 16, 1-13 (1986).
[31] S. Chatterjee, C. Carrera, L. A. Lynch, Genetic Algorithms and Traveling Salesman Problems. European Journal of Operational Research, 93, 3, 490-510 (1996).
[32] P. Larranaga, C.M.H. Kujipers, R.H. Murga, I.Innza, S. Dizdarevic, Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13, 2, 129-170 (1999).
[33] H.K. Tsai, J.M. Yang, Y.F. Tsai, C.Y. Kao, Heterogeneous Selection Genetic Algorithms for Traveling Salesman Problems. Engineering Optimization, 35, 3, 297– 311 (2003).
[34] S.S. Ray, S. Bandyopadhyay, S.K. Pal, New Operators of Genetic Algorithms for Travelling Salesman Problem. Proceedings of the 17th International Conference on Pattern Recognition, 23 – 26 August 2004, Cambridge, 497-500, (2004).
[35] J.H. Yang, C.G. Wu, H.P. Lee, Y.C. Liang, Solving Traveling Salesman Problems Using Generalized Chromosome Genetic Algorithm. Progress in Natural Science, 18, 887–892 (2008).
[36] Z. Tao, TSP Problem Solution Based On Improved Genetic Algorithm. In proceedings of the 2008 Fourth International Conference on Natural Computation, ICNC, IEEE Computer Society, Washington, DC, vol. 01, 686-690, 2008.
[37] B.F. Al-Dulaimi, A.A. Hamza, Enhanced Travelling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA). Proceedıngs Of World Academy Of Scıence, Engıneerıng And Technology, 28, 296-302 (2008).
[38] M. Bhattacharyya, A.K. Bandyopadhyay, Comparative Study of Some Solution Methods for Traveling Salesman Problem Using Genetic Algorithms. Cybernetics and Systems, 40, 1–24 (2009).
[39] O.M. Sallabi, Y. El-Haddad, An Improved Genetic Algorithm to Solve the Travelling Salesman Problem. World Academy of Science, Engineering and Technology, 3, 403-406 (2009).
[40] L. Shi, Z.Li, An Improved Pareto Genetic Algorithm for Multi-Objective TSP. Fifth International Conference on Natural Computation, Tianjian, China, 585–588, 2009.
[41] S. Elaoud, J. Teghem, T. Loukil, Multiple Crossover Genetic Algorithm for the MultiObjective Traveling Salesman Problem. Electron Notes Discrete Math, 36, 939–946 (2010).
[42] M.Albayrak, N. Allahverdi, Development a New Mutation Operator to Solve the Traveling Salesman Problem by Aid of Genetic Algorithms. Expert Systems with Applications, 38, 1313–1320 (2011).
[43] M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53–66 (1997)

APA	KUZU YILDIRIM S, Önay O, ŞEN U, TUNCER M, YILDIRIM B, KESKİNTÜRK T (2014). Gezgin satıcı problemlerinin metasezgiseller ile çözümü. , 1 - 27.
Chicago	KUZU YILDIRIM SULTAN,Önay Onur,ŞEN Uğur,TUNCER Mustafa,YILDIRIM Bahadır Fatih,KESKİNTÜRK Timur Gezgin satıcı problemlerinin metasezgiseller ile çözümü. (2014): 1 - 27.
MLA	KUZU YILDIRIM SULTAN,Önay Onur,ŞEN Uğur,TUNCER Mustafa,YILDIRIM Bahadır Fatih,KESKİNTÜRK Timur Gezgin satıcı problemlerinin metasezgiseller ile çözümü. , 2014, ss.1 - 27.
AMA	KUZU YILDIRIM S,Önay O,ŞEN U,TUNCER M,YILDIRIM B,KESKİNTÜRK T Gezgin satıcı problemlerinin metasezgiseller ile çözümü. . 2014; 1 - 27.
Vancouver	KUZU YILDIRIM S,Önay O,ŞEN U,TUNCER M,YILDIRIM B,KESKİNTÜRK T Gezgin satıcı problemlerinin metasezgiseller ile çözümü. . 2014; 1 - 27.
IEEE	KUZU YILDIRIM S,Önay O,ŞEN U,TUNCER M,YILDIRIM B,KESKİNTÜRK T "Gezgin satıcı problemlerinin metasezgiseller ile çözümü." , ss.1 - 27, 2014.
ISNAD	KUZU YILDIRIM, SULTAN vd. "Gezgin satıcı problemlerinin metasezgiseller ile çözümü". (2014), 1-27.

APA	KUZU YILDIRIM S, Önay O, ŞEN U, TUNCER M, YILDIRIM B, KESKİNTÜRK T (2014). Gezgin satıcı problemlerinin metasezgiseller ile çözümü. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(1), 1 - 27.
Chicago	KUZU YILDIRIM SULTAN,Önay Onur,ŞEN Uğur,TUNCER Mustafa,YILDIRIM Bahadır Fatih,KESKİNTÜRK Timur Gezgin satıcı problemlerinin metasezgiseller ile çözümü. İstanbul Üniversitesi İşletme Fakültesi Dergisi 43, no.1 (2014): 1 - 27.
MLA	KUZU YILDIRIM SULTAN,Önay Onur,ŞEN Uğur,TUNCER Mustafa,YILDIRIM Bahadır Fatih,KESKİNTÜRK Timur Gezgin satıcı problemlerinin metasezgiseller ile çözümü. İstanbul Üniversitesi İşletme Fakültesi Dergisi, vol.43, no.1, 2014, ss.1 - 27.
AMA	KUZU YILDIRIM S,Önay O,ŞEN U,TUNCER M,YILDIRIM B,KESKİNTÜRK T Gezgin satıcı problemlerinin metasezgiseller ile çözümü. İstanbul Üniversitesi İşletme Fakültesi Dergisi. 2014; 43(1): 1 - 27.
Vancouver	KUZU YILDIRIM S,Önay O,ŞEN U,TUNCER M,YILDIRIM B,KESKİNTÜRK T Gezgin satıcı problemlerinin metasezgiseller ile çözümü. İstanbul Üniversitesi İşletme Fakültesi Dergisi. 2014; 43(1): 1 - 27.
IEEE	KUZU YILDIRIM S,Önay O,ŞEN U,TUNCER M,YILDIRIM B,KESKİNTÜRK T "Gezgin satıcı problemlerinin metasezgiseller ile çözümü." İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43, ss.1 - 27, 2014.
ISNAD	KUZU YILDIRIM, SULTAN vd. "Gezgin satıcı problemlerinin metasezgiseller ile çözümü". İstanbul Üniversitesi İşletme Fakültesi Dergisi 43/1 (2014), 1-27.