Application of Genetic Algorithms to Solve the Clustered Generalized Traveling Salesman Problem
Main Article Content
Abstract
This paper explores the application of genetic algorithms (GAs) to solve the Traveling Salesman Problem (TSP) and its variants, specifically the Clustered Generalized Traveling Salesman Problem (CGTSP). In CGTSP, nodes (or cities) are grouped into clusters, and the primary objective is to determine the most efficient route that includes precisely one node from each cluster while minimizing the overall travel distance. This particular variation plays a crucial role in practical scenarios, such as logistics, vehicle routing, and network design. In these applications, destinations are naturally grouped, and visiting one representative from each group is often essential or mandatory. CGTSP effectively tackles the complexity and real-world constraints more adeptly than the traditional TSP by integrating the element of clustering. This feature makes it a versatile and applicable model for a wide range of industrial and scientific problems. The study aims to assess the effectiveness of Genetic Algorithms (GAs) in solving these complex optimization problems. The paper provides an overview of the TSP and CGTSP, shows how to rewrite a CGTSP in the form of a TSP and vice versa, discusses the fundamentals of GAs, and presents the application of GAs to the problem variants. In addition, we investigate a new method to generate the initial population in the genetic algorithm and evaluate the proposed algorithm's performance through experimental results. The findings highlight the potential of GAs as powerful tools for solving challenging optimization problems.
Keywords
Genetic Algorithms, Traveling Salesman Problem, Clustered Generalized Traveling Salesman Problem (CGTSP), Combinatorial Optimization
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
[1] D. L. Applegate et al., The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006, pp. 606.
[2] G. Prokudin et al., Traveling Salesman Problem in the function of freight transport optimization, Journal of Sustainable Development of Transport and Logistics, vol. 3, pp. 29–36, Apr. 2018. https://doi.org/10.14254/jsdtl.2018.3-1.3
[3] G. Laporte, The Traveling Salesman Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, vol. 59, no. 2, pp. 231–247, 1992.
[4] Agash Uthayasuriyan et al., A comparative study on Genetic Algorithm and Reinforcement Learning to solve the Traveling Salesman Problem, Research Reports on Computer Science, vol. 3, pp. 1–12, 2023. https://doi.org/10.37256/rrcs.2320232642
[5] M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, 1998.
[6] F. Gerges, G. Zouein, and D. Azar, Genetic algorithms with local optima handling to solve sudoku puzzles, Proceedings of the 2018 International Conference on Computing and Artificial Intelligence, pp. 19–22, 2018. https://doi.org/10.1145/3194452.3194463
[7] M. C. Burkhart and G. Ruiz, Neuroevolutionary representations for learning heterogeneous treatment effects, Journal of Computational Science, vol. 71, pp. 102054, 2023.
[8] Y. Du et al., Simultaneous pickup and delivery Traveling Salesman Problem considering the express lockers using attention route planning network, Computational Intelligence and Neuroscience, vol. 2021, no. 1, pp. 5590758, 2021.
[9] M. M. Sepehri, S. M. H. Motlagh, and J. Ignatius, A model for optimal routing of dangerous substances in warehousing operations via k-nested GTSP, International Journal of Nonlinear Sciences and Numerical Simulation, vol. 11, no. 9, pp. 701–704, 2010.
[10] K. Helsgaun, Solving the Clustered Traveling Salesman Problem using the Lin-Kernighan-Helsgaun Algorithm, Roskilde University, May 2014, pp. 1–13. [11] O. Cosma, P. Pop, and L. Cosma, A hybrid based genetic algorithm for solving the Clustered Generalized Traveling Salesman Problem, Hybrid Artificial Intelligent Systems, LNCS, pp. 352–362, Aug. 2023. https://doi.org/10.1007/978-3-031-40725-3_30
[12] P. Baniasadi et al., A transformation technique for the Clustered Generalized Traveling Salesman Problem with applications to logistics, European Journal of Operational Research, vol. 285, pp. 444–457, 2020.
[13] B. Zolghadr-Asli, Computational Intelligence-based Optimization Algorithms: From Theory to Practice, 1st ed., CRC Press, 2024, pp. 356.
[2] G. Prokudin et al., Traveling Salesman Problem in the function of freight transport optimization, Journal of Sustainable Development of Transport and Logistics, vol. 3, pp. 29–36, Apr. 2018. https://doi.org/10.14254/jsdtl.2018.3-1.3
[3] G. Laporte, The Traveling Salesman Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, vol. 59, no. 2, pp. 231–247, 1992.
[4] Agash Uthayasuriyan et al., A comparative study on Genetic Algorithm and Reinforcement Learning to solve the Traveling Salesman Problem, Research Reports on Computer Science, vol. 3, pp. 1–12, 2023. https://doi.org/10.37256/rrcs.2320232642
[5] M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, 1998.
[6] F. Gerges, G. Zouein, and D. Azar, Genetic algorithms with local optima handling to solve sudoku puzzles, Proceedings of the 2018 International Conference on Computing and Artificial Intelligence, pp. 19–22, 2018. https://doi.org/10.1145/3194452.3194463
[7] M. C. Burkhart and G. Ruiz, Neuroevolutionary representations for learning heterogeneous treatment effects, Journal of Computational Science, vol. 71, pp. 102054, 2023.
[8] Y. Du et al., Simultaneous pickup and delivery Traveling Salesman Problem considering the express lockers using attention route planning network, Computational Intelligence and Neuroscience, vol. 2021, no. 1, pp. 5590758, 2021.
[9] M. M. Sepehri, S. M. H. Motlagh, and J. Ignatius, A model for optimal routing of dangerous substances in warehousing operations via k-nested GTSP, International Journal of Nonlinear Sciences and Numerical Simulation, vol. 11, no. 9, pp. 701–704, 2010.
[10] K. Helsgaun, Solving the Clustered Traveling Salesman Problem using the Lin-Kernighan-Helsgaun Algorithm, Roskilde University, May 2014, pp. 1–13. [11] O. Cosma, P. Pop, and L. Cosma, A hybrid based genetic algorithm for solving the Clustered Generalized Traveling Salesman Problem, Hybrid Artificial Intelligent Systems, LNCS, pp. 352–362, Aug. 2023. https://doi.org/10.1007/978-3-031-40725-3_30
[12] P. Baniasadi et al., A transformation technique for the Clustered Generalized Traveling Salesman Problem with applications to logistics, European Journal of Operational Research, vol. 285, pp. 444–457, 2020.
[13] B. Zolghadr-Asli, Computational Intelligence-based Optimization Algorithms: From Theory to Practice, 1st ed., CRC Press, 2024, pp. 356.