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

**Authors:** Aigerim Bogyrbayeva, Taehyun Yoon, Hanbum Ko, Sungbin Lim, Hyokun Yun, Changhyun Kwon  
**arXiv:** [2112.12545](https://arxiv.org/abs/2112.12545)  
**Date:** 2021-12-22  
**Summary page:** https://www.summarizepaper.com/en/paper/2112.12545v3/

## Key points

- Reinforcement learning is a promising approach for solving combinatorial optimization problems like the TSP.
- Attention-based encoder-decoder models are effective for routing problems, but not for TSP-D involving a truck and a drone.
- The state-less attention-based decoder lacks coordination between vehicles in TSP-D.
- A hybrid model combining an attention encoder with an LSTM network decoder is proposed to address this limitation.
- The LSTM decoder's hidden state enables better coordination between the truck and drone by representing the sequence of actions made.
- Experimental results show that the hybrid model improves solution quality and computational efficiency compared to purely attention-based models.
- The hybrid model is more suitable for coordinated routing of multiple vehicles than the attention-based model in mmCVRP experiments.
- The proposed model achieves comparable results to operations research baseline methods.
- This study presents a deep reinforcement learning approach using a hybrid model for solving TSP-D.

## Summary

Reinforcement learning has emerged as a promising approach for solving combinatorial optimization problems such as the Traveling Salesman Problem (TSP). Attention-based encoder-decoder models have shown high effectiveness in solving routing problems. However, these models fail to perform well when applied to the TSP with Drone (TSP-D), which involves coordinating a heterogeneous fleet of vehicles consisting of a truck and a drone. In TSP-D, the vehicles move together and may need to wait at certain nodes for the other vehicle to join. The state-less attention-based decoder lacks the ability to coordinate between vehicles in this scenario. To address this limitation, the authors propose a hybrid model that combines an attention encoder with a Long Short-Term Memory (LSTM) network decoder. The LSTM decoder's hidden state is able to represent the sequence of actions made, enabling better coordination between the truck and drone. Experimental results demonstrate that this hybrid model improves both solution quality and computational efficiency compared to a purely attention-based model. The authors also conduct experiments on the min-max Capacitated Vehicle Routing Problem (mmCVRP) and find that the hybrid model is more suitable for coordinated routing of multiple vehicles than the attention-based model. Furthermore, the proposed model achieves comparable results to operations research baseline methods. Overall, this study presents a deep reinforcement learning approach for solving TSP-D using a hybrid model that combines an attention encoder with an LSTM network decoder. The empirical results highlight the effectiveness of this approach in improving solution quality and computational efficiency in comparison to existing models.