利索能及
我要发布
收藏
专利号: 202211042369X
申请人: 南京信息工程大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-06-16
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述规划方法包括以下步骤:步骤一:读取问题输入的信息,定义优化目标,设定约束条件;

步骤二:搭建以注意力‑指针网络机制为基础的编码器‑解码器架构中的基础神经网络,并初始化它们的权值和偏置等参数;

步骤三:在步骤二搭建的基础神经网络基础上,结合演员‑评论家算法,构建演员网络和评论家网络;

步骤四:设定网络训练过程参数;

步骤五:收集取送货节点位置信息,并为数据添加先后次序约束,构建数据集,划分为训练样本集、验证样本集以及测试数据集;

步骤六:输入训练样本集中的数据,使用演员网络给出骑手的预测行程序列,即骑手访问各个取送货节点的合法次序,并给出序列对应的行程距离,再利用评论家网络对演员网络的输出结果做出评价,即给出实际行程距离;

步骤七:进行网络的训练与更新,计算演员网络给出结果与评论家网络给出结果的差值,进行平方处理后作为损失值,根据损失值进行反向传播,并使用Adam优化器对神经网络的参数进行更新;

步骤八:终止判断,若已完成设定的训练轮数,或损失值满足终止条件,则终止迭代,保存最优网络参数,并在该参数下使用演员网络给出目标问题的规划结果,否则转至步骤六,重复训练过程,并通过观察损失的变化和当前网络在验证集上的表现评估网络训练情况。

2.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤一中问题的输入信息包括骑手平均速度、骑手最远行驶距离、骑手最大携带量、订单时间窗、单个节点最大需求量、节点总数目以及各节点位置;

所述优化目标为完成所有订单配送任务时的行程总距离最小;

所述约束条件为每个订单必须在时间窗内被完成且仅被完成一次、骑手的行驶距离不能超过最大行驶距离及骑手必须先取后送。

3.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤二中的基础神经网络包括卷积编码器网络、注意力机制网络、指针网络的其中一种或多种。

4.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤三中演员‑评论家算法是一种结合策略梯度和时序差分学习的强化学习方法,演员指策略函数,学习一个策略来得到尽量高的回报,评论员指值函数,对当前策略的值函数进行估计,评估演员的好坏。

5.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤三中演员网络使用编码器‑解码器架构,以卷积输入层作为编码器,注意力‑指针网络作为解码器,编码器的输出经过隐藏层处理后输入到解码器中,解码器中的注意力‑指针网络根据各节点当前注意力的情况,从上一个状态指向下一个状态。

6.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤一中:读取问题输入的信息,定义优化目标,设定约束条件的步骤如下:首先设定模型参数:

其中,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配对;

dij:节点i,j∈N之间的距离;

k

c:骑手k的行驶单位距离总成本;

k

v:骑手k的平均行驶速度;

qi:节点i处的外卖数量,i∈P时为正表示取餐,i∈D时为负表示送餐;

订单i∈P所允许的最大时间窗;

骑手k所能携带的外卖最大份数;

骑手k所能行驶的最远距离;

骑手k是否经过了路径(i,j)(i,j∈N),1代表是,0代表不是;

骑手k是否到过节点i∈N;

骑手k到达节点i∈N时携带的外卖份数;

骑手k到达节点i∈N时已经走过的距离;

骑手k到达节点i∈N时经历的时间;

然后明确模型假设:

k

所有骑手的平均速度、最远行驶距离、最大携带数量、单位距离花费均相同:v =v,(v,s,q,c为定值);

骑手位于配送中心时间为0,行走距离为0:假定骑手在每个节点都只取/送一份外卖: (i∈D时取‑1);

所有订单的时间窗相同: (t为一个定值);

接着完善模型约束:

保证每个订单都被唯一一位骑手取餐:

保证取餐后有对应的送餐:

保证先取餐再送餐:

保证订单与骑手的匹配关系:

骑手携带外卖最大份数约束:

订单时间窗口约束:

骑手最大行驶距离约束:

骑手携带外卖数量平衡约束:

路径平衡约束:

时间平衡约束:

路径时间约束:

最后确定总优化目标:

7.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤二中所述搭建的基本神经网络的相关结构如下:选定了编码器‑解码器作为基础架构,并引入了使用注意力机制的指针网络,用于完成传统方法中seq2seq的过程,其中指针网络在数学上的描述如下所示:式中,ej是编码器encoder在时间序列j次的隐藏层输出,di是解码器decoder在时间序列i次的隐藏状态输出;

所述编码器‑解码器结构中,编码器由一维卷积层构成,解码器由注意力‑指针网络构成,其中,注意力机制用于计算给定当前状态的输入节点上的注意力。

8.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法,其特征在于,所述步骤三中所述的演员‑评论家算法的实现步骤为:步骤一:初始化相关各参数;

步骤二:根据当前策略函数从当前状态空间中选择一个动作;

步骤三:执行该动作,并得到一个即时奖励;

步骤四:根据该即时奖励计算出执行该动作得到的总奖励;

步骤五:根据这个奖励值以及相关的学习率等参数,对策略函数和价值函数的相关参数进行更新;

步骤六:更新折扣率和当前状态;

步骤七:重复上述流程,直到当前状态执行结束,开始新的一轮循环;

步骤八:直到策略函数收敛,输出该策略函数;

步骤九:这个策略函数即为当前最佳动作选择方案。