LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing
Shaofeng Qin, Li Wang
原文摘要
Constructive neural routing solvers usually score the next action by matching a decoder context against candidate embeddings computed once per instance from static node features such as coordinates, demands, and time windows; deterministic one-step consequences such as travel, waiting, slack, and capacity changes are not provided as inputs and must be inferred implicitly by the model. We propose LINC, a decoder-side candidate decision architecture that decouples computing these consequences from learning how much they matter. The environment computes the consequences explicitly at each step; candidate-level consequences are scored by a state-conditioned shared linear comparator, while feasible-set summaries modulate the decoder context. This keeps the cached embeddings and standard global matching while giving the scoring function direct access to deterministic transition quantities. The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) serves as the main constrained-routing testbed, and the same interface extends to the Capacitated Vehicle Routing Problem (CVRP) and Traveling Salesman Problem (TSP). Across external benchmarks and no-retraining scale-transfer settings, LINC consistently improves strong neural baselines, with the advantage becoming more pronounced as test size moves further beyond the training scale, especially on constrained routing problems.
cs.LG