# Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 4 Jul 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [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)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2110.02634/) (2021)
- [Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention](https://mlsanity.com/paper/2006.09100/) (2020)
- [Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks](https://mlsanity.com/paper/1803.09621/) (2018)
- [Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size](https://mlsanity.com/paper/2201.01529/) (2022)
- [RP-DQN: An application of Q-Learning to Vehicle Routing Problems](https://mlsanity.com/paper/2104.12226/) (2021)

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

- [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)

## Abstract (arXiv)

This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) by adapting recent approaches that work well for regular TSPs. Common to these approaches is the use of graph models based on multi-head attention (MHA) layers. One idea for solving the pickup and delivery problem (PDP) is using heterogeneous attentions to embed the different possible roles each node can take. In this work, we generalize this concept of heterogeneous attentions to the TSPPC. Furthermore, we adapt recent ideas to sparsify attentions for better scalability. Overall, we contribute to the research community through the application and evaluation of recent DRL methods in solving the TSPPC.