用深度强化学习找多个高质量旅行商解，速度快且多样性好。
Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
- 设计编码器-解码器结构，结合相对化滤波提升鲁棒性。
- 多注意力主动搜索机制平衡解的最优与多样性，生成多组优质路径。
- 比传统算法快1.3到15倍，适用于车辆路径问题。
现有神经方法多聚焦于寻找单一最优解。为应对多解旅行商问题（MSTSP），本文提出一种基于深度强化学习的新型神经求解器，核心为编码器-解码器结构策略。一方面，设计相对化滤波器（RF）增强编码器对实例仿射变换的鲁棒性，提升解的质量；另一方面，提出多注意力自适应主动搜索（MA3S）机制，使解码器在最优性与多样性间取得平衡。在基准实例上的实验表明，该方法在多个指标上优于近期神经基线，且相比顶尖传统启发式算法，计算速度提升1.3至15倍。此外，方法可扩展至带容量约束的车辆路径问题（CVRP）。
原文摘要 · Abstract (English)
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\times$ to $15\times$ faster. Furthermore, we demonstrate that our method can also be applied to the Capacitated Vehicle Routing Problem (CVRP).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。