Multi-Objective Reinforcement Learning with Enhanced Pointer Networks for TSP
Nanjie Zhang, Yuquan Chen, Maoqin Ji, Wenchao Hong, Bing Wang · 2025
The Travelling Salesman Problem (TSP) presents a significant challenge in combinatorial optimization, with conventional methodologies proving inadequate for large-scale instances. This paper introduces an innovative reinforcement learning framework for TSP optimization, delivering four major technical contributions to advance the state-of-the-art. The first contribution is a novel pointer generation mechanism featuring learnable query vectors and adaptive scaling. This mechanism incorporates residual connections and layer normalization to mitigate gradient vanishing issues, thereby enhancing the model's capacity to capture spatial relationships between cities. Secondly, the paper develops an integrated architecture that combines a Transformer encoder with an LSTM decoder. Within this architecture, a hierarchical attention mechanism enhances both feature extraction and spatial modeling capabilities while maintaining efficient sequence generation. The third contribution is a comprehensive multi-dimensional reward function that addresses scale inconsistencies in multi-objective optimization. This unified framework incorporates path length, clustering metrics, crossing penalties, and path smoothness, providing more effective guidance for the reinforcement learning process. Finally, the research introduces an enhanced training protocol based on Proximal Policy Optimization (PPO) with adaptive clipping and early stopping mechanisms. Additionally, mixed-precision training is implemented to improve computational efficiency. Extensive experimental evaluation demonstrates consistent performance improvements of$2.8 \%-5.3 \%$across varying problem scales compared to state-of-the-art baselines. The approach exhibits remarkable solution stability, as evidenced by decreasing standard deviations from 0.419 for TSP10 to 0.227 for TSP100.