GeoRouteNet通过几何感知设计，显著提升TSP求解在不同规模和分布下的泛化能力。
GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem
- 引入节点偏移、径向基底与注意力机制，增强对空间结构的建模
- 在50/100节点及TSPLIB数据集上，最差误差仅3.60%，优于基线模型
- 适合需要高精度、强泛化的路径规划场景，如物流优化
非自回归神经求解器可跨多个旅行商问题实例分摊计算开销，但训练于随机欧氏实例的模型在节点数量或空间分布变化时性能会下降。本文研究显式几何特征与更丰富的实例内训练信号是否能提升跨图尺寸与空间分布的迁移能力。提出GeoRouteNet，通过中心化节点偏移与半径、可学习径向距离基底、距离感知图注意力、显式边消息传递及跨层表示混合，增强几何建模。同时引入多候选自比较强化学习（MCS-RL），每实例采样多个路径，采用留一法自适应基线、胜者-候选引导与退火熵正则化。单种子实验中，所有模型均仅在随机TSP-50实例上训练，使用相同贪婪与束搜索解码器。束搜索1000次下，GeoRouteNet-MCS-RL在用于检查点选择的TSP-50验证集上差距为0.32%，相关性TSP-100诊断集上为1.26%，27个TSPLIB EUC_2D实例上平均为3.60%。而NAR4TSP-PG对应结果为0.42%、2.73%和17.12%。2×2对比涵盖编码器与训练方式，结果显示在几何感知编码器下，使用MCS-RL进一步降低误差；而在原版编码器下，使用MCS-RL反而导致TSPLIB误差上升。
原文摘要 · Abstract (English)
Non-autoregressive neural solvers amortize computation across traveling salesman problem (TSP) instances, but models trained on random Euclidean instances can degrade when the number or spatial distribution of nodes changes. We study whether explicit geometric features and a richer within-instance training signal improve transfer across graph sizes and spatial distributions. We introduce GeoRouteNet, which augments a non-autoregressive TSP solver with centered node offsets and radii, learnable radial distance bases, distance-aware graph attention, explicit edge messages, and cross-layer representation mixing. We also introduce multi-candidate self-comparison reinforcement learning (MCS-RL), which trains on several sampled tours per instance using a leave-one-out adaptive baseline, winner-candidate guidance, and annealed entropy regularization. In a single-seed study, all neural variants are trained only on random TSP-50 instances and evaluated with the same greedy and beam-search decoders. Under Beam-1000 decoding, GeoRouteNet-MCS-RL obtains gaps of 0.32% on the TSP-50 validation set used for checkpoint selection, 1.26% on a correlated TSP-100 size diagnostic, and 3.60% across 27 TSPLIB EUC_2D instances. The NAR4TSP-PG gaps on the same evaluations are 0.42%, 2.73%, and 17.12%. A 2x2 comparison crosses encoder and training choices. Under PG, the geometry-aware encoder has lower gaps than the reproduced encoder on the TSP-100 diagnostic and TSPLIB. With the geometry-aware encoder, MCS-RL is associated with a further reduction; with the reproduced encoder, it has a higher TSPLIB gap.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。