Research map / Reinforcement learning / Visual and representation RL
Memory-Enhanced Neural Solvers for Routing Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MEMENTO, a memory-based module that adapts a neural routing solver's action logits at inference using data from repeated attempts, evaluated on TSP and CVRP.
Problem
Neural construction solvers for routing problems (TSP, CVRP) are not used efficiently under a multi-attempt inference budget; existing online adaptation (policy-gradient fine-tuning like EAS, tree search) is inefficient or rigid.
Approach
Store per-transition data (node, action, log-probs, return, budget) from past attempts in a memory; for each decision, retrieve data from the same node and use a learned MLP to produce scalar weights that build correction logits added to the frozen base policy's logits. Trained across multi-shot rollouts with an ECO-DQN-style best-so-far reward.
Key results
- On TSP100, MEMENTO (POMO) reaches 0.045% gap vs 0.161% for EAS and 0.185% for POMO sampling under a 1600-attempt budget; it outperforms EAS on all 8 standard tasks.
- Zero-shot combination MEMENTO(COMPASS) achieves new SOTA on 11 of 12 evaluated tasks, e.g., CVRP200 gap 1.808% vs 2.098% for COMPASS.
- On TSP500 low budget, MEMENTO(COMPASS) reaches 1.586% gap vs 2.006% for EAS and 1.603% for COMPASS; on CVRP500 low budget it reaches 0.215% gap vs 0.525% for EAS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MEMENTO inference-time memory adaptation instead of POMO sampling | POMO · TSP100 | Obj.: 7.779 -> 7.768 | Helped |
| Use MEMENTO inference-time memory adaptation instead of EAS policy-gradient fine-tuning | POMO · TSP200 | Obj.: 10.759 -> 10.758 | Helped |
| Use MEMENTO inference-time memory adaptation instead of EAS policy-gradient fine-tuning | POMO · CVRP200 | Obj.: 22.541 -> 22.492 | Helped |
| Apply MEMENTO zero-shot during COMPASS search | COMPASS · CVRP100 | Obj.: 15.644 -> 15.634 | Helped |
| Apply MEMENTO zero-shot during COMPASS search | COMPASS · CVRP200 | Obj.: 22.462 -> 22.405 | Helped |
| Use MEMENTO instead of EAS at high parallelism | POMO · CVRP500, N=80, 600 sequential attempts | Obj.: 37.2346 -> 37.2382 | Hurt |
| Use MEMENTO instead of EAS on large instances | POMO · TSP500 across tested batches and sequential attempts | Obj. | Helped |
| Use MEMENTO instead of EAS at low budgets | POMO · TSP500 and CVRP500 | Obj. | Helped |
| Use MEMENTO rather than EAS for inference-time adaptation | POMO · Inference time, instance size 1000 | speed: 20% faster | Helped |
| Use MEMENTO rather than EAS with a 10-layer decoder | POMO · Inference time, instance size 100 | speed: 40% slower | Helped |
Surprising findings
- EAS is outperformed by MEMENTO but with augmentation, EAS leads on some out-of-distribution tasks (e.g., TSP200 augmented, CVRP500 high budget).
- The authors report that autoregressive RL constructive methods are competitive at scale (TSP500), contradicting prior literature claims.
Limitations
- Incurs additional compute and memory overhead versus memory-less base policies.
- On large CVRP with high sequential budget and large batches, EAS can outperform MEMENTO.
- Zero-shot combination with COMPASS was not trained jointly; training with diversity-based methods is left to future work.
Experimental setup
Datasets: TSP100 training distribution (10k test instances) CVRP100 training distribution TSP125/150/200 and CVRP125/150/200 generalization sets TSP500 and CVRP500 test sets (128 instances)
Benchmarks: TSP100 TSP125 TSP150 TSP200 CVRP100 CVRP125 CVRP150 CVRP200 TSP500 CVRP500
Metrics: objective (tour length) optimality gap inference time
Baselines: POMO EAS SGBS COMPASS MoCo DIMES DeepACO Difusco Pointerformer LKH3 Concorde HGS
Builds on: POMO Efficient Active Search COMPASS ECO-DQN REINFORCE
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.89)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.89)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.88)
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.88)
- LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing (NeurIPS 2026 · similarity 0.88)
- Dynamic Latent Routing (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.