Solving the Traveling Salesman Problem with Greedy Genetic Algorithm
Article Sidebar
Published
Jun 30, 2024
Main Article Content
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: 20 sep. 2024.
Section
Natural Sciences - Regular Research Paper
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
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
[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