[0109] 当even(s,FAQ)>even(s,FDQ)时，说明进港队列承担了过多的延误损失，此时需要调整作为公共资源的混合跑道使用权限，方案有两种：A、从进港专用跑道选取一航班移至混合跑道；B、从混合跑道选取一离港航班移至离港专用跑道；这两种方案都增加了进港航班对混合跑道的使用权限，若航班和目标位置选取合适，方案A可以降低进港队列的延误损失，方案B则在降低进港队列延误损失的同时，增加离港队列的延误损失，两种方法都可以缩小even(s,FAQ)与even(s,FDQ)的差距；当even(s,FAQ)
[0110] 令个体x代表MRADGHP的一种航班飞行安排计划，其在温度t下的启发式局部搜索步骤描述如下，每个温度下的局部搜索次数为Lst：
[0111] Step 1初始化搜索次数k＝1；
[0112] Step 2执行温度t下的局部搜索；
[0113] Step 2.1计算个体x的进、离港队列的even(s,FAQ)和even(s,FDQ)；
[0114] Step 2.2随机产出choice＝rand()％2，若choice＝0，则实施方案A,否则实施方案B，具体Step如下：
[0115] Step 2.3确定参与局部搜索的专用跑道r，在专用跑道中随机选择r，满足：若choice＝0且even(s,FAQ)＞even(s,FDQ)或者choice＝1且even(s,FAQ)＜even(s,FDQ)时，r为进港专用跑道，否则为离港专用跑道；
[0116] Step 2.4确定航班基因移出跑道Rout和移入跑道Rin，若choice＝0，则Rout＝r，Rin为任意混合跑道；若choice＝1，则Rout为任意混合跑道，Rin＝r；
[0117] Step 2.5在Rout中选取基因g，如果Rin为专用跑道，则基因g对应航班需要满足跑道使用属性；在跑道Rin的航班序列中随机产生一个位置，将基因g插入，得到新个体y；
[0118] Step 2.6计算x和y的适应值H(x)、H(y)，若H(x)＜H(y),则x＝y；若H(x)＝H(y)，转Step 3；
[0119] Step 2.7计算y劣于x时的接受概率pa＝exp(-(H(y)-H(x))/t)；
[0120] Step 2.8产生随机数pr＝random(0,1)，若pa＞pr，则x＝y，H(x)＝H(y)；
[0121] Step 3 k＝k+1，若k≤Lst，则转Step2继续执行，否则停止温度t下的局部搜索；
[0122] 7)混合遗传算法的设计
[0123] 将上述启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划。遗传算子设计说明：
[0124] 选择算子：采用适应度比例选择策略复制个体，高适应度个体以较高概率进行复制。另外，遗传算法的随机性可能导致一些优秀个体被丢失，所以结合精华保留机制，优秀个体取代群体中的最差个体，直接进入下一代。
[0125] 交叉算子：本文针对问题的多跑道特征，采用文献“基于自适应多局部搜索memetic算法的多跑道地面等待问题求解[J].系统工程理论与实践,2012,32(11):2523-2532.”中的顺序交叉算子对个体进行交叉操作，详细设计过程参见该文献。
[0126] 变异算子：在文献“An efficient genetic algorithm with uniform crossover for air traffic control[J].Computers&Operations Research,2009,36(1):245-259.”的基础上提出如下的变异算子：1)算法的前期，逆序随机选取的某跑道中两点间航班基因；算法的后期，交换随机选取的某跑道上的相邻基因；2)随机选取不同跑道中的两个基因，并交换他们的位置；或者将某跑道上的航班基因移至另一跑道航班序列的尾部。
[0127] 交叉、变异概率：个体参与交叉、变异的概率采用固定形式。
[0128] 将所述步骤6)中启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划；所述混合GA对MRADGHP进行求解过程如下：
[0129] Step 1生成规模为popsize的初始群体pop，其中部分个体按航班使用跑道的计划时间先后次序产生，其余个体随机生成，计算个体的适应度函数值；设置模拟退火算法初始温度ts、终止温度te、温度下降率td以及Lst；设置最大进化代数maxgen、交叉概率Pc、变异概率Pm以及最优个体取代当前代中的最差个体数Subn，令代数g＝1；
[0130] Step 2使用上述适应度比例选择策略从pop中选取进入交配池的个体，并对交配池中的个体进行交叉、变异操作，生成新个体并组成临时种群temp_pop；
[0131] Step 3对所有x∈temp_pop执行模拟退火局部搜索；
[0132] Step 3.1初始化温度t＝ts；
[0133] Step 3.2使用步骤6)中局部搜索策略对x执行温度t下的模拟退火局部搜索，寻找适应度函数值更高、延误损失在进、离港队列之间分配更合理的个体代替x；
[0134] Step 3.3退温t＝td*t；
[0135] Step 3.4如果t＜te，结束个体x的局部搜索；否则转本步骤中所述Step3.2重新开始当前温度t下的局部搜索；
[0136] Step 4令pop＝temp_pop，得到新一代种群；
[0137] Step 5执行精华保留策略，以群体中的最优个体取代pop中Subn个最差个体；
[0138] Step 6 g＝g+1；
[0139] Step 7如果g＞maxgen，则结束算法，否则转本步骤中所述Step2继续执行。
[0140] 本实施例为了验证模型与算法的有效性，采用多组数据进行了测试，均取得了比较好的优化效果。本方案对有代表性的算例使用先来先服务FCFS、标准遗传算法(Standard GA,SGA)、无问题知识启发的随机局部搜索遗传算法(Stochastic Local Search GA,SLSGA)以及HLSGA进行计算，并对各算法计算结果作对比分析。
[0141] 1、仿真算例及算法参数设置
[0142] 以三条跑道机场航班数据为例，其中两条跑道分别用于进离港航班专用，另一条为混合使用跑道，选取25分钟内到达35个航班为算例，进港、离港以及续航航班数分别为17、18和5架。地面延误费用的计算采用现有技术中的航班延误显性成本计算公式：
[0143]
[0144] 航班p的CGp由该航班的运营成本 航空公司盈利损失 以及乘客经济损失组成，式中pp、vp和hp分别表示航班p的平均票价、平均利润率以及平均飞行时间，取值分别为750元、2.2％和2h，np表示乘客数，lp表示每名乘客的平均延误成本，国内乘客为50元/h，国际乘客为100元/h；运营成本根据航班的机型(重型(H)、中型(M)、小型(S))分别设定为4167、2916、208元/h。续航航班最短转场时间TRMh为20m，Sep(r,p1,p2)按国际民航组织规定的最小安全尾流间隔进行间隔，式(3)中系数kc取1.4。
[0145] HLSGA、SGA初始群体规模为180，其中按使用跑道时间先后顺序生成的个体数为18，精华保留参数亦为18。最大进化代数为50代，交叉概率、变异概率分别为0.94、0.25，适应度函数常量C＝50；模拟退火局部搜索算法参数，初始温度：100，终止温度：0.001，温度下降率：0.50，Lst＝10。本方案以C语言为工具实现算法，VC6.0中调试、运行。算例航班信息如表1所示，其中续号表示续航航班前后航班的对应号。
[0146] 表1仿真算例航班数据
[0147]
[0148] 2、仿真结果及分析
[0149] 对表1中的35个航班在25分钟内的进离港问题使用各算法进行排序，航班使用跑道的计划时间以及算法运行结果如表2所示。ETi表示航班使用跑道i的计划时间，时间采用格式：mm:ss，STA、GT、GC分别表示航班排序后的跑道使用时间、地面延误时间和费用，其中延误时间单位为s，延误费用单位为元，R代表航班使用的跑道。
[0150] 表2仿真实验排序结果
[0151]
[0152]
[0153] (1)问题的优化效果
[0154] 表1中所示进离港队列运输服务需求量分别为57.19、104.41，以21号航班为标准，则两队列的当量航班总数分别为21.41和39.09。表2中各算法排序结果统计如表3所示：
[0155] 表3实验数据统计结果
[0156]
[0157] 表中s代表各算法的排序结果方案，为叙述方便，以下使用算法名称代表该算法对应的航班安排计划。由表3数据显示知：
[0158] 1)SGA、SLSGA、HLSGA相对于FCFS算法，总延误成本分别降低了21.8％、50.5％和60.1％，HLSGA对应延误成本有了明显下降，且下降幅度最大。
[0159] 2)FCFS对应进离港队列延误费用分别为831.9和816.6元，分配较均等，然而由于航班当量总数的差异，致使当量航班平均延误损失even(FCFS,FAQ)与even(FCFS,FDQ)分别为38.85、20.89，前者近两倍于后者。HLSGA的even(HLSGA,FAQ)与even(HLSGA,FDQ)分别为10.95和10.82，延误损失分配均匀度偏差distance(HLSGA)由FCFS的17.96降至0.13，延误损失在进离港队列之间分配的合理性有了显著提高。SGA、SLSGA延误损失分配公平程度相对于FCFS有所改善，但较微弱。
[0160] (2)延误损失协同优化分析
[0161] 表4为FCFS安排下各跑道的航班序列，even(FCFS,FAQ)远高于even(FCFS,FDQ)。算例中进港专用跑道航班优先系数为0.93，混合跑道进港航班优先系数为0.47，由此产生了航班优先权的高压。所以HLSGA在跑道之间移动了部分进港航班，如FA10、FA15等，结果如表5所示。表4和表5中混合跑道上的进港航班虽然都为6架，但运输需求量由19.2增至21.7，而离港航班则由28.48降至20.49，专用跑道和混合跑道上的进港航班优先系数为0.86、0.53，趋于缓和，说明进港航班给予了较高的混合跑道使用权。经过优化，进港航班延误损失831.9降至234.5，离港航班由816.6降至423.1，下降幅度明显小于进港队列，进离港队列的当量航班平均延误损失分别为10.95和10.82，distance(HLSGA)由FCFS的17.96降至0.13。
[0162] 表4 FCFS各跑道航班序列
[0163]
[0164] 表5 HLSGA各跑道航班序列
[0165]
[0166] 由上述表格数据的描述知，本方案实施例中所提模型及其求解算法HLSGA在降低总延误成本、进离港队列延误损失分配等方面均都取得了较显著的效果，求解过程说明了HLSGA良好的寻优能力以及收敛性。
