Multiple travelling salesman problem with fuzzy c-means and ant colony optimization algorithms

Year 2023, Volume: 26 Issue: 49, 185 - 201, 23.06.2023

Derya Dikbıyık , Selçuk Alp

https://doi.org/10.31795/baunsobed.1005070

Abstract

Sezgisel algoritmalar, kabul edilebilir sürede optimuma yakın çözümler verebilen ve çok büyük boyutlu optimizasyon problemleri için kullanılabilen algoritmalardır. En iyi çözümün bulunacağı garanti edilememekle beraber, bulunan çözümün kabul edilebilir düzeyde olması, çözüme kolay ve hızlı ulaşılabilmesi açısından kullanımı oldukça yaygın olan yöntemlerdir. Sezgisel yöntemlerde problemin çözümüne yönelik yaklaşımlar; karar verme, optimizasyon, bulanık mantık, yapay zeka, makine öğrenmesi, derin öğrenme şeklinde karşımıza çıkar. Bu çalışmada; pek çok alanda uygulaması olan Gezgin Satıcı Problemi (GSP) için optimuma en yakın çözümü hızlı bir şekilde bulabilmek amacıyla Karınca Kolonisi Optimizasyonu (KKO) yöntemi seçilmiştir. Rastgele seçilen verileri gruplandırmak amacıyla da Bulanık C-Ortalamalı Kümeleme (BCO) Algoritması kullanılmıştır. Çalışmada kullanılan veriler BCO algoritması kullanılarak ayrı ayrı 3, 4 ve 5 kümeye ayrılmış; elde edilen veri setleri Çoklu KKO ile değerlendirilmiş ve sonuçlar karşılaştırılmıştır.

Keywords

Karınca kolonisi optimizasyonu, Bulanık c-ortalamalı kümeleme, Çoklu gezgin satıcı problemi

Multiple travelling salesman problem with fuzzy c-means and ant colony optimization algorithms

Abstract

Heuristic algorithms are algorithms that can provide near-optimum solutions for very large-scale optimization problems in an acceptable time. They are commonly used methods in terms of being at an acceptable level and reaching a solution easily and quickly, although it cannot be guaranteed that the best solution will be found. Problem solving approaches being used in heuristic methods; decision making, optimization, fuzzy logic, artificial intelligence, machine learning, deep learning. In this paper; chosen method in order to find the best solution of route optimization for the Travelling Salesman Problem (TSP), which has applications in many areas, is that Ant Colony Optimization (ACO). For classification of the data, that is randomly selected, Fuzzy C-Mean Clustering (FMC) Algorithm has being used. The data set has being separated into 3, 4 and 5 clusters and all cluster data sets obtained were evaluated with Multiple ACO and then the results were compared.

Keywords

Ant colony optimization, Fuzzy c-means clustering, Multiple travelling salesman problem

References

• Aziz Z.A. (2015), Ant colony hyper-heuristics for travelling salesman problem, IEEE International Symposium on Robotics and Intelligent Sensors (IEEE IRIS2015), Procedia Computer Science 76: 534-538.
• Bezdek J.C. (1981), Pattern recognition with fuzzy objective function algorithms, New York: Plenum Press. Christofides N., Eilon S. (1969), An algorithm for the vehicle-dispatching problem, Journal of the Operational Research Society, 20, 309–318.
• Cura T. (2008), Modern sezgisel teknikler ve uygulamaları, İstanbul: Papatya Yayınları.
• Dantzig G., Fulkerson R., Johnson S. (1954), Solution of a large-scale traveling-salesman problem, Journal of the Operations Research Society of America, 2(4), 393-410.
• Dunn, J.C. (1974), A fuzzy relative ISODATA process and its use in detecting compact well-separated clusters, Journal of Cybernetics, 3(3), 32-57.
• Gilmore P.C., Gomory R.E. (1964), Sequencing a one state-variable machine: a solvable case of the traveling salesman problem, Journal of Operations Research, 12(5), 655-679.
• Guo Y., Zi Y., Jiang Y. (2020), Contrastive study of distributed multitask fuzzy c-means clustering and traditional clustering algorithms, Communication, Image and Signal Processing (CCISP), 2020 5th International Conference on. :239-245 Nov, 2020.
• Işık M., Çamurcu A.Y. (2007), K-means, k-medoids ve bulanık c-means algoritmalarının uygulamalı olarak performanslarının tespiti, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 6(11), 31-45.
• Junjie P., Dingwei W. (2006), An ant colony optimization algorithm for multiple travelling salesman problem, Proceedings of the First International Conference on Innovative Computing, Information and Control (ICICIC'06).
• Karg R.L., Thompson G.L. (1964), A heuristic approach to solving travelling salesman problems, Journal of Management Science, 10(2), 225-248.
• Kuzu S., Önay O., Şen U., Tunçer M., Yıldırım B.F., Keskintürk T. (2014), Gezgin satıcı problemlerinin metasezgiseller ile çözümü, İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(1), 1-27.
• Lammel B., Gryzlak K., Dornberger R., Hanne T. (2016), An ant colony system solving the travelling salesman region problem, Computational and Business Intelligence (ISCBI), 2016 4th International Symposium on. :125-131 Sep, 2016.
• Lin S., Kernighan B.W. (1973), An effective heuristic algorithm for the traveling-salesman problem, Journal of Operations Research, 21(2), 498-516.
• Liu Z., Wang X., Yu H., Xing R. (2020), Thermal efficiency prediction model of cement clinker production based on fuzzy c-means monitoring clustering, 2020 39th Chinese Control Conference (CCC) Chinese Control Conference (CCC): 5391-5394 Jul, 2020.
• Mausor F.H., Jaafar J., Taib S.M. (2020), Missing values ımputation using fuzzy c means based on correlation of variable, 2020 International Conference on Computational Intelligence (ICCI) Computational Intelligence (ICCI),2020 International Conference on. :261-265 Oct, 2020.
• Mavrovouniotis, M., Shengxiang Y., Xin Y. (2014), Multi-colony ant algorithms for the dynamic travelling salesman problem, Computational Intelligence in Dynamic and Uncertain Environments (CIDUE), 2014 IEEE Symposium on. :9-16 Dec, 2014.
• Meniailov I., Chumachenko D., Bazilevych K. (2020), Determination of heart disease based on analysis of patient statistics using the fuzzy c-means clustering algorithm, 2020 IEEE Third International Conference on Data Stream Mining & Processing (DSMP) Data Stream Mining and Processing (DSMP), 2020 IEEE Third International Conference on. :333-336 Aug, 2020.
• Nicholson T. A. J. (1967), A sequential method for discrete optimization problems and its application to the assignment, travelling salesman, and three machine scheduling problems, IMA Journal of Applied Mathematics, 3(4), 362–375.
• Ratliff H.D., Rosenthal A.S. (1983), Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Journal of Operations Research, 31(3), 507-521.
• Shen Y., Pedrycz W., Chen Y., Wang X., Gacek A. (2020), Hyperplane division in fuzzy c-means: clustering big data, IEEE Transactions on Fuzzy Systems IEEE Trans. Fuzzy Syst. Fuzzy Systems, IEEE Transactions on. 28(11):3032-3046 Nov, 2020.
• Shrivastava K., Kumar S. (2018), The effectiveness of parameter tuning on ant colony optimization for solving the travelling salesman problem, 8th International Conference on Communication Systems and Network Technologies (CSNT).
• Srikakulapu R., Vinatha U. (2018), Optimized design of collector topology for offshore wind farm based on ant colony optimization with multiple travelling salesman problem, Journal of Modern Power Systems and Clean Energy, 6(6): 1181-1192.
• Şahin Y. (2019), Sezgisel ve metasezgisel yöntemlerin gezgin satıcı problemi çözüm performanslarının kıyaslanması, BAİBÜ Sosyal Bilimler Enstitüsü Dergisi, 19(4), 911-932.
• Thilagam M., Arunesh K., Rajeshkann, A. (2020), Analysis of brain MRI images for tumor segmentation using fuzzy c means algorithm, 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC) Electronics and Sustainable Communication Systems (ICESC), 2020 International Conference on. :183-186 Jul, 2020.
• Tomanova P., Holy V. (2020), Ant colony optimization for time-dependent travelling salesman problem, Intelligent Systems, In Proceedings of the 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, s:47-51, New York.
• Türe H., Başer F. (2015), Bulanık c-ortalama kümeleme algoritması ile ülke risk değerlendirmesi, İstanbul Üniversitesi İktisat Fakültesi Ekonometri ve İstatistik Dergisi, 23, 16-33.
• Valente de Oliveira J., Pedrycz W. (2007), Advances in fuzzy clustering and its applications, New York: John Wiley & Sons, Ltd.