Submit

Login Login

Register Register

Home / Journals / CMC / Online First / doi:10.32604/cmc.2025.071269
Journal Menu
Special Issues
Table of Content

All issues

Online First

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Open Access

ARTICLE

Graph Guide Diffusion Solvers with Noises for Travelling Salesman Problem

Yan Kong1, Xinpeng Guo2, Chih-Hsien Hsia3,4,*
1 School of Software, Nanjing University of Information Science and Technology, Nanjing, 210044, China
2 School of Computer Science, Nanjing University of Information Science and Technology, Nanjing, 210044, China
3 Department of Computer Science and Information Engineering, National Ilan University, Yilan, 26047, Taiwan
4 Office of Research and Industry-Academia Development, Chaoyang University of Technology, Taichung, 413310, Taiwan
* Corresponding Author: Chih-Hsien Hsia. Email: email

Computers, Materials & Continua https://doi.org/10.32604/cmc.2025.071269

Received 04 August 2025; Accepted 01 October 2025; Published online 30 October 2025

Abstract

With the development of technology, diffusion model-based solvers have shown significant promise in solving Combinatorial Optimization (CO) problems, particularly in tackling Non-deterministic Polynomial-time hard (NP-hard) problems such as the Traveling Salesman Problem (TSP). However, existing diffusion model-based solvers typically employ a fixed, uniform noise schedule (e.g., linear or cosine annealing) across all training instances, failing to fully account for the unique characteristics of each problem instance. To address this challenge, we present Graph-Guided Diffusion Solvers (GGDS), an enhanced method for improving graph-based diffusion models. GGDS leverages Graph Neural Networks (GNNs) to capture graph structural information embedded in node coordinates and adjacency matrices, dynamically adjusting the noise levels in the diffusion model. This study investigates the TSP by examining two distinct time-step noise generation strategies: cosine annealing and a Neural Network (NN)-based approach. We evaluate their performance across different problem scales, particularly after integrating graph structural information. Experimental results indicate that GGDS outperforms previous methods with average performance improvements of 18.7%, 6.3%, and 88.7% on TSP-500, TSP-100, and TSP-50, respectively. Specifically, GGDS demonstrates superior performance on TSP-500 and TSP-50, while its performance on TSP-100 is either comparable to or slightly better than that of previous methods, depending on the chosen noise schedule and decoding strategy.

Keywords

Combinatorial optimization problem; diffusion model; noise schedule; traveling salesman problem

  • 238

    View

  • 31

    Download

  • 0

    Like

Related articles
Copyright© 2025 Tech Science Press
© 1997-2025 TSP (Henderson, USA) unless otherwise stated

Share Link