提出显式计算路径决策后果的神经路由方法，提升求解精度
LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing
- 分离局部后果计算与隐式匹配，显式建模行程、等待等状态变化
- 在CVRPTW上将PolyNet的基准差距从13.83%/38.15%降至7.26%/14.71%
- 适用于多种路径规划问题，尤其适合需精确状态控制的任务
传统构造型神经路由求解器通过匹配解码器上下文与候选嵌入来评分下一步动作，但隐藏了行程、等待、松弛和容量变化等确定性一步后果。本文提出LINC（基于范数比较的局部推理），在解码器端显式计算这些后果。其中，相对后果以共享线性局部评分器进行归一化比较，可行集摘要则调节解码器上下文。该设计保留全局匹配机制，同时减轻隐藏状态对转移算术的重复学习负担。以带时间窗的车辆路径问题（CVRPTW）为主要测试场景，相同接口亦适用于CVRP与TSP。实验显示，对于CVRPTW，LINC将PolyNet在Solomon/Homberger数据集上的差距从13.83%/38.15%降低至7.26%/14.71%；在TSP与CVRP上也均取得外部基准差距的改进。
原文摘要 · Abstract (English)
Constructive neural routing solvers usually score the next action by matching a decoder context to candidate embeddings, hiding deterministic one-step consequences such as travel, waiting, slack, and capacity changes. We propose LINC (Local Inference via Normed Comparison), a decoder-side candidate decision architecture that computes these consequences explicitly. LINC uses them according to their decision role: centered relative consequences are compared by a shared linear local scorer, while feasible-set summaries modulate the decoder context. This preserves standard global matching and relieves the hidden state from rediscovering transition arithmetic. The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) serves as the main constrained-routing stress test; the same interface extends to the Capacitated Vehicle Routing Problem (CVRP) and Traveling Salesman Problem (TSP). In particular, for CVRPTW, LINC reduces PolyNet's Solomon/Homberger gaps from 13.83\%/38.15\% to 7.26\%/14.71\%; for TSP and CVRP, it also improves external-benchmark gaps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。