Publication Type
Conference Proceeding Article
Version
submittedVersion
Publication Date
7-2025
Abstract
Recent advances in neural models have shown considerable promise in solving Traveling Salesman Problems (TSPs) without relying on much hand-crafted engineering. However, while non-autoregressive (NAR) approaches benefit from faster inference through parallelism, they typically deliver solutions of inferior quality compared to autoregressive ones. To enhance the solution quality while maintaining fast inference, we propose DEITSP, a diffusion model with efficient iterations tailored for TSP that operates in a NAR manner. Firstly, we introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement, enabling optimal solution prediction through simultaneous denoising of multiple solutions. Secondly, we design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities, while further accelerating the inference with fewer layers. Thirdly, we develop an efficient iterative strategy that alternates between adding and removing noise to improve exploration compared to previous diffusion methods. Additionally, we devise a scheduling framework to progressively refine the solution space by adjusting noise levels, facilitating a smooth search for optimal solutions. Extensive experiments on real-world and large-scale TSP instances demonstrate that DEITSP performs favorably against existing neural approaches in terms of solution quality, inference latency, and generalization ability.
Keywords
combinatorial optimization; diffusion models; learning to optimize; non-autoregressive; traveling salesman problem
Discipline
Artificial Intelligence and Robotics | Databases and Information Systems
Research Areas
Intelligent Systems and Optimization
Publication
Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1
Volume
1
First Page
1469
Last Page
1480
ISBN
9798400712456
Identifier
10.1145/3690624.3709343
Publisher
Association for Computing Machinery
City or Country
Toronto
Citation
WANG, Mingzhao; ZHOU, You; CAO, Zhiguang; XIAO, Yubin; WU, Xuan; PANG, Wei; JIANG, Yuan; YANG, Hui; ZHAO, Peng; and LI, Yuanshu.
An efficient diffusion-based non-autoregressive solver for traveling salesman problem. (2025). Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. 1, 1469-1480.
Available at: https://ink.library.smu.edu.sg/sis_research/10543
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.1145/3690624.3709343