Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü

Öz

Gezgin Satıcı Problemi (GSP), bir satıcının bütün şehirleri sadece bir defa ziyaret ederek başlangıç noktasına dönmesini sağlayan en kısa rotanın belirlendiği problemdir. GSP, araç rotalamadan baskılı devre kartı montajına kadar birçok problemin temelini oluşturur. Bu problem, optimizasyon alanında çalışan kişilerden büyük ilgi görmüştür, ancak özellikle büyük ölçekli veri kümeleri için çözülmesi zordur. Bu çalışmada, GSP’nin çözümü için Akışkan Genetik Algoritma, En Yakın Komşu ve 2-Opt sezgiselleri üzerine kurulu melez bir yöntem sunulmaktadır. Önerilen yöntemin performansı literatürde bulunan En Yakın Komşu, Genetik Algoritma, Tabu Arama, Karınca Kolonisi Optimizasyonu ve Ağaç Fizyolojisi Optimizasyon algoritmaları kullanılarak elde edilen çözüm değerleri ile kıyaslanmıştır. Önerilen yöntemin sonuçları çözüm süresi ve kalitesi bakımından üstünlük göstermektedir.

Anahtar Kelimeler

• Gezgin satıcı,Meta-sezgiseller,Akışkan genetik algoritma

Solving travelling salesman problem using hybrid fluid genetic algorithm (HFGA)

Abstract

Travelling Salesman Problem (TSP) is a problem in which the shortest possible route enabling a salesman to return to the starting point after visiting all the cities exactly once is determined. Travelling Salesman Problem is the basis for many problems ranging from vehicle routing to printed circuit boards assembly. This problem has been attracting great attention from researchers in the field of optimization; nevertheless it is difficult to solve TSP, especially for large-scale data sets. This paper presents a hybrid solution method based on Fluid Genetic Algorithm, Nearest Neighbor and 2-Opt methods for the solution of TSP. The performance of the proposed method is evaluated with the solution values of the Nearest Neighbor, Genetic Algorithm, Tabu Search, Ant Colony Optimization and the Tree Physiology Optimization algorithms in the literature. The solution results show the superiority of the proposed method in terms of solution time and quality.

Keywords

• Traveling salesman,Metaheuristics,Fluid genetic algorithm

References

1. Potvin JY. “Genetic algorithms for the traveling salesman problem”. Annals of Operations Research, 63(3), 337-370, 1996.
2. Goyal S. “A survey on travelling salesman problem”. 43rd Midwest Instruction and Computing Symposium, Eau Claire, Wisconsin, USA, 16-17 April 2010.
3. Matai R, Singh S, Mittal ML. Traveling Salesman Problem: an Overview of Applications, Formulationsand Solution Approaches.Editor: Davendra D.Traveling salesman problem, theory and applications, Landon, United Kingdom, 1-24, InTech, 2010.
4. Burke EK, Cowling PI, Keuthen R. “New models and heuristics for component placement in printed circuit board assembly”. International Conference on Information Intelligence and Systems, Bethesda, Maryland, USA, 31October-3 November, 1999.
5. Hoffman KL, Padberg M. “Solving airline crew scheduling problems by branch-and-cut”. Management Science,39(6), 657-682, 1993.
6. Park J, Byung-In K. "The school bus routing problem: A review". European Journal of Operational Research,202(2), 311-319, 2010.
7. Yu Z, Jinhai L, Guochang G, Rubo Z, Haiyan, Y. “An implementation of evolutionary computation for path planning of cooperative mobile robots”. 4th World Congress on Intelligent Control and Automation, Shanghai, China, 10-14 June 2002.
8. Mazzeo S, Irene L. "An ant colony algorithm for the capacitated vehicle routing". Electronic Notes in Discrete Mathematics, 18, 181-186, 2004.

9. Ratliff HD, Rosenthal AS. “Orderpicking in a rectangular warehouse: a solvable case of the traveling salesman problem”.Operations Research, 31 (3), 507-521, 1983.
10. Karagul K, Aydemir, E, Tokat S. "Using 2-Opt based evolution strategy for travelling salesman problem". An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 6(2), 103-113, 2016.
11. Zhao F, Li S, Sun J, Mei D. "Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem." Computers & Industrial Engineering, 56(4), 1642-1648, 2009.
12. Dorigo M, Gambardella LM, "Ant colony system: a cooperative learning approach to the traveling salesman problem." IEEE Transactions on evolutionary computation,1(1), 53-66, 1997.
13. Mavrovouniotis M, Yang S. “Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors”.Applied Soft Computing, 13(10), 4023-4037, 2013.
14. Gendreau M, Laporte G, Semet F. “A tabu search heuristic for the undirected selective travelling salesman problem”.European Journal of Operational Research,106(2-3), 539-545, 1998.
15. Malek M, Guruswamy M, Pandya M, Owens H. “Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem”.Annals of Operations Research, 21(1), 59-84, 1989.
16. Snyder LV, Daskin MS. “A random-key genetic algorithm for the generalized traveling salesman problem”.European Journal of Operational Research, 174(1), 38-53, 2006.
17. Chang PC, Huang WH, Ting CJ. “Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems.”, Expert systems with applications,37(3), 1863-1878, 2010.
18. Razali NM, Geraghty J. “Genetic algorithm performance with different selection strategies in solving TSP”. InProceedings of the world congress on engineering, 2, 1134-1139, 2011.
19. Majumdar J, Bhunia AK. “Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times”. Journal of Computational and Applied Mathematics, 235(9), 3063-3078, 2011.
20. Deep K, Adane, HM. “New variations of order crossover for travelling salesman problem”. International Journal of Combinatorial Optimization Problems and Informatics, 2(1),2-13, 2011.
21. Antosiewicz M, Koloch G, Kamiński B. “Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: quality, uncertainty and speed”. Journal of Theoretical and Applied Computer Science, 7(1), 46-55, 2013.
22. Ahmed ZH. “An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem”. Mathematical Sciences,7(1), 10, 2013.
23. Kuzu S, Önay O, Şen U, Tunçer M, Yıldırım BF, Keskintürk, T. “Gezgin satıcı problemlerinin metasezgiseller ile çözümü”. Istanbul University Journal of the School of Business,43(1), 1-27, 2014.
24. Kang S, Kim SS, Won J, Kang YM. “GPU-based parallel genetic approach to large-scale travelling salesman problem”. The Journal of Supercomputing, 72(11), 4399-4414, 2016.
25. Halim AH, Ismail I. “Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem”. Archives of Computational Methods in Engineering, 2017. https://doi.org/10.1007/s11831-017-9247-y
26. Rana S, Srivastava SR. “Solving travelling salesman problem using ımproved genetic algorithm”. Indian Journal of Science and Technology,10(30), 1-6, 2017.
27. Jafari-Marandi R, Smith, BK. “Fluid genetic algorithm (FGA)”. Journal of Computational Design and Engineering, 4(2), 158-167, 2017.
28. Gen M, Cheng R. Genetic Algorithms and Engineering Design. New York, USA, Wiley, 1997.
29. Şahin Y, Eroğlu, A. “Kapasite kısıtlı araç rotalama problemi için metasezgisel yöntemler: bilimsel yazın taraması”. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi,19(4), 337-355, 2014.
30. Şahin Y. Depo Operasyonları ve Sipariş Dağıtım Faaliyetlerinin Sezgisel Yöntemler Kullanarak Eş Zamanlı Optimizasyonu. Doktora Tezi, Süleyman Demirel Üniversitesi, Isparta, Türkiye, 2014.
31. Eiben AE, Smith JE. Introdution to Evolutionary Computing. Berlin, Germany, Springer-Verlang Heidelberg, 2003.
32. Croes GA. “A method for solving large scale symmetric traveling salesman problems to optimality”. Operations Research, 6, 791-812, 1958.
33. Eryavuz M, Gencer C. “Araç rotalama problemine ait bir uygulama”.Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 6(1), 139-155, 2001.
34. Universität Heidelberg. “Index of /software/TSPLIB95/tsp”. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/(18.11.2017).
35. Joines A, Kay, MG, Karagul K, Tokat S. Performance analysis of Genetic Algorithm Optimization Toolbox via Traveling Salesperson Problem. Editor: Sayers W. Contemporary Issues in Social Sciencesand Humanities, 213-221, Landon, UK, AGP Research, 2017.
36. Yıldırım T, Kalaycı CB, Mutlu Ö. “Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 22(1), 64-70, 2016.