# Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 6 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [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)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)

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

- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Efficient Neural Neighborhood Search for Pickup and Delivery Problems](https://mlsanity.com/paper/2204.11399/) (2022)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Context](https://mlsanity.com/paper/2306.02689/) (2023)
- [Adversarial Generative Flow Network for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2503.01931/) (2025)
- [Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver](https://mlsanity.com/paper/2405.01906/) (2024)
- [Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning](https://mlsanity.com/paper/2209.06094/) (2022)
- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [Neural Airport Ground Handling](https://mlsanity.com/paper/2303.02442/) (2023)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems](https://mlsanity.com/paper/2309.17089/) (2023)
- [A deep learning Attention model to solve the Vehicle Routing Problem and the Pick-up and Delivery Problem with Time Windows](https://mlsanity.com/paper/2212.10399/) (2022)
- [Edge-DIRECT: A Deep Reinforcement Learning-based Method for Solving Heterogeneous Electric Vehicle Routing Problem with Time Window Constraints](https://mlsanity.com/paper/2407.01615/) (2024)
- [Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPs](https://mlsanity.com/paper/2603.01667/) (2026)
- [SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver](https://mlsanity.com/paper/2605.24484/) (2026)
- [Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01443/) (2022)
- [Where to go: Agent Guidance with Deep Reinforcement Learning in A City-Scale Online Ride-Hailing Service](https://mlsanity.com/paper/2212.05742/) (2022)
- [Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem](https://mlsanity.com/paper/2404.11458/) (2024)
- [Enhancing the Cross-Size Generalization for Solving Vehicle Routing Problems via Continual Learning](https://mlsanity.com/paper/2510.10262/) (2025)
- [Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver](https://mlsanity.com/paper/2605.10122/) (2026)
- [Enhancing Courier Scheduling in Crowdsourced Last-Mile Delivery through Dynamic Shift Extensions: A Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2402.09961/) (2024)
- [Prioritized League Reinforcement Learning for Large-Scale Heterogeneous Multiagent Systems](https://mlsanity.com/paper/2403.18057/) (2024)
- [A Coalition Game for On-demand Multi-modal 3D Automated Delivery System](https://mlsanity.com/paper/2412.17252/) (2024)
- [SED2AM: Solving Multi-Trip Time-Dependent Vehicle Routing Problem using Deep Reinforcement Learning](https://mlsanity.com/paper/2503.04085/) (2025)

## Abstract (arXiv)

Recently, there is an emerging trend to apply deep reinforcement learning to solve the vehicle routing problem (VRP), where a learnt policy governs the selection of next node for visiting. However, existing methods could not handle well the pairing and precedence relationships in the pickup and delivery problem (PDP), which is a representative variant of VRP. To address this challenging issue, we leverage a novel neural network integrated with a heterogeneous attention mechanism to empower the policy in deep reinforcement learning to automatically select the nodes. In particular, the heterogeneous attention mechanism specifically prescribes attentions for each role of the nodes while taking into account the precedence constraint, i.e., the pickup node must precede the pairing delivery node. Further integrated with a masking scheme, the learnt policy is expected to find higher-quality solutions for solving PDP. Extensive experimental results show that our method outperforms the state-of-the-art heuristic and deep learning model, respectively, and generalizes well to different distributions and problem sizes.