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

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. [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. [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. [3] Burkard, R.E. 1979. Travelling Salesman and Assignment Problems: A Survey, Annals of Discrete Mathematics, Cilt. 4, s. 193-215.
4. [4] Winston, W.L. 2003. Operations Research: Applications and Algorithms. 4th edition. Cengage Learning.
5. [5] Dantzig, G.B., Thapa, M.N. 1997. Linear Programming 1: Introduction. Springer-Verlang New York, USA.
6. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [24] Croes, G.A. 1958. A Method for Solving Traveling-Salesman Problems. Operations Research, Cilt. 6, Sayı. 6, s. 791–812.
25. [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. [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. [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. [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. [29] Universität Heidelberg. “Index of /software/TSPLIB95 /tsp”. http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/tsp/ (Erişim Tarihi: 18.11.2018).