A Travel Salesman Problem Solving Algorithm Based on Feature Enhanced Attention Model

A Travel Salesman Problem Solving Algorithm Based on Feature Enhanced Attention Model

In order to address the challenges of low accuracy and weak generalization capabilities in solving the traveling salesman problem (TSP) using end-to-end deep reinforcement learning (DRL) algorithms, this paper introduced a novel solution. This solution consisted of a feature enhanced attention model (FEAM) and a rotation expanded inference method. The FEAM combined a feature filtering layer, a graph embedding layer, and Transformer architecture in the encoder to better capture the complex relationships between cities, obtain richer and more accurate node representations, and thereby improved the model’s solving accuracy and generalization ability. The rotation expanded inference method generated new problem instances through coordinate rotation, enabling the model to consider path planning strategies from multiple perspectives, thus further enhancing solution accuracy. Numerous experiments on randomly generated benchmark datasets and public benchmark datasets show that the proposed end-to-end DRL algorithm performed better than other DRL algorithms in terms of solution quality and generalization ability.