A NOVEL SOLUTION APPROACH FOR SOLVING TRAVELLING SALESMAN PROBLEM BASED ON HUNGARIAN ALGORITHM

Year 2019, Volume: 7 Issue: 3, 561 - 571, 15.09.2019

Kenan Karagül

https://doi.org/10.21923/jesd.523623

Cited By: 1

Abstract

In this study, a novel solution algorithm which takes advantage of the
relationship between traveling salesman and assignment problems which are
famous problems of combinatorial optimization area is proposed. By using the
Hungarian Algorithm, which provides the optimal solution for the assignment
problems, initial solutions were obtained for the symmetric traveling salesman problem.
The obtained initial solutions were solved using the Nearest Neighbor and 2-Opt
(NNH_2-Opt) heuristics. The proposed approach has been analyzed with the frequently
used traveling salesman test problems and compared with the results of some
studies in the scientific literature. As a result, it has been shown that the
proposed method is superior to the other methods with regard to solution speed
and quality. In particular, as the size of the problem increases, the solution
times of the compared methods are getting longer, while the proposed method can
also provide fast solutions for large-scale problems.

Keywords

Travelling salesman problem, Hungarian algorithm, Munkres algorithm, Nearest neighbor heuristic, 2-Opt algorithm

GEZGİN SATICI PROBLEMİNİN ÇÖZÜMÜ İÇİN MACAR ALGORİTMASI ESASLI YENİ BİR ÇÖZÜM YAKLAŞIMI

Abstract

Bu çalışmada kombinatoryal optimizasyon
alanının ünlü problemlerinden olan gezgin satıcı ve atama problemleri arasındaki
ilişkiden faydalanan yeni bir çözüm algoritması önerilmektedir. Atama
problemleri için optimal çözümü veren Macar Algoritması ile simetrik gezgin
satıcı problemi için başlangıç çözümleri elde edilmiştir. Elde edilen başlangıç
çözümleri En Yakın Komşu ve 2-Opt (NNH_2-Opt) sezgiselleri kullanılarak
çözülmüştür. Önerilen yaklaşım sıklıkla kullanılan gezgin satıcı test
problemleri ile analiz edilmiş ve bilimsel yazında yer alan bazı çalışmaların
sonuçları ile kıyaslama yapılmıştı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 uzarken, önerilen yöntem büyük boyutlu problemler için de hızlı çözümler
sunabilmektedir. 

Keywords

Gezgin satıcı problemi, Macar algoritması, Munkres algoritması, En yakın komşu sezgiseli, 2-Opt algoritması

References

• 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, vol. 7, no. 1, pp. 46-55.
• Balas, E., Christofides, N., 1981. A Restricted LagrangeanApproach to the Traveling Salesman Problem. Mathematical Programming. 21(1), 19–46.
• Balinski, M. L., Gomory, R. E., 1964. A Primal Method for the Assignment and Transportation Problems. Management Science, 10(3):578-593. http://dx.doi.org/10.1287/mnsc.10.3.578
• Basirzadeh, H., 2014. Ones Assignment Method for Solving Traveling Salesman Problem. Journal of Mathematics and Computer Science. Vol. 10, Iss. 4, pp. 258-265.
• Bertsekas, D.P., 1981. A New Algorithm for the Assignment Problem. Mathematical Programming. 21: 152. https://doi.org/10.1007/BF01584237
• Burkard, R.E., 1979. Travelling Salesman and Assignment Problems: A Survey. Annals of Discrete Mathematics. Vol. 4, pp. 193-215
• Chitty, D. M., 2017. Applying ACO To Large Scale TSP Instances. UK Workshop on Computational Intelligence, pp. 104-118. Springer, Cham, 2017
• Croes, G. A. (1958). A Method for Solving Traveling-Salesman Problems. Operations Research, 6 (6), 791–812.
• Dantzig, G.B., Thapa, M.N., 1997. Linear programming 1: introduction. Springer-Verlang New York, USA.
• Dorigo, M., Gambardella, L.M., 1997. Ant Colony System: ACooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
• Frank, A., 2005. On Kuhn's Hungarian Method—A tribute from Hungary.Naval Research Logistics Quarterly. Vol. 52, Iss. 1, pp. 2-5.
• Gendreau, M., Laporte, G., Semet, F., 1998. A TabuSearch Heuristic for the Undirected Selective Travelling Salesman Problem. European Journal of Operational Research, 106(2-3), 539-545.
• Halim, A.H., Ismail, I., 2017. Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem, Archives of Computational Methods in Engineering, 1-14. https://doi.org/10.1002/net.3230200605
• Jewell, W.S.,1977. The Analytic Methods of Operations Research. Phil. Trans. R. Soc. Lond. A., 287, 373-404.
• Joines, A., Kay, M.G., Karabacak, M.F., Karagül, K., Tokat, S. Performance analysis of Genetic Algorithm Optimization Toolbox via Traveling Salesperson Problem. Editor: Sayers W. Contemporary Issues in Social Sciences and Humanities, 213-221, Landon, UK, AGP Research, 2017.
• Jonker, R., Volgenant, T., 1986. Improving the Hungarian Assignment Algorithm. Operations Research Letters. Vol. 5, Iss. 4, pp. 171-175.
• 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), 6(2), 103-113.
• Kolinski, A., Kolinski, M., 2013. The Use of Hungarian Method in the Evaluation of Production Efficiency (Chapter) in (Eds. RyszardKnosala) Innovations in Management and Production Engineering. Publishing House of Polish Association for Production Management.
• Kuhn, H. W., 1955. The Hungarian method for the Assignment Problem. Naval Research Logistics Quarterly. Volume:2, Issue:1-2, s.83-97
• Kuhn, H.W., 1956. Variants of the Hungarian Method for Assignment Problems. Naval Research Logistics Quarterly. Volume:3, Issue:4, p. 253-258.
• Lawler, E.L., 1971. A solvable case of the traveling salesman problem. Mathematical Programming. Vol. 1, Iss. 1, pp. 267–269.
• Little,J.D.C., Murty, K.G., Sweeney, D.W.,Karel, C., 1963. An Algorithm for the Traveling Salesman Problem.Operations Research.Vol. 11, No. 6, pp. 972-989
• Lucena, A., 1990. Time‐dependent traveling salesman problem–the deliveryman case. Networks. Vol. 20, Iss. 6, pp. 753-763.
• 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, 21(1), 59-84.
• Martello, S., 2010. Jenő Egerváry: From the Origins of the Hungarian Algorithm to Satellite Communication. Cent Eur J Oper Res (2010) 18: 47. https://doi.org/10.1007/s10100-009-0125-z
• Mavrovouniotis, M., Yang, S., 2013. Ant Colony Optimization with Immigrants Schemes for the Dynamic Travelling Salesman Problem with Traffic Factors. Applied Soft Computing. 13(10), 4023-4037.
• Mondal,R. N., Hossain, M. R., Saha, S. K., 2013. An Approach for Solving Traveling Salesman Problem. International Journal of Applied Operational Research. Vol. 3, No. 2, pp. 15-26.
• Munkres, J., 1957. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics. Vol. 5, No. 1, pp. 32-38.
• Nayak, J., Nanda, S., Acharya, S., 2017. Hungarian Method to Solve Travelling Salesman Problem with Fuzzy Cost. International Journal of Mathematics Trends and Technology. (IJMTT) –Vol. 49, Num. 5, pp. 281-284.
• P. C. Gilmore, R. E. Gomory, 1964. Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem. Operations Research. vol. 12, Iss. 5, pp. 655-679. http://dx.doi.org/10.1287/opre.12.5.655
• Ratliff, H.D., Rosenthal, A.S., 1983. Order Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem. Operations Research, 31 (3), 507-521.
• Robinson, J., 1949. On the Hamiltonian Game (A Travelling Salesman Problem). U.S. Air Force Project RAND. RAND Doc. No:204961.
• Şahin, Y., Kulak, O., 2013. Depo Operasyonlarının Planlanması İçin Genetik Algoritma Esaslı Modeller. Uluslararası Alanya İşletme Fakültesi Dergisi, 5(3), 141-153.
• Ş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.
• Universität Heidelberg. “Index of /software/TSPLIB95 /tsp”. http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/tsp/ (18.11.2018).
• Winston, W. L., 2003. Operations Research: Applications and Algorithms, Cengage Learning, 4th edition.
• Zhao, F., Li, S., Sun, J., Mei, D., 2009. Genetic Algorithm for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem. Computers & Industrial Engineering, 56(4), 1642-1648.