Multi-type attention for solving multi-depot vehicle routing problems

• Main Authors: LI, Jinqi, DAI, Bing Tian, NIU, Yunyun, XIAO, Jianhua, WU, Yaoxin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Vehicle routing; Transformers; Heuristic algorithms; Decoding; Decision making; Computer architecture; Training; Deep reinforcement learning; learning to optimize; multi-depot vehicle routing problem; multi-depot open vehicle routing problem; attention mechanism; transformer model; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/9208
• Institution: Singapore Management University

In recent years, there has been a growing trend towards using deep reinforcement learning (DRL) to solve the NP-hard vehicle routing problems (VRPs). While much success has been achieved, most of the previous studies solely focused on single-depot VRPs, which became less effective in handling more practical scenarios, such as multi-depot VRPs. Although there are many preprocessing measures, such as natural decomposition, those scenarios are still more challenging to optimize. To resolve this issue, we propose the multi-depot multi-type attention (MD-MTA) to solve the multi-depot VRP (MDVRP) and multi-depot open VRP (MDOVRP), respectively. We design a multi-type attention in the network to combine different types of embeddings and the state of the environment at each step, so as to accurately select the next node to visit and construct the route. We introduce a depot rotation augmentation to enhance solution decoding. Results show that it performs favorably against various representative traditional baselines and DRL-based baselines.