Publication Type

Journal Article

Version

acceptedVersion

Publication Date

7-2021

Abstract

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.

Keywords

Routing, Deep learning, Decoding, Computational modeling, Reinforcement learning, Urban areas, Informatics, Deep learning, Deep reinforcement learning, Intelligent transportation system, Routing problems

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

IEEE Transactions on Industrial Informatics

Volume

17

Issue

7

First Page

4861

Last Page

4871

ISSN

1551-3203

Identifier

10.1109/TII.2020.3031409

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TII.2020.3031409

Download

Share

COinS