Yıl: 2019 Cilt: 21 Sayı: 63 Sayfa Aralığı: 819 - 832 Metin Dili: Türkçe DOI: 10.21205/deufmd.2019216312 İndeks Tarihi: 14-02-2020

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

Öz:
Bu çalışmada, yöneylem araştırması alanının en çok çalışılan problemlerden biri olan gezgin satıcı veulaştırma problemleri üzerinde durulmakta ve aralarındaki ilişkiden faydalanan yeni bir çözümalgoritması ö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. Bu yöntem gezgin satıcı problemini dahaetkin çözmek için yıllardır süren araştırmalara bir katkı sağlamak için önerilmiştir. Önerilenyöntemde gezgin satıcı uzaklık matrisi, bir ulaştırma tablosu gibi ele alınarak, matris üzerinde yapılanözel bir normalizasyon işlemi ile gezgin satıcı problemi için başlangıç çözümü elde edilmektedir. Dahasonra, elde edilen başlangıç çözümünün performansı 2-Opt algoritması ile geliştirilmektedir.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 doğrudan başlangıç çözümüneuygulanan 2-Opt algoritması sezgisellerinin çözümleri ile karşılaştırılmıştır. Önerilen yaklaşımsıklıkla kullanılan gezgin satıcı test problemleri ve bilimsel yazında yer alan bir grup problem ileanaliz edilmiştir. Ortalama çözüm değeri optimalden %26 sapma gösterirken, En Yakın Komşualgoritması için optimalden sapma %16 olarak gerçekleşmiştir. Ancak 2-Opt ile hem TPORT hem deEn Yakın Komşu algoritmalarının çözümleri geliştirildiğinde, sırasıyla %4 ve %3 optimalden ortalamasapma elde edilmiştir. Bu bağlamda önerilen çözüm yaklaşımının çözüm performansı açısındanrekabetçi olduğu ileri sürülebilir. Ayrıca çözüm süreleri açısından yapılan karşılaştırmalarda önerilenyöntemle En Yakın Komşu algoritması arasında önemli düzeyde fark vardır. Sonuç olarak, önerilenyöntemin çözüm hızı açısından üstün, çözüm kalitesi bakımından kıyaslanan yöntemlere görerekabetçi olduğu gösterilmiştir. Özellikle, problem boyutu büyüdükçe kıyaslanan yöntemlerin çözümsüresi neredeyse sabit bir seviyede seyrederken En Yakın Komşu algoritmasının çözüm süreleri üstelbir eğilim göstermiştir.
Anahtar Kelime:

Konular: Bilgisayar Bilimleri, Yazılım Mühendisliği Endüstri Mühendisliği

A Novel Solution Approach for Travelling Salesman Problem: TPORT

Öz:
In this study, one of the most frequently studied problems in the field of operations research, the traveling salesman problem and the transportation problem, are considered, and a new solution algorithm that takes advantage of the relationship between them is proposed. Many initial solution algorithms have been proposed for transportation problems. In this study, with a similar approach and intuition, an approach called TPORT is proposed for the initial solution of the symmetric traveling salesman problem. This method has been proposed to contribute to years of research to solve the traveling salesman problem more effectively. In the proposed method, the traveling salesman distance matrix is treated as a transportation table, and a special normalization process on the matrix provides the initial solution of the traveling salesman problem. Then, the performance of the initial solutions is improved 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 the solutions of the directly applied 2-Opt algorithm. 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 has 26% deviation from the optimal, whereas the performance of the nearest neighbor algorithm has a 16% deviation from the optimal. However, when the solutions of TPORT and nearest neighbor algorithm were improved 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 is superior in terms of solution speed and competitive in terms of solution quality. 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 exponential increasing trend.
Anahtar Kelime:

Konular: Bilgisayar Bilimleri, Yazılım Mühendisliği Endüstri Mühendisliği
Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • Kuhn, H.W. 1955. The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly, Cilt. 2, Sayı. 1-2,s. 83-97.
  • 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.
  • Burkard, R.E. 1979. Travelling Salesman and Assignment Problems: A Survey, Annals of Discrete Mathematics, Cilt. 4, s. 193-215.
  • Winston, W.L. 2003. Operations Research: Applications and Algorithms. 4th edition. Cengage Learning.
  • Dantzig, G.B., Thapa, M.N. 1997. Linear Programming 1: Introduction. Springer-Verlang New York, USA.
  • 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.
  • 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.
  • 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.
  • Ş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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Szabo, J. 2016. Comparison of Methods for Generating Initial Solution for Simulated Annealing. Central European Researchers Journal, Cilt. 2, Sayı. 1, s. 37-41.
  • Ş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.
  • 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.
  • 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.
  • Matworks, File Exchange, https://www.mathworks.com/matlabcentral/ fileexchange/25542-nearest-neighbor-algorithmfor-the-travelling-salesman-problem, (Erişim Tarihi: 18.02.2019).
  • Croes, G.A. 1958. A Method for Solving TravelingSalesman Problems. Operations Research, Cilt. 6, Sayı. 6, s. 791–812.
  • 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/223 589
  • 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).
  • 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.
  • 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).
  • Universität Heidelberg. “Index of /software/TSPLIB95 /tsp”. http://comopt.ifi.uniheidelberg.de/ software/TSPLIB95/tsp/ (Erişim Tarihi: 18.11.2018).
APA Karagul K (2019). Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. , 819 - 832. 10.21205/deufmd.2019216312
Chicago Karagul Kenan Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. (2019): 819 - 832. 10.21205/deufmd.2019216312
MLA Karagul Kenan Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. , 2019, ss.819 - 832. 10.21205/deufmd.2019216312
AMA Karagul K Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. . 2019; 819 - 832. 10.21205/deufmd.2019216312
Vancouver Karagul K Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. . 2019; 819 - 832. 10.21205/deufmd.2019216312
IEEE Karagul K "Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT." , ss.819 - 832, 2019. 10.21205/deufmd.2019216312
ISNAD Karagul, Kenan. "Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT". (2019), 819-832. https://doi.org/10.21205/deufmd.2019216312
APA Karagul K (2019). Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi, 21(63), 819 - 832. 10.21205/deufmd.2019216312
Chicago Karagul Kenan Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 21, no.63 (2019): 819 - 832. 10.21205/deufmd.2019216312
MLA Karagul Kenan Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi, vol.21, no.63, 2019, ss.819 - 832. 10.21205/deufmd.2019216312
AMA Karagul K Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi. 2019; 21(63): 819 - 832. 10.21205/deufmd.2019216312
Vancouver Karagul K Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi. 2019; 21(63): 819 - 832. 10.21205/deufmd.2019216312
IEEE Karagul K "Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT." Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi, 21, ss.819 - 832, 2019. 10.21205/deufmd.2019216312
ISNAD Karagul, Kenan. "Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT". Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 21/63 (2019), 819-832. https://doi.org/10.21205/deufmd.2019216312