一种基于覆盖偏移度及安全效用的无人机起降点规划方法

1.本发明涉及无人机起降点规划技术领域，尤其涉及一种基于覆盖偏移度及安全效用的无人机起降点规划方法。


背景技术：

2.随着我国低空空域的逐步开放，无人机相关管理条例的逐步完善，城市“最后一公里”配送方式出现变革，推动了城区物流无人机起降场点选址、布局、规划等一系列问题发展。物流无人机起降点选址规划作为物流配送的核心环节，对无人机配送系统的高效运行起着至关重要的作用。
3.目前，无人机物流配送逐渐成为了现实，成为一种缓解地面交通拥堵，提高城市居民生活质量的新方式。无人机起降场点布局规划作为未来大规模物流无人机运行的关键步骤以及城市低空航路网络精细划设的基础需要。然而，纵观国内外已有研究成果，现有无人机起降点规划研究考虑影响因素较为单一，忽视实际禁飞区限制，安全性考虑不充分；少数研究虽提出需求全覆盖等要求，但未考虑覆盖距离过大导致的配送效率低下，影响服务质量。因此，如何在确保无人机运输方式的可行性与安全性前提下，实现需求全覆盖、符合现实需求，科学规划物流无人机起降点数量及位置是建立物流无人机运输体系面临的重要问题。


技术实现要素：

4.本发明的目的在于针对上述现有技术的不足，本发明提供了一种基于覆盖偏移度及安全效用的无人机起降点规划方法，有效改善了物流运输过程中的安全效用，并以相对较小覆盖距离实现了对可行空域内需求点的全面覆盖，在保证安全的情况下较为均匀地使用各起降点，避免了起降点容量的过度闲置。
5.实现本发明的技术方案为：
6.一种基于覆盖偏移度及安全效用的无人机起降点规划方法，包括以下步骤：
7.步骤一：定义覆盖偏移度、安全效用；
8.步骤二：考虑多约束条件，从覆盖偏移度和安全效用的角度出发，建立城市物流无人机起降场点的布局规划模型；
9.步骤三：设计改进贪婪取走启发式算法对模型进行求解。
10.进一步的，所述覆盖偏移度以需求总量与起降点容量的比值求得，用以衡量起降点个数选取的适当性。
11.进一步的，所述安全效用为无人机在需求点与起降点之间的配送安全系数，用以刻画选址的安全性。
12.进一步的，所述多约束条件包括：起降点覆盖约束、起降点容量约束、服务范围约束、配送关系存在约束、起降点服务能力约束、需求点分配约束、起降点不互通约束、无人机载重约束、无人机航程约束、安全系数约束、逻辑变量约束。
13.进一步的，所述城市物流无人机起降场点的布局规划模型为多目标规划模型，需要进行归一化处理并赋予权重。
14.进一步的，所述改进贪婪取走启发式算法是针对传统贪婪取走算法易陷入局部最优解而提出的优化改进。
15.进一步的，所述起降点覆盖约束：每个需求点的需求都有唯一一个起降点进行满足；
16.所述起降点容量约束：每个起降点所负责配送的需求总量在起降点的容量限制内；
17.所述服务范围约束：无人机起降点所负责配送的需求点在其服务范围内；
18.所述配送关系存在约束：只有当起降点与需求点之间存在连通路径，配送关系才有可能存在；
19.所述起降点服务能力约束：当起降点被选择时，至少覆盖一个需求点，至多不超过其服务能力上限；
20.所述需求点分配约束：需求点通常分配给离它最近的起降点；
21.所述起降点不互通约束：各起降点之间不存在相应连通路径允许货物的流通与交换；
22.所述无人机载重约束：无人机所装载的包裹重量不超过其最大承载能力；
23.所述无人机航程约束：无人机的续航里程至少保证其完成对需求点的配送并返回起降点；
24.所述安全系数约束：为无人机在需求点与起降点之间的配送安全系数；
25.所述逻辑变量约束：指只有真值或假值的变量，即取值只能是“1”或“0”的变量；
26.进一步的，所述逻辑变量约束包括：起降点逻辑变量约束、连通路径逻辑变量约束、配送关系逻辑变量约束、需求点空域约束、起降点空域约束、连通路径空域约束。
27.进一步的，所述起降点逻辑变量约束：变量取值表示该起降点是否被选择；
28.所述连通路径逻辑变量约束：变量取值表示起降点与需求点之间是否存在连同路径；
29.所述配送关系逻辑变量约束：变量取值表示起降点与需求点之间是否存在配送关系；
30.所述需求点空域约束：变量取值表示需求点是否处于禁飞空域；
31.所述起降点空域约束：变量取值表示起降点是否处于禁飞空域；
32.所述连通路径空域约束：变量取值表示起降点与需求点的连通路径是否处于禁飞空域。
33.进一步的，所述改进贪婪取走启发式算法是在传统贪婪取走启发式算法的基础上，加入局部搜索和禁忌搜索算法中的禁忌表概念，并对目标函数改变量相同的情况提出了判断准则。
34.与现有技术相比，本发明具有如下有益效果：
35.1.本发明提供的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，解决了背景技术中的问题，有效改善了物流运输过程中的安全效用；
36.2.本发明以相对较小覆盖距离实现了对可行空域内需求点的全面覆盖，在保证安
全的情况下较为均匀地使用各起降点，避免了起降点容量的过度闲置。
附图说明
37.图1为本发明一种基于覆盖偏移度及安全效用的无人机起降点规划方法实施例的流程图。
38.图2为本发明一种基于覆盖偏移度及安全效用的无人机起降点规划方法实施例的覆盖偏移度示意图。
39.图3为本发明一种基于覆盖偏移度及安全效用的无人机起降点规划方法实施例的改进贪婪取走启发式算法流程示意图。
具体实施方式
40.为了更加清楚地描述本发明的思想，技术方案和优点，具体实施方式通过实施例和附图来表明。显然地，所描述的实施例是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在未付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
41.本发明提供了一种基于覆盖偏移度及安全效用的无人机起降点规划方法，如图1所示，包括以下步骤：
42.步骤一：定义覆盖偏移度、安全效用；
43.步骤二：考虑多约束条件，从覆盖偏移度和安全效用的角度出发，建立城市物流无人机起降场点的布局规划模型；
44.步骤三：设计改进贪婪取走启发式算法对模型进行求解。
45.上述方法针对物流无人机起降点选址规划问题，考虑需求环境、空域限制、无人机飞行性能等因素，以起降点数量相对最少和安全效用相对最大为目标函数构建物流无人机起降点选址模型，设计改进贪婪取走启发式算法对模型进行求解，如图3所示；有效改善了物流运输过程中的安全效用，并以相对较小覆盖距离实现了对可行空域内需求点的全面覆盖，在保证安全的情况下较为均匀地使用各起降点，避免了起降点容量的过度闲置。
46.下表为本实施例中所涉及的符号所表述的意义：
[0047][0048][0049]
一、约束条件：
[0050]
所述多约束条件包括：起降点覆盖约束、起降点容量约束、服务范围约束、配送关系存在约束、起降点服务能力约束、需求点分配约束、起降点不互通约束、无人机载重约束、无人机航程约束、安全系数约束、逻辑变量约束。
[0051]
1、起降点覆盖约束
[0052]
每个需求点j的需求都有唯一一个起降点i进行满足，其约束表示如下：
[0053]
[0054]
2、起降点容量约束
[0055]
每个起降点所负责配送的需求总量在起降点的容量限制内，其约束表示如下：
[0056][0057]
3、服务范围约束
[0058]
无人机起降点所负责配送的需求点在其服务范围内，其约束表示如下：
[0059]
l
ij
≤l
[0060]
4、配送关系存在约束
[0061]
只有当起降点i与需求点j之间存在连通路径，配送关系才有可能存在，其约束表示如下：
[0062]
α
ij
β
ij-y
ij
≥0
[0063]
5、起降点服务能力约束
[0064]
当起降点被选择时，至少覆盖一个需求点，至多不超过其服务能力上限，其约束表示如下：
[0065][0066]
6、需求点分配约束
[0067]
需求点j通常分配给离它最近的起降点i，其约束表示如下：
[0068]dijyij
≤d
ij
xi[0069]
7、起降点不互通约束
[0070]
各起降点之间不存在相应连通路径允许货物的流通与交换，其约束表示如下：
[0071]dii
＝0
[0072]
8、无人机载重约束
[0073]
无人机k所装载的包裹重量不超过其最大承载能力，其约束表示如下：
[0074]
qk≤qk[0075]
9、无人机航程约束
[0076]
无人机k的续航里程至少保证其完成对需求点j的配送并返回起降点i，其约束表示如下：
[0077]
lk≥2d
ij
[0078]
10、安全系数约束
[0079]
无人机在需求点与起降点之间的配送安全系数，其约束表示如下：
[0080][0081]
11、逻辑变量约束
[0082]
指只有真值或假值的变量，即取值只能是“1”或“0”的变量。其约束表示如下：
[0083][0084]
二、目标函数
[0085]
如图2所示，覆盖偏移度以需求总量与起降点容量的比值求得，用以衡量起降点个数选取的适当性。
[0086]
安全效用为无人机在需求点与起降点之间的配送安全系数，用以刻画选址的安全性。
[0087]
1、覆盖偏移度函数
[0088]
为衡量起降点个数选取的适当性，以配送中心覆盖度为判断标准进行说明，为使选中的起降场点没有过多冗余，能够得到充分利用，所求解的起降场点个数应满足配送中心覆盖偏移度最小，表示为下式：
[0089][0090]
2、安全效用函数
[0091]
安全效用为无人机在需求点与起降点之间的配送安全系数，用以刻画选址的安全性，表示为下式：
[0092][0093]
基于覆盖偏移度及安全效用的无人机起降点布局规划模型如下：
[0094][0095]
[0096][0097]
三、模型求解处理：
[0098]
本发明所建立布局规划模型包含最小化覆盖偏移度目标与最大化安全效用目标，为求解模型总目标函数值，现对目标函数作归一化处理，表示为下式：
[0099][0100]
[0101]
其中，覆盖偏移度f1作为逆向目标，值越小越优；安全效用f2作为正向目标，值越大越优。
[0102]
综上，本模型的总目标函数计算公式表示为下式：
[0103]
f(x)＝ω1f1+ω2f2[0104]
其中，ω1ω2分别表示目标函数一与目标函数二的权重。
[0105]
四、模型求解
[0106]
如图3所示，改进贪婪取走启发式算法的具体可以如下：
[0107]
(1)初始化
[0108]
选中所有备选物流中心，将其放入选址点集合u，此时，弃址点集合v＝φ。
[0109]
(2)初始分配
[0110]
依据禁飞域限制和连通路径限制，将下级点分配至集合u中距离其最近的起降场点，未分配到下级点的起降场点加入集合v。
[0111]
(3)再分配
[0112]
将集合u中不满足约束条件的下级点按照距离大小依次剔除，并将剔除的点重新分配。
[0113]
(4)更新集合
[0114]
从集合u中选出一个起降场点放入集合v，使得集合u中起降场点对下级点重新覆盖后覆盖距离的增加值最小/减少值最大，若增加量/减少量相同，选择覆盖方差大的点放入集合v。
[0115]
(5)局部搜索
[0116]
随机交换集合u和集合v中的一个元素，若覆盖距离变小，保留交换后的集合元素，若变大或不变，保留交换前的集合元素。
[0117]
(6)禁忌搜索
[0118]
若互换后，原起降场点覆盖的下级点中存在无法满足的点，将互换元素加入禁忌表a，在后续搜索过程中不再进行交换。
[0119]
(7)终止条件
[0120]
集合u中元素个数为p时，停止求解，算法结束。
[0121]
因此，本发明采用的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，解决了背景技术中的问题，有效改善了物流运输过程中的安全效用，并以相对较小覆盖距离实现了对可行空域内需求点的全面覆盖，在保证安全的情况下较为均匀地使用各起降点，避免了起降点容量的过度闲置。
[0122]
最后应说明的是：以上实施例仅用以说明本发明的技术方案而非对其进行限制，尽管参照较佳实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对本发明的技术方案进行修改或者等同替换，而这些修改或者等同替换亦不能使修改后的技术方案脱离本发明技术方案的精神和范围。

技术特征：
1.一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于，包括以下步骤：步骤一：定义覆盖偏移度、安全效用；步骤二：考虑多约束条件，从覆盖偏移度和安全效用的角度出发，建立城市物流无人机起降场点的布局规划模型；步骤三：设计改进贪婪取走启发式算法对模型进行求解。2.根据权利要求1所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述覆盖偏移度以需求总量与起降点容量的比值求得，用以衡量起降点个数选取的适当性。3.根据权利要求1所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述安全效用为无人机在需求点与起降点之间的配送安全系数，用以刻画选址的安全性。4.根据权利要求1所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述多约束条件包括：起降点覆盖约束、起降点容量约束、服务范围约束、配送关系存在约束、起降点服务能力约束、需求点分配约束、起降点不互通约束、无人机载重约束、无人机航程约束、安全系数约束、逻辑变量约束。5.根据权利要求1所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述城市物流无人机起降场点的布局规划模型为多目标规划模型，需要进行归一化处理并赋予权重。6.根据权利要求1所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述改进贪婪取走启发式算法是针对传统贪婪取走算法易陷入局部最优解而提出的优化改进。7.根据权利要求4所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于，所述起降点覆盖约束：每个需求点的需求都有唯一一个起降点进行满足；所述起降点容量约束：每个起降点所负责配送的需求总量在起降点的容量限制内；所述服务范围约束：无人机起降点所负责配送的需求点在其服务范围内；所述配送关系存在约束：只有当起降点与需求点之间存在连通路径，配送关系才有可能存在；所述起降点服务能力约束：当起降点被选择时，至少覆盖一个需求点，至多不超过其服务能力上限；所述需求点分配约束：需求点通常分配给离它最近的起降点；所述起降点不互通约束：各起降点之间不存在相应连通路径允许货物的流通与交换；所述无人机载重约束：无人机所装载的包裹重量不超过其最大承载能力；所述无人机航程约束：无人机的续航里程至少保证其完成对需求点的配送并返回起降点；所述安全系数约束：为无人机在需求点与起降点之间的配送安全系数；所述逻辑变量约束：指只有真值或假值的变量，即取值只能是“1”或“0”的变量。8.根据权利要求7所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述逻辑变量约束包括：起降点逻辑变量约束、连通路径逻辑变量约束、配送
关系逻辑变量约束、需求点空域约束、起降点空域约束、连通路径空域约束。9.根据权利要求8所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述起降点逻辑变量约束：变量取值表示该起降点是否被选择；所述连通路径逻辑变量约束：变量取值表示起降点与需求点之间是否存在连同路径；所述配送关系逻辑变量约束：变量取值表示起降点与需求点之间是否存在配送关系；所述需求点空域约束：变量取值表示需求点是否处于禁飞空域；所述起降点空域约束：变量取值表示起降点是否处于禁飞空域；所述连通路径空域约束：变量取值表示起降点与需求点的连通路径是否处于禁飞空域。10.根据权利要求1所述的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，其特征在于：所述改进贪婪取走启发式算法是在传统贪婪取走启发式算法的基础上，加入局部搜索和禁忌搜索算法中的禁忌表概念，并对目标函数改变量相同的情况提出了判断准则。

技术总结
本发明公开了一种基于覆盖偏移度及安全效用的无人机起降点规划方法，包括以下步骤：步骤一：定义覆盖偏移度、安全效用；步骤二：考虑多约束条件，从覆盖偏移度和安全效用的角度出发，建立城市物流无人机起降场点的布局规划模型；步骤三：设计改进贪婪取走启发式算法对模型进行求解。本发明采用的一种基于覆盖偏移度及安全效用的无人机起降点规划方法，有效改善了物流运输过程中的安全效用，并以相对较小覆盖距离实现了对可行空域内需求点的全面覆盖，在保证安全的情况下较为均匀地使用各起降点，避免了起降点容量的过度闲置。避免了起降点容量的过度闲置。避免了起降点容量的过度闲置。


技术研发人员：冯棣坤 张洪海 邓成 李金波 周锦伦 王非
受保护的技术使用者：南京航空航天大学
技术研发日：2023.05.23
技术公布日：2023/9/5