Optimization Techniques for Solving the Travelling Salesman Problem in Robot Operating System
DOI:
https://doi.org/10.64882/ijrt.v14.i1.1095Keywords:
Travelling Salesman Problem, Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization, Metaheuristic Algorithms, Path Planning, Mobile Robot Navigation, Robot Operating SystemAbstract
The Travelling Salesman Problem (TSP) represents a fundamental combinatorial optimization challenge with critical applications in mobile robotics. This paper presents a comprehensive analysis of three metaheuristic algorithms—Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO)—for TSP solution in Robot Operating System (ROS) environments. The proposed system integrates GMapping for simultaneous localization and mapping with Dynamic Window Approach (DWA) for real-time path planning. Extensive simulations across 5-500 nodes reveal that ACO achieves optimal path lengths (20-23% shorter than GA and PSO), while GA offers superior computation speed. Key findings indicate algorithm selection should be based on application requirements: GA for time-critical scenarios, ACO for path-optimal solutions. This research provides actionable insights for deploying optimization techniques in real-world mobile robotics applications.
References
Barber, R., Crespo, J., Gomez, C., Hernandez, A. C., & Galli, M. (2018). Mobile robot navigation in indoor environments: Geometric, topological and semantic navigation. In Applications of Mobile Robots (pp. 88-110). InTech.
Dorigo, M., & Gambardella, L. M. (2023). Ant colonies for the travelling salesman problem. BioSystems, 43(2), 73-81.
Fairchild, C., & Harman, T. L. (2017). ROS Robotics by Example. Packt Publishing.
Fox, D., Burgard, W., & Thrun, S. (2021). The dynamic window approach to collision avoidance. IEEE Transactions on Robotics and Automation, 14(1), 126-133.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
Grisetti, G., Stachniss, C., & Burgard, W. (2025). Improving grid maps with Rao-Blackwellized particle filters. IEEE Transactions on Robotics, 21(6), 1188-1197.
Gutin, G., & Punnen, A. P. (2024). The Travelling Salesman Problem and its Variations. Springer.
Kennedy, J., & Eberhart, R. (2024). Particle swarm optimization. In Proceedings of ICNN'95. IEEE.
Montana, D. J. (1994). Genetic algorithms: Theory and application. IEEE Transactions on Evolutionary Computation, 1(1), 17-27.
Wang, C., Tok, Y. C., Poolat, R., Chattopadhyay, S., & Elara, M. R. (2022). How to Secure autonomous mobile robots? An approach with fuzzing, detection and mitigation. Journal of Systems Architecture, 108, 101-123.
Wu, Q., Chen, Z., Wang, L., Lin, H., Jiang, Z., Li, S., & Chen, D. (2020). Real-time dynamic path planning of mobile robot: A novel hybrid heuristic optimization algorithm. Sensors, 20(188), 1-18.
Xu, L., Wang, D., Song, B., & Cao, M. (2017). Global smooth path planning for mobile robots based on continuous Bezier curve. In Proceedings of 2017 Chinese Automation Congress (pp. 2081-2085).
Downloads
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
