文章目录
- Abstract
- 1 Introduction
- 2. Related Work
- 2.1 引言
- 2.2.基于RNN的VRP解决方案
- 2.3.基于GNN的VRP解决方案
- 2.4.基于Transformer的车辆路径问题求解方法
- 3 边嵌入注意力模型
- 3.1 编码器
- 3.1.1 边嵌入多头注意力
- 3.1.2. 前馈网络（FFN）、批量归一化和残差连接
- 3.2 解码器
- 3.2.1 解码器上下文向量
- 3.2.2 解码器注意力层
- 3.2.3. 车辆容量更新和masking规则
- 4. 训练网络的DRL算法
- 5. Computational Experiment
- 5.1 与基线的比较
- 5.2 不同图大小的泛化能力
- 5.3 我们框架与残差E-GAT的结果比较
- 5.4 真实世界图测试
- 6. Conclusion
Abstract
车辆路径问题（VRP）是经典的组合优化问题之一，需要在一些约束条件下，以最小的总成本访问客户。最近，VRP通过使用深度强化学习（DRL）来解决，将节点集视为图结构。现有的基于Transformer的DRL解仅依赖于节点信息，忽略了图中节点之间边的信息在图结构中的作用。在本文中，我们提出了一种基于注意力的端到端DRL模型来解决VRP，该模型嵌入了节点之间的边信息，以进行丰富的图表示学习。我们使用了带有嵌入边信息多头注意力（EEMHA）层的基于Transformer的编码器-解码器框架。基于EEMHA的编码器学习图的底层结构，并通过合并节点和边信息生成表达力强的图拓扑表示。我们使用近端策略优化（PPO）和一些代码级优化技术训练我们的模型。我们在随机生成的实例和从道路网络生成的真实世界数据上进行了实验，以验证我们提出的模型的性能。所有实验结果表明，我们的模型比现有的DRL方法和大多数传统启发式在从随机实例训练到不同问题尺寸的真实世界实例测试的泛化能力上表现更好。
© 2023 日本电气工程师学会。由Wiley Periodicals LLC出版。
