mlsanityData to 14 Oct 2026

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

arXiv 1911.04936 ↗First posted 12 Nov 2019cs.LG stat.MLcited by 78

Not on the map. Why?

Abstract (arXiv)

In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to constrained combinatorial optimization problems such as the TSP with time windows, we train hierarchical GPNs (HGPNs) using RL, which learns a hierarchical policy to find an optimal city permutation under constraints. Each layer of the hierarchy is designed with a separate reward function, resulting in stable training. Our results demonstrate that GPNs trained on small-scale TSP50/100 problems generalize well to larger-scale TSP500/1000 problems, with shorter tour lengths and faster computational times. We verify that for constrained TSP problems such as the TSP with time windows, the feasible solutions found via hierarchical RL training outperform previous baselines. In the spirit of reproducible research we make our data, models, and code publicly available.

Key facts. Cited by 78 papers in the map (data through 14 Oct 2026). First posted on arXiv 12 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 16; 2023: 18; 2024: 14; 2025: 7; 2026: 5.

78 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  3. 2021End-to-End Constrained Optimization Learning: A Surveycited by 157
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  5. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  6. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  7. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  8. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  9. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 69
  10. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 44
  11. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  12. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
38 more
  1. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  2. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  3. 2021Analytics and Machine Learning in Vehicle Routing Researchcited by 22
  4. 2021An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problemcited by 22
  5. 2022Reinforcement learning on graphs: A surveycited by 20
  6. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  7. 2022A Survey on Influence Maximization: From an ML-Based Combinatorial Optimizationcited by 15
  8. 2021Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problemscited by 13
  9. 2021Solve routing problems with a residual edge-graph attention neural networkcited by 13
  10. 2021Learning Combinatorial Node Labeling Algorithmscited by 10
  11. 2024BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learningcited by 10
  12. 2021Generalization in Deep RL for TSP Problems via Equivariance and Local Searchcited by 9
  13. 2022DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAVcited by 9
  14. 2021Improving Generalization of Deep Reinforcement Learning-based TSP Solverscited by 8
  15. 2022LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisationcited by 8
  16. 2022Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learningcited by 8
  17. 2024Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problemcited by 8
  18. 2021Reversible Action Design for Combinatorial Optimization with Reinforcement Learningcited by 7
  19. 2025Learning for routing: A guided review of recent developments and future directionscited by 7
  20. 2021Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windowscited by 6
  21. 2021Generalising Discrete Action Spaces with Conditional Action Treescited by 6
  22. 2024Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSPcited by 6
  23. 2022Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networkscited by 5
  24. 2023Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problemscited by 5
  25. 2023A Survey on Service Route and Time Prediction in Instant Delivery: Taxonomy, Progress, and Prospectscited by 5
  26. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  27. 2023Multi-Objective Reinforcement Learning-based Approach for Pressurized Water Reactor Optimizationcited by 5
  28. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 5
  29. 2021Hybrid Pointer Networks for Traveling Salesman Problems Optimizationcited by 4
  30. 2023A Lightweight CNN-Transformer Model for Learning Traveling Salesman Problemscited by 4
  31. 2023Learning to Branch in Combinatorial Optimization with Graph Pointer Networkscited by 4
  32. 2022The First AI4TSP Competition: Learning to Solve Stochastic Routing Problemscited by 3
  33. 2023Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Networkcited by 3
  34. 2023Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networkscited by 3
  35. 2023TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problemcited by 3
  36. 2024Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problemcited by 3
  37. 2024Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solverscited by 3
  38. 2025Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problemscited by 3

50 most cited of 78 All 78 (JSON)