Adaptive Distance-Aware Attention Models for Routing Problems
Chao Zhang, Jinbiao Xing, Hui Wang, Kuangzheng Li, Weihao Jiang, Shiliang Pu · 2024
Attention-based models (AMs) with deep reinforcement learning (DRL) training schemes have emerged as a prominent research direction in the field of machine learning for combinatorial optimization (ML4CO). These models have demonstrated great potential for quickly constructing solutions, without depending on expert knowledge or relying on costly supervised labels. However, existing AMs often neglect the use of positional embeddings and fail to exploit the relative distance information between nodes. To address this limitation, this paper proposes a novel adaptive distance-aware (ADA) mechanism for AMs. Drawing inspiration from the positional encoding technology used in Transformers, the ADA mechanism encodes the distance between pairs of nodes to re-scale the raw self-attention weights. Additionally, the proposed mechanism leverages multiple distance-aware structures to provide the decoder with diverse horizons, enabling it to effectively solve routing problems. The effectiveness of the proposed adaptive DA mechanism is validated through numerous experiments. The results demonstrate that integrating the ADA mechanism into existing attention models significantly improves the quality of the constructed solutions and enhances the generalization capability across different problem sizes.