Step-wise deep learning models for solving routing problems

• Main Authors: XIN, Liang, SONG, Wen, CAO, Zhiguang, ZHANG, Jie
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Routing; Deep learning; Decoding; Computational modeling; Reinforcement learning; Urban areas; Informatics; Deep reinforcement learning; Intelligent transportation system; Routing problems; Numerical Analysis and Scientific Computing; Operations Research, Systems Engineering and Industrial Engineering; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/8155; https://ink.library.smu.edu.sg/context/sis_research/article/9158/viewcontent/Step_Wise_Deep_Learning_Models_for_Solving_Routing_Problems_av.pdf
• Institution: Singapore Management University

Routing problems are very important in intelligent transportation systems. Recently, a number of deep learning-based methods are proposed to automatically learn construction heuristics for solving routing problems. However, these methods do not completely follow Bellman's Principle of Optimality since the visited nodes during construction are still included in the following subtasks, resulting in suboptimal policies. In this article, we propose a novel step-wise scheme which explicitly removes the visited nodes in each node selection step. We apply this scheme to two representative deep models for routing problems, pointer network and transformer attention model (TAM), and significantly improve the performance of the original models. To reduce computational complexity, we further propose the approximate step-wise TAM model by modifying one layer of attention. It enables training on larger instances compared to step-wise TAM, and outperforms state-of-the-art deep models with greedy decoding strategy.