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

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

1. 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.
2. Balas, E., Christofides, N., 1981. A Restricted LagrangeanApproach to the Traveling Salesman Problem. Mathematical Programming. 21(1), 19–46.
3. 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
4. Basirzadeh, H., 2014. Ones Assignment Method for Solving Traveling Salesman Problem. Journal of Mathematics and Computer Science. Vol. 10, Iss. 4, pp. 258-265.
5. Bertsekas, D.P., 1981. A New Algorithm for the Assignment Problem. Mathematical Programming. 21: 152. https://doi.org/10.1007/BF01584237
6. Burkard, R.E., 1979. Travelling Salesman and Assignment Problems: A Survey. Annals of Discrete Mathematics. Vol. 4, pp. 193-215
7. Chitty, D. M., 2017. Applying ACO To Large Scale TSP Instances. UK Workshop on Computational Intelligence, pp. 104-118. Springer, Cham, 2017
8. Croes, G. A. (1958). A Method for Solving Traveling-Salesman Problems. Operations Research, 6 (6), 791–812.

9. Dantzig, G.B., Thapa, M.N., 1997. Linear programming 1: introduction. Springer-Verlang New York, USA.
10. 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.
11. Frank, A., 2005. On Kuhn's Hungarian Method—A tribute from Hungary.Naval Research Logistics Quarterly. Vol. 52, Iss. 1, pp. 2-5.
12. 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.
13. 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
14. Jewell, W.S.,1977. The Analytic Methods of Operations Research. Phil. Trans. R. Soc. Lond. A., 287, 373-404.
15. 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.
16. Jonker, R., Volgenant, T., 1986. Improving the Hungarian Assignment Algorithm. Operations Research Letters. Vol. 5, Iss. 4, pp. 171-175.
17. 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.
18. 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.
19. Kuhn, H. W., 1955. The Hungarian method for the Assignment Problem. Naval Research Logistics Quarterly. Volume:2, Issue:1-2, s.83-97
20. Kuhn, H.W., 1956. Variants of the Hungarian Method for Assignment Problems. Naval Research Logistics Quarterly. Volume:3, Issue:4, p. 253-258.
21. Lawler, E.L., 1971. A solvable case of the traveling salesman problem. Mathematical Programming. Vol. 1, Iss. 1, pp. 267–269.
22. 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
23. Lucena, A., 1990. Time‐dependent traveling salesman problem–the deliveryman case. Networks. Vol. 20, Iss. 6, pp. 753-763.
24. 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.
25. 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
26. 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.
27. 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.
28. 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.
29. 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.
30. 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
31. 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.
32. Robinson, J., 1949. On the Hamiltonian Game (A Travelling Salesman Problem). U.S. Air Force Project RAND. RAND Doc. No:204961.
33. Ş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.
34. Ş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.
35. Universität Heidelberg. “Index of /software/TSPLIB95 /tsp”. http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/tsp/ (18.11.2018).
36. Winston, W. L., 2003. Operations Research: Applications and Algorithms, Cengage Learning, 4th edition.
37. 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.