Professor Niu Lingfeng,Virtual Economy and Data Science Research Center, School of Economics and Management, University of Chinese Academy of Sciences

Deep learning based methods have shown great potential for solving Vehicle Routing Problems (VRPs) in recent years. In the current learning based models, attention mechanism plays an important role and becomes one of the key modules for improving the performance. However, the aggregate-by-summation paradigm of attention is not expressive enough to fully capture the rich information in VRPs. To solve this problem, we propose a novel capsule aggregated attention mechanism, which utilizes capsule to store more information and applies dynamic routing for information aggregation. Besides, a soft gated capsule selector is exploited to differentiate the importance of different capsules, and the context node vector in the decoding process is modified to reflect the state changes. Based on the proposed capsule aggregated attention mechanism, we present a new graph attention network for solving VRPs under the reinforcement learning framework in this paper. Extensive numerical experiments on two typical VRPs, including traveling salesman problem and capacitated vehicle routing problem, validate the effectiveness and efficiency of our proposed method.