Optimizing and comparison of market chain product distribution problem with different genetic algorithm versions

Year 2023, Volume: 6 Issue: 1, 180 - 196, 10.03.2023

Burak Gülmez

https://doi.org/10.47495/okufbed.1117220

Cited By: 4

Abstract

In this study, it is aimed to carry out product distributions with the lowest distance and lowest cost for a market chain in Kayseri. Since there are too many market branches, the distribution of products in different orders affects the result quite a lot. This problem has been defined as the traveling salesman problem. When the traveling salesman problem is large, it cannot be solved by integer linear programming in polynomial time. It is therefore an NP-hard problem type. Therefore, a genetic algorithm was used for the solution. The genetic algorithm does not guarantee the optimum solution, but it can obtain acceptable solutions. It also obtains these solutions in a short time. The solution obtained is at an acceptable level, even if it is not optimal. In this study, a route was created with a genetic algorithm for 61 markets in Kayseri. In addition to the classical genetic algorithm, genetic algorithm variations that have emerged in recent years have been used As a result of all these algorithms, approximately 80 kilometers has been obtained to visit all the markets. When the solution obtained was examined, it was observed that it was a very good route.

Keywords

Traveling salesman problem, Genetic algorithm, Product distribution

Market zinciri ürün dağıtımı probleminin farklı genetik algoritma versiyonları ile çözümü ve karşılaştırması

Abstract

Bu çalışmada Kayseri’de bulunan bir market zinciri için ürün dağıtımlarının en düşük mesafe ve en düşük maliyet ile gerçekleştirilmesi hedeflenmiştir. Market şubeleri çok fazla olduğu için ürün dağıtımlarının farklı sıralamalar ile yapılması, sonucu oldukça etkilemektedir. Bu problem gezgin satıcı problemi şeklinde tanımlanmıştır. Gezgin satıcı problemi büyük boyutlu olduğunda polinom zaman içerisinde saf tam sayılı doğrusal programlama ile çözülememektedir. Bundan dolayı NP-zor bir problem türüdür. Bu yüzden çözüm için genetik algoritma kullanılmıştır. Genetik algoritma optimum çözümü garanti etmez fakat kabul edilebilir çözümler elde edebilir. Ayrıca bu çözümleri kısa bir zaman içerisinde elde eder. Elde edilen çözüm optimum olmasa bile kabul edilebilir seviyededir. Bu çalışmada Kayseri’deki 61 adet market için genetik algoritma ile bir rota oluşturulmuştur. Klasik genetik algoritmaya ilave olarak son yıllarda çıkan genetik algoritma varyasyonları kullanılmıştır. Tüm bu algoritmalar sonucunda bütün marketleri dolaşmak için yaklaşık 80 kilometrelik bir mesafe elde edilmiştir. Elde edilen çözüm incelendiğinde gayet iyi bir rota olduğu gözlemlenmiştir.

Keywords

Gezgin satıcı problemi, Ürün dağıtımı, Genetik algoritma

References

• Agrawal M., Jain V. Applying improved genetic algorithm to solve travelling salesman problem. Second International Conference on Inventive Research in Computing Applications (ICIRCA), 15-17 Haziran 2020, Coimbatore, Hindistan.
• Alkafaween E., Hassanat A.B., Tarawneh S. Improving initial population for genetic algorithm using the multi linear regression based technique (MLRBT). Communications-Scientific Letters of the University of Zilina 2021; 23 (1): 1–10.
• Ç. Özkır V., Topçu B. Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems. Pamukkale University Journal of Engineering Sciences 2018; 24 (1): 76–82.
• Cansiz O.F., Göçmen S. Distance analysis of multimodal transportation based on traveling salesman problem with particle swarm optimization method. International Journal of Advanced Engineering Research and Science 2018; 5 (6): 264138.
• Cheng B., Lu H., Huang Y., Xu K. Particle swarm optimization algorithm based on self-adaptive excellence coefficients for solving traveling salesman problem. Journal of Computer Applications 2017; 37 (3): 750–754.
• Choong S.S., Wong L.P. A hyper-heuristic based artificial bee colony optimization for the traveling salesman problem. Big Data Summit 2: HPC and AI Empowering Data Analytics, 3-6 Ekim 2018, Pinang, Malezya.
• Choong S.S., Wong L.-P., Lim C.P. An artificial bee colony algorithm with a modified choice function for the traveling salesman problem. Swarm and Evolutionary Computation 2019; 44 (1): 622–635.
• Chowdhury S., Marufuzzaman M., Tunc H., Bian L., Bullington W. A modified ant colony optimization algorithm to solve a dynamic traveling salesman problem: a case study with drones for wildlife surveillance. Journal of Computational Design and Engineering 2019; 6 (3): 368–386.
• Çolak Y.S. Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi 2010; 19 (3): 423–438.
• Di̇kmen H., Di̇kmen H., Elbi̇r A., Ekşi̇ Z., Çeli̇k F. Gezgin satıcı probleminin karınca kolonisi ve genetik algoritmalarla eniyilemesi ve karşılaştırılması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 2014; 18 (1): 8–13.
• Ertuğrul İ., Özçi̇l A. Siyasi parti mitinglerinin gezgin satıcı problemi yaklaşımı ile analizi. Siyaset, Ekonomi ve Yönetim Araştırmaları Dergisi 2016; 4 (4): 223–238.
• Eskandari L., Jafarian A., Rahimloo P., Baleanu D. Mathematical methods in engineering. New York: Springer; 2018.
• Fairee S., Khompatraporn C., Prom-on S., Sirinaovakul B. Combinatorial artificial bee colony optimization with reinforcement learning updating for travelling salesman problem. 16th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), 10-13 Haziran 2019, Pattaya, Tayland.
• Flood M.M. The traveling-salesman problem. Operations Research 1956; 4 (1): 61–75.
• Fujimura T. Quantum algorithm for traveling salesman problem by quarter method. Global Journal of Pure and Applied Mathematics 2020; 16 (5): 711–721.
• Gao W. New ant colony optimization algorithm for the traveling salesman problem. International Journal of Computational Intelligence Systems 2020; 13 (1): 44–55.
• Gülcü Ş., Mahi M., Baykan Ö.K., Kodaz H. A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem. Soft Computing 2018; 22 (5): 1669–1685.
• Gülcü S.D., Örnek H.K. Solution of multiple travelling salesman problem using particle swarm optimization based algorithms. International Journal of Intelligent Systems and Applications in Engineering 2019; 7 (2): 72–82.
• Gülmez B., Kulluk S., Social Spider algorithm for training artificial neural networks. International Journal of Business Analytics (IJBAN) 2019; 6 (4): 32-49.
• Ha Q.M., Deville Y., Pham Q.D., Hà M.H. A hybrid genetic algorithm for the traveling salesman problem with drone. Journal of Heuristics 2020; 26 (2): 219–247.
• Held M., Karp R.M. The traveling-salesman problem and minimum spanning trees. Operations Research 1970; 18 (6): 1138–1162.
• Hussain A., Muhammad Y.S., Nauman Sajid M., Hussain I., Mohamd Shoukry A., Gani S. Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Computational Intelligence and Neuroscience 2017; 2017 (1): 7430125.
• Karaboga D., Gorkemli B. Solving traveling salesman problem by using combinatorial artificial bee colony algorithms. International Journal on Artificial Intelligence Tools 2019; 28 (1): 1950004.
• Karagül K. Prüfer-karagül algoritması: gezgin satıcı problemi için yeni bir yaklaşım. Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi 2019; 6 (2): 452–470.
• Karagül K. Gezgin satıcı problemi iç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.
• Khan I., Maiti M.K. A swap sequence based artificial bee colony algorithm for traveling salesman problem. Swarm and Evolutionary Computation 2019; 44 (1): 428–438.
• Khan I., Pal S., Maiti M.K. A modified particle swarm optimization algorithm for solving traveling salesman problem with imprecise cost matrix. 4th International Conference on Recent Advances in Information Technology (RAIT), 15-17 Mart 2018, New York, ABD.
• Liao E., Liu C. A hierarchical algorithm based on density peaks clustering and ant colony optimization for traveling salesman problem. IEEE Access 2018; 6 (1): 38921–38933.
• Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem. Operations Research 1963; 11 (6): 972–989.
• Moon C., Kim J., Choi G., Seo Y. An efficient genetic algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research 2002; 140 (3): 606–617.
• Nuri̇yeva F., Kizilateş G. Gezgin satıcı problemi için merkezden kenarlara hipersezgisel yöntem. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 2016; 20 (2): 319-323.
• Osaba E., Ser J.D., Sadollah A., Bilbao M.N., Camacho D. A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem. Applied Soft Computing 2018; 71 (1): 277–290.
• Pamosoaji A.K., Setyohadi D.B. Novel graph model for solving collision-free multiple-vehicle traveling salesman problem using ant colony optimization. Algorithms 2020; 13 (6): 153-172.
• Pandiri V., Singh A. An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem. Applied Soft Computing 2019; 78 (1): 481–495.
• Pulat M., Kocakoç İ.D. Gezgin satıcı probleminin çözümünde kullanılan genetik algoritmanın parametrelerinin incelenmesi. Uluslararası İktisadi ve İdari İncelemeler Dergisi 2017; 19 (1): 21–36.
• Pulat M., Kocakoç İ.D. Gezgin satıcı probleminin genetik algoritmalar kullanarak çözümünde çaprazlama operatörlerinin örnek olaylar bazlı incelenmesi. İzmir İktisat Dergisi 2019; 34 (2): 225–243.
• Rokbani N., Kumar R., Abraham A., Alimi A.M., Long H.V., Priyadarshini I. Bi-heuristic ant colony optimization-based approaches for traveling salesman problem. Soft Computing 2020; 25 (5):1–20.
• Şahi̇n Y. Sezgisel ve metasezgisel yöntemlerin gezgin satıcı problemi çözüm performanslarının kıyaslanması. Bolu Abant İzzet Baysal Üniversitesi Sosyal Bilimler Enstitüsü Dergisi 2019; 19 (4): 911–932.
• Şahi̇n Y., Karagül K. Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 2019; 25 (1): 106–114.
• Sharma S., Jain V. A novel approach for solving tsp problem using genetic algorithm problem. IOP Conference Series: Materials Science and Engineering 2021; 1116 (1): 012194.
• Tüker M., Ballı S., Pembeci İ. Çok etmenli sistemlerde netlogo ile karınca kolonisi optimizasyonu. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 2013; 19 (2): 88–96.
• Wang K. P., Huang L., Zhou C. G., Pang W. Particle swarm optimization for traveling salesman problem. International Conference on Machine Learning and Cybernetics, 27-28 Haziran 2022, Toyama, Japonya.
• Wang Y., Xu N. A hybrid particle swarm optimization method for traveling salesman problem. International Journal of Applied Metaheuristic Computing 2017; 8 (3): 53–65.
• Whitley D. A genetic algorithm tutorial. Statistics and Computing 1994; 4 (2): 65–85.
• Yildirim T., Kalayci C.B., Mutlu Ö. Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 2016; 22 (1): 64–70.
• Zhong Y., Lin J., Wang L., Zhang H. Hybrid discrete artificial bee colony algorithm with threshold acceptance criterion for traveling salesman problem. Information Sciences 2017; 421 (1): 70–84.
• Zhong Y., Lin J., Wang L., Zhang H. Discrete comprehensive learning particle swarm optimization algorithm with metropolis acceptance criterion for traveling salesman problem. Swarm and Evolutionary Computation 2018; 42 (1): 77–88.