Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning

DOI10.1007/978-3-031-15791-2_14MaRDI QIDQ6041315zbMATH OpenOpenAlexFDO

Authors Christian Löwens, Inaam Ashraf, Alexander Gembus, Genesis Cuizon, Jonas K. Falkner, Lars Schmidt-Thieme

Publication date 26 May 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.01443

zbMATH Keywords

deep reinforcement learningheterogeneous attentiontraveling salesperson problem with precedence constraints

Mathematics Subject Classification ID

Artificial neural networks and deep learning (68T07) Combinatorial optimization (90C27)

Abstract: 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.

Recommendations

• Deep policy dynamic programming for vehicle routing problems
• Learning the travelling salesperson problem requires rethinking generalization
• An efficient genetic algorithm for the traveling salesman problem with precedence constraints
• Learning heuristics for the TSP by policy gradient
• Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization

Cites work

• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers
• An inexact algorithm for the sequential ordering problem
• Simple statistical gradient-following algorithms for connectionist reinforcement learning
• The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm

Cited in

(5)

• Learning the travelling salesperson problem requires rethinking generalization
• Deep policy dynamic programming for vehicle routing problems
• Dynamic graph conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem
• Learn to solve dominating set problem with GNN and reinforcement learning
• An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem

This page was built for publication: Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041315)