基于残差图卷积网络与深度强化学习的需求可拆分车辆路径优化算法

作者：罗佳; 李朝锋^*

来源：控制理论与应用, 2023, 1-13.

• 需求可拆分车辆路径问题
• 残差图卷积神经网络
• 注意力机制
• 深度强化学习

需求可拆分车辆路径问题(the Split Delivery Vehicle Routing Problem, SDVRP)出现在广泛的物流配送场景中,具有重要的研究价值.高效的SDVRP优化算法能够提高车辆装载率,降低物流配送成本.为提高SDVRP的求解效率,本文提出基于残差图卷积神经网络(the Residual Graph Convolutional Network, RGCN)和多头注意力的深度强化学习算法(REINFORCE)逐步构建可行解序列.首先,从强化学习的角度出发,对SDVRP建立马尔科夫决策模型,定义序列预测过程的环境状态、智能体动作空间、状态转移函数等.其次,建立编-解码模型求解节点选择策略,其中使用残差图卷积神经网络的编码器重构配送中心和客户节点的特征,将配送网络中节点间的连接关系与节点特征相互关联,获得差异性显著的特征嵌入向量;利用注意力网络解码器在重构后的嵌入向量基础上融合动态变化的车辆剩余装载量和客户需求等信息执行解码任务,实现每次迭代为单个案例提供多个可行解.最后,提出基于平均基准值的REINFORCE算法更新模型参数,通过求解不同问题规模测试集、标准SDVRP数据集,以及京东物流实际配送任务,验证了所提算法的有效性.

• 单位
  上海海事大学