Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT

Year 2019, Volume: 21 Issue: 63, 819 - 832, 20.09.2019

Kenan Karagül

https://doi.org/10.21205/deufmd.2019216312

Cited By: 3

Abstract

Bu çalışmada, 1800’lü yıllardan bu
yana, yöneylem araştırması alanının en çok çalışılan problemlerinden biri olan
gezgin satıcı ve ulaştırma problemleri üzerinde durulmakta ve aralarındaki
ilişkiden faydalanan yeni bir çözüm algoritması önerilmektedir. Ulaştırma
problemleri için bir çok başlangıç çözüm algoritması önerilmiştir. Benzer bir
mantık ve sezgi ile simetrik gezgin satıcı problemine başlangıç çözümü üretmek
için TPORT adı verilen bir yaklaşım önerilmiştir. Elde edilen başlangıç
çözümünün performansı 2-Opt  sezgiseli
ile geliştirilmiştir. Geliştirilen sezgisel En Yakın Komşu algoritması ile
yakınlık gösterdiği için gezgin satıcı problemlerinin çözüm performansları En
Yakın Komşu algoritması ve 2-Opt sezgisellerinin çözümleri ile
karşılaştırılmıştır. Önerilen yaklaşım sıklıkla kullanılan gezgin satıcı test
problemleri ve bilimsel yazında yer alan bir grup ile analiz edilmiştir.
Ortalama çözüm değeri %26 optimalden uzak iken, En Yakın Komşu algoritması için
%16 olarak gerçekleşmiştir. Ancak 2-Opt ile hem TPORT hem de En Yakın Komşu
algoritmalarının çözümleri geliştirildiğinde, sırasıyla %4 ve %3 optimalden
ortalama sapma elde edilmiştir. Bu bağlamda önerilen çözüm yaklaşımı çözüm
performansı açısından rekabetçi olduğu ileri sürülebilir. Ancak çözüm süreleri
açısından yapılan karşılaştırmalarda önerilen yöntemle En Yakın Komşu
algoritması arasında önemli düzeyde fark vardır. Sonuç olarak, önerilen
yöntemin hem çözüm hızı hem de çözüm kalitesi bakımından kıyaslanan yöntemlere
göre iyi olduğu gösterilmiştir. Özellikle, problem boyutu büyüdükçe kıyaslanan
yöntemlerin çözüm süresi neredeyse sabit bir seviyede seyrederken En Yakın
Komşu algoritmasının çözüm süreleri asimptotik bir eğilim göstermiştir.

Keywords

Gezgin Satıcı Problemi, Ulaştırma Problemi, En Yakın Komşu Algoritması, 2-Opt

A Novel Solution Approach For Travelling Salesman Problem: TPORT

Abstract

In this study, a novel solution
algorithm taking advantage of the relationship between traveling salesman and
transportation problems that are the most studied problems of operations
research field since 1800s, is proposed. Many initial solution algorithms have
been proposed for transportation problems. In this study, an approach called
TPORT is proposed for the initial solution for the symmetric traveling salesman
problem with similar approach and intuition. The performance of the initial
solutions is developed with 2-Opt algorithm. As the developed heuristic has
similarities with the nearest neighbor algorithm, the solution performances of
the traveling salesman problems were compared with the solutions of the nearest
neighbor algorithm and 2-Opt. The proposed approach has been analyzed by the
well-known traveling salesman test instances and a group of test instances from
the literature. The average solution performance of the proposed method was
26%, while the performance of the nearest neighbor algorithm was 16%. However,
when the solutions of TPORT and nearest neighbor algorithm were developed with
2-Opt, the average deviation was obtained as 4% and 3%, respectively. In this
context, it can be argued that the proposed solution approach is competitive in
terms of solution performance. Also, there is a huge difference between the
proposed method and the nearest neighbor algorithm in terms of solution times.
As a result, it has been shown that the proposed method with 2-Opt improvement
is superior for both the solution speed and the quality of the solutions. In
particular, as the problem size is increased, the solution time of the
comparable methods is almost constant, while the solution time of the nearest
neighbor algorithm shows an asymptotic trend.

Keywords

Traveling Salesman Problem, Transportation Problem, Nearest Neigbor Algortithm, 2-Opt

References

• [1] Kuhn, H.W. 1955. The Hungarian method for the Assignment Problem, Naval Research Logistics Quarterly, Cilt. 2, Sayı. 1-2,s. 83-97.
• [2] Munkres, J. 1957. Algorithms for the Assignment and Transportation Problems, Journal of the Society for Industrial and Applied Mathematics, Cilt. 5, Sayı. 1, s. 32-38.
• [3] Burkard, R.E. 1979. Travelling Salesman and Assignment Problems: A Survey, Annals of Discrete Mathematics, Cilt. 4, s. 193-215.
• [4] Winston, W.L. 2003. Operations Research: Applications and Algorithms. 4th edition. Cengage Learning.
• [5] Dantzig, G.B., Thapa, M.N. 1997. Linear Programming 1: Introduction. Springer-Verlang New York, USA.
• [6] Ratliff, H.D., Rosenthal, A.S. 1983. Order Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem. Operations Research, Cilt. 31, Sayı. 3, s. 507-521.
• [7] Zhao, F., Li, S., Sun, J., Mei, D. 2009. Genetic Algorithm for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem. Computers & Industrial Engineering. Cilt. 56, Sayı. 4, s. 1642-1648.
• [8] Joines, A., Kay, M.G., Karabacak, M.F., Karagül, K., Tokat, S. 2017. Performance analysis of Genetic Algorithm Optimization Toolbox via Traveling Salesperson Problem. ss. 213-221. Sayers, W. ed. Contemporary Issues in Social Sciences and Humanities, UK, AGP Research, London.
• [9] Şahin, Y., Karagül, K. 2019. Solving Travelling Salesman Problem Using Hybrid Fluid Genetic Algorithm (HFGA), Pamukkale University Journal of Engineering Sciences, Ahead of Print: PAJES-81084 | DOI: 10.5505/pajes.2018.81084.
• [10] Karagul, K., Aydemir, E., Tokat, S. 2016. Using 2-Opt Based Evolution Strategy for Travelling Salesman Problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), Cilt. 6, Sayı. 2, s. 103-113.
• [11] Dorigo, M., Gambardella, L.M. 1997. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, Cilt. 1, Sayı. 1, s. 53-66.
• [12] Mavrovouniotis, M., Yang, S. 2013. Ant Colony Optimization with Immigrants Schemes for the Dynamic Travelling Salesman Problem with Traffic Factors. Applied Soft Computing. Cilt. 13, Sayı. 10, s. 4023-4037.
• [13] Gendreau, M., Laporte, G., Semet, F. 1998. A Tabu Search Heuristic for the Undirected Selective Travelling Salesman Problem. European Journal of Operational Research, Cilt. 106, Sayı. 2-3, s. 539-545.
• [14] Malek, M., Guruswamy, M., Pandya, M., Owens, H. 1989. Serial and Parallel Simulated Annealing andTabu Search Algorithms for the Traveling Salesman Problem. Annals of Operations Research, Cilt. 21, Sayı. 1, s. 59-84.
• [15] Halim, A.H., Ismail, I. 2017. Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem. Archives of Computational Methods in Engineering, s. 1-14. DOI: 10.1002/net.3230200605.
• [16] Antosiewicz, M., Koloch, G., Kamiński, B. 2013. 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, Cilt. 7, Sayı. 1, s. 46-55.
• [17] Chitty, D. M. 2017. Applying ACO To Large Scale TSP Instances. UK Workshop on Computational Intelligence, s. 104-118. Springer, Cham. arXiv:1709.03187. DOI: 10.1007/978-3-319-66939-7_9.
• [18] Karagul, K., Kay, M. G., Tokat, S. 2018. A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science, Cilt. 31, Sayı. 2, s. 489–513.
• [19] Szabo, J. 2016. Comparison of Methods for Generating Initial Solution for Simulated Annealing. Central European Researchers Journal, Cilt. 2, Sayı. 1, s. 37-41.
• [20] Şahin, Y., Kulak, O. 2013. Depo Operasyonlarının Planlanması İçin Genetik Algoritma Esaslı Modeller. Uluslararası Alanya İşletme Fakültesi Dergisi, Cilt. 5, Sayı. 3, s. 141-153.
• [21] Kızılateş, G., Nuriyeva, F. 2013. On the Nearest Neighbor Algorithms for the Traveling Salesman Problem. In: Nagamalai D., Kumar A., Annamalai A. (eds) Advances in Computational Science, Engineering and Information Technology. Advances in Intelligent Systems and Computing, vol 225. Springer, Heidelberg.
• [22] Kay, M. 2016. MATLOG: Logistics Engineering Using Matlab. Mühendislik Bilimleri ve Tasarım Dergisi, Cilt. 4, Sayı. 1, s. 15-20. Retrieved from http://dergipark.gov.tr/jesd/issue/20875/224091.
• [23] Matworks, File Exchange, https://www.mathworks.com/matlabcentral/fileexchange/25542-nearest-neighbor-algorithm-for-the-travelling-salesman-problem, (Erişim Tarihi: 18.02.2019).
• [24] Croes, G.A. 1958. A Method for Solving Traveling-Salesman Problems. Operations Research, Cilt. 6, Sayı. 6, s. 791–812.
• [25] Eryavuz, M., Gencer, C. 2001. Araç Rotalama Problemine Ait Bir Uygulama. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, Cilt. 6, Sayı. 1, s. 139-155. . Retrieved from http://dergipark.gov.tr/sduiibfd/issue/20850/223589.
• [26] Kuang, E. 2012. A 2-opt-based Heuristic for the Hierarchical Traveling Salesman Problem. http://honors.cs.umd.edu/reports/kuang.pdf, (Erişim Tarihi: 18.02.2019).
• [27] Sathyan, A., Boone, N., Cohen, K. 2015. Comparison of Approximate Approaches to Solving the Travelling Salesman Problem and its Application to UAV Swarming. International Journal of Unmanned UAV Swarming Systems Engineering (IJUSEng), Cilt. 3, Sayı. 1, s. 1-16.
• [28] Burkardt, J. 2019. Data for the Traveling Salesperson Problem. https://people.sc.fsu.edu/~jburkardt/ datasets/tsp/tsp.html, (Erişim Tarihi: 18.02.2019).
• [29] Universität Heidelberg. “Index of /software/TSPLIB95 /tsp”. http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/tsp/ (Erişim Tarihi: 18.11.2018).