(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210884085.9 (22)申请日 2022.07.26 (71)申请人 西北师范大学 地址 730030 甘肃省兰州市安宁区安宁东 路967号 (72)发明人 田冉　冷吉锴　高鑫　马忠彧　 刘颜星　杨馥宁　杨赛赛　卢梦　 康春明　赵光路　 (74)专利代理 机构 北京盛凡佳华专利代理事务 所(普通合伙) 11947 专利代理师 靳桂琳 (51)Int.Cl. G06Q 10/08(2012.01) G06Q 10/06(2012.01) G06Q 10/04(2012.01)G06Q 30/02(2012.01) G06N 3/04(2006.01) G06N 3/08(2006.01) G06N 20/00(2019.01) (54)发明名称 一种基于Concurrent Decode强化学习的异 构车队分批交付方法 (57)摘要 本发明提供了一种基于ConcurrentDecode 强化学习的异构车队分批交付方法。 该方法是一 种具有表征HFVRPSD中不同信息的Encoder ‑ Decoder架构， 首先， Encoder额外地融合了车队 的容量信息， 增强了决策网络对于不同车辆容量 的敏感性， 然后提出了一种并发自适应神经网络 结构， 该方法集成了深度强化学习和Attention 机制来学习路径构建策略。 具体来说， 策略网络 并发地对于每辆车和其配送能力范围内的节点 做了车‑节点匹配， Decoder 针对每辆 车上下文以 车队整体角度并发地为每辆车求得最优回路。 实 验结果表明， 该方法在总体解决质量方面优于大 多数传统的启发 式算法， 并且具有更短的计算时 间。 本方法促进了基于深度强化学习的方法在组 合优化领域的发展， 以解决各种车辆路径问题。 权利要求书5页 说明书10页 附图4页 CN 115130970 A 2022.09.30 CN 115130970 A 1.一种基于Concurrent  Decode强化学习的异构车队分批交付方法， 其特征在于包括 下述步骤： 定义： CDDRL全称为Concurr entDecode  Deep Reinforcement  Learning， 即并发解码深 度强化学习， 本发明设计了一种具有表征HFVRPSD中不同信息的Enco der‑Decoder架构， 来 增强DRL拟合不同场景的能力， 用以自动选择节点， 在这种架构中， 在解码过程中收纳了不 同的额外信息， 并且迭代更新用以补充不同状态对于A gent决策的影响， 然后， 提出了一种 并发搜索策略， 以车队整体角度并发地为每辆车求得最优回路， 这种搜索策略能够更为精 确的表征解码过程中图的状态， 并且能够使得不同容量的车辆之 间能够协同地处理客户节 点的需求； 步骤1： 对HFVRPSD的混合整数规划公式进行问题建模； 我们假定， 在一个HFVRPSD中， 一 组n个需求节点和一个交付中心被表示为一个图G， 假设G＝(P,K)为该交付任务， 其中P＝ {P0,P1,P2,......,Pn,}表示顶点集， 包括交付中心P0＝{x0,y0}和需求节点Pi＝{Pix,Piy, ρi| i∈n}， (Pix,Piy)和ρi分别表示节点i的坐标与需求量； 弧集A＝{(Pi,Pj)|Pi,Pj∈P,i≠j,}为 任意两点之间的弧， 距离矩阵D＝C(i,j)为弧(Pi,Pj)的长度， K＝{kb|b＝1,2,...,K}表示交 付中心配有K辆核载量 为kb的车， 车辆k在客户点 i的交付量为wki， 定义决策变量如下： 其中， 是一个二元变量， 表示车辆k的路径是否包含弧(Pi,Pj)， yki表示节点Pi是否在 车辆k的路径上， 据此， HFVRP SD的目标函数 可以表示 为： 步骤2： 马尔可夫决策过程建模； 在HFVRPSD中每辆车服务过多个节点之后回到车场的 过程上可以看作是一个决策序列， 因此， 我们将这样的路线建设过程建模为马尔可夫决策 过程(MarkovDeci sionProc ess， MDP)， 由四元组M＝{S,A, τ,R}表示， S表示状态， A为智能体， τ为状态转移规则， R为奖励函数， MDP的元素， 即状态空间、 动作空间、 转换规则和奖励函数 定义如下： 步骤2.1： 状态； 状态S＝(St|t＝1,2,...,T)表示状态集合， 状态ST表示在所有节点需求 都被满足且所有车辆全部回到交付中心时为最后一个状态， 其中 由车辆状态 和节点状态Ot组成， 表示车辆状态， 其中 表示车辆k在解 码步骤t时的剩余核载量 和位置 为节点状态， 表示节点i在t时刻 的剩余需求； 步骤2.2： 动作； 动作A＝π(G)＝{at|t＝1,2,...,T ‑1}表示由策略π在图G下产生的一系 列动作集， 表示车辆k在t时刻选择了节点 i作为交付任务；权　利　要　求　书 1/5 页 2 CN 115130970 A 2步骤2.3： 状态转移规则； 状态转移规则Γ根据执行的动作 将前一状态St转换为下一 状态St+1， 则 其中车辆状态 的更新如下： 上式表示如果在St时执行了动作 则车辆k在St+1时刻的剩余核载量为状态St时的核 载量 减去选择节点的需求量 其他车辆保持不变； 同理， 式二表示如果在St时执行了 动作 则车辆k在St+1时刻的位置为节点Pi， 其他车辆位置不变； 节点状态更新如下： 上式代表如果在状态St时执行了动作 则节点i在St+1时的剩余 需求为状态St时节点 i的剩余需求 量 减去车辆 z的剩余核载量 其它节点St时保持一 致； 此外， HFVRP SD的掩码规则计算如下： 上式表示车辆k在t时刻对于节点j的可访问性， 意味着只要当前车辆k还有剩余核载量 或者还有需求未被满足时为False， 代表可以访问， 其余为True； 同理， 式二表 示车辆k在t时 刻对于交付中心的可访问性， 当且仅当车辆剩余核载量为零或者没有需求需要交付时为 False， 代 表可以回到交付中心， 反 之亦然； 最终掩码规则为： 表示最终掩码规则由交付中心掩码 与需求节点掩码 组合而成； 步骤2.4： 奖励； 奖励： 出于强化学习最大化奖励的目标， 目标函数的负值被 计算为奖励， 表示 为： 目标函数： 为了最小化目标函数中的目标， 可以将最终回报定义 为： 最终需要求得最优策略π*， 即：权　利　要　求　书 2/5 页 3 CN 115130970 A 3