# Learning to Optimize Industry-Scale Dynamic Pickup and Delivery Problems

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 27 May 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games](https://mlsanity.com/paper/1703.10069/) (2017)
- [Relational Deep Reinforcement Learning](https://mlsanity.com/paper/1806.01830/) (2018)
- [Towards Practical Multi-Object Manipulation using Relational Reinforcement Learning](https://mlsanity.com/paper/1912.11032/) (2019)
- [A Cooperative Multi-Agent Reinforcement Learning Framework for Resource Balancing in Complex Logistics Network](https://mlsanity.com/paper/1903.00714/) (2019)
- [ORL: Reinforcement Learning Benchmarks for Online Stochastic Optimization Problems](https://mlsanity.com/paper/1911.10641/) (2019)
- [Deep Multi-Agent Reinforcement Learning with Relevance Graphs](https://mlsanity.com/paper/1811.12557/) (2018)
- [Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations](https://mlsanity.com/paper/1507.02731/) (2015)

## Built on by (most cited first, 15 of 15)

- [Scalable Multi-Agent Reinforcement Learning for Warehouse Logistics with Robotic and Human Co-Workers](https://mlsanity.com/paper/2212.11498/) (2022)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [LaDe: The First Comprehensive Last-mile Delivery Dataset from Industry](https://mlsanity.com/paper/2306.10675/) (2023)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [Joint Estimation and Prediction of City-wide Delivery Demand: A Large Language Model Empowered Graph-based Learning Approach](https://mlsanity.com/paper/2408.17258/) (2024)
- [Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey](https://mlsanity.com/paper/2108.04462/) (2021)
- [Off-line approximate dynamic programming for the vehicle routing problem with a highly variable customer basis and stochastic demands](https://mlsanity.com/paper/2109.10200/) (2021)
- [Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem](https://mlsanity.com/paper/2404.11458/) (2024)
- [Multi-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems](https://mlsanity.com/paper/2511.17435/) (2025)
- [Introduction to The Dynamic Pickup and Delivery Problem Benchmark -- ICAPS 2021 Competition](https://mlsanity.com/paper/2202.01256/) (2022)
- [FeatureBox: Feature Engineering on GPUs for Massive-Scale Ads Systems](https://mlsanity.com/paper/2210.07768/) (2022)
- [Heuristic Algorithm-based Action Masking Reinforcement Learning (HAAM-RL) with Ensemble Inference Method](https://mlsanity.com/paper/2403.14110/) (2024)
- [TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problems](https://mlsanity.com/paper/2502.15777/) (2025)
- [A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem](https://mlsanity.com/paper/2510.03065/) (2025)
- [A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing](https://mlsanity.com/paper/2607.16875/) (2026)

## Abstract (arXiv)

The Dynamic Pickup and Delivery Problem (DPDP) is aimed at dynamically scheduling vehicles among multiple sites in order to minimize the cost when delivery orders are not known a priori. Although DPDP plays an important role in modern logistics and supply chain management, state-of-the-art DPDP algorithms are still limited on their solution quality and efficiency. In practice, they fail to provide a scalable solution as the numbers of vehicles and sites become large. In this paper, we propose a data-driven approach, Spatial-Temporal Aided Double Deep Graph Network (ST-DDGN), to solve industry-scale DPDP. In our method, the delivery demands are first forecast using spatial-temporal prediction method, which guides the neural network to perceive spatial-temporal distribution of delivery demand when dispatching vehicles. Besides, the relationships of individuals such as vehicles are modelled by establishing a graph-based value function. ST-DDGN incorporates attention-based graph embedding with Double DQN (DDQN). As such, it can make the inference across vehicles more efficiently compared with traditional methods. Our method is entirely data driven and thus adaptive, i.e., the relational representation of adjacent vehicles can be learned and corrected by ST-DDGN from data periodically. We have conducted extensive experiments over real-world data to evaluate our solution. The results show that ST-DDGN reduces 11.27% number of the used vehicles and decreases 13.12% total transportation cost on average over the strong baselines, including the heuristic algorithm deployed in our UAT (User Acceptance Test) environment and a variety of vanilla DRL methods. We are due to fully deploy our solution into our online logistics system and it is estimated that millions of USD logistics cost can be saved per year.