Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning
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.