TY  - JOUR
T1  - GEZGİN SATICI PROBLEMİNİN ÇÖZÜMÜ İÇİN MACAR ALGORİTMASI ESASLI YENİ BİR ÇÖZÜM YAKLAŞIMI
TT  - A NOVEL SOLUTION APPROACH FOR SOLVING TRAVELLING SALESMAN PROBLEM BASED ON HUNGARIAN ALGORITHM
AU  - Karagül, Kenan
PY  - 2019
DA  - September
Y2  - 2019
DO  - 10.21923/jesd.523623
JF  - Mühendislik Bilimleri ve Tasarım Dergisi
JO  - MBTD
PB  - Süleyman Demirel University
WT  - DergiPark
SN  - 1308-6693
SP  - 561
EP  - 571
VL  - 7
IS  - 3
LA  - tr
AB  - Bu çalışmada kombinatoryal optimizasyonalanının ünlü problemlerinden olan gezgin satıcı ve atama problemleri arasındakiilişkiden faydalanan yeni bir çözüm algoritması önerilmektedir. Atamaproblemleri için optimal çözümü veren Macar Algoritması ile simetrik gezginsatı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ı testproblemleri ile analiz edilmiş ve bilimsel yazında yer alan bazı çalışmalarınsonuçları ile kıyaslama yapılmıştır. Sonuç olarak, önerilen yöntemin hem çözümhızı hem de çözüm kalitesi bakımından kıyaslanan yöntemlere göre iyi olduğugösterilmiştir. Özellikle, problem boyutu büyüdükçe kıyaslanan yöntemlerin çözümsüresi uzarken, önerilen yöntem büyük boyutlu problemler için de hızlı çözümlersunabilmektedir.
KW  - Gezgin satıcı problemi
KW  - Macar algoritması
KW  - Munkres algoritması
KW  - En yakın komşu sezgiseli
KW  - 2-Opt algoritması
N2  - In this study, a novel solution algorithm which takes advantage of therelationship between traveling salesman and assignment problems which arefamous problems of combinatorial optimization area is proposed. By using theHungarian Algorithm, which provides the optimal solution for the assignmentproblems, 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 frequentlyused traveling salesman test problems and compared with the results of somestudies in the scientific literature. As a result, it has been shown that theproposed method is superior to the other methods with regard to solution speedand quality. In particular, as the size of the problem increases, the solutiontimes of the compared methods are getting longer, while the proposed method canalso provide fast solutions for large-scale problems.
CR  - 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.
CR  - Balas, E., Christofides, N., 1981. A Restricted LagrangeanApproach to the Traveling Salesman Problem. Mathematical Programming. 21(1), 19–46.
CR  - 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
CR  - Basirzadeh, H., 2014. Ones Assignment Method for Solving Traveling Salesman Problem. Journal of Mathematics and Computer Science. Vol. 10, Iss. 4, pp. 258-265.
CR  - Bertsekas, D.P., 1981. A New Algorithm for the Assignment Problem. Mathematical Programming. 21: 152. https://doi.org/10.1007/BF01584237
CR  - Burkard, R.E., 1979. Travelling Salesman and Assignment Problems: A Survey. Annals of Discrete Mathematics. Vol. 4, pp. 193-215
CR  - Chitty, D. M., 2017. Applying ACO To Large Scale TSP Instances. UK Workshop on Computational Intelligence, pp. 104-118. Springer, Cham, 2017
CR  - Croes, G. A. (1958). A Method for Solving Traveling-Salesman Problems. Operations Research, 6 (6), 791–812.
CR  - Dantzig, G.B., Thapa, M.N., 1997. Linear programming 1: introduction. Springer-Verlang New York, USA.
CR  - 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.
CR  - Frank, A., 2005. On Kuhn's Hungarian Method—A tribute from Hungary.Naval Research Logistics Quarterly. Vol. 52, Iss. 1, pp. 2-5.
CR  - 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.
CR  - 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
CR  - Jewell, W.S.,1977. The Analytic Methods of Operations Research. Phil. Trans. R. Soc. Lond. A., 287, 373-404.
CR  - 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.
CR  - Jonker, R., Volgenant, T., 1986. Improving the Hungarian Assignment Algorithm. Operations Research Letters. Vol. 5, Iss. 4, pp. 171-175.
CR  - 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.
CR  - 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.
CR  - Kuhn, H. W., 1955. The Hungarian method for the Assignment Problem. Naval Research Logistics Quarterly. Volume:2, Issue:1-2, s.83-97
CR  - Kuhn, H.W., 1956. Variants of the Hungarian Method for Assignment Problems. Naval Research Logistics Quarterly. Volume:3, Issue:4, p. 253-258.
CR  - Lawler, E.L., 1971. A solvable case of the traveling salesman problem. Mathematical Programming. Vol. 1, Iss. 1, pp. 267–269.
CR  - 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
CR  - Lucena, A., 1990. Time‐dependent traveling salesman problem–the deliveryman case. Networks. Vol. 20, Iss. 6, pp. 753-763.
CR  - 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.
CR  - 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
CR  - 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.
CR  - 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.
CR  - 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.
CR  - 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.
CR  - 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
CR  - 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.
CR  - Robinson, J., 1949. On the Hamiltonian Game (A Travelling Salesman Problem). U.S. Air Force Project RAND. RAND Doc. No:204961.
CR  - Ş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.
CR  - Ş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.
CR  - Universität Heidelberg. “Index of /software/TSPLIB95 /tsp”. http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/tsp/ (18.11.2018).
CR  - Winston, W. L., 2003. Operations Research: Applications and Algorithms, Cengage Learning, 4th edition.
CR  - 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.
UR  - https://doi.org/10.21923/jesd.523623
L1  - https://dergipark.org.tr/en/download/article-file/805898
ER  -