Variance-Preserving Stochastic Differential Equation Algorithm for the Traveling Salesman Problem
Yuchen Wang, Hiroyuki Ebara · 2024
The traveling salesman problem (TSP) stands as a classic combinatorial optimization problem with widespread research interest and practical relevance. Despite its computational complexities, recent advancements in deep learning and stochastic differential equations (SDE) have introduced new methodologies to improve TSP solutions. In this study, we introduce the vertex-conditioned forward path generation (V-FPG) method, building upon the variational path sampling with differential equations (VPSDE) framework. V-FPG integrates urban vertex graphs with optimal path datas, utilizing SDEs and Gaussian noise to generate candidate paths. Backward optimization with a scoring function ensures clear guidance during path generation. Experimental results demonstrate the superior accuracy and robustness of our method across random point tests and the TSP-LIB dataset.