This paper presents an overview of deep learning(DL)-based algorithms designed for solving the traveling salesman problem(TSP),categorizing them into four categories:end-to-end construction algorithms,end-to-end impro...This paper presents an overview of deep learning(DL)-based algorithms designed for solving the traveling salesman problem(TSP),categorizing them into four categories:end-to-end construction algorithms,end-to-end improvement algorithms,direct hybrid algorithms,and large language model(LLM)-based hybrid algorithms.We introduce the principles and methodologies of these algorithms,outlining their strengths and limitations through experimental comparisons.End-to-end construction algorithms employ neural networks to generate solutions from scratch,demonstrating rapid solving speed but often yielding subpar solutions.Conversely,end-to-end improvement algorithms iteratively refine initial solutions,achieving higher-quality outcomes but necessitating longer computation times.Direct hybrid algorithms directly integrate deep learning with heuristic algorithms,showcasing robust solving performance and generalization capability.LLM-based hybrid algorithms leverage LLMs to autonomously generate and refine heuristics,showing promising performance despite being in early developmental stages.In the future,further integration of deep learning techniques,particularly LLMs,with heuristic algorithms and advancements in interpretability and generalization will be pivotal trends in TSP algorithm design.These endeavors aim to tackle larger and more complex realworld instances while enhancing algorithm reliability and practicality.This paper offers insights into the evolving landscape of DL-based TSP solving algorithms and provides a perspective for future research directions.展开更多
基金funded by the National Key R&D Program of China(2020YFA0907000)the National Natural Science Foundation of China(Grant Nos.32270657,32271297,82130055,62072435)the Youth Innovation Promotion Association,Chinese Academy of Sciences.
文摘This paper presents an overview of deep learning(DL)-based algorithms designed for solving the traveling salesman problem(TSP),categorizing them into four categories:end-to-end construction algorithms,end-to-end improvement algorithms,direct hybrid algorithms,and large language model(LLM)-based hybrid algorithms.We introduce the principles and methodologies of these algorithms,outlining their strengths and limitations through experimental comparisons.End-to-end construction algorithms employ neural networks to generate solutions from scratch,demonstrating rapid solving speed but often yielding subpar solutions.Conversely,end-to-end improvement algorithms iteratively refine initial solutions,achieving higher-quality outcomes but necessitating longer computation times.Direct hybrid algorithms directly integrate deep learning with heuristic algorithms,showcasing robust solving performance and generalization capability.LLM-based hybrid algorithms leverage LLMs to autonomously generate and refine heuristics,showing promising performance despite being in early developmental stages.In the future,further integration of deep learning techniques,particularly LLMs,with heuristic algorithms and advancements in interpretability and generalization will be pivotal trends in TSP algorithm design.These endeavors aim to tackle larger and more complex realworld instances while enhancing algorithm reliability and practicality.This paper offers insights into the evolving landscape of DL-based TSP solving algorithms and provides a perspective for future research directions.
