面向时间窗口的多无人机机场选址与随机任务调度方法与流程

1.本发明属于无人机技术领域，具体是一面向时间窗口的多无人机机场选址与随机任务调度方法。

背景技术：

2.具有低成本和高效率的服务对物流公司及其合同客户非常重要。这一服务通常需要建立基于多资源的路径规划模型，目的是在合理的计算时间内，以最小的总成本，满足取货和交货的特定时间窗口，改善服务。
3.无人机是近年来物流领域研究最深入的技术之一。它们结合了符合当前运输业和社会趋势的技术特征，如自主性、灵活性和敏捷性。其中，在面向物流的无人机的各种概念中，包裹运送是最受欢迎的应用场景之一。利用无人机进行包裹运送能最大程度解决“最后一公里配送”难题，同时实现降低总成本和提高客户满意度。
4.无人机单次飞行的续航时间一直是制约其大规模应用的瓶颈，尤其当服务的多个对象散布在大尺度的地理范围时。因此，可以考虑使用具备无人值守化作业功能的智能机场以实现对无人机的自动充电，同时实现灵活部署、无人值守、360度无死角监控、远程操控、及时响应等目标。

技术实现要素：

5.本发明的目的是提供一种面向时间窗口的多无人机机场选址与随机任务调度方法，该方法针对单次飞行有续航时长约束、可在智能机场自动更换电池、服务任务具有随机性、任务的开始与完成具有时间窗口场景下的无人机路径规划、任务分配以及智能机场选址。
6.为了达到上述目的，本发明所采取的技术方案为：
7.步骤(1)、任务区域图表征，每架无人机可在任务点之间以及任务点与智能机场之间沿直线飞行。根据任务点、智能机场的分布情况，通过将任务点、备选智能机场点建模成顶点，将任务点之间以及任务点与备选智能机场点之间的距离建模成边，从而获得原问题的图表征。包括以下过程：
8.(1.1)、任务顶点集：
9.a＝{a1,...,ai,...,an}
ꢀꢀꢀ
(1)，
10.式(1)中，a表示n个任务点构成的顶点集，ai表示第i个任务点；
11.(1.2)、智能机场顶点集：
12.p＝{p1,...,p2,...,pm}
ꢀꢀꢀ
(2)，
13.式(2)中，p表示m个备选智能机场点构成的顶点集，pj表示第j个备选智能机场点；
14.(1.3)、任务点之间的路径构成的边集：
[0015][0016]
式(3)中，v表示n个任务点之间的路径构成的边集，表示第i1个任务点和第i2个
任务点之间的边；
[0017]
(1.4)、任务点与备选智能机场点之间的路径构成的边集：
[0018][0019]
式(4)中，v'表示n个任务点与m个备选智能机场点之间的路径构成的边集，表示第i个任务点和第j个备选智能机场点之间的边；
[0020]
(1.5)、计算任务点之间的边的权重：
[0021][0022]
式(5)中，表示表示第i1个任务点和第i2个任务点之间的权重，和分别表示第i1个任务点和第i2个任务点的二维坐标；
[0023]
(1.6)、计算任务点和备选智能机场点之间的边的权重：
[0024][0025]
式(6)中，表示第i个任务点和第j个备选智能机场点之间的权重，(xi,yi)和(xj,yj)分别表示第i个任务点和第j个备选智能机场点的二维坐标；
[0026]
步骤(2)、一种无人机最优飞行路径求解方法，其特征在于：在随机任务需求、每个无人机的服务任务集以及智能机场选址给定的情况下确定每个无人机的最优飞行路径。包括以下过程：
[0027]
(2.1)、给定随机任务需求的实现：
[0028][0029]
式(7)中，u表示具有配送任务需求的所有任务点对的集合，为表征任务点对(i1,i2)是否有配送任务的变量，当时表示任务点对(i1,i2)有配送任务，当时表示任务点对(i1,i2)无配送任务；
[0030]
(2.2)、给定智能机场选址：
[0031]
h＝{j|yj＝1,1≤j≤m}
ꢀꢀꢀꢀ
(8)，
[0032]
式(8)中，h表示安置智能机场的备选智能机场点集合，yj表征备选智能机场点j是否安置智能机场的变量，当yj＝1时表示备选智能机场点j安置智能机场，当yj＝0时表示备选智能机场点j不安置智能机场；
[0033]
(2.3)、给定智能机场j的服务任务：
[0034][0035]
(2.4)、定义智能机场j的服务任务集：
[0036][0037]
式(10)中，uj表示分配给智能机场j的任务集合；
[0038]
(2.5)、对智能机场j对应无人机的飞行顺序决策变量进行约束：
[0039][0040]
式(11)中，和分别表示智能机场j第r个服务任务的起点和终点，对任意集合s，
|s|表示其元素个数；
[0041]
(2.6)、对智能机场j的等待时间进行约束：
[0042][0043]
式(12)中，表示智能机场j在开始执行第r个任务之前的等待时间；
[0044]
(2.7)、计算智能机场j服务第r个任务的耗时：
[0045][0046]
式(13)中，表示智能机场j服务第r个任务的耗时，νj表示智能机场j对应无人机的飞行速度，表示智能机场j对应无人机的单次飞行最大续航，m为一充分大的正数；
[0047]
(2.8)、计算智能机场j服务完第r个任务的时间：
[0048][0049]
式(14)中，表示智能机场j服务完第r个任务的时间，智能机场j服务完第1个任务的时间为务的时间为表示对应无人机在智能机场j的充电或换电池时间；
[0050]
(2.9)、计算智能机场j服务完所有任务的时间：
[0051][0052]
式(15)中，tj表示智能机场j服务完所有任务的时间；
[0053]
(2.10)、计算智能机场j服务第r个任务的起点不准时惩罚：
[0054][0055]
式(16)中，表示智能机场j服务第r个任务的起点不准时惩罚，其中，表示任务起点的理想任务开始时间，表示任务起点的过迟单位时间惩罚，表示任务终点的过早单位时间惩罚，
[0056]
(2.11)、计算智能机场j服务第r个任务的终点不准时惩罚：
[0057][0058]
式(17)中，表示智能机场j服务第r个任务的终点不准时惩罚，其中，表示任务终点的理想任务开始时间，表示任务终点的过迟单位时间惩罚，表示任务终点的过早单位时间惩罚；
[0059]
(2.12)、以智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小设置目标函数：
[0060][0061]
式(18)中，和分别表示智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的权重；
[0062]
(2.13)、综合式(7)—式(18)，写成如下形式：
[0063][0064]
(2.14)、上述路径规划问题属于混合整数非线性规划。本发明使用粒子算法进行求解。算法的框架如下：1)设定粒子大小为n，最大迭代数为i
max
；2)随机初始化式(13)的n个解；3)求出n个解中的单粒子最佳位置和粒子最佳位置；4)对k＝1,
…
,i
max
做5)至第7)；5)根据式(18)计算n个解对应的加权平均以作为它们的适应度；6)根据某一函数确定惯性权重函数ω(k)、收缩系数r1和r2、加速度系数c1和c2，更新每个粒子在每个方向上的坐标和速度；7)根据每个粒子的新位置，更新其适应度，以及单粒子最佳位置和粒子最佳位置；8)以此迭代，直到到达最大迭代数，输出此时的粒子最佳位置作为原问题的最优解。用表示具有任务需求的所有任务点对的集合为u、安置智能机场的备选智能机场点集合为h、分配给智能机场j的任务集合为uj时按照上述算法求得的智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小值。
[0065]
步骤(3)、一种智能机场任务分配优化方法，其特征在于：在随机任务需求、智能机场选址给定的情况下确定所有智能机场的最优任务分配。包括以下过程：
[0066]
(3.1)、对任务分配决策变量的取值进行约束：
[0067][0068]
(3.2)、对每个任务的服务智能机场数进行约束：
[0069][0070]
(3.3)、以所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小设置目标函数：
[0071][0072]
(3.4)、综合式(20)—式(22)，写成如下形式：
[0073][0074]
(3.5)、上述优化问题属于非线性0-1规划问题，本发明使用量子遗传算法进行求解，该算法是一种基于量子计算原理的一种遗传算法，它与传统的遗传算法的区别在于将量子的态矢量表达引入遗传编码，利用量子逻辑门实现染体的演化。算法的框架如下：1)初始化种，随机生成n个以量子比特为编码的染体；2)对初始种中的每个个体进行一次测量，得到对应的确定解；3)对各确定解进行适应度评估；4)记录最优个体和对应的适应度；5)判断计算过程是否可以结束，若满足结束条件则退出，否则继续计算；6)当迭代次数为k时，对种中的每个个体实施一次测量，得到相应的确定解；7)对各确定解进行适应度评估；8)利用量子旋转门对个体实施调整，得到新的种；9)记录最优个体和对应的适应度；10)将迭代次数k加1，返回步骤5)。用f
*
(u,h)表示具有任务需求的所有任务点对的集合为u、安置智能机场的备选智能机场点集合为h时按照上述算法求得的所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小值。
[0075]
步骤(4)、一种智能机场最优选址求解方法，其特征在于：在随机任务未实现的情况下确定所有智能机场的最优选址。包括以下过程：
[0076]
(4.1)、对智能机场选址决策变量的取值进行约束：
[0077]
yj∈{0,1},1≤j≤m
ꢀꢀꢀ
(24)；
[0078]
(4.2)、以所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚、机场设置成本的加权平均期望最小设置目标函数：
[0079][0080]
式(25)中，eu(g)表示对随机变量u求期望运算，cj表示在备选点j处安装智能机场的成本，η1和η2为各自的权重；
[0081]
(4.3)、综合式(24)、式(25)，写成如下形式：
[0082][0083]
(4.4)、上述优化问题属于随机非线性0-1规划问题，本发明使用结合随机抽样的
量子遗传算法进行求解，算法的框架如下：1)对每个任务对(i1,i2)，若的概率为则建立参数为的伯努利分布；2)对所有任务对(i1,i2)，根据上述分布，同时l次随机抽样；3)将每一次随机抽样看做随机变量的一次实现u，则u一共有l个实现值u1、u2、...u
l
；4)以作为式(26)中的目标函数的离散化；5)对上述离散化后的优化问题，使用步骤(3)中的量子遗传算法进行求解。
[0084]
本发明提出了一种面向时间窗口的多无人机机场选址与随机任务调度方法，该方法针对单次飞行有续航时长约束、可在智能机场自动更换电池、服务任务具有随机性、任务的开始与完成具有时间窗口场景下的无人机路径规划、任务分配以及智能机场选址问题，利用混合整数非线性规划、非线性0-1规划和随机非线性0-1规划建模上述问题。
[0085]
本发明还提出了一种针对上述混合整数非线性规划、非线性0-1规划和随机非线性0-1规划模型的、结合粒子算法和量子遗传算法的最优路径规划、任务分配以及机场选址求解算法。
附图说明
[0086]
图1本发明实施场景示意图；
[0087]
图2本发明技术方案实施流程图；
[0088]
图3任务场景的图结构示意图；
[0089]
图4随机需求已实现、智能机场选址和服务任务集已给定下的无人机最优飞行路径示意图；
[0090]
图5随机需求已实现、智能机场选址已给定下的最优任务分配示意图；
[0091]
图6随机需求实现前的最优智能机场选址及该选址下的最优任务分配示意图。
具体实施方式
[0092]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合实施例对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施实施例仅仅是本发明一部分实施实施例，而不是全部的实施实施例。基于本发明中的实施实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施实施例，都属于本发明保护的范围。
[0093]
目前，在无人机产业应用方面还存在如下问题：一、已有的研究常集中于单无人机的飞行路径规划问题，并未考虑多无人机之间的协同优化；二、当使用智能机场进行自动充电或更换电池时，没有进一步综合优化智能机场选址、任务分配和路径规划；三、在智能机场选址之前，客户需求通常尚未确定，因而需要建立面向随机客户需求的优化模型。
[0094]
基于此，本发明实施提供的一种面向时间窗口的多无人机机场选址与随机任务调度方法，可以缓解现有技术中存在的上述问题。
[0095]
本实施实施例中选择的无人机飞行速度为120m/min，单次飞行最长飞行时间为35min。
[0096]
智能机场是固定于地面的、实现无人机无人值守化作业的智能装备，提供了无人机收纳、智能待观、自动更换无人机电池、电池自动保养、ups断电保护、故障自检、起飞条件检测等功能。可灵活部署、24小时无人值守、极速响应、交叉持续的执行任务，无需人员操
控，并能支持无人机夜间降落。本发明的实施场景如图1所示。
[0097]
本发明的技术方案实施过程如图2所示。
[0098]
步骤一：任务区域图表征，每架无人机可在任务点之间以及任务点与智能机场之间沿直线飞行。根据任务点、智能机场的分布情况，通过将任务点、备选智能机场点建模成顶点，将任务点之间以及任务点与备选智能机场点之间的距离建模成边，从而获得原问题的图表征。
[0099]
包括以下过程：
[0100]
1、任务顶点集：
[0101]
a＝{a1,...,ai,...,an}
ꢀꢀꢀ
(27)，
[0102]
式(27)中，a表示n个任务点构成的顶点集，ai表示第i个任务点。在本例中，n＝12，a由图3中的12个圆形所示，圆形中标识了任务点的序号；
[0103]
2、智能机场顶点集：
[0104]
p＝{p1,...,p2,...,pm}
ꢀꢀꢀ
(28)，
[0105]
式(28)中，p表示m个备选智能机场点构成的顶点集，pj表示第j个备选智能机场点。在本例中，m＝4，p由图3中的4个正方形所示，正方形中标识了备选点的序号；
[0106]
3、任务点之间的路径构成的边集：
[0107][0108]
式(29)中，v表示n个任务点之间的路径构成的边集，表示第i1个任务点和第i2个任务点之间的边。在本例中，v即为图3中所有圆形之间的两两直线连接。由于线条过多，图中省略；
[0109]
4、任务点与备选智能机场点之间的路径构成的边集：
[0110][0111]
式(30)中，v'表示n个任务点与m个备选智能机场点之间的路径构成的边集，表示第i个任务点和第j个备选智能机场点之间的边。在本例中，v'即为图3中正方形与圆形之间的两两直线连接。由于线条过多，图中省略；
[0112]
5、计算任务点之间的边的权重：
[0113][0114]
式(31)中，表示表示第i1个任务点和第i2个任务点之间的权重，和分别表示第i1个任务点和第i2个任务点的二维坐标。在本例中，任务点之间的边的权重即为图3中所有圆形之间的直线距离；
[0115]
6、计算任务点和备选智能机场点之间的边的权重：
[0116][0117]
式(32)中，表示第i个任务点和第j个备选智能机场点之间的权重，(xi,yi)和(xj,yj)分别表示第i个任务点和第j个备选智能机场点的二维坐标。在本例中，图3中任务点和备选点之间的边的权重即为正方形与圆形之间的直线距离；
[0118]
步骤二：一种无人机最优飞行路径求解方法，其特征在于：在随机任务需求、每个无人机的服务任务集以及智能机场选址给定的情况下确定每个无人机的最优飞行路径。包
括以下过程：
[0119]
1、给定随机任务需求的实现：
[0120][0121]
式(33)中，u表示具有配送任务需求的所有任务点对的集合，为表征任务点对(i1,i2)是否有配送任务的变量，当时表示任务点对(i1,i2)有配送任务，当时表示任务点对(i1,i2)无配送任务。在本例中，如图4所示，直线连接的两个圆形表示具有配送任务需求的任务点对，即u
1,2
＝u
3,4
＝u
5,6
＝u
7,8
＝u
9,10
＝u
11,12
＝1，其余
[0122]
2、给定智能机场选址：
[0123]
h＝{j|yj＝1,1≤j≤m}
ꢀꢀꢀ
(34)，
[0124]
式(34)中，h表示安置智能机场的备选智能机场点集合，yj表征备选智能机场点j是否安置智能机场的变量，当yj＝1时表示备选智能机场点j安置智能机场，当yj＝0时表示备选智能机场点j不安置智能机场。在本例中，如图4所示，实心的正方形表示该备选点安置智能机场，即y1＝y2＝0，其余yj＝0；
[0125]
3、给定智能机场j的服务任务：
[0126][0127]
在本例中，如图4所示，所有与正方形之间有虚线连接圆形表示该智能机场的服务任务，即
[0128]
4、定义智能机场j的服务任务集：
[0129][0130]
式(36)中，uj表示分配给智能机场j的任务集合。在本例中，u1＝{(1,2),(9,10),(11,12)}，u2＝{(3,4),(5,6),(7,8)}。以下以智能机场1为例，求解其对应无人机的最优飞行路径。
[0131]
5、对智能机场j对应无人机的飞行顺序决策变量进行约束：
[0132][0133]
式(37)中，和分别表示智能机场j第r个服务任务的起点和终点，对任意集合s，|s|表示其元素个数。在本例中，|u1|＝3；
[0134]
6、对智能机场j的等待时间进行约束：
[0135][0136]
式(38)中，表示智能机场j在开始执行第r个任务之前的等待时间；
[0137]
7、计算智能机场j服务第r个任务的耗时：
[0138][0139]
式(39)中，表示智能机场j服务第r个任务的耗时，νj表示智能机场j对应无人机
的飞行速度，表示智能机场j对应无人机的单次飞行最大续航，m为一充分大的正数。在本例中，ν1＝120m/min，m＝100；
[0140]
8、计算智能机场j服务完第r个任务的时间：
[0141][0142]
式(40)中，表示智能机场j服务完第r个任务的时间，智能机场j服务完第1个任务的时间为务的时间为表示对应无人机在智能机场j的充电或换电池时间。在本例中，
[0143]
9、计算智能机场j服务完所有任务的时间：
[0144][0145]
式(41)中，tj表示智能机场j服务完所有任务的时间；
[0146]
10、计算智能机场j服务第r个任务的起点不准时惩罚：
[0147][0148]
式(42)中，表示智能机场j服务第r个任务的起点不准时惩罚，其中，表示任务起点的理想任务开始时间，表示任务起点的过迟单位时间惩罚，表示任务起点的过早单位时间惩罚，在本例中，t
1,2
＝1，t
9,10
＝18，t
11,12
＝25，ρ
1,2
＝ρ
9,10
＝ρ
11,12
＝3，ρ'
1,2
＝ρ'
9,10
＝ρ'
11,12
＝0.3；
[0149]
11、计算智能机场j服务第r个任务的终点不准时惩罚：
[0150][0151]
式(43)中，表示智能机场j服务第r个任务的终点不准时惩罚，其中，表示任务终点的理想任务开始时间，表示任务终点的过迟单位时间惩罚，表示任务终点的过早单位时间惩罚。在本例中，
[0152]
12、以智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小设置目标函数：
[0153][0154]
式(44)中，和分别表示智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的权重。在本例中，
[0155]
13、综合式(33)—式(44)，写成如下形式：
[0156][0157]
14、上述路径规划问题属于混合整数非线性规划。本发明使用粒子算法进行求解。算法的框架如下：1、设定粒子大小为200，最大迭代数为20；、2、随机初始化式(45)的200个解；3、求出200个解中的单粒子最佳位置和粒子最佳位置；4、k＝1,
…
,20；5)根据式(44)计算200个解各自的加权平均b1，以作为它们的适应度；6)惯性权重ω(k)采用类sigmoid函数(具体表达式为ω(k)＝1/(1+exp(-αk))、收缩系数r1和r2是两个从0到1之间的均匀分布中取样的随机数、加速度系数c1＝2和c2＝2，更新每个粒子在每个方向上的坐标和速度。由于不能平衡探索与利用，恒定的惯性权重的效率不高。而单纯的线性和非线性惯性权重被证明虽能够在一定程度上改善粒子算法的搜索能力，但它们仍然难以在全局收敛和收敛效率之间获得良好的平衡。大量实验表明，本发明所使用的类sigmoid函数能够在线性和非线性行为之间实现较好的平衡；7)根据每个粒子的新位置，更新其适应度，以及单粒子最佳位置和粒子最佳位置；8)以此迭代，直到到达最大迭代数，输出此时的粒子最佳位置作为原问题的最优解。用表示具有任务需求的所有任务点对的集合为u、安置智能机场的备选智能机场点集合为h、分配给智能机场j的任务集合为uj时按照上述算法求得的智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小值。在本例中，可求得智能机场1的如图4所示的最优飞行路径，其中箭头上的数字表示无人机的飞行顺序即为最优飞行路径。
[0158]
步骤三：一种智能机场任务分配优化方法，其特征在于：在随机任务需求、智能机场选址给定的情况下确定所有智能机场的最优任务分配。包括以下过程：
[0159]
1、对任务分配决策变量的取值进行约束：
[0160][0161]
2、对每个任务的服务智能机场数进行约束：
[0162]
[0163]
3、以所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小设置目标函数：
[0164][0165]
4、综合式(46)—式(48)，写成如下形式：
[0166][0167]
5、上述优化问题属于非线性0-1规划问题，本发明使用量子遗传算法进行求解，该算法是一种基于量子计算原理的一种遗传算法，它与传统的遗传算法的区别在于将量子的态矢量表达引入遗传编码，利用量子逻辑门实现染体的演化。算法的框架如下：1)初始化种，随机生成100个以量子比特为编码的染体；2)对初始种中的每个个体进行一次测量，得到对应的确定解；3)将确定解代入式(48)，计算出各自的加权平均值f，并以作为其适应度；4)记录最优个体和对应的适应度；5)判断是否迭代至20代，若满足则退出，否则继续计算；6)当迭代次数为k时，对种中的每个个体实施一次测量，得到相应的确定解；7)将确定解代入式(48)，计算出各自的加权平均值f，并以作为其适应度；8)利用量子旋转门对个体实施调整，得到新的种。量子旋转门的调整操作为：使用该操作更新染体的概率幅；9)记录最优个体和对应的适应度；10)将迭代次数k加1，返回步骤5)。用f
*
(u,h)表示具有任务需求的所有任务点对的集合为u、安置智能机场的备选智能机场点集合为h时按照上述算法求得的所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小值。在本例中，可求得如图5所示的最优任务分配。其中，所有与正方形之间有虚线连接圆形表示该智能机场的服务任务。
[0168]
步骤四：一种智能机场最优选址求解方法，其特征在于：在随机任务未实现的情况下确定所有智能机场的最优选址。包括以下过程：
[0169]
1、对智能机场选址决策变量的取值进行约束：
[0170]
yj∈{0,1},1≤j≤m
ꢀꢀꢀ
(50)；
[0171]
2、以所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚、机场设置成本的加权平均期望最小设置目标函数：
[0172][0173]
式(51)中，eu(g)表示对随机变量u求期望运算，cj表示在备选点j处安装智能机场的成本，η1和η2为各自的权重。在本例中，c1＝c2＝c3＝c4＝20，η1＝η2＝0.5；
[0174]
3、综合式(50)、式(51)，写成如下形式：
[0175]
[0176]
4、上述优化问题属于随机非线性0-1规划问题，本发明使用结合随机抽样的量子遗传算法进行求解。在本例中，对每个任务对(i1,i2)，的概率为0.5。算法的框架如下：1)对每个任务对(i1,i2)，建立参数为0.5的伯努利分布；2)对所有任务对(i1,i2)，根据上述分布，同时100次随机抽样；3)将每一次随机抽样看做随机变量的一次实现u，则u一共有100个实现值u1、u2、...u
100
；4)以作为式(52)中的目标函数的离散化；5)对上述离散化后的优化问题，使用步骤三中的量子遗传算法进行求解。在本例中，可求得如图6所示的最优智能机场选址方案，将此方案代入步骤三中，可求得每个智能机场的最优任务分配方案。图6中，实心的正方形表示该备选点安置智能机场，所有与正方形之间有虚线连接圆形表示该智能机场的服务任务。
[0177]
在本发明的描述中，需要理解的是，术语“上”、“下”、“左”、“右”等指示方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以及特定的方位构造和操作，因此，不能理解为对本发明的限制。此外，“第一”、“第二”仅由于描述目的，且不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。因此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者多个该特征。本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。
[0178]
在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”“相连”“连接”等应做广义理解，实施例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接连接，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。
[0179]
以上对本发明的一个实施例进行了详细说明，但所述内容仅为本发明的较佳实施例，不能被认为用于限定本发明的实施范围。凡依本发明申请范围所作的均等变化与改进等，均应仍归属于本发明的专利涵盖范围之内。

技术特征：

1.任务区域图表征，每架无人机可在任务点之间以及任务点与智能机场之间沿直线飞行。根据任务点、备选智能机场点的分布情况，通过将任务点、备选智能机场点建模成顶点，将任务点之间以及任务点与备选智能机场点之间的距离建模成边，从而获得原问题的图表征。包括以下过程：(1.1)、任务顶点集：a＝{a1,...,a
i
,...,a
n
}
ꢀꢀꢀꢀꢀꢀ
(1)，式(1)中，a表示n个任务点构成的顶点集，a
i
表示第i个任务点；(1.2)、备选智能机场顶点集：p＝{p1,...,p2,...,p
m
}
ꢀꢀꢀꢀꢀꢀ
(2)，式(2)中，p表示m个备选智能机场点构成的顶点集，p
j
表示第j个备选智能机场点；(1.3)、任务点之间的路径构成的边集：式(3)中，v表示n个任务点之间的路径构成的边集，表示第i1个任务点和第i2个任务点之间的边；(1.4)、任务点与备选智能机场点之间的路径构成的边集：式(4)中，v'表示n个任务点与m个备选智能机场点之间的路径构成的边集，表示第i个任务点和第j个备选智能机场点之间的边；(1.5)、计算任务点之间的边的权重：式(5)中，表示表示第i1个任务点和第i2个任务点之间的权重，和分别表示第i1个任务点和第i2个任务点的二维坐标；(1.6)、计算任务点和备选智能机场点之间的边的权重：式(6)中，表示第i个任务点和第j个备选智能机场点之间的权重，(x
i
,y
i
)和(x
j
,y
j
)分别表示第i个任务点和第j个备选智能机场点的二维坐标。2.一种基于权利要求1所述的任务区域图表征方法的无人机最优飞行路径求解方法，其特征在于：在随机任务需求、每个无人机的服务任务集以及智能机场选址给定的情况下确定每个无人机的最优飞行路径。包括以下过程：(2.1)、给定随机任务需求的实现：式(7)中，u表示具有配送任务需求的所有任务点对的集合，为表征任务点对(i1,i2)是否有配送任务的变量，当时表示任务点对(i1,i2)有配送任务，当时表示任务点对(i1,i2)无配送任务；(2.2)、给定智能机场选址：h＝{j|y
j
＝1,1≤j≤m}
ꢀꢀꢀꢀꢀꢀ
(8)，
式(8)中，h表示安置智能机场的备选智能机场点集合，y
j
表征备选智能机场点j是否安置智能机场的变量，当y
j
＝1时表示备选智能机场点j安置智能机场，当y
j
＝0时表示备选智能机场点j不安置智能机场；(2.3)、给定智能机场j的服务任务：(2.4)、定义智能机场j的服务任务集：式(10)中，u
j
表示分配给智能机场j的任务集合；(2.5)、对智能机场j对应无人机的飞行顺序决策变量进行约束：式(11)中，和分别表示智能机场j第r个服务任务的起点和终点，对任意集合s，|s|表示其元素个数；(2.6)、对智能机场j的等待时间进行约束：式(12)中，表示智能机场j在开始执行第r个任务之前的等待时间；(2.7)、计算智能机场j服务第r个任务的耗时：式(13)中，表示智能机场j服务第r个任务的耗时，ν
j
表示智能机场j对应无人机的飞行速度，表示智能机场j对应无人机的单次飞行最大续航，m为一充分大的正数；(2.8)、计算智能机场j服务完第r个任务的时间：式(14)中，表示智能机场j服务完第r个任务的时间，智能机场j服务完第1个任务的时间为时间为表示对应无人机在智能机场j的充电或换电池时间；(2.9)、计算智能机场j服务完所有任务的时间：式(15)中，t
j
表示智能机场j服务完所有任务的时间；(2.10)、计算智能机场j服务第r个任务的起点不准时惩罚：
式(16)中，表示智能机场j服务第r个任务的起点不准时惩罚，其中，表示任务起点的理想任务开始时间，表示任务起点的过迟单位时间惩罚，表示任务起点的过早单位时间惩罚，(2.11)、计算智能机场j服务第r个任务的终点不准时惩罚：式(17)中，表示智能机场j服务第r个任务的终点不准时惩罚，其中，表示任务终点的理想任务开始时间，表示任务终点的过迟单位时间惩罚，表示任务终点的过早单位时间惩罚；(2.12)、以智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小设置目标函数：式(18)中，和分别表示智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的权重；(2.13)、综合式(7)—式(18)，写成如下形式：(2.14)、上述路径规划问题属于混合整数非线性规划。本发明使用粒子算法进行求
解。算法的框架如下：1)设定粒子大小为n，最大迭代数为i
max
；2)随机初始化式(13)的n个解；3)求出n个解中的单粒子最佳位置和粒子最佳位置；4)对k＝1,
…
,i
max
做5)至第7)；5)根据式(18)计算n个解对应的加权平均以作为它们的适应度；6)根据某一函数确定惯性权重函数ω(k)、收缩系数r1和r2、加速度系数c1和c2，更新每个粒子在每个方向上的坐标和速度；7)根据每个粒子的新位置，更新其适应度，以及单粒子最佳位置和粒子最佳位置；8)以此迭代，直到到达最大迭代数，输出此时的粒子最佳位置作为原问题的最优解。用b
j*
(u,h,u
j
)表示具有任务需求的所有任务点对的集合为u、安置智能机场的备选智能机场点集合为h、分配给智能机场j的任务集合为u
j
时按照上述算法求得的智能机场j的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小值。3.一种基于权利要求2所述的无人机最优飞行路径求解方法的智能机场任务分配优化方法，其特征在于：在随机任务需求、智能机场选址给定的情况下确定所有智能机场的最优任务分配。包括以下过程：(3.1)、对任务分配决策变量的取值进行约束：(3.2)、对每个任务的服务智能机场数进行约束：(3.3)、以所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小设置目标函数：(3.4)、综合式(20)—式(22)，写成如下形式：(3.5)、上述优化问题属于非线性0-1规划问题，本发明使用量子遗传算法进行求解，该算法是一种基于量子计算原理的一种遗传算法，它与传统的遗传算法的区别在于将量子的态矢量表达引入遗传编码，利用量子逻辑门实现染体的演化。算法的框架如下：1)初始化种，随机生成n个以量子比特为编码的染体；2)对初始种中的每个个体进行一次测量，得到对应的确定解；3)对各确定解进行适应度评估；4)记录最优个体和对应的适应度；5)判断计算过程是否可以结束，若满足结束条件则退出，否则继续计算；6)当迭代次数为k时，对种中的每个个体实施一次测量，得到相应的确定解；7)对各确定解进行适应度评估；8)利用量子旋转门对个体实施调整，得到新的种；9)记录最优个体和对应的适应度；10)将迭代次数k加1，返回步骤5)。用f
*
(u,h)表示具有任务需求的所有任务点对的集合为u、安置智能机场的备选智能机场点集合为h时按照上述算法求得的所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚的加权平均最小值。4.一种基于权利要求3所述的智能机场任务分配优化方法的智能机场最优选址求解方
法，其特征在于：在随机任务未实现的情况下确定所有智能机场的最优选址。包括以下过程：(4.1)、对智能机场选址决策变量的取值进行约束：y
j
∈{0,1},1≤j≤m (24)；(4.2)、以所有智能机场的任务完成时间、起点不准时惩罚和终点不准时惩罚、机场设置成本的加权平均期望最小设置目标函数：式(25)中，e
u
(g)表示对随机变量u求期望运算，c
j
表示在备选点j处安装智能机场的成本，η1和η2为各自的权重；(4.3)、综合式(24)、式(25)，写成如下形式：(4.4)、上述优化问题属于随机非线性0-1规划问题，本发明使用结合随机抽样的量子遗传算法进行求解，算法的框架如下：1)对每个任务对(i1,i2)，若的概率为则建立参数为的伯努利分布；2)对所有任务对(i1,i2)，根据上述分布，同时l次随机抽样；3)将每一次随机抽样看做随机变量的一次实现u，则u一共有l个实现值u1、u2、...u
l
；4) 以作为式(26)中的目标函数的离散化；5)对上述离散化后的优化问题，使用权利要求3中的量子遗传算法进行求解。

技术总结

本发明公开了一种面向时间窗口的多无人机机场选址与随机任务调度方法，该方法针对单次飞行有续航时长约束、可在智能机场自动更换电池、服务任务具有随机性、任务的开始与完成具有时间窗口场景下的无人机路径规划、任务分配以及智能机场选址问题，利用混合整数非线性规划、非线性0-1规划和随机非线性0-1规划建模上述问题。同时本发明还公开了一种针对上述混合整数非线性规划、非线性0-1规划和随机非线性0-1规划模型的、结合粒子算法和量子遗传算法的最优路径规划、任务分配以及机场选址求解算法。解算法。解算法。