一种基于差分进化算法的多机场协同调度鲁棒优化方法

摘要

本发明公开了一种基于差分进化算法的多机场协同调度鲁棒优化方法，属于优化设计技术领域。所述的方法包括建立机场延误模型、建立鲁棒优化模型和鲁棒优化设计的步骤。本发明根据历史数据计算得到传播延误最大的前四名机场排名，假设四个机场形成一个闭合网络，调整四个机场间的航班排序问题，以最小总延误量为目标，建立多机场协同调度鲁棒优化模型，并设计差分进化算法对所述的多机场协同调度鲁棒优化模型进行求解，本发明模型具有较大可实施性，解决了多机场协同调度中的不确定性问题。

说明书

技术领域

本发明属于优化设计技术领域，具体涉及一种基于差分进化算法的多机场协调调度鲁棒优化方法。

背景技术

离港终端区航班起飞调度是空中交通流量管理中的核心问题之一。它旨在为待起飞的航班给出合理有效的调度方案，在保障安全的前提下，达到缩短航班等待时间以及减少延误的目的，具有显著的社会与经济效益。实际上航班起飞调度是一个具有不确定因素的动态过程；因此，需要研究能够独立于具体场景的鲁棒的终端区航班起飞调度方法。鲁棒优化是基于对最坏情况优化的考虑，即求解在最坏情况下依然保持优化特性。单机场终端区离港起飞调度排序问题的研究受到广泛关注。目前，针对多机场间协同航班调度问题的研究甚少。但多机场协同航班调度问题对减少全局延误有影响，综合考虑不确定性的协同优化研究相对较少，因此多机场协同调度鲁棒优化研究具有重要意义。差分进化(DE)是一种基于种群的启发式全局随机搜索算法，具有结构紧凑、容易实现和运用等特点，同时具有良好的鲁棒性和收敛性。

发明内容

为了解决现有技术中存在的问题，本发明提供一种基于差分进化算法的多机场协同调度鲁棒优化方法。本发明根据历史数据计算得到传播延误最大的前四名机场排名，假设四个机场形成一个闭合网络，调整四个机场间的航班排序问题，以最小总延误量为目标，建立多机场协同调度鲁棒优化模型，并设计差分进化算法对所述的多机场协同调度鲁棒优化模型进行求解。由于存在不确定性因素，而鲁棒优化是基于对最坏情况优化的考虑，即所求解在最坏情况下依然保持优化特性。因此，鲁棒优化模型使得网络更加稳定高效。

所述的基于差分进化算法的多机场协同调度鲁棒优化方法，具体包括如下步骤：

第一步，建立机场延误模型。

第二步，建立鲁棒优化模型。

第三步，鲁棒优化设计步骤如下：

(3.1)确定优化目标函数和约束条件。

(3.2)确定航班起飞和飞行过程中所受的主要不确定参数和波动范围，并将其组合为航班的k种不确定状态。

(3.3)初始化种群。

(3.4)对每个个体进行k种不确定状态，选取k种情况下函数值最小(即总延误时间最小)的作为该个体的函数值；从m个个体对应得到的函数值中，选择最大函数值(即总延误最大)对应的个体作为这一代中的最优个体，即应用最大最小优化方法，选择每一代中的最优个体。

(3.5)判断是否满足鲁棒优化终止条件。终止条件可设置为当迭代数达到最大代数时，则停止鲁棒优化。

如果不满足终止条件，则把从上一代得到的最优个体采取变异、交叉、选择，对种群进行操作，产生下一代种群，并返回(3.4)。

如果满足终止条件，则输出最优个体对应的函数值，得到鲁棒性和最优性兼容的鲁棒最优值。

本发明的优点在于：

(1)根据历史数据计算传播延误机场排名。

(2)本发明以一个闭合网络来建立鲁棒优化模型，解决了多机场协同调度中的不确定性问题。

(3)现在研究大多是关于单机场调度，针对多机场间协同航班调度问题的研究甚少；但多机场协同航班调度问题对减少全局延误有影响。

(4)模型具有较大可实施性。

附图说明

图1是飞机在机场和空中、从停机位到扇形离港区的飞机调度示意图。

图2是本发明中鲁棒优化模型的优化方法设计流程图。

图3是差分进化算法中交叉操作用到的部分映射法。

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

本发明提供的一种基于差分进化算法的多机场协同调度鲁棒优化方法，具体包括如下步骤：

第一步，建立机场延误模型。

如图1所示，图中，

飞机起飞之前的延误归因于出发机场，此时延迟归因于到达机场。空中产生的延迟分配给到达机场。若提前起飞,则出发机场的延误为0。初始延迟是机场由于内在问题,如机械问题,当地的恶劣天气条件,需求增加等造成的延迟。它包含EDCT预期离港放行时刻，但本发明将初始延误和放行延误分开。传播延迟是由于上一机场的晚出发所造成的任何机场延误。

根据飞机机尾号的不同分离传播延误和原始延误。

航班串:多个在空间上和时间上连接的航班按顺序组合在一起而形成的一组航班。在空间上连接是指后一个航班的出发机场与前一个航班的到达机场相同，在时间上连续是指前后两航班的衔接时间满足最短衔接时间限制，也即后一航班的出发时间在前一航班到达时间之后，并且时间差大于最短衔接时间。

航班环：若干天内满足飞机维修定检要求的航班组合成的航班串，该航班串的起点和终点是同一城市(一般指基地)。

假设一天行程的航班环，且没有延迟到行程中第一个机场。默认行程最后所有累积延迟被最终机场吸收。

假设一个航班环经过M个机场，这些机场按照先后顺序依次编号1、2...M；假设第一个机场也是第M+1个机场，且每个航班环中机场均需重新编号。一天中机场i有K架航班经过。机场i每天的执行率为λ_i。不同机场执行率不同；同一机场不同天，执行率不同。

起飞延误＝实际起飞时间-计划起飞时间

设机场i到机场i+1的计划起飞时间为实际起飞时间则机场i到机场j＝i+1的起飞延误为：

其中i＝1,2,...,M。

加入机场执行率后，机场i到机场j的实际起飞延误为

起飞延误可以分为初始延误、传播延误、EDCT延误。假设相邻两个机场间只有初始延误，不存在传播延误。设机场i到下一机场i+1注入的初始延误为机场i对机场j产生的传播延误为之前机场对机场j产生的传播延误之和为p_j。由于EDCT延误相比于初始、传播延误较小，在计算中可忽略不计。所述的实际起飞延误、初始延误和传播延误的关系可由下面公式表示：

且

即其中i＝1、2...M,j＝3、4、5...M+1。

(1)假设一天中一个航班环M个机场从第一个机场到最终回到第一个机场经过的机场分别编号为1、2...M、M+1。当机场i的起飞延误小于等于下一机场i+1的起飞延误则机场i的初始延误为之前机场到机场i的传播延误之和为当机场i的起飞延误大于下一机场i+1的起飞延误则令机场i的初始延误为之前机场到机场i的传播延误之和为

即：

若则

若则

(2)一个航班环中机场j前面每个机场是按照一定比例将延误传播给机场j。这个比例可根据之前延误比例进行计算。具体如下：

若要求出机场i对机场j的传播延误则要知道第一个机场对机场j-1、第二个机场对机场j-1...机场j-3对机场j-1的传播延误及机场j-2对机场j-1的初始延误，所有之和为他们比值为：

根据以上比例，可以得出比例系数α_ij，即

机场i到机场j的传播延误为：其中i＝1、2...M,j＝3、4、5...M+1。

(3)设一天中一架航班包含M个机场，则机场i的传播延误为：

一天中K架航班在机场i的总传播延误为:

机场i所占传播延误百分比为：

第二步，建立鲁棒优化模型。

鲁棒优化是基于对最坏情况优化的考虑，即所求解在最坏情况下依旧保持优化特性。鲁棒最优解不一定是某一情况下的最优策略，而是在所有情况下得到的效益值均可接受的策略。在所有不确定性集合内求得目标优化函数的所有保守最大值，目的是使优化结果满足所有不确定性下的极限情况；然后在长时间尺度下取所有保守最大值的最小保守结果，在数学上可将此类带不确定性因素的求目标函数最小值min问题归结为一类带约束min-max-min优化问题。其中航班实际起飞时间空中飞行时间是不确定性参数，它会在一定的范围内波动其中，为实际起飞时间的最小值和最大值，为空中飞行时间的最小值和最大值。

根据上述机场延误模型计算出传播延误比例排名前四的机场。为改善这四个机场的延误量，使得未来因这四个机场而造成的传播延误损失最小化。假设四个传播延误最大机场A、B、C、D形成一个闭合网络。传播延误最大机场A按照原航班计划形成一个航班序列，机场B、C、D根据一定的约束条件进行排序，计算适应值，然后机场A的航班序列经过交叉、变异、选择操作生成下一代种群，三个机场再次相互制约，生成新的序列，经过不断迭代，最终使得四个机场的总延误量最小。

假设:(1)机场都是单跑道，起飞与降落不能同时进行；

(2)所有航班地面单位时间延迟已知；

(3)终端区在未来各时段的容量值已知；

(4)同一机场不同机型航班从跑道起飞后到达扇形区所用时间相同。

利用鲁棒优化求解航班延误优化目标函数，则鲁棒优化模型可表示为：

m表示初始化种群中的个体数量，k表示不确定状态的种类数。

第三步，鲁棒优化，如图2所示，具体设计步骤如下：

(3.1)确定优化目标函数和约束条件。

目标函数为最小化四个机场总延误：

约束条件：

p_it≤D_it(3)

参数说明：

T为航班f可能的起飞时段集合，由等长度的时间段t组成；

N为机场个数，这里定义为4；

F_i为机场i的起飞航班集合；

为航班f的计划起飞时刻；

为航班f的实际起飞时刻；

p_it为机场i在t时段的流量，D_it为机场i在t时段的容量；

f^*为航班f的后续航班；

δ为航班f的尾流间隔。

式(2)表示每架航班只有一个起飞时刻；式(3)机场容量约束；式(4)表示航班不可提前起飞；式(5)表示飞机序列之间必须满足安全间隔。约束(6)为起飞机场经过空中飞行到达目的机场，目的机场必须空出相应时间段进行降落以及地面操作，如此相互制约生成剩余三个机场的起飞排序，计算适应值。经不断迭代后，最终使得总延误量最小化。

(3.2)确定航班起飞和飞行过程中所受的主要不确定参数和波动范围，并将其组合为航班的k种不确定状态。其波动范围通常会有上下界，若有n种主要不确定性参数，则总有k＝2ⁿ种不确定状态。本发明中不确定性参数为航班起飞时间空中飞行时间则在这两种不确定性参数作用下，不确定状态有4种。

(3.3)用航班的起飞序号排列来表示染色体，采用自然码排列进行染色体编码，染色体的长度为航班数量。每个染色体由一组基因组成，每个基因表示航班的起飞序号，基因的位置排序代表航班的起飞次序。按照这样的编码方式，染色体编码可以表示为(1,2...n)，其中染色体中基因表示航班的起飞序号，其取值范围是[1，n]。这里选择最大传播延误机场A进行优化。初始种群为最大传播延误机场A的初始航班计划形成的序列，再在此基础上随机初始化形成包含m个个体的种群。

(3.4)对每个个体进行k种不确定状态，选取k种情况下函数值最小(即总延误时间最小)的作为该个体的函数值；从m个个体对应得到的函数值中，选择最大函数值(即总延误最大)对应的个体作为这一代中的最优个体，即应用最大最小优化方法，选择每一代中的最优个体。具体操作如下：

对于每个个体进行4种不确定状态分析，得到函数值y₁，y₂，y₃，y₄。在4种状态下，若都满足约束条件，则以最小函数值作为该个体的函数值，即yy＝min(y₁,y₂,y₃,y₄)。

从m个个体对应得到的函数值yy_j(j＝1,2,...,m)中选择最大的yy_j对应的个体，作为这一代的最优个体。

(3.5)判断是否满足鲁棒优化终止条件。终止条件可设置为当迭代数达到最大代数时，则停止鲁棒优化。

如果不满足终止条件，则把从上一代得到的最优个体采取变异、交叉、选择，对种群进行操作，产生下一代种群，并返回(3.4)。结合图3，具体操作如下：

适应度函数：

DE算法(差分进化算法)对包含m个个体的种群(即m个候选解X_i＝(x_i1,x_i2,...,x_in)，i＝1,2,...,m)进行进化。在进化的每一代G，每个个体X_i,G称为目标矢量。DE算法根据父代个体间的差分矢量进行变异、交叉和选择操作，其中变异操作产生变异矢量V_i,G＝(v_i1,G,v_i2,G,...,v_in,G,)，变异矢量与目标矢量交叉生成试验矢量U_i,G＝(u_i1,G,u_i2,G,...,u_in,G,)，试验矢量再与目标矢量通过选择操作产生下一代个体X_i,G+1。

变异操作：由于染色体中飞机编号必须且只能出现一次，为了保证后代变异运算后的合法性，算法采用染色体中随机确定两个变异位置进行位置交换的方式处理变异运算。首先随机确定两个变异位置，再进行交换。这种变异概率较大时将有助于优化结果的快速获得。

交叉操作：变异操作完成后，对目标矢量X_i,G和变异矢量V_i,G进行交叉操作，生成试验矢量U_i,G：

其中CR∈[0,1)为交叉概率常数，j_rand∈[1,m]中的随机整数，使试验矢量U_i,G不同于其相应的目标矢量X_i,G；rand_j[0,1]表示为确定试验矢量U_i,G第j维时产生的一个范围[0,1]内的均匀随机实数；n为问题空间维数。为了确保变异矢量V_i,G的每个“染色体”至少有一个“基因”遗传给下一代，第一个交叉操作的基因是随机取出V_i,G中的第j_rand位“基因”作为交叉后“染色体”U_i,G第j_rand位等位“基因”。后续的交叉操作过程，则是通过交叉概率CR来选取x_ij,G还是v_ij,G的等位基因作为u_ij,G的等位基因。

初步交叉后，同一个体中可能有重复的编号，将不重的数字保留，对于有重复的数字采用部分映射的方法进行消除。

选择操作：通过变异、交叉操作后，判断试验矢量U_i,G每一维是否超出优化问题参数空间的搜索空间，并将超出的各维用搜索空间的相应维内的均匀随机数进行初始化。然后，采用贪婪算法选择进入下一代种群个体X_i，G+1：

如果满足终止条件，则输出最优个体对应的函数值，得到鲁棒性和最优性兼容的鲁棒最优值。