Research map / Architectures and efficiency / RNNs and normalization
GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time
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.
GLOP hybridizes a non-autoregressive global heatmap partitioner with autoregressive local SHPP revisers to solve large-scale TSP, ATSP, CVRP and PCTSP in real time.
Problem
Neural combinatorial solvers for routing struggle to scale to thousands or tens of thousands of nodes under real-time constraints.
Approach
Partition large routing problems hierarchically (global NAR heatmap partition into sub-TSPs, then local AR revisers that solve small Shortest Hamiltonian Path Problems via random-insertion initialization and decompose-reconstruct revisions), combining the scalability of NAR with the solution quality of AR.
Key results
- On TSP100K, GLOP achieves a 5.1% optimality gap (238.0 vs LKH-3 226.4) with a 174x speedup over 1-trial LKH-3, the only neural solver in the comparison that runs at that scale.
- On CVRP1K-7K, GLOP-G reaches 47.1/63.5/141.9/191.7 objective with per-instance times of 0.4-2.4s, outperforming TAM-AM and TAM-LKH3 in quality and time.
- On TSP500, GLOP achieves a 3.14% gap in 19s total runtime for 128 instances, versus 40.9 minutes for Concorde.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add more revisions | GLOP · TSP100K | Gap(%): 6.01 -> 5.10 | Helped |
| replace the neural SHPP solver with LKH-3 (ablation) | GLOP local policy · TSP500 | Time: 19s -> 34m | Hurt |
| replace the neural SHPP solver with LKH-3 (ablation) | GLOP local policy · TSP500 | Obj.: 17.07 -> 16.86 | Helped |
| add bidirectional decoding (ablation) | GLOP local policy · TSP500 | Obj.: 16.88 -> 16.80 | Helped |
| add coordinate transformation (ablation) | GLOP local policy · TSP1K | Obj.: 24.17 -> 23.73 | Helped |
| add first-stage curriculum learning (ablation) | GLOP local policy · TSP500 | Obj.: 16.91 -> 16.80 | Helped |
| add second-stage curriculum learning (ablation) | GLOP local policy · TSP500 | Obj.: 16.94 -> 16.80 | Helped |
| use the learned global partition policy instead of random partition (ablation) | GLOP · PCTSP500 | Obj.: 19.0 -> 14.6 | Helped |
| use sampling decoding instead of greedy decoding | GLOP · PCTSP5K | Obj.: 46.0 -> 44.9 | Helped |
| add more revisions | GLOP · TSP500 | Obj.: 17.07 -> 16.91 | Helped |
Surprising findings
- Neural heuristics as SHPP solvers are about 27-120x faster than LKH-3 in the local policy while losing only about 0.2-1% in objective.
Limitations
- Less competitive when prolonged execution time is allowed, since iterative refinement methods can trade time for quality better.
- Solution quality trails MCTS- and LKH-3-based methods on TSP at moderate scales (e.g., TSP500 gap 3.14% vs 1.99% with more revisions).
Experimental setup
Datasets: uniform random TSP instances TSPLIB EUC_2D instances (<1000 nodes, test) CVRP instances generated per TAM settings CVRPLIB instances (test) PCTSP instances generated per AM settings ATSP test instances following MatNet
Benchmarks: TSP500 TSP1K TSP10K TSP100K TSPLIB ATSP150 ATSP250 ATSP1000 CVRP1K CVRP2K CVRP5K CVRP7K
Metrics: optimality gap (%) objective value runtime
Baselines: LKH-3 Concorde AM LCP GCN+MCTS POMO-EAS DIMES H-TSP Pointerformer DeepACO TAM MatNet
Builds on: Attention Model REINFORCE DIMES Learning Collaborative Policy Two-stage Divide Method
Closest papers by meaning
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.88)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.88)
- Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems (NeurIPS 2025 · similarity 0.87)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.87)
- MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.87)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
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.