Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
7-2023
Abstract
The traveling salesman problem (TSP) is the most well-known problem in combinatorial optimization which hasbeen studied for many decades. This paper focuses on dealing with one of the most difficult TSP variants named thequadratic traveling salesman problem (QTSP) that has numerous planning applications in robotics and bioinformatics.The goal of QTSP is similar to TSP which finds a cycle visiting all nodes exactly once with minimum total costs. However, the costs in QTSP are associated with three vertices traversed in succession (instead of two like in TSP). This leadsto a quadratic objective function that is much harder to solve.To efficiently solve the problem, we propose a hybrid geneticalgorithm including a local search procedure for intensification and a new mutation operator for diversification. The local search is composed of a restricted double-bridge move(a variant of 4-Opt); and we show the neighborhood can beevaluated in O(n2), the same complexity as for the classicalTSP. The mutation phase is inspired by a ruin-and-recreatescheme. Experimental results conducted on benchmark instances show that our method significantly outperforms state-of-the-art algorithms in terms of solution quality. Out of the800 instances tested, it finds 437 new best-known solutions.
Keywords
Benchmarking, Combinatorial optimization, Genetic algorithms, Local search (optimization), Robot programming
Discipline
Artificial Intelligence and Robotics | Databases and Information Systems
Research Areas
Data Science and Engineering; Information Systems and Management; Intelligent Systems and Optimization
Publication
33rd International Conference on Automated Planning and Scheduling (ICAPS-2023), Prague, Czech Republic, July 2023
Identifier
10.1609/icaps.v33i1.27212
Publisher
Association for the Advancement of Artificial Intelligence
City or Country
Prague, Czech Republic
Citation
PHAM, Quang Anh; LAU, Hoong Chuin; HA, Minh Hoang; and VU, Lam.
An efficient hybrid genetic algorithm for the quadratic traveling salesman problem. (2023). 33rd International Conference on Automated Planning and Scheduling (ICAPS-2023), Prague, Czech Republic, July 2023.
Available at: https://ink.library.smu.edu.sg/sis_research/8253
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.