# A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 22 Dec 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [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)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach](https://mlsanity.com/paper/2002.05513/) (2020)
- [Multi-Agent Routing Value Iteration Network](https://mlsanity.com/paper/2007.05096/) (2020)
- [A Reinforcement Learning Approach for Rebalancing Electric Vehicle Sharing Systems](https://mlsanity.com/paper/2010.02369/) (2020)
- [On the Min-cost Traveling Salesman Problem with Drone](https://mlsanity.com/paper/1512.01503/) (2015)
- [A Variable Neighborhood Search for Flying Sidekick Traveling Salesman Problem](https://mlsanity.com/paper/1804.03954/) (2018)
- [Drone-assisted deliveries: new formulations for the Flying Sidekick Traveling Salesman Problem](https://mlsanity.com/paper/1905.13463/) (2019)

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

- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)
- [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)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems](https://mlsanity.com/paper/2404.15852/) (2024)
- [USPR: Learning a Unified Solver for Profiled Routing](https://mlsanity.com/paper/2505.05119/) (2025)
- [Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems](https://mlsanity.com/paper/2505.15862/) (2025)
- [Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting](https://mlsanity.com/paper/2508.17087/) (2025)
- [A Unified Model for Multi-Task Drone Routing in Post-Disaster Road Assessment](https://mlsanity.com/paper/2510.21525/) (2025)
- [Neural Ising Machines via Unrolling and Zeroth-Order Training](https://mlsanity.com/paper/2602.00302/) (2026)
- [Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones](https://mlsanity.com/paper/2606.30680/) (2026)
- [Drive, Pack, Fly: The Travelling Thief Problem with Drone](https://mlsanity.com/paper/2608.16435/) (2026)
- [RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization](https://mlsanity.com/paper/2609.11452/) (2026)

## Abstract (arXiv)

Reinforcement learning has recently shown promise in learning quality solutions in many combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on various routing problems, including the Traveling Salesman Problem (TSP). Unfortunately, they perform poorly for the TSP with Drone (TSP-D), requiring routing a heterogeneous fleet of vehicles in coordination -- a truck and a drone. In TSP-D, the two vehicles are moving in tandem and may need to wait at a node for the other vehicle to join. State-less attention-based decoder fails to make such coordination between vehicles. We propose a hybrid model that uses an attention encoder and a Long Short-Term Memory (LSTM) network decoder, in which the decoder's hidden state can represent the sequence of actions made. We empirically demonstrate that such a hybrid model improves upon a purely attention-based model for both solution quality and computational efficiency. Our experiments on the min-max Capacitated Vehicle Routing Problem (mmCVRP) also confirm that the hybrid model is more suitable for the coordinated routing of multiple vehicles than the attention-based model. The proposed model demonstrates comparable results as the operations research baseline methods.