A Discrete Diffusion-Based Approach for Solving Multi-Objective Traveling Salesman Problem

Thanks to the highly-expressive generative capabilities exhibited by diffusion models, recent works have shown their promising performance in combinatorial optimization (CO) problems, where the complicated problems are converted into the corrupting and denoising of heatmaps. The characteristics of diffusion-based approaches result in special advantages for Multi-Objective CO (MOCO) problems, especially MultiObjective Traveling Salesman Problem (MOTSP) better aligned with that solving paradigm. In this paper, we improve and adapt the diffusion-based approaches to tackle MOTSP, which are trained to generate various Pareto optimal solutions according to the problem decomposition strategies. Experimental results demonstrate that although the proposed approach may lag behind with the most advanced neural methods at present, it outperforms several traditional heuristics with a single graph neural network, indicating its effectiveness and potentiality in addressing MOCO problems.