异构多无人机协同取送货路径优化方法、装置及设备

1.本技术涉及数据处理技术领域，特别是涉及一种异构多无人机协同取送货路径优化方法、装置及设备。


背景技术：

2.随着移动电子商务、在线支付和新零售的普及，人们的购物和消费习惯出现了翻天覆地的变化。依靠大数据、5g和人工智能等技术，在线购物的实效性、便利度、性价比不断提升，依托大数据实现“私人订制”的购物平台为消费者提供商品辅助选择的功能，虚拟现实技术依托高速互联网，令消费者能够在线上体验更接近于线下的消费体验，这使得消费者在线购物的欲望增强了。
3.然而，伴随着巨大的交易额，“退货退款”这一热潮也登上了各大热搜榜单。退换货中涉及的逆向物流需要强大的物流系统支持，实行逆向物流有助于社会经济的可持续发展，同时也能为企业带来明显的经济效益，强化企业的竞争优势。然而大多数企业将正向物流配送和逆向物流回收看成两个独立的系统进行运作，造成了各种资源的严重浪费，因此行业对整合正逆向物流的需求愈发增长。
4.目前主流的无人机配送模式分为两类：第一类由单一无人机独立完成配送任务，将包裹由仓库送至客户处，这种交付模式能够有效缓解人工配送的压力，同时由于无人机的控制便捷性与飞行灵活性的优势，无人机交付几乎不受地面交通条件的限制，因此在拥挤的车流高峰期，也可以为“最后一公里”配送带来更优的服务质量；第二类将卡车配送与无人机配送相结合，实行卡车与无人机的联合运输，这种交付模式下，借助卡车的高运载能力与极长的巡航里程，无人机的交付半径得到了大幅提升。
5.但这两类无人机配送模式都存在一定的限制与不足。第一类配送模式下，由单一无人机独立完成配送任务时，由于配送的距离因素，单一无人机的配送将受到无人机硬件条件的限制，其中包括最大飞行距离，最大负载能力，电力限制等。因此单一无人机独立完成配送时，能够覆盖的服务范围将受到货物仓库和无人机硬件的严格限制。
6.而第二类配送模式下，由卡车与无人机相结合，进行联合运输时，卡车作为传统末端物流配送中的重要工具，其局限性将对整个配送系统的效率形成制约。当无人机从运动中的卡车起飞时，这将包含潜在的安全隐患；而无人机若在卡车停稳后起飞，则为卡车安排适当的停车位将成为一项难题。此外，卡车在地面沿着路网行进，受到路网的约束，难以沿最短路线向目的地前进，同时沿路网运行还意味着卡车将会受到地面交通条件的限制，在车流高峰期或某些特殊情况下，卡车的运行将会受阻。此外卡车的高能耗和高污染也不符合资源节约与绿色环保的趋势。因此在卡车与无人机结合进行联合运输时，卡车的运行效率将会形成短板效应，制约配送系统的全局运行效率，限制配送系统的时效性。


技术实现要素：

7.基于此，有必要针对上述技术问题，提供一种由多种类无人机共同配合，能够提升
物流时效性，整合正逆向物流的异构多无人机协同取送货路径优化方法、装置及设备。
8.一种异构多无人机协同取送货路径优化方法，所述方法包括：
9.构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务；
10.基于所述支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分所述支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径；
11.对所述无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对所述无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。
12.其中一个实施例中，构建无人机路线规划模型，包括：
13.考虑支线无人机最短航程、末端无人机最短航程及时效性评估，并根据所述支线无人机最短航程、所述末端无人机最短航程及所述时效性评估构建无人机路线规划模型。
14.其中一个实施例中，支线无人机最短航程的目标函数表示为：
[0015][0016]
末端无人机最短航程的目标函数表示为：
[0017][0018]
时效性评估的函数表达式为：
[0019][0020]
式中，ff表示支线无人机的总飞行距离，fe表示末端无人机的总飞行距离，i、j表示客户节点，d
ij
表示客户节点i到客户节点j之间的距离，为变量，表示ij段是否被支线无人机访问；k＝1,2,3,...,k，k表示末端无人机的数量，为变量，表示ij段是否被第k架末端无人机访问；cf表示各个客户节点的平均时效，ci表示每个客户节点的时效。
[0021]
其中一个实施例中，根据所述支线无人机最短航程、所述末端无人机最短航程及所述时效性评估构建无人机路线规划模型，包括：
[0022]
根据述支线无人机最短航程、所述末端无人机最短航程及所述时效性评估，构建平均时效性最优以及无人机飞行总里程最短的无人机路线规划模型，其函数表达式为：
[0023][0024]
式中，f表示优化的总体目标函数，k1、k2分别表示无人机总距离、无人机取送货时效性的归一化系数。
[0025]
其中一个实施例中，基于所述支线无人机物流配送任务，采用贪婪算法生成支线
无人机初始路径，并根据最大化成本节约策略，将部分所述支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径，包括：
[0026]
支线无人机从仓库出发，遍历全部客户节点，找到距离当前客户节点最近的客户节点，将寻得的最近客户节点连接在当前路径的末端，然后更新当前客户节点，得到支线无人机初始路径；
[0027]
将当前客户节点的支线无人机转换为末端无人机进行配送，根据最大化成本节约策略，如果节约成本大于0，则接受该修改，将该客户节点的支线无人机替换为末端无人机，最终得到无人机初始路径。
[0028]
其中一个实施例中，对所述无人机初始路径进行领域结构优化，包括：
[0029]
考虑所述无人机初始路径中，客户节点在支线无人机与末端无人机配送中的变化，通过位移算子、交换算子及切换算子三种领域结构进行优化。
[0030]
其中一个实施例中，通过metropolis准则及禁忌搜索算法对所述无人机初始路径进行调整，得到优化后的支线无人机及末端无人机配送路径，包括：
[0031]
通过领域结构优化所述无人机初始路径，并通过metropolis准则在搜索过程中以一定概率接受较差的无人机路径解，接受概率的表达式为：
[0032][0033]
式中，t表示当前退火温度，f(s
*
)表示新的无人机路径解，f(s)表示当前无人机路径解；
[0034]
并根据所述禁忌搜索算法得到无人机路径的最优解，通过所述无人机路径的最优解对所述无人机初始路径进行更新，得到优化后的异构多无人机物流配送路径。
[0035]
一种异构多无人机协同取送货路径优化装置，所述装置包括：
[0036]
模型构建模块，构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务；
[0037]
初始路径生成模块，基于所述支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分所述支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径；
[0038]
优化路径生成模块，对所述无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对所述无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。
[0039]
一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现上述权利要求任一项所述方法的步骤。
[0040]
上述异构多无人机协同取送货路径优化方法、装置及设备，首先构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时
效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务；基于支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径；对无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。
[0041]
本发明在规划无人机物流配送路径时，首先在构建无人机路线规划模型上，综合考虑了取货客户节点及送货客户节点两种情况，整合了正逆向物流，并引入了时效性这一参数来衡量配送产生的额外成本，采用贪婪算法能够更高效的得到当前情况下的近似最优解，生成无人机初始路径；再通过领域结构对当前情况下的近似最优解进行搜索；在搜索过程中，通过metropolis准则避免过早陷入局部最优解，更有利于到达全局最优解，引入禁忌搜索算法避免迂回搜索，提高搜索过程效率。本发明的方法整合了正逆向物流，考虑了时效性产生的额外成本，通过多种类无人机共同配合提高灵活性，克服了地面交通条件限制的问题，在提高客户满意度的同时，降低物流配送成本；且不再使用动态规划，在进行路径规划时，当无人机路径计算规模增加时，整体的计算量增加并不明显，适用性更广泛。
附图说明
[0042]
图1为一个实施例中异构多无人机协同取送货路径优化方法的流程示意图；
[0043]
图2为一个实施例中根据最大化成本节约策略更新的初始无人机路径示意图；
[0044]
图3为一个实施例中位移算子示意图示意图；
[0045]
图4为一个实施例中交换算子示意图示意图；
[0046]
图5为一个实施例中切换算子示意图，其中，(a)为切换后将客户节点放入现有无人机路径中示意图，(b)为切换后将客户节点放入新的无人机路径中示意图；
[0047]
图6为一个实施例中实验分析中各算法的优劣比较示意图；
[0048]
图7为一个实施例中实验分析中各算法耗时比较结果展示图；
[0049]
图8为一个实施例中与其他异构多无人机物流配送算法运行结果比较示意图；
[0050]
图9为一个实施例中与其他异构多无人机物流配送算法求解耗时比较示意图；
[0051]
图10为一个实施例中异构多无人机协同取送货路径优化装置的结构框图；
[0052]
图11为一个实施例中计算机设备的内部结构图。
具体实施方式
[0053]
为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
[0054]
值得说明的是，本发明将客户节点分为取货客户节点和送货客户节点两种，目的在于，通过合理规划支线无人机(f-uav)和末端无人机(e-uav)这两类无人机的配送路径，使得在完成全部客户节点的任务后，全部无人机的飞行总里程最短，客户满意度最高。
[0055]
因此，为简化问题描述，在构建无人机路线规划模型时，忽略其他次要因素，对无人机路线规划模型模型做以下假设：
[0056]
1.由p架支线无人机(f-uav)和k架末端无人机(e-uav)完成配送。
[0057]
2.每个客户点只能被一架无人机服务一次，每个客户点的需求都可以被无人机一次完成。
[0058]
3.所有的客户节点都需要被服务。
[0059]
4.支线无人机(f-uav)的最大载重量大于末端无人机(e-uav)。
[0060]
5.支线无人机(f-uav)完成全部任务后必须返回起飞点(仓库)，末端无人机(e-uav)完成任务后返回仓库。
[0061]
6.末端无人机(e-uav)只能在支线无人机(f-uav)位于客户节点上空时起飞，在仓库降落。
[0062]
7.支线无人机(f-uav)装载的包裹总重量不超过其最大载重量m。
[0063]
8.末端无人机(e-uav)装载的包裹总数量不超过其最大运载数量n。
[0064]
9.全部末端无人机(e-uav)型号相同。
[0065]
同时，为了简化描述，本发明提出的异构多无人机协同取送货路径优化方法将其命名为sa-tl。
[0066]
在一个实施例中，如图1所示，提供了一种异构多无人机协同取送货路径优化方法，包括以下步骤：
[0067]
步骤102，构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务。
[0068]
可以理解，为了整合正逆向物流，引入了取货任务和送货任务并存的条件；同时针对末端物流对时效的需要，引入时间窗约束，最终构建考虑时间窗的异构多无人机协同取送货问题模型。
[0069]
在考虑时间窗的异构多无人机协同取送货问题时可以用图g＝{v,a}定义。其中，v＝{1,2......,n}为配送区域内所有客户节点、仓库和无人机自动机场的集合，a为弧集合，每段弧{(i,j)|i,j∈v,i≠j}都有其长度。定义v1为支线无人机所配送的客户节点的集合，v2为e-uav所配送的客户节点的集合，其中，值得说明的是，还规定了客户节点的包裹重量m＞0时为送货节点，m＜0时为取货节点。无人机自动机场是协助无人机作业的地面自动化设施，可以取代人工操作干预，降低无人机物流配送中对人工的依赖，无人机自动机场可以部署在特定区域，e-uav完成配送任务后，无人机自动降落于自动机场内，在自动机场中，无人机可进行充电等整备工作，为后续的配送任务做好准备。
[0070]
因此，在构建无人机路线规划模型时，考虑支线无人机最短航程、末端无人机最短航程及时效性评估。其中，支线无人机需要服务全部超出末端无人机载重上限的客户节点，并在节点附近空域放飞末端无人机进行配送，支线无人机最短航程的目标函数表示为：
[0071][0072]
支线无人机最短航程的路径优化约束条件为：
[0073][0074][0075][0076][0077][0078][0079]
式中，式中，ff表示支线无人机的总飞行距离，i、j表示客户节点，d
ij
表示客户节点i到客户节点j之间的距离，为变量，表示ij段是否被支线无人机访问，其取值为0-1，当取值为1时表示被访问，取值为0时表示未被访问，q表示客户节点集合的非空真子集，ti表示到达客户节点i的时刻，wi表示在客户节点i完成任务所需时间，t
ij
表示支线无人机从客户节点i到客户节点j所需的时间，p表示支线无人机数量，df表示支线无人机最大航程。
[0080]
其中，(1.2)、(1.3)式表示支线无人机至多只能访问每个客户节点一次，(1.4)式表示对于每个任务，前序任务的数量等于后续任务的数量，(1.5)式表示在支线无人机的路径优化中没有回路产生，(1.6)表示配送中的时间约束，(1.7)表示支线无人机的最大航程约束。
[0081]
末端无人机将从支线无人机中起飞，携带包裹完成剩余客户节点的配送任务，并在完成任务后，返回支线无人机。末端无人机最短航程的目标函数表示为：
[0082][0083]
末端无人机最短航程的路径优化约束条件为：
[0084][0085][0086]
[0087][0088][0089][0090]
式中，k＝1,2,3,...,k，k表示末端无人机的数量，m
ij
表示从客户节点i到客户节点j所需配送的包裹质量，t
ik
表示第k架末端无人机到达客户节点i的时刻，wi表示在客户节点i完成任务所需时间，t
ijk
表示第k架末端无人机从客户节点i到客户节点j所需的时间，de末端无人机最大航程，d
ij
表示客户节点i到客户节点j之间的距离，为变量，表示ij段是否被第k架末端无人机访问，其取值为0-1，当取值为1时表示被访问，取值为0时表示未被访问。
[0091]
其中(2.2)式表示每个客户节点仅能被配送一次；(2.3)式表示末端无人机到达客户节点i后，必须离开该节点；(2.4)式表示末端无人机的总载重不能超过其最大载重；(2.5)式表示末端无人机装载的包裹总数量不超过其最大运载数量；(2.6)表示末端无人机服务的时间需求；(2.7)表示末端无人机的航程约束。
[0092]
时效性评估是指无人机在取货或者送货时，是否准时的标准的参数，通过该参数来衡量配送时产生的额外成本。时效性评估的函数表达式为：
[0093][0094][0095]
式中，cf表示各个客户节点的平均时效，ci表示每个客户节点的时效，t表示无人机服务的时刻，t
i0
表示客户节点i的预定服务时刻，ti表示客户节点i延误时限，ki表示客户节点i时效性衰减系数，该系数由客户最大可忍耐的服务延误所决定。
[0096]
根据上述支线无人机最短航程目标函数、末端无人机最短航程的目标函数及时效性评估函数，来构建平均时效性最优以及无人机飞行总里程最短的无人机路线规划模型，其函数表达式为：
[0097]
[0098]
式中，f表示优化的总体目标函数，k1、k2分别表示无人机总距离、无人机取送货时效性的归一化系数。该表达式中，采用倒数使二者均向极大值方向优化。
[0099]
步骤104，基于支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径。
[0100]
可以理解，这里得到的无人机初始路径生成是基于“支线无人机优先，末端无人机其次”的策略设计的。因此，首先采用贪婪算法为支线无人机规划全部由支线无人机完成配送任务的路线，其次，采取最大化成本节约策略，依次判断哪些节点被替换为末端无人机配送节点能够节约成本，最终得到替换后的结果作为初始解。
[0101]
具体地，支线无人机从仓库出发，遍历全部客户节点，找到距离当前客户节点最近的客户节点，将寻得到最近客户节点连接在当前路径的末端，然后更新当前客户节点，得到支线无人机初始路径。将当前客户节点的支线无人机转换为末端无人机配送，根据最大化成本节约策略，如果节约成本大于0，则接受该修改，将该节点的支线无人机替换为末端无人机，依照此方式，最终得到无人机初始路径。
[0102]
如图2所示，提供了最大化成本节约策略更新的初始无人机路径示意图，其中实线表示支线无人机路径，虚线表示末端无人机路径。
[0103]
步骤106，对无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。优化后的异构多无人机物流配送路径包括优化后的支线无人机物流配送路径及优化后的末端无人机物流配送路径。
[0104]
可以理解，由于考虑时效性的异构多无人机协同取送货路径优化问题呈现出极大的复杂性使用传统路径优化问题中的传统邻域结构会在优化中产生若干不可行解，这使得计算力被大量浪费，因此需要通过特地设计邻域结构以尽可能的确保解的可行性。因此，考虑到客户节点在e-uav与f-uav配送中变化的不同情况设计了三种算子来构成三种邻域结构。三种算子分别是位移算子、交换算子及切换算子。
[0105]
其中，如图3所示，位移算子将随机选择一个客户节点，将其移动到规划方案中的一个其他位置，在这一过程中，限制客户节点只能位移到同一类型的路线中，即服务客户节点的无人机类型不变。其中，当客户节点同时是f-uav放飞e-uav的节点时，移动客户节点的位置并不改变放飞关系。
[0106]
如图4所示，交换算子随机选取无人机飞行路线中的两个客户节点，交换其两者的访问顺序，同时需要检查无人机的载荷能力上限。
[0107]
如图5所示，切换算子与位移算子有相似之处，其主要区别在于，切换算子中，服务客户节点的无人机类型必须发生改变。切换算子将选择一个随机节点，改变服务它的无人机类型。当客户节点从支线无人机切换为末端无人机服务时，需要检查无人机的载荷能力上限，此时有两种情况：将该客户节点放入一个新的末端无人机路径中，或将该客户节点放入一个现有的末端无人机路径中。
[0108]
通过邻域结构对无人机初始路径进行优化后，以metropolis准则判定是否接受新解。通过metropolis准则在接受较差解中引入随机因素，能够避免算法过早地陷入局部最优，从而更有利于到达全局最优解。同时，引入禁忌列表，有利于避免陷入局部最优。
[0109]
具体地，将metropolis准则应用在搜索过程中，如果新的解比当前解差，则将以一定的概率接受，其概率为：
[0110][0111]
式中，t表示当前退火温度，f(s
*
)表示新的无人机路径解，f(s)表示当前无人机路径解。
[0112]
同时为了避免重复搜索，提高寻优效率，采用禁忌搜索算法中的禁忌表来改善搜索过程的效率。在执行领域结构搜索时，禁忌表会记录邻域变化情况并在未来的移动中禁止该操作，禁忌长度的定义使得禁忌表仅禁止在禁忌长度内发生过的移动，而“特赦准则”则在算法探寻产生全局最优时，能够暂时忽视禁忌列表，以获得最优解。通过引入禁忌表，执行领域结构搜索时能够记录并灵活选择优化中的动作，使搜索过程获得了“记忆”能力，有利于摆脱局部最优，防止重复搜索。
[0113]
具体地，建立一个禁忌表来记录移动的动作，当新的解被接受时，这一移动将被记录入禁忌列表，之后进行下一个移动，如果同样的动作发生在禁忌长度内，该移动动作就会被禁止，如果移动的动作能获得迄今为止最好的解，则使用“特赦准则”，从禁忌表中释放该全局最优解，允许使用该动作以更新最优解。通过无人机路径的最优解对无人机初始路径进行更新，得到优化后的异构多无人机物流配送路径。
[0114]
上述异构多无人机协同取送货路径优化方法、装置及设备，首先构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务；基于支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径；对无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。
[0115]
本发明在规划无人机物流配送路径时，首先在构建无人机路线规划模型上，综合考虑了取货客户节点及送货客户节点两种情况，整合了正逆向物流，并引入了时效性这一参数来衡量配送产生的额外成本，采用贪婪算法能够更高效的得到当前情况下的近似最优解，生成无人机初始路径；再通过领域结构对当前情况下的近似最优解进行搜索；在搜索过程中，通过metropolis准则避免过早陷入局部最优解，更有利于到达全局最优解，引入禁忌搜索算法避免迂回搜索，提高搜索过程效率。本发明的方法整合了正逆向物流，考虑了时效性产生的额外成本，通过多种类无人机共同配合提高灵活性，克服了地面交通条件限制的问题，在提高客户满意度的同时，降低物流配送成本；且不再使用动态规划，在进行路径规划时，当无人机路径计算规模增加时，整体的计算量增加并不明显，适用性更广泛。
[0116]
应该理解的是，虽然图1的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的
执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。
[0117]
在其中一个实施例中，通过计算机模拟实验，对本发明提出的sa-tl进行有效性验证。
[0118]
在20组计算机随机生成，客户节点的规模分别为30-125的算例上，将sa-tl算法与cplex求解器进行对比，并与其他解决同类问题的智能优化算法相比较。实验主要在一台asus pc下进行，其配置为amd ryzen 74800h with radeon graphics 2.9ghz，16.0g内存，算法采用python3.7编程实现。
[0119]
实验参数设置参照vrp-d问题设置，假定支线无人机的平均航行速度为70km/h，末端无人机的平均航行速度为40km/h，小型客户节点的包裹质量设置在(0.1，2.0)kg的区间范围内，支线无人机的数量为3架，每架支线无人机搭载末端无人机的数量为6架。
[0120]
实验仿真场景为一个100公里
×
100公里的正方形区域，客户节点随机分布在实验仿真场景中，以计算机随机生成。
[0121]
设计了4种启发式算法作为对比算法，即大规模邻域搜索算法(large neighborhood search,lns)、禁忌搜索算法(tabu search，ts)、模拟退火算法(simulated annealing algorithm，sa)以及贪婪算法，并以cplex求解器中的精确算法作为标准对不同算法的结果进行衡量。其中，贪婪算法以及求解器是确定性算法，只需运行一次进行求解，其余算法是随机性算法，在求解时，各运行25次取其平均值。由计算机随机生成9组算例，其中客户节点的规模分别为30-70。
[0122]
为比较4种对比算法与sa-tl算法的解的差距，引入gap来描述算法与最优解之间的差距，通过以下公式计算：
[0123][0124]
式中，si表示由算法i所找到的满意解，i代表greed，ts，sa，lns以及sa-tl这5种算法中的一种，s
cplex
表示由cplex求得的最优解。计算结果如表1及图6所示，观察图表发现，相比于传统的启发式算法，sa-tl算法在求解相对较大的算例时具有结果上的优势。此外，值得注意的是，gap随着任务规模的增加而增加，当任务规模较小时，sa-tl所得到的结果与其他4种示例算法的结果非常接近，但在处理大规模任务时，其他算法的有效性迅速下降，其中由于greed算法采用了简单的贪婪策略，其与sa-tl算法的差距甚至达到了50％，总的来说，sa-tl在解决大规模问题时表现出明显的性能优势。
[0125]
观察表1及图6发现，在传统的启发式算法的比较中，lns算法优于其他几类，但与sa-tl相比，仍有一定差距。lns算法采用破坏和修复算子来跳出局部最优解，而sa-tl同样在马尔科夫链中设计了多种邻域结构来防止陷入局部最优，两者具备一定的相似度，但由于sa-tl引入了禁忌列表，通过避免迂回搜索，提升了算法的勘探效率。
[0126]
表1算法性能比较结果表
tl算法运行时间并未产生明显的变化趋势，而相比之下，三阶段迭代优化算法的运行耗时出现了骤增。这是由于三阶段迭代优化算法中，对于末端无人机路径进行优化时，采用了动态规划(dp)这一精确算法。在末端无人机配送节点较少，飞行路线复杂度较低时，采用精确算法进行求解有助于改善解的精度，但当末端无人机配送能力增加，且考虑到时间窗和取送货共存后，承担配送任务的复杂度随之上升的情况下，采用动态规划解决末端配送将消耗大量的运算时间，这对于算法的时效性非常不利，甚至当复杂度过高时，动态规划在能够接受的时间内无法得到结果。
[0135]
因此，在无人机装载能力较强，或末端物流情况节点多，条件复杂的情况下，本发明的sa-tl算法能够在短时间内产生与三阶段迭代优化算法结果相近的满意解。
[0136]
因此，从上述实验验证，可以看出，本发明提供的sa-tl算法具有一定的优越性、适用性及可行性，实用价值较高。
[0137]
在一个实施例中，如图10所示，提供了一种异构多无人机协同取送货路径优化装置，包括：模型构建模块、初始路径生成模块及优化路径生成模块，其中：
[0138]
模型构建模块，构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务。
[0139]
初始路径生成模块，基于支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径。
[0140]
优化路径生成模块，对无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。
[0141]
关于异构多无人机协同取送货路径优化装置的具体限定可以参见上文中对于异构多无人机协同取送货路径优化方法的限定，在此不再赘述。上述异构多无人机协同取送货路径优化装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。
[0142]
在一个实施例中，提供了一种计算机设备，该计算机设备可以是服务器，其内部结构图可以如图11所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口和数据库。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统、计算机程序和数据库。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的数据库用于存储异构多无人机协同取送货路径优化数据。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种异构多无人机协同取送货路径优化方法。
[0143]
本领域技术人员可以理解，图11中示出的结构，仅仅是与本技术方案相关的部分结构的框图，并不构成对本技术方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。
[0144]
在一个实施例中，提供了一种计算机设备，包括存储器和处理器，该存储器存储有计算机程序，该处理器执行计算机程序时实现以下步骤：
[0145]
步骤102，构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务。
[0146]
步骤104，基于支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径。
[0147]
步骤106，对无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。优化后的异构多无人机物流配送路径包括优化后的支线无人机物流配送路径及优化后的末端无人机物流配送路径。
[0148]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(rom)、可编程rom(prom)、电可编程rom(eprom)、电可擦除可编程rom(eeprom)或闪存。易失性存储器可包括随机存取存储器(ram)或者外部高速缓冲存储器。作为说明而非局限，ram以多种形式可得，诸如静态ram(sram)、动态ram(dram)、同步dram(sdram)、双数据率sdram(ddrsdram)、增强型sdram(esdram)、同步链路(synchlink)dram(sldram)、存储器总线(rambus)直接ram(rdram)、直接存储器总线动态ram(drdram)、以及存储器总线动态ram(rdram)等。
[0149]
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0150]
以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本发明范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术的保护范围应以所附权利要求为准。

技术特征：
1.一种异构多无人机协同取送货路径优化方法，其特征在于，所述方法包括：构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务；基于所述支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分所述支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径；对所述无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对所述无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。2.根据权利要求1所述的异构多无人机协同取送货路径优化方法，其特征在于，构建无人机路线规划模型，包括：考虑支线无人机最短航程、末端无人机最短航程及时效性评估，并根据所述支线无人机最短航程、所述末端无人机最短航程及所述时效性评估构建无人机路线规划模型。3.根据权利要求2所述的异构多无人机协同取送货路径优化方法，其特征在于，支线无人机最短航程的目标函数表示为：末端无人机最短航程的目标函数表示为：时效性评估的函数表达式为：式中，f
f
表示支线无人机的总飞行距离，f
e
表示末端无人机的总飞行距离，i、j表示客户节点，d
ij
表示客户节点i到客户节点j之间的距离，为变量，表示ij段是否被支线无人机访问；k＝1,2,3,...,k，k表示末端无人机的数量，为变量，表示ij段是否被第k架末端无人机访问；c
f
表示各个客户节点的平均时效，c
i
表示每个客户节点的时效。4.根据权利要求3所述的异构多无人机协同取送货路径优化方法，其特征在于，根据所述支线无人机最短航程、所述末端无人机最短航程及所述时效性评估构建无人机路线规划模型，包括：根据述支线无人机最短航程、所述末端无人机最短航程及所述时效性评估，构建平均时效性最优以及无人机飞行总里程最短的无人机路线规划模型，其函数表达式为：
式中，f表示优化的总体目标函数，k1、k2分别表示无人机总距离、无人机取送货时效性的归一化系数。5.根据权利要求1至4任一项所述的异构多无人机协同取送货路径优化方法，其特征在于，基于所述支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分所述支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径，包括：支线无人机从仓库出发，遍历全部客户节点，找到距离当前客户节点最近的客户节点，将寻得的最近客户节点连接在当前路径的末端，然后更新当前客户节点，得到支线无人机初始路径；将当前客户节点的支线无人机转换为末端无人机进行配送，根据最大化成本节约策略，如果节约成本大于0，则接受该修改，将该客户节点的支线无人机替换为末端无人机，最终得到无人机初始路径。6.根据权利要求5所述的异构多无人机协同取送货路径优化方法，其特征在于，对所述无人机初始路径进行领域结构优化，包括：考虑所述无人机初始路径中，客户节点在支线无人机与末端无人机配送中的变化，通过位移算子、交换算子及切换算子三种领域结构进行优化。7.根据权利要求6所述的异构多无人机协同取送货路径优化方法，其特征在于，通过metropolis准则及禁忌搜索算法对所述无人机初始路径进行调整，得到优化后的支线无人机及末端无人机配送路径，包括：通过领域结构优化所述无人机初始路径，并通过metropolis准则在搜索过程中以一定概率接受较差的无人机路径解，接受概率的表达式为：式中，t表示当前退火温度，f(s
*
)表示新的无人机路径解，f(s)表示当前无人机路径解；并根据所述禁忌搜索算法得到无人机路径的最优解，通过所述无人机路径的最优解对所述无人机初始路径进行更新，得到优化后的异构多无人机物流配送路径。8.一种异构多无人机协同取送货路径优化装置，其特征在于，所述装置包括：模型构建模块，构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分，其中，异构多无人机物流配送任务包括支线无人机物流配送任务及末端无人机物流配送任务；初始路径生成模块，基于所述支线无人机物流配送任务，采用贪婪算法生成支线无人机初始路径，并根据最大化成本节约策略，将部分所述支线无人机初始路径中的配送节点替换为末端无人机的配送节点，得到无人机初始路径；优化路径生成模块，对所述无人机初始路径进行领域结构优化，并通过metropolis准则及禁忌搜索算法对所述无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。
9.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至7中任一项所述方法的步骤。

技术总结
本申请涉及异构多无人机协同取送货路径优化方法、装置及设备。通过构建无人机路线规划模型，并根据待配送客户节点信息、待取货客户节点信息、无人机信息、距离矩阵及时效性对异构多无人机物流配送任务进行划分；基于支线无人机物流配送任务，采用贪婪算法及最大化成本节约策略，得到无人机初始路径；对无人机初始路径进行领域结构优化，并通过Metropolis准则及禁忌搜索算法对无人机初始路径进行调整，得到优化后的异构多无人机物流配送路径。本发明整合了正逆向物流，考虑了时效性产生的额外成本，通过多种类无人机共同配合提高灵活性，在提高客户满意度的同时，降低物流配送成本。降低物流配送成本。降低物流配送成本。


技术研发人员：袁于斐 伍国华 周玲
受保护的技术使用者：中南大学
技术研发日：2023.05.24
技术公布日：2023/8/13