Solving the Traveling Salesman Problem with Greedy Genetic Algorithm

Main Article Content

Recep Colak

Abstract

The traveling salesman problem (TSP) is an NP-hard problem that is difficult to solve. TSP is a general problem with many sub-branches such as vehicle routing, cargo distribution, circuit element placement for electronic cards, school busses. The problem can be solved in N! time by trying all possibilities. When the number of points to be visited is small, precise methods can be used, while when the number of points is high, a solution in an acceptable time is not possible with precise methods. When the number of points is large, the problem is solved with heuristic algorithms that give solutions close to the optimum solution. Genetic Algorithm (GA), which is an heuristic method, is a frequently used method in solving the TSP problem. In this study, the effect of assigning the initial chromosomes of GA with Greedy Heuristic (GH) on the solution was investigated. In the Greedy approach, the first point is randomly selected, the next visit point is selected, and the closest point to the last selected point is selected and the tours are completed. The obtained results showed that the initial routes were assigned with GH instead of random assignment, giving better solutions. In addition, fewer chromosomes were needed in the solutions obtained with GH, thus shortening the runtime.

Article Details

How to Cite
COLAK, Recep. Solving the Traveling Salesman Problem with Greedy Genetic Algorithm. Journal of Multidisciplinary Developments, [S.l.], v. 9, n. 1, p. 9-18, june 2024. ISSN 2564-6095. Available at: <http://jomude.com/index.php/jomude/article/view/111>. Date accessed: 16 july 2024.
Section
Natural Sciences - Regular Research Paper

References

[1] V. Cacchiani, C. Contreras-Bolton, L. M. Escobar-Falcón, and P. Toth. (2023). A matheuristic algorithm for the pollution and energy minimization traveling salesman problems. International Transactions in Operational Research, vol. 30, no. 2, pp. 655–687.

[2] R. M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan. (2010). An exact method for the double TSP with multiple stacks. International Transactions in Operational Research, vol. 17, no. 5, pp. 637–652.

[3] N. M. Yunos, A. Shurbevski, and H. Nagamochi. (2016). A polynomial-space exact algorithm for TSP in degree-6 graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9943 LNCS, pp. 228–240.

[4] L. Shen and B. W. Kernighan. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, vol. 21, no. 2, pp. 498–516.

[5] N. Rokbani et al..(2021). Bi-heuristic ant colony optimization-based approaches for traveling salesman problem. Soft Computing, vol. 25, no. 5, pp. 3775–3794.

[6] A. Uǧur, S. Korukoǧlu, A. Çalişkan, M. Cinsdikici, and A. Alp. (2009). Genetic algorithm based solution for TSP on a sphere. Mathematical and Computational Applications, vol. 14, no. 3, pp. 219–228.

[7] C. A. R. Jahuira and E. C. Vargas. (2002). Hybrid genetic algorithm with exact techniques applied to TSP. in In Second international workshop on Intelligent systems design and application, pp. 110–124.
[8] M. Mahjoob, S. S. Fazeli, S. Milanlouei, L. S. Tavassoli, and M. Mirmozaffari. (2022). A modified adaptive genetic algorithm for multi-product multi-period inventory routing problem. Sustainable Operations and Computers, vol. 3, pp. 1–9.

[9] E. Messaoud. (2022). Solving a stochastic programming with recourse model for the stochastic electric capacitated vehicle routing problem using a hybrid genetic algorithm. European Journal of Industrial Engineering, vol. 16, no. 1, pp. 71–90.

[10] A. Maskooki, K. Deb, and M. Kallio. (2022). A customized genetic algorithm for bi-objective routing in a dynamic network. European Journal of Operational Research, vol. 297, no. 2, pp. 615–629.

[11] V. Chvatal. (1979). A greedy heuristic for the set-covering problem. Mathematics of operations research, vol. 4, no. 3, pp. 233–235.

[12] N. L. Biggs, E. K. Lloyd, and R. J. Wilson, Graph Theory 1736-1936. New York: Oxfort University Press, 1986.

[13] Y. Şahin, K. Karagül. (2019). Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1), 106-114. vol. 25, no. 1, pp. 106–114.

[14] K. Karagul, Y. Sahin, E. Aydemir, and A. Oral. (2019). A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption. International Series in Operations Research and Management Science, vol. 273, pp. 161–187.

[15] T. Yiğit, Ö. Ünsal, and Ö. Deperlioğlu. (2018). Using the metaheuristic methods for real-time optimisation of dynamic school bus routing problem and an application. International Journal of Bio-Inspired Computation, vol. 11, no. 2, pp. 123–133.

[16] Atmaca, E. (2012). Bir kargo şirketinde araç rotalama problemi. Tübav Bilim Dergisi, 5(2), 12-27.

[17] D. Schubert, H. Kuhn, and A. Holzapfel. (2021). Same-day deliveries in omnichannel retail: Integrated order picking and vehicle routing with vehicle-site dependencies. Naval Research Logistics, vol. 68, no. 6, pp. 721–744.

[18] Y. Wang. (2019). PCB Drill Path Optimization by Improved Genetic Algorithm. 5th International Conference on Control, Automation and Robotics. ICCAR 2019, 2019, pp. 744–748.

[19] D. Messon, D. Verma, M. Rastogi, and A. Singh. (2022). Comparative Study of Time Optimization Algorithms for Traveling Salesman Problem. Lecture Notes in Networks and Systems, vol. 392, pp. 555–566.

[20] J. Wang et al..(2022). A Carnivorous Plant Algorithm With Heuristic Decoding Method for Traveling Salesman Problem. IEEE Access, vol. 10, pp. 97142–97164.

[21] O. Nurdiawan, F. A. Pratama, D. A. Kurnia, Kaslani, and N. Rahaningsih. (2020). Optimization of Traveling Salesman Problem on Scheduling Tour Packages using Genetic Algorithms. Journal of Physics: Conference Series, vol. 1477, no. 5, pp. 141–151.

[22] A. Roy, A. Manna, and S. Maity. (2019). A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique, Decision Making: Applications in Management and Engineering, vol. 2, no. 2, pp. 100–111.
[23] D. E. Gomes, M. I. D. Iglésias, A. P. Proença, T. M. Lima, and P. D. Gaspar. (2021). Applying a genetic algorithm to a m-tsp: Case study of a decision support system for optimizing a beverage logistics vehicles routing problem. Electronics (Switzerland), vol. 10, no. 18.

[24] H. Cui, J. Qiu, J. Cao, M. Guo, X. Chen, and S. Gorbachev. (2023). Route optimization in township logistics distribution considering customer satisfaction based on adaptive genetic algorithm. Mathematics and Computers in Simulation, vol. 204, pp. 28–42.

[25] Kara Yolları Genel Müdürlüğü. (2023). https://www.kgm.gov.tr/SiteCollectionDocuments/KGMdocuments/Root/Uzakliklar/ilmesafe.xlsx
Date of Access: 15/12/2022

[26] Http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/atsp/
Date of Access: 15/12/2022