LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing
This work addresses the bottleneck of hidden state rediscovering transition arithmetic in neural routing solvers, providing a modular decoder architecture that improves performance on constrained routing problems.
LINC decouples local consequence scoring from hidden matching in constructive neural routing, explicitly computing travel, waiting, slack, and capacity changes. For CVRPTW, it reduces PolyNet's Solomon/Homberger gaps from 13.83%/38.15% to 7.26%/14.71%, and improves gaps for TSP and CVRP.
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.