一种面向时变性需求的无人机末端配送路径规划方法

1.本发明涉及无人机物流技术领域，具体为一种面向时变性需求的无人机末端配送路径规划方法。


背景技术：

2.目前物流行业蓬勃发展，物流行业的总运输量和同比增长量逐年增加，物流行业运输压力大。传统的车辆运输受制于成本和配送路径限制，难以实现物流行业的需求。国内外物流企业开始寻求利用无人机作为物流末端配送的新方式。
3.无人机灵活方便，且单位距离飞行成本低，可以减少人力劳动，越来越多的企业和政府将其视为解决物流配送“最后一公里”问题的有效途径。在保证物流需求满足的前提下，合理规划无人机的送货路径，使得无人机的成本得到更有效的降低，是目前无人机物流配送路径规划的目标之一。
4.为解决上述问题，国内外利用精确式和启发式算法进行了求解，可以在静态小规模环境下得到一个较为理想的解。但实际中，可能需要求解的问题规模较大，且顾客需求可能会随着时间的改变而发生变化，而传统的解决方法未考虑这一问题，不能满足实际使用的需要。。


技术实现要素：

5.本发明的目的在于：提供一种面向时变性需求的无人机末端配送路径规划方法，以解决以上缺陷。
6.为了实现上述目的，本发明提供如下技术方案：
7.一种面向时变性需求的无人机末端配送路径规划方法，包括以下步骤：
8.s1、数据预处理阶段：对物流配送区域中的相关数据进行预处理，将配送点位置、顾客需求信息编码成向量形式，以便后续送入模型进行训练；
9.s2、构建模型阶段：基于s1步骤得到的编码信息，设计相应的状态空间、动作空间和状态回报函数，并基于此构建深度强化学习模型；
10.s3、模型训练阶段：基于s2步骤设计的状态空间state、动作空间action和状态回报函数reward，结合物流信息，进行深度强化学习的模型训练；
11.s4、无人机路径规划阶段：结合s3步骤训练好的模型，基于深度强化学习输出无人机的路径序列；
12.s5、无人机路径优化阶段：对s4步骤得到的路径序列，采用2-opt算法进行优化，若能得到更优解，则保留；否则保持原来的结果不变。
13.优选地，所述步骤s1，具体如下：收集物流配送区域内各个需求点的位置信息，即顾客需求点的经度和纬度坐标，以及顾客的具体需求信息，其中包括顾客的需求量及顾客希望取货的时间窗；将上述信息存入向量中，作为后续模型中编码器的输入；送入编码器的向量形式具体如下：
[0014][0015]
式中，xi,yi分别代表配送任务点i的纬度和经度坐标；代表配送任务点i在当前时间步si下的需求，随时间步更新；ei,ji分别代表配送任务点顾客服务的开始时间和结束时间，即(ei,ji)表示该需求点的时间窗；si代表当前时间步。
[0016]
优选地，在步骤s2中，构建的深度强化学习模型，采用encoder-decoder结构，即编码器-解码器结构，其中编码器encoder接收数据预处理阶段的编码信息，经过时间注意力机制编码时间信息，空间注意力机制编码空间信息后，输出至解码器decoder结构进行解码，decoder结构解码输出无人机末端物流配送的路径序列。
[0017]
优选地，所述编码器encoder，其结构编码的信息包括节点嵌入和图嵌入，代表节点嵌入，初始节点信息经过多头注意力机制编码成最终的经过多头注意力机制编码成最终的代表图嵌入，即为所有节点嵌入的平均值来代替。
[0018]
优选地，在步骤s3中，所述动作空间的设计，具体为：无人机选择去往哪一个配送任务点或保持原地不动，状态回报值函数则设计为无人机飞行距离的负值；所述动作空间为在每一个时间步t，无人机选择要服务的下一个配送任务点，其中先前服务过的则采用掩码的方式防止其再次被服务。
[0019]
优选地，在步骤s2中，所述状态空间，包括静态状态和动态状态；所述静态状态，包括：单位距离配送成本、配送任务点位置及未变化的顾客需求量；所述动态状态，即时变的顾客需求量。
[0020]
优选地，在步骤s3中，所述状态回报函数为r＝-distance
total
，随着训练过程中累积奖励的增加，无人机物流配送的总距离将逐渐降低。
[0021]
优选地，在步骤s3中，所述模型训练，采用基于策略的梯度下降算法进行，在每个训练周期结束时，进行t检验，当候选参数的成本显著降低时，基线参数才使用当前策略进行更新。
[0022]
优选地，在步骤s3的模型训练过程中，采用adam优化算法，其公式如下：
[0023][0024]
式中，l(π|s)是当前模型的损失，b(s)是基线损失
[0025]
优选地，所述步骤s5，具体如下：对s4步骤得到的路径序列，重复采用2-opt算法随机交换子路径的两个节点位置，检验交换后的结果是否比原来的路径更加优化；若是，则保留路径；若不是，则选择原来的路径。
[0026]
本发明的有益效果在于：
[0027]
本发明一种面向时变性需求的无人机末端配送路径规划方法，在路径规划过程中，同时将图信息和节点信息输入模型并编码，有效地利用了配送区域的环境信息，能够更加合理地规划无人机的路径，结合环境信息中的具体实例，减少无人机路径规划的不合理性；利用时间注意力机制和空间注意力机制分别提取时间和空间信息，解决实际应用中配送任务点需求发生变化的情况，同时利用需求随时间步的变化更新，能够实现无人机路径的实时规划；结合深度强化学习进行无人机的路径规划，相较于传统的使用精确式和启发
式算法的方法，有效地降低了计算求取时间，增加了求解过程中的鲁棒性，同时本发明提出的算法在训练后，对于大规模算例有较好的泛化性能，可以实现实时计算；在得到路径序列之后，通过2-opt算法进行路径优化，能够更有效地找到潜在的最优解，实现路径的更优化。本发明一种面向时变性需求的无人机末端配送路径规划方法，能够实现大规模环境下的理想求解，并随着顾客需求的临时改变而重新规划路线，路径规划时间短，效率高，精准度高，实时性好，同时能够有效降低运营成本。
附图说明
[0028]
图1：本发明方法流程图；
[0029]
图2：本发明中的2-opt算法流程图；
[0030]
图3：本发明中无人机末端配送的路径示意图。
具体实施方式
[0031]
以下结合实施例对本发明作进一步的说明，需要说明的是，仅仅是对本发明构思所作的举例和说明，所属本技术领域的技术人员对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，只要不偏离发明的构思或者超越本权利要求书所定义的范围，均应视为落入本发明的保护范围。
[0032]
实施例1：
[0033]
如图1-3所示，一种面向时变性需求的无人机末端配送路径规划方法，包括以下步骤：
[0034]
s1、数据预处理阶段：对物流配送区域中的相关数据进行预处理，将配送点位置、顾客需求信息编码成向量形式，以便后续送入模型进行训练，具体步骤如下：
[0035]
收集物流配送区域内各个需求点的位置信息，即顾客需求点的经度和纬度坐标，以及顾客的具体需求信息，其中包括顾客的需求量及顾客希望取货的时间窗；将上述信息存入向量中，作为后续模型中编码器的输入；送入编码器的向量形式具体如下：
[0036][0037]
式中，xi,yi分别代表配送任务点i的纬度和经度坐标；代表配送任务点i在当前时间步si下的需求，进一步地，随时间步更新；ei,ji分别代表配送任务点顾客服务的开始时间和结束时间，即(ei,ji)表示该需求点的时间窗；si代表当前时间步。
[0038]
s2、构建模型阶段：基于s1步骤得到的编码信息，设计相应的状态空间、动作空间和状态回报函数，并基于此构建深度强化学习模型。
[0039]
其中，构建的深度强化学习模型，采用encoder-decoder结构，即编码器-解码器结构，其中编码器encoder接收数据预处理阶段的编码信息，经过时间注意力机制编码时间信息，空间注意力机制编码空间信息后，输出至解码器decoder结构进行解码，decoder结构解码输出无人机末端物流配送的路径序列。
[0040]
其中，编码器encoder，其结构编码的信息包括节点嵌入和图嵌入，代表节点嵌入，初始节点信息被映射为一个128维的张量，经过多头注意
力机制编码成最终的力机制编码成最终的代表图嵌入，即为所有节点嵌入的平均值来代替。
[0041]
在编码器中设置多头注意力机制来捕捉更丰富的节点信息。经过多头注意力层之后，再通过全连接层基于激活函数获取更多信息，并输出至解码器中。初始节点的特征通过下面的公式得到：
[0042][0043]
式中，代表初始节点特征，w,b均为可以训练的参数，xi是配送任务节点的信息。
[0044]
然后，节点嵌入信息，进入到多头注意力机制层，每层包含一个多头注意力机制层和一个feedforward层即前馈层。为了防止训练过程中出现梯度爆炸，每一层还加入残差连接和正则化操作，其公式如下：
[0045][0046][0047]
式中，n代表head即头的个数，在实施例中选择n＝8，q、k、v分别是每个节点的query，key和value值，bn代表批量标准化，softmax为激活函数，dh为嵌入维度。
[0048]
由于考虑到时变需求，因此分别设置有两个多头注意力机制层，分别提取时间和空间信息，二者仅在输入上有所不同，其余的包括head头数和激活函数等均保持一致。
[0049]
每一层之后还有前馈层，即feedforward层，用于融合信息，接收多头注意力层传来的嵌入信息，并通过激活函数relu输出结果。
[0050]
对于解码层，其输入为上下文向量h＝[h
encoder
:h
last
]，而后在解码器中利用另一个mha(多头注意力)层处理h，通过计算节点嵌入和上下文向量之间的注意力值得到变换后的h'。其中，h
encoder
表示encoder结构传入的信息，h
last
代表上一个访问过的节点的隐藏层信息，包括上次访问节点、剩余容量、剩余电量和顾客需求时间窗的更新信息；[.:.]代表向量的连接操作，即对两个张量执行concatenation操作。上下文向量将每个时间步的静态和动态特征组合起来，并在下一个时间步进行更新，以记录顾客时变性需求。
[0051]
解码器根据概率分布输出具有最高概率的配送任务点，执行完成后将各个时间步概率最高的配送任务点按照顺序连接起来即为路径序列，其中概率分布为：
[0052][0053]
式中，π
1:t-1
代表之前已经完成的配送任务路径，在此基础上，使用基于注意力网络的编码器-解码器结构和策略梯度方法来学习带有参数向量的策略。解码器中掩码用于屏蔽不能被访问的节点及已经访问过的节点。不能访问的节点，包括：剩余容量无法满足顾客需求，剩余时间窗不在待配送任务时间窗内，及飞机由于电量消耗需要返回起飞点充电等。特别的是无人机起飞与降落节点将永远不会被屏蔽。
[0054]
与编码器类似，利用query、key和value计算节点的相似度，再经过一个softmax函数计算并输出最大概率。
[0055]
计算相似度公式和softmax函数公式具体如下：
[0056][0057][0058]
输出无人机路径序列其中表示第i个无人机要执行的第k个任务，无人机执行完所有任务后要返回无人机起飞点。
[0059]
s3、模型训练阶段：基于s2步骤设计的状态空间state、动作空间action和状态回报函数reward，结合物流信息，进行深度强化学习的模型训练。
[0060]
动作空间的设计，具体为：无人机选择去往哪一个配送任务点或保持原地不动，状态回报值函数则设计为无人机飞行距离的负值；所述动作空间为在每一个时间步t，无人机选择要服务的下一个配送任务点，其中先前服务过的则采用掩码的方式防止其再次被服务。
[0061]
状态空间，包括静态状态和动态状态；所述静态状态，包括：单位距离配送成本、配送任务点位置及未变化的顾客需求量；所述动态状态，即时变的顾客需求量。
[0062]
状态回报函数为r＝-distance
total
，随着训练过程中累积奖励的增加，无人机物流配送的总距离将逐渐降低。
[0063]
模型训练，采用基于策略的梯度下降算法进行，在每个训练周期结束时，进行t检验，当候选参数的成本显著降低时，基线参数才使用当前策略进行更新。
[0064]
其中，使用greedy rollout的策略来稳定baseline，增加baseline也可以减小训练方差，增加训练稳定性。
[0065]
在模型训练过程中，采用adam优化算法，其公式如下：
[0066][0067]
式中，l(π|s)是当前模型的损失，b(s)是基线损失
[0068]
s4、无人机路径规划阶段：结合s3步骤训练好的模型，基于深度强化学习输出无人机的路径序列。
[0069]
路径规划阶段输入图信息和节点信息，输出结果为带配送任务点的序列，无人机配送将按照序列的顺序执行。考虑时变性需求的无人机路径规划，在每一个时间步对待配送任务点的需求进行更新，解码器在解码过程中始终关注上一个时间步，将上一个时间步更新的信息作为上下文向量嵌入到下一个时间步的计算中，实现实时更新。
[0070]
s5、无人机路径优化阶段：对s4步骤得到的路径序列，重复采用2-opt算法随机交换子路径的两个节点位置，检验交换后的结果是否比原来的路径更加优化；若是，则保留路径；若不是，则选择原来的路径。具体步骤如下：
[0071]
s5.1、根据深度强化学习模型得到的路径，使用贪心算法找到某个无人机一条子路径记录在数组中，并记录下总路径长l1。
[0072]
s5.2、随机生成两个不同的随机数num1,num2(将其对应到路径中顶点的下标)，交换路径中num1,num2之间的路径，得到一条新路径并记录下路径总长l2。
[0073]
s5.3、比较新得到的路径总长与原来的路径总长，若新路径更短，则更新路径为新路径并将计数器置0，否则计数器加1。
[0074]
s5.4、重复步骤s5.2、s5.3，直到计数器达到最大循环次数n。
[0075]
图1为本发明方法流程图，图2为本发明中的2-opt算法流程图，图3为本发明中无人机末端配送的路径示意图。如图1、2、3所示，本发明一种面向时变性需求的无人机末端配送路径规划方法，在路径规划过程中，同时将图信息和节点信息输入模型并编码，有效地利用了配送区域的环境信息，能够更加合理地规划无人机的路径，结合环境信息中的具体实例，减少无人机路径规划的不合理性；利用时间注意力机制和空间注意力机制分别提取时间和空间信息，解决实际应用中配送任务点需求发生变化的情况，同时利用需求随时间步的变化更新，能够实现无人机路径的实时规划；结合深度强化学习进行无人机的路径规划，相较于传统的使用精确式和启发式算法的方法，有效地降低了计算求取时间，增加了求解过程中的鲁棒性，同时本发明提出的算法在训练后，对于大规模算例有较好的泛化性能，可以实现实时计算；在得到路径序列之后，通过2-opt算法进行路径优化，能够更有效地找到潜在的最优解，实现路径的更优化。
[0076]
本发明一种面向时变性需求的无人机末端配送路径规划方法，能够实现大规模环境下的理想求解，并随着顾客需求的临时改变而重新规划路线，路径规划时间短，效率高，精准度高，实时性好，同时能够有效降低运营成本。
[0077]
上述是对发明进行了示例性描述，显然本发明具体实现并不受上述方式的限制，只要采用了本发明的方法构思和技术方案进行的这种非实质改进，或未经改进将发明的构思和技术方案直接应用于其他场合的，均在本发明的保护范围之内。

技术特征：
1.一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，包括以下步骤：s1、数据预处理阶段：对物流配送区域中的相关数据进行预处理，将配送点位置、顾客需求信息编码成向量形式，以便后续送入模型进行训练；s2、构建模型阶段：基于s1步骤得到的编码信息，设计相应的状态空间、动作空间和状态回报函数，并基于此构建深度强化学习模型；s3、模型训练阶段：基于s2步骤设计的状态空间state、动作空间action和状态回报函数reward，结合物流信息，进行深度强化学习的模型训练；s4、无人机路径规划阶段：结合s3步骤训练好的模型，基于深度强化学习输出无人机的路径序列；s5、无人机路径优化阶段：对s4步骤得到的路径序列，采用2-opt算法进行优化，若能得到更优解，则保留；否则保持原来的结果不变。2.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，所述步骤s1，具体如下：收集物流配送区域内各个需求点的位置信息，即顾客需求点的经度和纬度坐标，以及顾客的具体需求信息，其中包括顾客的需求量及顾客希望取货的时间窗；将上述信息存入向量中，作为后续模型中编码器的输入；送入编码器的向量形式具体如下：式中，x
i
,y
i
分别代表配送任务点i的纬度和经度坐标；代表配送任务点i在当前时间步s
i
下的需求，随时间步更新；e
i
,j
i
分别代表配送任务点顾客服务的开始时间和结束时间，即(e
i
,j
i
)表示该需求点的时间窗；s
i
代表当前时间步。3.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，在步骤s2中，构建的深度强化学习模型，采用encoder-decoder结构，即编码器-解码器结构，其中编码器encoder接收数据预处理阶段的编码信息，经过时间注意力机制编码时间信息，空间注意力机制编码空间信息后，输出至解码器decoder结构进行解码，decoder结构解码输出无人机末端物流配送的路径序列。4.根据权利要求3所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，所述编码器encoder，其结构编码的信息包括节点嵌入和图嵌入，代表节点嵌入，初始节点信息经过多头注意力机制编码成最终的经过多头注意力机制编码成最终的代表图嵌入，即为所有节点嵌入的平均值来代替。5.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，在步骤s3中，所述动作空间的设计，具体为：无人机选择去往哪一个配送任务点或保持原地不动，状态回报值函数则设计为无人机飞行距离的负值；所述动作空间为在每一个时间步t，无人机选择要服务的下一个配送任务点，其中先前服务过的则采用掩码的方式防止其再次被服务。6.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，在步骤s2中，所述状态空间，包括静态状态和动态状态；所述静态状态，包括：单位
距离配送成本、配送任务点位置及未变化的顾客需求量；所述动态状态，即时变的顾客需求量。7.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，在步骤s3中，所述状态回报函数为r＝-distance
total
，随着训练过程中累积奖励的增加，无人机物流配送的总距离将逐渐降低。8.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，在步骤s3中，所述模型训练，采用基于策略的梯度下降算法进行，在每个训练周期结束时，进行t检验，当候选参数的成本显著降低时，基线参数才使用当前策略进行更新。9.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，在步骤s3的模型训练过程中，采用adam优化算法，其公式如下：式中，l(π|s)是当前模型的损失，b(s)是基线损失。10.根据权利要求1所述的一种面向时变性需求的无人机末端配送路径规划方法，其特征在于，所述步骤s5，具体如下：对s4步骤得到的路径序列，重复采用2-opt算法随机交换子路径的两个节点位置，检验交换后的结果是否比原来的路径更加优化；若是，则保留路径；若不是，则选择原来的路径。

技术总结
本发明公开了一种面向时变性需求的无人机末端配送路径规划方法，首先对物流配送区域及相关数据进行预处理，通过将配送点位置和需求等信息编码成向量形式送入模型计算；其次基于编码信息构建深度强化学习模型，同时考虑配送过程中时变性需求的信息提取及编码的特殊性，构建时间和空间注意力机制进行信息的实时提取；其次设计合理的动作动态及状态回报函数，结合进行深度强化学习模型的训练，对无人机末端配送进行路径规划；最后，利用2-opt算法对生成的子路径进行优化，得到更优解。本发明考虑配送中顾客需求的时变性，实现了无人机末端配送路径的实时规划，能够应用于较大规模的实例计算，具有较快的计算速度和较高的鲁棒性能，精准度高。精准度高。精准度高。


技术研发人员：姚宝珍 时彬 仲潜 崔贺淇 陈思轩
受保护的技术使用者：大连理工大学
技术研发日：2023.08.25
技术公布日：2023/10/15