基于改进型差分算法的解决飞机着陆问题的方法

技术领域

本发明属于飞机调度领域，尤其是一种基于改进型差分算法的解决飞机着陆问题的方法。

背景技术

在过去的20年里,人们对航空运输的需求显著增加，这导致空域越来越拥堵,造成机场无法应付所有的需求。因此,机场管理者在提供高效服务,转移或改变一些飞机着陆或起飞时间上面临巨大挑战，这些变化可能导致机场资源的低效率使用和降低客户服务，飞机着陆问题在确定到达飞机的着陆时间上扮演着关键角色，因此做好飞机着陆问题的优化计算对实际运用中的成本降低有着巨大作用。飞机着陆问题包括建设一套飞机着陆时间表,这样使每架飞机被分配在一个特定时间着陆在一个特定的跑道,同时确保所有的问题和安全达到约束条件，目的是使飞机着陆比预定时间早到或晚到造成的经济惩罚最小化。

飞机着陆问题是一个困难非确定性多项式(NP-hard)问题。因为这个原因，在可接受的时间范围内，启发式和元启发式算法取代了精确算法，被广泛用来寻找高质量的解。尽管精确算法可以提供最佳的解决方案,但他们的计算时间往往随着问题规模的增加成倍增长,这使得它们只适合中小型问题。尽管目前为解决飞机着陆问题提出了众多算法,但基本没有一个算法在所有实例中被证明是一个有效的解决问题方法，并且他们的性能通常随着实例变大逐渐下降。

差分进化算法是一个非常著名的进化算法，在解决连续优化问题时非常有效，可惜的是，差分进化算法在组合优化问题的运用中并没有这么好，其中最主要的劣势在于其非常高的计算花费，特别是当种群规模较大的时候，收敛速度迅速下降，大大降低了优化的效率。对差分进化算法进行改进，以弥补收敛速度慢的问题就显得意义重大。

发明内容

本发明所解决的技术问题在于提供一种基于改进型差分算法的解决飞机着陆问题的方法，在差分算法中引入变异、交叉、选择，加快了收敛速度，提高了优化精度和效率，并减少了飞机着陆问题中的经济惩罚。

实现本发明目的的技术解决方案为：

基于改进型差分算法的解决飞机着陆问题的方法，包括以下步骤：

步骤1：给定飞机着陆问题的约束条件和最大迭代次数G_max，建立飞机着陆模型和适应度函数；

步骤2：根据飞机着陆模型生成初代种群，种群规模为NP，其中，每个种群个体代表一种飞机着陆方案；

步骤3：根据适应度函数，计算每个种群个体的适应度值；

步骤4：对每个种群个体的目标解进行变异操作，生成突变解以下迭代公式针对目标解中的一维进行变异，即

$>m_{i,j}^G=x_{1,j}^G+F*(x_{2,j}^G-x_{3,j}^G)$>

其中，目标解表示所有飞机的着陆方案的集合；n代表的是飞机着陆问题中飞机的总数，j表示当前飞机的编号数，表示第i套着陆方案中第j架飞机的着陆方案安排；F＝rand(0.1,1.5)，F表示变异操作中的变异因子；和分别是随机从当前种群中选取的解，且

步骤5：对目标解和突变解进行交叉操作，生成新一代种群

步骤6：计算新一代种群的适应度值，并与的适应度值比较，进行选择生成新目标解

步骤7：判断是否达到最大迭代次数G_max，若是，则输出否则，转到步骤3。

进一步的，本发明的基于改进型差分算法的解决飞机着陆问题的方法，步骤1中，飞机着陆问题的约束条件为：

$>\left(\begin{array}{c}{E}_i\le x_i\le L_i\\ x_j-x_i>s_{ij}\end{array}\right)$>

其中，x_i为第i号飞机的着陆时间，x_j为第j号飞机的着陆时间，i＝1,2,...,n，j＝1,2,...,n，i≠j，n为飞机数量，E_i为第i号飞机规定的最早着陆时间，L_i为第i号飞机规定的最晚着陆时间，s_ij为着陆在同一跑道上的第i号飞机和第j号飞机的规定着陆间隔时间。

进一步的，本发明的基于改进型差分算法的解决飞机着陆问题的方法，步骤1中，适应度函数为：

$>f=\underset{i=1}{\overset{n}{\Sigma }}{p}_i$>

$>p_i=\left(\begin{array}{cc}C{1}_i(T_i-x_i)& x_i\le T_i\\ C{2}_i(x_i-T_i)& x_i>T_i\end{array}\right)$>

其中，f为适应度函数，T_i表示第i号飞机的目标到达时间，C1_i表示第i号飞机相对目标到达时间晚到而产生的每单位时间内的经济惩罚，C2_i表示第i号飞机相对目标到达时间早到而产生的每单位时间内的经济惩罚，i＝1,2,...,n，n为飞机数量。

进一步的，本发明的基于改进型差分算法的解决飞机着陆问题的方法，步骤2中，飞机着陆方案包括每架飞机的着陆跑道和着陆时间。

进一步的，本发明的基于改进型差分算法的解决飞机着陆问题的方法，步骤5中，新一代种群为：

$>m_{i,j}^{G+1}=\left(\begin{array}{cccc}{m}_{i,j}^G& Rand\left(j\right)\le CR& or& j=Rnd\left(i\right)\\ x_{i,j}^G& Rand\left(j\right)>CR& or& j\ne Rnd\left(i\right)\end{array}\right)$>

其中，CR∈[0,1]为交叉比率，Rand(j)∈[0,1]表示对应于第j号的飞机随机选取一个数，Rnd(i)∈{1,2,...,n}表示随机选取的飞机编号数。

进一步的，本发明的基于改进型差分算法的解决飞机着陆问题的方法，步骤6中，新目标解为：

$>x_i^{G+1}=\left(\begin{array}{cc}{m}_i^{G+1}& f\left(m_i^{G+1}\right)\le f\left(x_i^G\right)\\ x_i^G& f\left(m_i^{G+1}\right)>f\left(x_i^G\right)\end{array}\right)$>

其中，f(·)为适应度函数。

本发明采用以上技术方案与现有技术相比，具有以下技术效果：

1、本发明的方法收敛速度快，同时解决了停滞问题，提高优化效率；

2、本发明的方法在飞机着陆问题的运用过程中增加了种群的多样性，优化精度高，大大减少了经济惩罚成本；

3、本发明的方法在飞机着陆问题中具有普遍适用性。

附图说明

图1是本发明的基于改进型差分算法的解决飞机着陆问题的方法流程图。

具体实施方式

下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

飞机着陆问题的描述如下：

(1)每架飞机必须被分配到一条确定的跑道上；

(2)在同一跑道上的同一时间只能有不超过一架飞机着陆；

(3)每架飞机的着陆时间都应该在预先定义的时间窗范围内；

(4)在同一跑道上着陆的飞机间的间隔时间必须达到安全标准的间隔时间。

首先建立飞机着陆问题的参数体系，如下表所示：

本发明提出的基于改进型差分算法的解决飞机着陆问题的方法，方法流程如图1所示，具体包括以下步骤：

步骤1：给定飞机着陆问题的约束条件和最大迭代次数G_max，建立飞机着陆模型和适应度函数。

飞机着陆问题的约束条件为：

$>\left(\begin{array}{c}{E}_i\le x_i\le L_i\\ x_j-x_i>s_{ij}\end{array}\right)$>

其中，x_i为第i号飞机的着陆时间，x_j为第j号飞机的着陆时间，i＝1,2,...,n，j＝1,2,...,n，i≠j，n为飞机数量，E_i为第i号飞机规定的最早着陆时间，L_i为第i号飞机规定的最晚着陆时间，s_ij为着陆在同一跑道上的第i号飞机和第j号飞机的规定着陆间隔时间。

适应度函数为：

$>f=\underset{i=1}{\overset{n}{\Sigma }}{p}_i$>

$>p_i=\left(\begin{array}{cc}C{1}_i(T_i-x_i)& x_i\le T_i\\ C{2}_i(x_i-T_i)& x_i>T_i\end{array}\right)$>

其中，f为适应度函数，T_i表示第i号飞机的目标到达时间，C1_i表示第i号飞机相对目标到达时间晚到而产生的每单位时间内的经济惩罚，C2_i表示第i号飞机相对目标到达时间早到而产生的每单位时间内的经济惩罚，i＝1,2,...,n，n为飞机数量。

步骤2：根据飞机着陆模型生成初代种群，种群规模取NP＝5，其中，每个种群个体代表一种飞机着陆方案。此处所取的种群规模较小，称之为微差分进化，能够有效地提升差分进化算法的收敛速度，但是会增加出现停滞问题的风险。

飞机着陆方案的解得表示形式为：

一架飞机的着陆方案包括飞机的着陆跑道和着陆时间，用一个带小数的实数来表示着陆方案，整数部分表示着陆的跑道，小数部分表示在该跑道上的着陆时间。

本实施例的飞机着陆方案如下表所示：

这里的跑道总数为3条，所以整数部分的取值在[1,3]，分别代表三条跑道，小数部分表示着陆时间，在同一跑道上，以升序排列的方式对应于时间的优先顺序。例如第3号飞机的着陆方案1.3表示为：着陆跑道为跑道1号，0.3＝(该飞机在跑道1着陆时间-跑道1预设最早可着陆时间)/(跑道1预设最晚可着陆时间-跑道1预设最早可着陆时间)。

步骤3：根据适应度函数，计算每个种群个体的适应度值。

步骤4：对每个种群个体的目标解进行变异操作，生成突变解以下迭代公式针对目标解中的一维进行变异，即

$>m_{i,j}^G=x_{1,j}^G+F*(x_{2,j}^G-x_{3,j}^G)$>

其中，目标解表示所有飞机的着陆方案的集合；n代表的是飞机着陆问题中飞机的总数，j表示当前飞机的编号数，表示第i套着陆方案中第j架飞机的方案安排；F＝rand(0.1,1.5)，F表示变异操作中的变异因子；和分别是随机从当前种群中选取的解，且

这里的变异因子F并不是只随机选取一次，而是每次进行变异操作计算的时候都要重新做F＝rand(0.1,1.5)操作，这么做可以大大增加种群的多样性，从而有效解决了缩小种群规模带来的停滞问题。

步骤5：对目标解和突变解进行交叉操作，生成新一代种群

新一代种群表示为：

$>m_{i,j}^{G+1}=\left(\begin{array}{cccc}{m}_{i,j}^G& Rand\left(j\right)\le CR& or& j=Rnd\left(i\right)\\ x_{i,j}^G& Rand\left(j\right)>CR& or& j\ne Rnd\left(i\right)\end{array}\right)$>

其中，CR∈[0,1]为交叉比率，Rand(j)∈[0,1]表示对应于第j号的飞机随机选取一个数，Rnd(i)∈{1,2,...,n}表示随机选取的飞机编号数，Rnd(i)操作保证了至少可以从中取得一个变量。

步骤6：计算新一代种群的适应度值，并与的适应度值比较，进行选择生成新目标解

新目标解表示为：

$>x_i^{G+1}=\left(\begin{array}{cc}{m}_i^{G+1}& f\left(m_i^{G+1}\right)\le f\left(x_i^G\right)\\ x_i^G& f\left(m_i^{G+1}\right)>f\left(x_i^G\right)\end{array}\right)$>

其中，f(·)为适应度函数。

步骤7：判断是否达到最大迭代次数G_max，若是，则输出否则，转到步骤3。

至此，基于改进型差分进化算法的解决飞机着陆问题的方法全部流程结束，取上述过程获取的最优解，我们可以得出如下结论：

首先本方法普遍适用于飞机着陆问题，且所得最优解达到目前已有的算法优化的水平，通过优化，大大降低经济惩罚和成本，而且，解决了传统差分进化算法在解决组合优化问题中的慢收敛的问题，提高了优化的速度和效率。

以上所述仅是本发明的部分实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进，这些改进应视为本发明的保护范围。