Search papers, labs, and topics across Lattice.
This paper addresses the representation-decision mismatch in neural asymmetric routing by proposing an edge-aware decoder that incorporates transition-level quantities into the final routing score. By adding candidate-specific terms for directed edges and utilizing static lightweight lookahead, the approach enhances the routing model's performance on various instances of the Asymmetric Traveling Salesman Problem (ATSP) and the Asymmetric Capacitated Vehicle Routing Problem (ACVRP). The edge-aware decoder significantly reduces the gap in performance on ATSP-1000 from 4.13% to 2.73% compared to the RADAR reference, demonstrating the importance of decision-time exposure of edge information in routing tasks.
Transition-level edge information can dramatically enhance routing model performance, cutting ATSP-1000 gaps by over a third.
Neural asymmetric routing models increasingly encode directionality through matrix representations and asymmetry-aware attention. The final routing action, however, is not a node in isolation but a directed transition chosen under the current partial route. This creates a representation--decision mismatch: pairwise cost information may be encoded upstream while the final candidate logit is still largely parameterized as context--node compatibility. We propose a decoder-design principle for neural asymmetric routing: the final score should explicitly expose transition-level quantities suggested by the problem's cost-to-go structure. We instantiate this principle with an edge-aware decoder that adds candidate-specific terms for the current directed edge, return-to-start closure, and static lightweight lookahead, while keeping the representation backbone fixed. On a controlled SVD/Sinkhorn asymmetric backbone, the decoder improves over the RADAR reference when trained on ATSP-100 and evaluated zero-shot on ATSP-100/200/500/1000, reducing the ATSP-1000 gap from $4.13\%$ to $2.73\%$. On ACVRP, the same score-level modification shows the same qualitative trend under a richer routing state. ATSP ablations and directed-transition diagnostics sharpen the mechanism: the strongest evidence concerns sensitivity to the current directed edge, while closure and static lookahead act as heuristic continuation cues. The results support a mechanism study: a key decoder-side signal in neural asymmetric routing is decision-time exposure of transition-level edge information.
NUS