关键词: TSP, GCN-Pointransformer, MHLSA, 可逆残差, 指针层

Abstract: Because the Transformer model is based on the fully connected attention mechanism, the computational complexity is high and the GPU memory usage is too large when solving the classic Traveling Salesman Problem. To solve this problem, a GCN-Pointransformer model based on graph convolutional embedding layer and multi-head local self-attention mechanism was proposed. Firstly, the graph convolutional embedding method is used to learn spatial features from the input data, and the graph convolutional embedding layer contains multiple convolution kernels that can extract the local features of the input data, and secondly, the Multi Head Local Self is used Attention, which removes redundant information and extracts useful features, in addition, uses a reversible residual network in the encoder to store only input and output embedding feature pairs during backpropagation, and finally, the model adds a Pointer layer in the decoder, using attention weights as probability distributions to determine the next node to be visited. Comparative experiments on the TSP random datasets show that the optimization gap is reduced by 12%, the GPU memory is reduced by about 11%, and the inference time is reduced by about 25%, and the results show that the proposed method is superior to the standard Transformer model for solving TSP.

Key words: TSP, GCN-Pointransformer, MHLSA, Reversible residual, Pointer layer