# GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time

arXiv: https://arxiv.org/abs/2312.08224 · HTML: https://mlsanity.com/paper/2312.08224/

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 58 references that are in the map.
- First posted on arXiv 13 Dec 2023.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum](https://mlsanity.com/paper/2204.03236/) (2022)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)

## Built on by (most cited first, 30 of 85)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer](https://mlsanity.com/paper/2402.02317/) (2024)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [Self-Improved Learning for Scalable Neural Combinatorial Optimization](https://mlsanity.com/paper/2403.19561/) (2024)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems](https://mlsanity.com/paper/2406.03503/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems](https://mlsanity.com/paper/2401.06979/) (2024)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)
- [Destroy and Repair Using Hyper Graphs for Routing](https://mlsanity.com/paper/2502.16170/) (2025)
- [Learning to Reduce Search Space for Generalizable Neural Routing Solver](https://mlsanity.com/paper/2503.03137/) (2025)
- [MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver](https://mlsanity.com/paper/2506.02935/) (2025)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [RRNCO: Towards Real-World Routing with Neural Combinatorial Optimization](https://mlsanity.com/paper/2503.16159/) (2025)
- [Hierarchical Neural Constructive Solver for Real-world TSP Scenarios](https://mlsanity.com/paper/2408.03585/) (2024)
- [Learning to Insert for Constructive Neural Vehicle Routing Solver](https://mlsanity.com/paper/2505.13904/) (2025)
- [Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver](https://mlsanity.com/paper/2405.01906/) (2024)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costs](https://mlsanity.com/paper/2408.16717/) (2024)
- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [RADAR: Learning to Route with Asymmetry-aware DistAnce Representations](https://mlsanity.com/paper/2603.03388/) (2026)
- [Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding](https://mlsanity.com/paper/2403.07559/) (2024)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2502.15791/) (2025)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2510.04792/) (2025)

## Abstract (arXiv)

The recent end-to-end neural solvers have shown promise for small-scale routing problems but suffered from limited real-time scaling-up performance. This paper proposes GLOP (Global and Local Optimization Policies), a unified hierarchical framework that efficiently scales toward large-scale routing problems. GLOP partitions large routing problems into Travelling Salesman Problems (TSPs) and TSPs into Shortest Hamiltonian Path Problems. For the first time, we hybridize non-autoregressive neural heuristics for coarse-grained problem partitions and autoregressive neural heuristics for fine-grained route constructions, leveraging the scalability of the former and the meticulousness of the latter. Experimental results show that GLOP achieves competitive and state-of-the-art real-time performance on large-scale routing problems, including TSP, ATSP, CVRP, and PCTSP.