基于Linformer和多关系解码器的异构车队路径规划模型研究

Research on Heterogeneous Capacitated Vehicle Routing Models Based on Linformer and Multi-Relational Decoder

摘要: 异构有容量限制的车辆路径规划问题(Heterogeneous Capacitated Vehicle Routing Problem, HCVRP)因其广泛的实际应用和复杂的约束条件，成为现代物流优化中的重要研究课题。然而，现有方法在处理异构车队多目标优化任务时，仍存在计算复杂度高和泛化能力不足的问题。针对上述挑战，本文提出了一种基于深度强化学习(Deep Reinforcement Learning, DRL)的新型HCVRP求解框架。首先，引入低秩注意力机制的Linformer模型，显著降低了传统Transformer在大规模问题中的计算复杂度。其次，设计多关系节点选择解码器，通过结合动态节点特征实时更新和车辆状态建模，有效提升了路径优化的解质量。在随机生成的数据集上，通过与多种经典启发式算法和现有深度强化学习方法的对比实验，验证了所提方法的性能。结果表明，本文方法在解质量和计算效率方面均具有显著优势，尤其在复杂约束和大规模实例中表现出更高的适用性。本文为解决异构车队路径规划问题提供了新的理论方法和实践工具，具备广泛的应用前景。

Abstract: The Heterogeneous Capacitated Vehicle Routing Problem (HCVRP) is a critical research topic in modern logistics optimization due to its extensive real-world applications and complex constraints. However, existing methods often face challenges such as high computational complexity and limited generalization ability when handling heterogeneous fleets and multi-objective optimization tasks. To address these issues, this paper proposes a novel HCVRP solution framework based on Deep Reinforcement Learning (DRL). First, a Linformer model with a low-rank attention mechanism is introduced, significantly reducing the computational complexity of traditional Transformers in large-scale problems. Second, a multi-relational node selection decoder is designed to enhance solution quality by dynamically updating node features and modeling vehicle states in real time. Extensive experiments on randomly generated datasets demonstrate the performance of the proposed approach compared with various classical heuristic algorithms and existing DRL methods. The results show that the proposed framework achieves significant advantages in both solution quality and computational efficiency, especially in scenarios with complex constraints and large-scale instances. This study provides a new theoretical methodology and practical tool for solving heterogeneous fleet routing problems, offering broad application prospects.