An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem

Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li · 2025

Read An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem by Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13767.txt.

Description

Mingzhao Wang and a team of co-authors solve the traveling salesman problem with a diffusion model that guesses whole tours at once. Their work appeared in twenty twenty-five. Step-by-step solvers are slow; parallel ones are fast but sloppy, and tours suffer.

Their system, DEITSP, denoises many candidate tours simultaneously in a single step, steadied by a self-consistency trick. A dual graph transformer reads both city points and the roads between them, with fewer layers for speed. Iterations alternate adding and removing noise, widening the search beyond earlier diffusion attempts. A noise schedule refines the solution space as it goes. On real and large synthetic instances, the solver matched or beat rival neural methods on quality, speed, and generalization.

Catalog record

CREATORMingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13767

Browse the full library · About the Tower of Babel