Step-Wise Deep Learning Models for Solving Routing Problems

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.

Automated summary

The article proposes a novel step-wise scheme to remove visited nodes in each node selection step, addressing the issue of suboptimal policies in routing problems. By applying this scheme, the performance of two deep models is significantly improved, and an approximate step-wise TAM model is introduced to reduce computational complexity.