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

1.本发明属于路径规划技术领域，具体涉及一种基于深度强化学习的外卖配送路径规划方法。

背景技术：

2.据最新调查数据显示，2020年国内外卖市场总体规模高达8352亿元，外卖用户规模多达5亿人。外卖配送作为外卖行业中不可或缺的重要部分，对其进行路径规划，从而提高配送效率和质量，降低配送成本，具有一定的研究价值和应用前景。外卖配送路径规划问题属于带时间窗的取送货问题(pdptw)，近年来，学者们对pdptw问题做了大量研究。li和lim于2003年提出禁忌嵌入模拟退火的启发式算法，该算法结合了禁忌表和模拟退火跳出局部循环的特点，高效地求解pdptw问题；bent于2006年提出了第一个两阶段混合算法用于解决pdptw问题，在第一阶段使用简单的模拟退火算法来减少路线数量和优化解质量，而第二阶段使用大邻域搜索(lns)来减少总旅行成本；潘立军和符卓于2012年提出时差的插入策略，设计了快速时差插入和最优时差插入方法，并结合遗传算法求解带时间窗的取送货问题。常规的启发式算法适应能力较差，不能对更加复杂的问题进行模拟和求解，且整体算法收敛速度有待提升，泛化能力不强。

技术实现要素：

3.针对现有技术的不足，本发明的目的在于提供一种基于深度强化学习的外卖配送路径规划方法，以解决上述背景技术中提出的问题。
4.本发明的目的可以通过以下技术方案实现：
5.一种基于深度强化学习的外卖配送路径规划方法，所述规划方法包括以下步骤：
6.步骤一：读取问题输入的信息，定义优化目标，设定约束条件；
7.步骤二：搭建以注意力-指针网络机制为基础的编码器-解码器架构中的基础神经网络，并初始化它们的权值和偏置等参数；
8.步骤三：在步骤二搭建的基础神经网络基础上，结合演员-评论家算法，构建演员网络和评论家网络；
9.步骤四：设定网络训练过程参数；
10.步骤五：收集取送货节点位置信息，并为数据添加先后次序约束，构建数据集，划分为训练样本集、验证样本集以及测试数据集；
11.步骤六：输入训练样本集中的数据，使用演员网络给出骑手的预测行程序列，即骑手访问各个取送货节点的合法次序，并给出序列对应的行程距离，再利用评论家网络对演员网络的输出结果做出评价，即给出实际行程距离；
12.步骤七：进行网络的训练与更新，计算演员网络给出结果与评论家网络给出结果的差值，进行平方处理后作为损失值，根据损失值进行反向传播，并使用adam优化器对神经网络的参数进行更新；
13.步骤八：终止判断，若已完成设定的训练轮数，或损失值满足终止条件，则终止迭代，保存最优网络参数，并在该参数下使用演员网络给出目标问题的规划结果，否则转至步骤六，重复训练过程，并通过观察损失的变化和当前网络在验证集上的表现评估网络训练情况。
14.优选地，所述步骤一中问题的输入信息包括骑手平均速度、骑手最远行驶距离、骑手最大携带量、订单时间窗、单个节点最大需求量、节点总数目以及各节点位置；
15.所述优化目标为完成所有订单配送任务时的行程总距离最小；
16.所述约束条件为每个订单必须在时间窗内被完成且仅被完成一次、骑手的行驶距离不能超过最大行驶距离及骑手必须先取后送。
17.优选地，所述步骤二中的基础神经网络包括卷积编码器网络、注意力机制网络、指针网络的其中一种或多种。
18.优选地，所述步骤三中演员-评论家算法是一种结合策略梯度和时序差分学习的强化学习方法，演员指策略函数，学习一个策略来得到尽量高的回报，评论员指值函数，对当前策略的值函数进行估计，评估演员的好坏。
19.优选地，所述步骤三中演员网络使用编码器-解码器架构，以卷积输入层作为编码器，注意力-指针网络作为解码器，编码器的输出经过隐藏层处理后输入到解码器中，解码器中的注意力-指针网络根据各节点当前注意力的情况，从上一个状态指向下一个状态。
20.优选地，所述步骤一中：读取问题输入的信息，定义优化目标，设定约束条件的步骤如下：
21.首先设定模型参数；
22.然后明确模型假设；
23.接着完善模型约束；
24.最后确定总优化目标：
[0025][0026]
优选地，所述步骤二中所述搭建的基本神经网络的相关结构如下：
[0027]
选定了编码器-解码器作为基础架构，并引入了使用注意力机制的指针网络，用于完成传统方法中seq2seq的过程，其中指针网络在数学上的描述如下所示：
[0028][0029][0030]
所述编码器-解码器结构中，编码器由一维卷积层构成，解码器由注意力
‑ꢀ
指针网络构成，其中，注意力机制用于计算给定当前状态的输入节点上的注意力。
[0031]
优选地，所述步骤三中所述的演员-评论家算法的实现步骤为：
[0032]
步骤一：初始化相关各参数；
[0033]
步骤二：根据当前策略函数从当前状态空间中选择一个动作；
[0034]
步骤三：执行该动作，并得到一个即时奖励；
[0035]
步骤四：根据该即时奖励计算出执行该动作得到的总奖励；
[0036]
步骤五：根据这个奖励值以及相关的学习率等参数，对策略函数和价值函数的相关参数进行更新；
[0037]
步骤六：更新折扣率和当前状态；
[0038]
步骤七：重复上述流程，直到当前状态执行结束，开始新的一轮循环；
[0039]
步骤八：直到策略函数收敛，输出该策略函数；
[0040]
步骤九：这个策略函数即为当前最佳动作选择方案。
[0041]
本发明的有益效果：
[0042]
1、本发明具有求解速度快、泛化能力强的优点，使用了强化学习原理，并通过搭建深度神经网络，拟合强化学习算法中的相关函数，实现了深度学习与强化学习的结合；
[0043]
2、本发明将深度强化学习应用于组合优化问题的求解，深度强化学习有着更好的适应能力和发展前景，能够对更加复杂的问题进行模拟和求解，这是启发式算法等传统算法所无法比拟的；
[0044]
3、本发明引入注意力-指针网络结构加快了算法收敛的速度，且经过大量数据训练的网络具有很强的泛化能力，解决新问题的效果很好，已训练好的网络参数可以保存，一次训练，多次使用，不需要每次重新进行大量的运算。
附图说明
[0045]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0046]
图1是本发明流程示意图；
[0047]
图2是本发明取送货问题(pdp)示意图；
[0048]
图3是本发明中训练过程中网络的变化情况；
[0049]
图4是本发明中基于深度强化学习求解实例得到的10节点路径规划图；
[0050]
图5是本发明中基于深度强化学习求解实例得到的20节点路径规划图；
[0051]
图6是本发明与传统算法的结果对比图。
具体实施方式
[0052]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0053]
请参阅图1所示，本发明提出一种基于深度强化学习的外卖配送路径规划方法，包括以下步骤：
[0054]
步骤一：读取问题输入的信息，定义优化目标，设定约束条件：
[0055]
所述问题的输入信息包括骑手平均速度、骑手最远行驶距离，骑手最大携带量、订单时间窗、单个节点最大需求量、节点总数目以及各节点位置等；所述优化目标为完成所有订单配送任务时的行程总距离最小；所述约束条件为每个订单必须在时间窗内被完成且仅被完成一次、骑手的行驶距离不能超过最大行驶距离及骑手必须先取后送等。
[0056]
步骤二：搭建编码器-解码器架构中的基础神经网络：
[0057]
搭建以注意力-指针网络机制为基础的编码器-解码器架构中的一些基础神经网
络，如卷积编码器网络、注意力机制网络、指针网络等神经网络，并初始化它们的权值和偏置等参数。
[0058]
步骤三：构建演员和评论家网络：
[0059]
演员-评论家算法是一种结合策略梯度和时序差分学习的强化学习方法。其中演员(actor)是指策略函数，即学习一个策略来得到尽量高的回报，评论员 (critic)是指值函数，对当前策略的值函数进行估计，即评估演员的好坏；
[0060]
根据演员-评论家算法的思想，在之前步骤中已搭建网络的基础上，可构建演员网络和评论家网络，作为对该算法中的策略函数和值函数的拟合。其中演员网络使用了编码器-解码器架构，以卷积输入层作为编码器，注意力-指针网络作为解码器，编码器的输出经过隐藏层处理后输入到解码器中，解码器中的注意力-指针网络根据各节点当前注意力的情况，从上一个状态指向下一个状态。
[0061]
步骤四：设定网络训练过程参数：
[0062]
设定网络训练的相关参数，如本次训练是否生成新的测试集、训练的轮数、训练的终止条件、数据集的大小、学习率、网络参数保存地址以及损失和优化器使用的算法等；。
[0063]
步骤五：构建数据集：
[0064]
收集大量取送货节点位置信息，并为相关数据添加先后次序约束，即取货节点与送货节点必须两两配对，且满足了取货点的负需求之后才允许访问送货点满足其正需求，在此基础上构建数据集，划分为训练样本集、验证样本集以及测试数据集。
[0065]
步骤六：演员网络和评论家网络的前向传递：
[0066]
输入训练样本集中的数据，使用演员网络给出骑手的预测行程序列即骑手访问各个取送货节点的合法次序，并给出序列对应的行程距离，再利用评论家网络对演员网络的输出结果做出评价，即给出实际行程距离。
[0067]
步骤七：网络的训练与更新：
[0068]
计算演员网络给出结果与评论家网络给出结果的差值，进行平方处理后作为损失值，根据该损失进行反向传播，并使用adam优化器对神经网络的参数进行更新，其中，adam优化器是一种可以替代传统随机梯度下降过程的一阶优化算法，它能基于训练数据迭代地更新神经网络权重。
[0069]
步骤八：终止判断：
[0070]
若已完成设定的训练轮数，或损失值满足了终止条件，则终止迭代，保存最优网络参数，并在该参数下使用演员网络给出目标问题的规划结果，否则转步骤六，重复上述训练过程，并可通过观察损失的变化和当前网络在验证集上的表现评估网络训练情况。
[0071]
步骤一中：读取问题输入的信息，定义优化目标，设定约束条件的步骤如下：
[0072]
首先设定模型参数：
[0073]
k＝{1,2,...,k}：骑手集合，共有k个骑手；
[0074]
n＝{0,1,...,2n}：节点集合，其中0表示配送中心；
[0075]
p＝{1,...,n}：取餐点集合，代表有n个订单；
[0076]
d＝{n+1,...,2n}：送餐点集合，i∈p，iin∈d，i与iin配对；
[0077]dij
：节点i,i∈n之间的距离；
[0078]ck
：骑手k的行驶单位距离总成本；
[0079]
vk：骑手k的平均行驶速度；
[0080]
qi：节点i处的外卖数量，i∈p时为正表示取餐，i∈d时为负表示送餐；
[0081]
订单i∈p所允许的最大时间窗；
[0082]
骑手k所能携带的外卖最大份数；
[0083]
骑手k所能行驶的最远距离；
[0084]
骑手k是否经过了路径(i,i)(i,i∈n)，1代表是，0代表不是；
[0085]
骑手k是否到过节点i∈n；
[0086]
骑手k到达节点i∈n时携带的外卖份数；
[0087]
骑手k到达节点i∈n时已经走过的距离；
[0088]
骑手k到达节点i∈n时经历的时间。
[0089]
然后明确模型假设：
[0090]
(1)所有骑手的平均速度、最远行驶距离、最大携带数量、单位距离花费均相同：(v，s，q，c为定值)；
[0091]
(2)骑手位于配送中心时间为0，行走距离为0：
[0092]
(3)假定骑手在每个节点都只取/送一份外卖：(i∈d时取-1)；
[0093]
(4)所有订单的时间窗相同：(t为一个定值)；
[0094]
接着完善模型约束：
[0095]
(1)保证每个订单都被唯一一位骑手取餐：
[0096]
(2)保证取餐后有对应的送餐：
[0097]
(3)保证先取餐再送餐：
[0098]
(4)保证订单与骑手的匹配关系：
[0099]
(5)骑手携带外卖最大份数约束：
[0100]
(6)订单时间窗口约束：
[0101]
(7)骑手最大行驶距离约束：
[0102]
(8)骑手携带外卖数量平衡约束：
[0103]
(9)路径平衡约束：
[0104]
(10)时间平衡约束：
[0105]
(11)路径时间约束：
[0106]
最后确定总优化目标：
[0107][0108]
步骤二中所述搭建的基本神经网络的相关结构如下：
[0109]
(1)本发明选定了编码器-解码器(encoder-decoder)结构作为基础架构，并引入了使用注意力机制(attention)的指针网络(pointer network)，用于完成类似于传统方法中seq2seq的过程。其中指针网络在数学上的描述如下所示：
[0110][0111][0112]
其中ej是编码器encoder在时间序列j次的隐藏层输出，di是解码器decoder 在时间序列i次的隐藏状态输出。对直接求softmax就可以得到输出字典的概率向量，其输出的向量维度和输入保持一致。公式中剩余的参数v
t
,w1,w2均为固定维度的参数，可被训练出来。
[0113]
(2)在上述编码器-解码器结构中，编码器由一维卷积层构成，解码器由注意力-指针网络构成。其中注意力机制用于计算给定当前状态的输入节点上的注意力。
[0114]
步骤三中所述的演员-评论家算法的实现步骤为：
[0115]
(1)初始化相关各参数；
[0116]
(2)根据当前策略函数从当前状态空间中选择一个动作；
[0117]
(3)执行该动作，并得到一个即时奖励；
[0118]
(4)根据该即时奖励计算出执行该动作得到的总奖励；
[0119]
(5)根据这个奖励值以及相关的学习率等参数，对策略函数和价值函数的相关参数进行更新；
[0120]
(6)更新折扣率和当前状态；
[0121]
(7)重复上述流程，直到当前状态执行结束，开始新的一轮循环；
[0122]
(8)直到策略函数收敛，输出该策略函数；
[0123]
(9)这个策略函数即为当前最佳动作选择方案。
[0124]
图2所示为取送货问题示意图，分别用矩形和圆形代表取货点和送货点。外卖配送路径规划问题即可建模为带时间窗的取送货问题(pdptw)，它是一种组合优化问题。假设取货点与送货点两两配对，且必须先访问取货点，为了使规划路径合法，需要进行合理的订单顺序安排，且在订单时间窗的限制范围之内，骑手需要满足送货点的需求。
[0125]
假定在一个城市中，有若干外卖配送中心，每个配送中心内有一定数量的外卖配送人员，且每个中心只负责一定区域范围内的订单。现假定有一区域，当前所有的送餐点与
取餐点均位于此区域内，在某一时刻，该区域内产生了若干的订单(每个订单都有一对配对的取餐点和送餐点，且必须先到取餐点满足该节点的负需求，之后才能到达送餐点满足其正需求，完成订单，如示意图2 中a、b、c、d四个任务完成流程)，这些订单均需在一定的时间窗口内完成，则系统将这些订单按一定的规则分给各配送员，并在配送总成本最小的前提下，为每个配送员做路径规划。配送员按合理的顺序依次访问所有节点后，配送员返回配送中心，如示意图2中所示。
[0126]
假定模型中骑手的速度均匀，所有骑手速度相同，骑手取餐时到店便能取餐，送餐时到达送餐点外卖便会被取走，即取送餐均没有等待时间。假定所有骑手所能携带的外卖数量上限相同，所能行驶的最远距离相同，行驶单位距离花费的总成本相同，且骑手在每个取餐点取走的外卖只能送到对应的送货点。假定骑手剩余可行驶距离不足以访问下一个节点并返回配送中心，则直接返回配送中心，下一个骑手随即出发，并继承前者未完成的任务。
[0127]
该模型以1
×
1的坐标图和数值坐标来代替实际的地图和地理位置，以坐标图中的点代替实际中的取餐地址和送餐地址，以简化计算量和工作量，坐标地图中忽略实际地形中的各种限制，认为在任意两点之间均可以以最短的直线距离行进。即可认为，本模型更关注各节点访问顺序的问题，由一个给定的坐标点序列，给出一个对应的坐标点访问顺序序列。
[0128]
由于现实场景下较难收集大量数据构建数据集，故演示中的数据集通过程序随机生成，可以证明，在随机生成的数据集上进行训练，泛化能力更强。
[0129]
本发明的效果可以通过以下仿真实验进一步说明：
[0130]
1、实验条件：
[0131]
在intel(r)core(tm)i7-11400h cpu，16g运行内存,windows 11系统上使用python3.9.7进行仿真。
[0132]
2、实验内容：
[0133]
随机生成大量节点坐标数据，构建数据集，分为训练集、验证集和测试集，反复训练网络以求令规划路径距离最小的网络参数，可在验证集上观察训练过程中的网络的效果，在测试集上展示网络最终完成训练后的效果，具体流程如下：
[0134]
首先设置初始参数，对规模为10节点/20骑手最大负载的问题进行测试。初始参数中，订单时间窗指的是完成所有订单的最大时间限制，单个节点最大需求代表一个节点随机生成的需求份数的最大值，是否生成新的测试集是指是否使用不同于上一次模拟、新生成的节点数据集进行路线规划，训练次数是指对神经网络进行多少次训练，训练次数越大效果越好，但消耗的时间也越长，若训练次数等于0，则默认读取已经训练好的网络参数直接进行路径规划。
[0135]
确认模型参数后，点击开始随机模拟，若训练次数不等于0，则会先对网络进行设定次数的训练，截取其中一次的训练过程如图3所示，其中reward值表示在1
×
1的平面图中的原始移动路程。待全部训练完成后，系统会将效果最好的网络参数保存在相应的文件夹中，下次使用系统时即可将训练次数设置为 0，直接使用训练好的参数。
[0136]
网络参数训练和加载完毕后，系统将自动在测试集上随机选取数据进行路径规划展示效果，10节点/20骑手最大负载在测试集上的的路径规划结果演示如图4所示。
[0137]
为了检测算法和程序的健壮性，进一步扩大外卖配送问题的规模。重新运行程序，
将节点数目选择为20，此时骑手的最大携带量变为30份，按照上述流程重新进行测试。
[0138]
与10节点/20骑手最大负载同理，20节点/30骑手最大负载在测试集上的路径规划结果演示如图5所示。
[0139]
3、实验结果
[0140]
(1)在相同的条件下，采用本发明中已经训练好的演员网络，与现有的以最小路径为优化目标的算法(以蚁算法、模拟退火算法、遗传算法为例)均在相同的多组给定节点序列上进行运算，求解在给定的10/20个节点序列上的路径规划以及多次规划的平均行程距离，结果如图6所示，由图可知，不论是在10节点的情况下，还是在20节点的情况下，深度强化学习的规划结果的平均行程距离都是最小的，亦即相对于其它几种算法，其效果最好；
[0141]
(2)结果图中的星号标志代表配送中心，sn指向的是send送货点，cn指向carry取货点，取货点和送货点两两配对，即必须先到取货点取得外卖，才能去对应的送货点送货，且二者的需求绝对值相同，符号相反，如送货点有5份外卖(i5)的需求，则可在对应的取货点取走这5份外卖(-5)(需确保骑手此时可携带数量大于节点需求绝对值)。骑手均从配送中心出发，若一个骑手在配送中可行驶距离不足，则返回配送中心，下一个骑手随即以最大可行驶距离出发，且继承上一个骑手携带的货物。
[0142]
骑手的出发顺序如右上角的标注所示，0对应颜的线条即为第一个骑手的行驶路线，之后的1、2
……
依次对应2号骑手、三号骑手
……
[0143]
所有骑手的各项参数如平均速度、可携带外卖数量均相同，系统追求的目标是所有骑手的行驶的距离的总和尽可能的小。
[0144]
当所有节点的需求均被满足，任务完成，路径规划结束。由图中展示的数据可知，在10节点的情况下，所有规划路径的平均行程距离为8.06km(在1： 2000m的平面图中)，在20节点的情况下，所有规划路径的平均行程距离为 11.75km，均满足了订单时间窗的要求。
[0145]
如展示图3所示，在多次的迭代过程中，神经网络的loss值基本维持稳定且趋近于零，说明在反复的训练过程中，网络已经明显趋于收敛，由于神经网络的参数可以保存和读取，训练完毕后，该模型便可反复和快速的进行使用。观察训练好的神经网络给出的10/20节点结果路径图，符合直观的感觉，没有多余的轨迹，说明该模型的最终效果较好，i中的结论也说明了这一点。
[0146]
即便单个骑手平均行驶路径只有微小的减少，也能带来总成本的极大减少，以及用户平均等待时间的减少，这对于提高用户的满意度，增加骑手的收益，减少公司的成本，都是有益的。
[0147]
在本说明书的描述中，参考术语“一个实施例”、“示例”、“具体示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
[0148]
以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。

技术特征：

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配对；d
ij
：节点i,j∈n之间的距离；c
k
：骑手k的行驶单位距离总成本；v
k
：骑手k的平均行驶速度；q
i
：节点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时经历的时间；然后明确模型假设：所有骑手的平均速度、最远行驶距离、最大携带数量、单位距离花费均相同：v
k
＝v,(v，s，q，c为定值)；骑手位于配送中心时间为0，行走距离为0：假定骑手在每个节点都只取/送一份外卖：(i∈d时取-1)；所有订单的时间窗相同：(t为一个定值)；接着完善模型约束：保证每个订单都被唯一一位骑手取餐：保证取餐后有对应的送餐：保证先取餐再送餐：保证订单与骑手的匹配关系：骑手携带外卖最大份数约束：订单时间窗口约束：
骑手最大行驶距离约束：骑手携带外卖数量平衡约束：路径平衡约束：时间平衡约束：路径时间约束：最后确定总优化目标：7.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤二中所述搭建的基本神经网络的相关结构如下：选定了编码器-解码器作为基础架构，并引入了使用注意力机制的指针网络，用于完成传统方法中seq2seq的过程，其中指针网络在数学上的描述如下所示：学上的描述如下所示：式中，e
j
是编码器encoder在时间序列j次的隐藏层输出，d
i
是解码器decoder在时间序列i次的隐藏状态输出；所述编码器-解码器结构中，编码器由一维卷积层构成，解码器由注意力-指针网络构成，其中，注意力机制用于计算给定当前状态的输入节点上的注意力。8.根据权利要求1所述的一种基于深度强化学习的外卖配送路径规划方法，其特征在于，所述步骤三中所述的演员-评论家算法的实现步骤为：步骤一：初始化相关各参数；步骤二：根据当前策略函数从当前状态空间中选择一个动作；步骤三：执行该动作，并得到一个即时奖励；步骤四：根据该即时奖励计算出执行该动作得到的总奖励；步骤五：根据这个奖励值以及相关的学习率等参数，对策略函数和价值函数的相关参数进行更新；步骤六：更新折扣率和当前状态；步骤七：重复上述流程，直到当前状态执行结束，开始新的一轮循环；步骤八：直到策略函数收敛，输出该策略函数；步骤九：这个策略函数即为当前最佳动作选择方案。

技术总结

本发明公开了路径规划技术领域的一种基于深度强化学习的外卖配送路径规划方法，所述规划方法包括以下步骤：步骤一：读取问题输入的信息，定义优化目标，设定约束条件；步骤二：搭建编码器-解码器架构中的基础神经网络；步骤三：构建演员和评论家网络；步骤四：设定网络训练过程参数；步骤五：构建数据集；步骤六：演员网络和评论家网络的前向传递；步骤七：网络的训练与更新；步骤八：终止判断。本发明具有求解速度快、泛化能力强的优点，有着更好的适应能力和发展前景，能够对更加复杂的问题进行模拟和求解，引入注意力-指针网络结构加快了算法收敛的速度，已训练好的网络参数可以保存，不需要每次重新进行大量的运算。不需要每次重新进行大量的运算。不需要每次重新进行大量的运算。