用简单神经网络加贪心算法，快速生成多样且高质量的旅行商路线。
Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion
- 先用图指针网络生成大量优质路线，通过熵损失控制质量与多样性平衡
- 再用贪心算法选出最分散的k条路线，平均杰卡德指数达0.015（柏林数据集）
- 比传统方法快360倍以上，适合大规模物流与机器人路径规划
我们解决多样旅行商问题（D-TSP），目标是在保证每条路线长度不超过最优解长度的c|T*|前提下，使所选k条路线间平均杰卡德相似度最小。该问题对物流规划、机器人路径规划及战略巡逻等需兼顾解质量与容错性的场景至关重要。现有方法受限：传统启发式如尼奇化遗传算法（NMA）计算复杂度高达O(n³)，而现代神经方法（如RF-MA3S）多样性不足且依赖复杂外部机制。为此，我们提出一种新混合框架：首先使用改进的图指针网络（GPN），结合近似序列熵损失，高效生成大量高质量路线；其次采用贪心算法求解2-近似分散问题，从生成池中选取最终的k条最大分散路线。实验表明，本方法达到领先性能：在柏林实例上平均杰卡德指数为0.015，显著优于NMA（0.081）和RF-MA3S。借助GPU加速，GPN实现接近线性的实测运行时间增长O(n)。相比复杂双目标算法，本方法在保持相当多样性的同时，大尺度实例（783城市）速度提升超360倍，实现高效简洁的高质量解生成。
原文摘要 · Abstract (English)
We address the Diverse Traveling Salesman Problem (D-TSP), a bi-criteria optimization challenge that seeks a set of $k$ distinct TSP tours. The objective requires every selected tour to have a length at most $c|T^*|$ (where $|T^*|$ is the optimal tour length) while minimizing the average Jaccard similarity across all tour pairs. This formulation is crucial for applications requiring both high solution quality and fault tolerance, such as logistics planning, robotics pathfinding or strategic patrolling. Current methods are limited: traditional heuristics, such as the Niching Memetic Algorithm (NMA) or bi-criteria optimization, incur high computational complexity $O(n^3)$, while modern neural approaches (e.g., RF-MA3S) achieve limited diversity quality and rely on complex, external mechanisms. To overcome these limitations, we propose a novel hybrid framework that decomposes D-TSP into two efficient steps. First, we utilize a simple Graph Pointer Network (GPN), augmented with an approximated sequence entropy loss, to efficiently sample a large, diverse pool of high-quality tours. This simple modification effectively controls the quality-diversity trade-off without complex external mechanisms. Second, we apply a greedy algorithm that yields a 2-approximation for the dispersion problem to select the final $k$ maximally diverse tours from the generated pool. Our results demonstrate state-of-the-art performance. On the Berlin instance, our model achieves an average Jaccard index of $0.015$, significantly outperforming NMA ($0.081$) and RF-MA3S. By leveraging GPU acceleration, our GPN structure achieves a near-linear empirical runtime growth of $O(n)$. While maintaining solution diversity comparable to complex bi-criteria algorithms, our approach is over 360 times faster on large-scale instances (783 cities), delivering high-quality TSP solutions with unprecedented efficiency and simplicity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。