← Back to all news
arXiv AI By Andoni Irazusta Garmendia

A First Guess Is Rarely the Final Answer: Learned Local Search That Generalizes to Larger Routing Problems

Read the original on arXiv AI →

The paper introduces NICO, a learned 2‑opt local search policy for routing problems that improves upon initial neural solutions by repeatedly applying local moves. NICO addresses three shortcomings of prior policies—incumbent representation, input feature scaling, and move‑gain computation—by using edge‑based tokens without positional encodings, scale‑free features, and exact move gains added to logits. Experiments show that NICO generalizes to larger instances, achieving a 1.1% gap on 1000‑node Euclidean TSP and outperforming both greedy 2‑opt and previous learned policies, while also enhancing tours from constructive and diffusion‑based solvers on road‑network and CVRP benchmarks.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv AI.

Related stories

arXiv Machine Learning
Aug 5

Beyond Solving: Prescriptive Probing for Neural Routing Solvers

arXiv:2602. 07216v2 Announce Type: replace Abstract: Neural combinatorial optimization (NCO) trains fast heuristics for routing problems, but planners often need more than a single solve: they ask which stop to drop, which transition to preserve, or which subset of stops to remove if a route is infeasible.

By Reuben Narad, L\'eonard Boussioux, Michael Wagner
reinforcement-learningbenchmarkssafety
More like this →
arXiv AI
Oct 27

From Comparison to Selection: Enhancing Cross-Scale Generalization of Pointer Networks Trained with Reinforcement Learning for Capacitated Vehicle Routing Problem

The paper investigates why attention-based Pointer Networks, though size‑agnostic, lose performance when applied to different sized Capacitated Vehicle Routing Problems (CVRP). It identifies three causes—node‑density shifts, attention dispersion, and diluted graph context—and evaluates architectural changes on both encoder and decoder sides, including a learned permutation‑invariant graph‑context aggregation. The authors show that entropy‑based attention scaling improves large‑to‑small transfer, while the new aggregation methods best aid small‑to‑large transfer, and they combine these insights into a selector that chooses the optimal model for each train‑test size pair, reducing costs by up to 3.2% across seen and many unseen sizes.

By Sofiene Lassoued, Devara Tertia, Stefan Lier, Andreas Schwung
reinforcement-learning
More like this →