A Deep Reinforcement Learning Assisted Heuristic for Solving Traveling Salesman Problems
Ye Tian, Qinghui Zhu, Shuai Shao, Langchun Si, Xingyi Zhang · 2024
The traveling salesman problem (TSP) has long been a central focus in combinatorial optimization, with extensive applications in areas such as logistics and transportation. With the rapid development of machine learning, the research focusing on TSPs has shifted from traditional heuristics, often involving a substantial amount of manually designed rules, to machine learning-based approaches. However, due to the limitations of models and hardware, generative approaches based on machine learning often fall short of expectations in terms of effectiveness, and they generally lag behind well-established traditional heuristics. To address these limitations and leverage the strengths of both approaches, the integration of heuristics with machine learning has become a crucial branch for solving TSPs. Thus, this paper proposes an approach that combines a traditional heuristic, specifically guided fast local search, with a neural network to tackle TSPs, where reinforcement learning techniques are employed to train the neural network. Experimental results showcase the superiority of the proposed approach over the original heuristic, outperforming the majority of mainstream machine learning-based approaches. Notably, the proposed approach achieves zero-gap results for instances with 20 and 50 nodes and a minimal gap of 0.07% for instances with 100 nodes. Compared with existing reinforcement learning-based approaches, the proposed approach also stands out with the best overall performance.