mlsanityData to 7 Oct 2026

Efficient Neural Neighborhood Search for Pickup and Delivery Problems

arXiv 2204.11399 ↗First posted 25 Apr 2022cs.LG cs.AIcited by 29

Not on the map. Why?

Abstract (arXiv)

We present an efficient Neural Neighborhood Search (N2S) approach for pickup and delivery problems (PDPs). In specific, we design a powerful Synthesis Attention that allows the vanilla self-attention to synthesize various types of features regarding a route solution. We also exploit two customized decoders that automatically learn to perform removal and reinsertion of a pickup-delivery node pair to tackle the precedence constraint. Additionally, a diversity enhancement scheme is leveraged to further ameliorate the performance. Our N2S is generic, and extensive experiments on two canonical PDP variants show that it can produce state-of-the-art results among existing neural methods. Moreover, it even outstrips the well-known LKH3 solver on the more constrained PDP variant. Our implementation for N2S is available online.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 18 of its 39 references that are in the map. First posted on arXiv 25 Apr 2022.

Builds on

18 of 39 references.

References · 18

  1. 2017Attention Is All You Needcited by 59,932
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2021Domain Generalization: A Surveycited by 760
  4. 2018Attention, Learn to Solve Routing Problems!cited by 646
  5. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  6. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  7. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  8. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  9. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  10. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  11. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  12. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 108
6 more
  1. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  2. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  3. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  4. 2021Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learningcited by 35
  5. 2021Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problemcited by 31
  6. 2021Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problemscited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 10; 2025: 4; 2026: 5.

29 papers.

Sort:

  1. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  2. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  3. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  4. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  5. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  6. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  7. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  8. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  9. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  10. 2024Auto-configuring Exploration-Exploitation Tradeoff in Evolutionary Computation via Deep Reinforcement Learningcited by 17
  11. 2023Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Contextcited by 16
  12. 2023Neural Multi-Objective Combinatorial Optimization with Diversity Enhancementcited by 13
17 more
  1. 2024Hierarchical Neural Constructive Solver for Real-world TSP Scenarioscited by 9
  2. 2024Learning to optimize: A tutorial for continuous and mixed-integer optimizationcited by 8
  3. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  4. 2023Neural Airport Ground Handlingcited by 7
  5. 2025Learning for routing: A guided review of recent developments and future directionscited by 6
  6. 2023Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problemscited by 5
  7. 2025Learning to Segment for Vehicle Routing Problemscited by 5
  8. 2024Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptationcited by 2
  9. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 2
  10. 2022Where to go: Agent Guidance with Deep Reinforcement Learning in A City-Scale Online Ride-Hailing Servicecited by 1
  11. 2024Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problemcited by 1
  12. 2025GAMA: A Neural Neighborhood Search Method with Graph-aware Multi-modal Attention for Vehicle Routing Problemcited by 0
  13. 2025Deep Learning--Accelerated Multi-Start Large Neighborhood Search for Real-time Freight Bundlingcited by 0
  14. 2026Cluster-Aware Attention-Based Deep Reinforcement Learning for Pickup and Delivery Problemscited by 0
  15. 2026Rethinking Positional Encoding for Neural Vehicle Routingcited by 0
  16. 2026JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environmentcited by 0
  17. 2026MiLoop: Selective Memory Propagation for Neural Combinatorial Optimizationcited by 0