ARC: Assignment-Structured Representation and Construction for Asymmetric TSP

Neural constructive solvers efficiently generate tours for the asymmetric traveling salesman problem (ATSP), but maintaining solution quality beyond the training scale remains challenging. With direction-dependent costs, a cheap move to one node may force another node to use an expensive alternative. This competition arises because each node in a tour must have exactly one predecessor and one successor. Assignment captures this requirement through a one-to-one pairing of source and destination nodes, providing a global reference for local choices. When this structure remains implicit, neural policies must infer the changing competition from learned representations and tour states, even at unseen scales. We propose ARC (Assignment-structured Representation and Construction), which uses assignment structure both to represent directed costs and to guide tour construction. ARC derives source and destination dual potentials and gauge-adjusted edge costs from a full-instance assignment decomposition, providing complementary node and edge inputs. The adjustment shifts every complete tour's cost by the same constant, preserving which tours are cheaper. As construction proceeds, ARC updates a pressure signal for each remaining destination through residual assignment rebalancing. Frontier Sinkhorn Pressure (FSP) uses these signals to guide choices without fully solving the remaining assignment problem at every step. Experiments show that ARC outperforms the evaluated neural baselines on standard ATSP benchmarks and generalizes to larger unseen instances. Structured inputs reduce reliance on many starts, while FSP improves policies without retraining.