一种基于深度强化学习的外卖配送路径规划方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115841286A(43)申请公布日2023.03.24(21)申请号202211042369.X(22)申请日2022.08.29(71)申请人南京信息工程大学地址210044江苏省南京市浦口区宁六路219号(72)发明人张朔(74)专利代理机构北京同辉知识产权代理事务所(普通合伙)11357专利代理师何静(51)Int.Cl.G06Q10/0835(2023.01)G06Q10/047(2023.01)G06N3/084(2023.01)G06N3/0464(2023.01)G06N3/04(2023.01)权利要求书3页说明书8页附图4页(54)发明名称一种基于深度强化学习的外卖配送路径规划方法(57)摘要本发明公开了路径规划技术领域的一种基于深度强化学习的外卖配送路径规划方法，所述规划方法包括以下步骤：步骤一：读取问题输入的信息，定义优化目标，设定约束条件；步骤二：搭建编码器‑解码器架构中的基础神经网络；步骤三：构建演员和评论家网络；步骤四：设定网络训练过程参数；步骤五：构建数据集；步骤六：演员网络和评论家网络的前向传递；步骤七：网络的训练与更新；步骤八：终止判断。本发明具有求解速度快、泛化能力强的优点，有着更好的适应能力和发展前景，能够对更加复杂的问题进行模拟和求解，引入注意力‑指针网络结构加快了算法收敛的速度，已训练好的网络参数可以保存，不需要每次重新进行大量的运算。CN115841286ACN115841286A权利要求书1/3页1.一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述规划方法包括以下步骤：步骤一：读取问题输入的信息，定义优化目标，设定约束条件；步骤二：搭建以注意力‑指针网络机制为基础的编码器‑解码器架构中的基础神经网络，并初始化它们的权值和偏置等参数；步骤三：在步骤二搭建的基础神经网络基础上，结合演员‑评论家算法，构建演员网络和评论家网络；步骤四：设定网络训练过程参数；步骤五：收集取送货节点位置信息，并为数据添加先后次序约束，构建数据集，划分为训练样本集、验证样本集以及测试数据集；步骤六：输入训练样本集中的数据，使用演员网络给出骑手的预测行程序列，即骑手访问各个取送货节点的合法次序，并给出序列对应的行程距离，再利用评论家网络对演员网络的输出结果做出评价，即给出实际行程距离；步骤七：进行网络的训练与更新，计算演员网络给出结果与评论家网络给出结果的差值，进行平方处理后作为损失值，根据损失值进行反向传播，并使用Adam优化器对神经网络的参数进行更新；步骤八：终止判断，若已完成设定的训练轮数，或损失值满足终止条件，则终止迭代，保存最优网络参数，并在该参数下使用演员网络给出目标问题的规划结果，否则转至步骤六，重复训练过程，并通过观察损失的变化和当前网络在验证集上的表现评估网络训练情况。2.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤一中问题的输入信息包括骑手平均速度、骑手最远行驶距离、骑手最大携带量、订单时间窗、单个节点最大需求量、节点总数目以及各节点位置；所述优化目标为完成所有订单配送任务时的行程总距离最小；所述约束条件为每个订单必须在时间窗内被完成且仅被完成一次、骑手的行驶距离不能超过最大行驶距离及骑手必须先取后送。3.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤二中的基础神经网络包括卷积编码器网络、注意力机制网络、指针网络的其中一种或多种。4.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤三中演员‑评论家算法是一种结合策略梯度和时序差分学习的强化学习方法，演员指策略函数，学习一个策略来得到尽量高的回报，评论员指值函数，对当前策略的值函数进行估计，评估演员的好坏。5.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤三中演员网络使用编码器‑解码器架构，以卷积输入层作为编码器，注意力‑指针网络作为解码器，编码器的输出经过隐藏层处理后输入到解码器中，解码器中的注意力‑指针网络根据各节点当前注意力的情况，从上一个状态指向下一个状态。6.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤一中：读取问题输入的信息，定义优化目标，设定约束条件的步骤如下：首先设定模型参数：2CN115841286A权利要求书2/3页其中，K＝{1,2,...,k}：骑手集合，共有k个骑手；N＝{0,1,...,2n}：节点集合，其中0表示配送中心；P＝{1,...,n}：取餐点集合，代表有n个订单；D＝{n+1,...,2n}：送餐点集合，i∈P，i+n∈D，i与i+n配对；