Learning-based methods have become increasingly popular for solving vehicle
routing problems due to their near-optimal performance and fast inference
speed. Among them, the combination of deep reinforcement learning and graph
representation allows for the abstraction of node topology structures and
features in an encoder-decoder style. Such an approach makes it possible to
solve routing problems end-to-end without needing complicated heuristic
operators designed by domain experts. Existing research studies have been
focusing on novel encoding and decoding structures via various neural network
models to enhance the node embedding representation. Despite the sophisticated
approaches applied, there is a noticeable lack of consideration for the
graph-theoretic properties inherent to routing problems. Moreover, the
potential ramifications of inter-nodal interactions on the decision-making
efficacy of the models have not been adequately explored. To bridge this gap,
we propose an adaptive Graph Attention Sampling with the Edges Fusion framework
(GASE),where nodes' embedding is determined through attention calculation from
certain highly correlated neighbourhoods and edges, utilizing a filtered
adjacency matrix. In detail, the selections of particular neighbours and
adjacency edges are led by a multi-head attention mechanism, contributing
directly to the message passing and node embedding in graph attention sampling
networks. Furthermore, we incorporate an adaptive actor-critic algorithm with
policy improvements to expedite the training convergence. We then conduct
comprehensive experiments against baseline methods on learning-based VRP tasks
from different perspectives. Our proposed model outperforms the existing
methods by 2.08\%-6.23\% and shows stronger generalization ability, achieving
state-of-the-art performance on randomly generated instances and real-world
datasets.

我们提出了一种自适应图注意力采样与边融合框架（GASE），通过使用具有高度相关邻域和边的注意力计算从而确定节点的嵌入，进一步融合采样网络中的消息传递和节点嵌入，在学习导向的 VRP 任务上表现出色，并在随机生成实例和真实世界数据集上展现出超越现有方法的性能。