Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2025

Abstract

Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy. Concretely, on the one hand, a Relativization Filter (RF) is designed to enhance the robustness of the encoder to affine transformations of the instances, so as to potentially improve the quality of the found solutions. On the other hand, a Multi-Attentive Adaptive Active Search (MA3S) is tailored to allow the decoders to strike a balance between the optimality and diversity. Experimental evaluations on benchmark instances demonstrate the superiority of our method over recent neural baselines across different metrics, and its competitive performance against state-of-the-art traditional heuristics with significantly reduced computational time, ranging from 1.3× to 15× faster. Furthermore, we demonstrate that our method can also be applied to the Capacitated Vehicle Routing Problem (CVRP).

Keywords

combinatorial optimization, data-driven optimization, deep reinforcement learning, travelling salesman problem, multi-solution TSP, diversity optimization, deep reinforcement learning, encoder–decoder models, active search, attention mechanisms, neural combinatorial optimization, CVRP, solution robustness

Discipline

Artificial Intelligence and Robotics

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

683

Last Page

694

ISBN

9798400712456

Identifier

10.1145/3690624.3709181

Publisher

Association for Computing Machinery

City or Country

Toronto

Additional URL

https://doi.org/10.1145/3690624.3709181

Download

Share

COinS