CN107016462B - 一种基于混合遗传算法的多跑道机场航班起降协同优化方法 - Google Patents

Abstract

本发明公开了一种基于混合遗传算法的多跑道机场航班起降协同优化方法，包括以下步骤：1)描述航班列队组成；2)设置航班优先权；3)设定单条跑道上航班的优先系数；4)建立多跑道机场进离港地面等待问题协同优化模型；5)设置协同优化评价标准；6)提出启发式局部搜索策略；7)混合遗传算法的设计；本发明旨在解决地面等待策略在多跑道机场进、离港地面等待问题中的应用难题，使得延误费用能够在进离港航班队列之间进行合理的分配，相比现有技术本发明建立的模型以降低延误损失为目标，实现延误损失的协同优化；使用当量航班平均延误损失作为启发信息，引导局部搜索朝着既定的方向进行，避免了搜索的盲目性，对延误费用的协同优化有了明显的提高。

Description

一种基于混合遗传算法的多跑道机场航班起降协同优化方法

技术领域

本发明涉及一种降低航班延误费用的优化方法，尤其涉及一种基于混合遗传算法的多跑道机场航班起降协同优化方法。

背景技术

随着我国经济的高速发展，空中运输需求量持续上升，由此带来了我国航空运输业的兴起和快速发展。2014年，我国机场吞吐量各项指标再创历史新高，其中旅客吞吐量为39195万人次，比2013年增长的幅度为10.7％，仅国内航线就完成了36040万人次，其中北京、上海和广州三大城市机场旅客吞吐量占全部机场旅客吞吐量的28.3％。由于空中交通流量的激增，我国现有的航空运输设备和管理技术变得难以适应；在空中交通流量的高峰期，会出现严重的空中交通拥挤，从而导致航班大面积延误。2014年，我国航班的正常率仅为68.37％，航班延误既造成巨额的经济损失，也给飞机飞行带来安全隐患。美国每年因为航班延误造成的经济损失达30亿美元，欧洲的情形更加糟糕，而且延误损失呈现逐增的趋势。我国三大航空枢纽中心北京、上海、广州的航班延误损失亦是巨大，同时航班延误也严重影响了乘客的正常生活。

地面等待策略是目前解决空中交通拥挤的主要办法，因为地面等待较空中等待费用低且安全系数高，其基本思想是确定飞机的最佳起飞时间，通过起飞机场的地面等待调节空中交通网络的航班流量，减少延误时间，从而降低延误损失，并保证飞行的安全与准时。随着机场多跑道建设的兴起，如我国的首都、浦东、广州、成都等机场等都存在多条跑道，安徽建设并已投入运营中的合肥新桥机场计划投建四条跑道，这些机场构成了我国航空运输的中坚力量。然而，航班在多跑道机场起降过程的协调运作愈加复杂化，除北京、上海和广州机场之外，我国大多数多跑道机场的运行时间不长，积累经验也不足，特别是在管制策略、运行法规和规范的研究方面显得较为薄弱。针对我国航空运输业发展的现状，基于地面等待策略的多跑道机场中航班起降问题的研究几近空白。

地面等待问题(Ground-holdingProblem,GHP)成为众多科研机构的研究对象，Richetta等对地面等待问题(Ground-holdingProblem,GHP)展开了一系列的分析、研究，提出了问题的模型以及求解算法，这些工作都是围绕进港航班进行讨论的，且往往只考虑单跑道目标机场。然而，任何机场都存在航班的进、离港，且过程相互影响，Gilbo考虑机场进场和离场容量的曲线关系，通过调整航班的优先系数，实现了机场进离港容量的相互转化，奠定了进离港地面等待问题(Arrival-Departure GHP,ADGHP)的研究基础；马正平等在此模型基础上，考虑续航航班的转场时间要求，提出了结合RBS和Compress思想的ADGHP动态规划求解算法；然而这些模型忽略了飞机延误费用的差异，张洪海在考虑该因素的基础上通过合理转化进离场容量，结合协同决策思想，实现了各航空公司之间延误费用的协同优化。上述ADGHP模型是基于单跑道或将跑道视为系统进行分析的，随着航空业的蓬勃发展，多跑道进离港地面等待问题(Multi-RunwayADGHP,MRADGHP)成为当前GHP研究的热点。罗喜伶根据跑道的使用方式，分别对进港航班和离港航班的进离港过程进行了形式化的描述，对确定型和随机型MRADGHP进行了讨论，是目前关于该问题较全面的研究成果。然而该模型未对起降混合使用跑道进行分析和描述，且航班优先系数没有联系进离港航班的实际情况，影响机场跑道资源的合理分配，另外忽略了航班的延误成本差异。目前一些大型机场拥有多条跑道，如我国首都机场设置了三条跑道，其中两条分别用于飞机的起飞和降落，另一条则根据实际需要用于飞机的起降混合使用。显然，建立一种有效的MRADGHP优化模型具有十分重要的现实意义。

MRADGHP是一类新的组合优化问题，较GHP、ADGHP更为复杂，是NP完全的，其求解的难点在于航班的跑道指派以及进离港航班延误费用的协同优化。若采用常规算法如线性规划法解决此类问题，存在算法运行耗时较长、解的品质难以保证等缺陷。遗传算法(GeneticAlgorithm，GA)以其良好的全局搜索能力而广泛应用于诸多工程领域，如GHP的求解，然而较弱的局部搜索特性容易使算法陷入局部最优，而无法保证解的品质。Kazarlis提出了引入爬山法的GA，并将其用于优化问题的求解；苏生等根据问题特征，提出了高效的局部搜索算子，并与GA结合，对间歇过程生产调度、大规模复杂网络社区探测等问题进行求解，优化效果明显。随着生产的不断发展，工程中面临的问题会愈加复杂，努力提高GA的问题求解能力，增强局部搜索能力成为GA研究的一种趋势。

针对上述问题，本发明主要采取如下策略予以解决：(1)以多跑道机场为场景，根据进离港航班的实际组成及跑道计划分配情况，设置航班的优先系数，以达到对混合跑道的合理分配，调节专用跑道的负载量；(2)根据航班对跑道的使用优先权，建立一种MRADGHP事件驱动优化模型，在降低航班总延误费用的同时，实现延误损失在进离港航班之间延误费用的协同优化；同时考虑航班延误成本差别、续航航班转场时间等多种因素，以更全面地描述这一问题的特性；(3)根据MRADGHP的特点，提出了一种启发式局部搜索策略，依据进离港航班在各跑道的分配和延误损失情况，在跑道之间移动航班，以使得延误损失在进离港航班之间合理分配；针对问题的复杂性，将该策略与GA结合，形成一种混合GA(HybridGA,HGA)，并用于对问题模型的求解。

本发明中将启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划。遗传算子设计说明：

选择算子：采用适应度比例选择策略复制个体，高适应度个体以较高概率进行复制。另外，遗传算法的随机性可能导致一些优秀个体被丢失，所以结合精华保留机制，优秀个体取代群体中的最差个体，直接进入下一代。

交叉算子：本文针对问题的多跑道特征，采用文献“基于自适应多局部搜索memetic算法的多跑道地面等待问题求解[J].系统工程理论与实践,2012,32(11):2523-2532.”中的顺序交叉算子对个体进行交叉操作，详细设计过程参见该文献。

变异算子：在文献“An efficient genetic algorithm withuniform crossoverfor airtraffic control[J].Computers&Operations Research,2009,36(1):245-259.”的基础上提出如下的变异算子：1)算法的前期，逆序随机选取的某跑道中两点间航班基因；算法的后期，交换随机选取的某跑道上的相邻基因；2)随机选取不同跑道中的两个基因，并交换他们的位置；或者将某跑道上的航班基因移至另一跑道航班序列的尾部。

交叉、变异概率：个体参与交叉、变异的概率采用固定形式。

发明内容

本发明的目的是为了克服现有技术的不足，提供了一种基于混合遗传算法的多跑道机场航班起降协同优化方法，以解决现有技术中航班混合跑道的分配不合理，专用跑道的负载量不好调节，以及延误损失在进、离港航班之间分配不合理的技术问题；

本发明采用的技术方案如下：本发明公开了一种基于混合遗传算法的多跑道机场航班起降协同优化方法，其特征在于，包括以下步骤：

1)描述航班列队组成

航班的单位时间延误成本反映了该航班被延误时将造成的经济损失，单位时间延误成本同时还体现了该航班应该承担的延误损失；从而，进、离港队列的航班组成可表示为相应队列中航班单位时间延误成本的叠加，为叙述方便，称该叠加为队列的服务需求量，所述队列的服务需求量定义如下：

定义1设由M架航班组成队列FS，令CD_m表示FS中飞机m的单位时间地面延误损失系数，令

服务需求量反映了队列航班如果被延误则会造成的延误损失量，即队列航班使用跑道总的期望值，同时也体现了该队列航班应该承担的延误损失；

2)设置航班优先权

航班对跑道的使用优先权体现了飞行管制人员对航班类型的倾向性，多跑道机场中起降航班的优先性考虑了以下两个因素：

a.队列服务需求量

队列服务需求量划分为两部分，即当前已服务的需求量和尚待服务的需求量，显然航班使用跑道的优先权正比于所在队列的总需求量以及尚待服务的需求量，反比于该队列已服务的需求量，因为已服务需求量体现了跑道资源在一段时间内被该队列使用情况；

b.专用跑道和混合跑道的构成

航班进行起降时，机场为其分配专用跑道或混合跑道，而机场中进、离港专用跑道以及混合跑道数可能存在差异，所以为了均衡航班队列的延误损失，航班在专用和混合跑道中选择一条合理的跑道进行起降；

因此，混合跑道rm上航班nrm的优先系数

其中，FRMA、FRMD和FRM分别为混合跑道上的进港航班、离港航班及所有航班，FAQ为进港队列，FDQ为离港队列；

其中，(2)式中将进港专用跑道视为一个系统，以Dtrans(FAQ)在专用和混合跑道上的分配比例作为相应航班的优先系数,来调节进港队列FAQ在专用、混合跑道上的分布；以Dtrans(FDQ)在专用和混合跑道上的分配比例作为相应航班的优先系数,来调节离港队列FDQ在专用、混合跑道上的分布；

实际中，由于进港专用跑道数RA和离港专用跑道数RD的不同，进一步优化得到进港航班优先系数为Dtrans(FRA)/RA/Dtrans(FAQ)，以均衡相应队列航班在专用跑道上的优先权，其中，FRA为专用跑道上进港航班；对于混合跑道，进港航班优先系数为其服务需求量与混合跑道服务总需求量的比例，即Dtrans(FRMA)/Dtrans(FRM)；

3)设定单条跑道上航班的优先系数

令

采用cr(r)作为跑道r上航班的优先系数，当跑道r上航班延误损失较大时，其对应的优先系数则较大，反之亦然，所以通过系数cr(r)可调节跑道r的负载量；式中，表示跑道r上航班nr在时间使用跑道r时所产生的地面延误费用；kc为常量；

4)建立多跑道机场进离港地面等待问题协同优化模型

以航班进离港专用跑道以及混合跑道的优先权为基础，建立多跑道机场进离港地面等待问题协同优化模型，目标函数描述如下：

式中，RA、RD分别为进港专用跑道数和离港专用跑道数；RM为混合跑道数；N_r为分配到跑道r上的航班数；表示飞机p在跑道r上进行起降时的分配下降时间；

5)设置协同优化评价标准

当GA通过遗传操作生成新的个体后，计算该个体的进、离港延误费用，记为CPA和CPD；由于所述定义1中Dtrans(FS)反映了队列FS的服务需求量，不能直观表达其航班组成，故在所述定义1的基础上，对现有的当量航班概念重新定义，定义如下：

定义2设FQ为一航班队列，任取航班p∈FQ，以其为基准，则航班q∈FQ的当量为两者单位时间地面延误费用之比：

ν(p,q)＝CG_q/CG_p (5)

FQ的当量航班总数说明了该队列的航班组成情况，从而进离港队列的航班组成差异可以通过队列当量航班总数之间的比较进行说明，记进、离港队列FAQ、FDQ的当量航班总数分别为V(p,FAQ)和V(p,FDQ)；

定义3队列的延误费用与其当量航班总数之比称为该队列的当量航班平均延误损失；

航班安排计划s下的进、离港队列当量航班平均延误损失分别为CPA/V(p,FAQ)和CPD/V(p,FDQ),并分别记为even(s,FAQ)和even(s,FDQ)；当even(s,FAQ)与even(s,FDQ)的值越接近，说明s的延误费用分配越合理，反之则说明不公平；

定义4设even(s,FAQ)和even(s,FDQ)分别为s对应进、离港当量航班平均延误损失，令：distance(s)＝|even(s,FAQ)-even(s,FDQ)|，称distance(s)为计划s延误损失的分配均匀度偏差；

6)提出启发式局部搜索策略

当even(s,FAQ)>even(s,FDQ)时，说明进港队列承担了过多的延误损失，此时需要调整作为公共资源的混合跑道使用权限，方案有两种：A、从进港专用跑道选取一航班移至混合跑道；B、从混合跑道选取一离港航班移至离港专用跑道；这两种方案都增加了进港航班对混合跑道的使用权限，若航班和目标位置选取合适，方案A可以降低进港队列的延误损失，方案B则在降低进港队列延误损失的同时，增加离港队列的延误损失，两种方法都可以缩小even(s,FAQ)与even(s,FDQ)的差距；当even(s,FAQ)<even(s,FDQ)时，说明离港队列承担了过多的延误损失，此时亦需要调整作为公共资源的混合跑道使用权限，调整方案：C、从离港专用跑道上随机选取一航班移至混合跑道的某一位置；D、从混合跑道上随机选取一进港航班移至进港专用跑道上的某一位置；相应地，这两种方案都增加了离港航班对混合跑道的使用权限，且在降低离港队列延误损失的同时，增加进港队列的延误损失，均缩小了even(s,FAQ)与even(s,FDQ)的差距；

令个体x代表MRADGHP的一种航班飞行安排计划，其在温度t下的启发式局部搜索步骤描述如下，每个温度下的局部搜索次数为Lst：

Step 1初始化搜索次数k＝1；

Step 2执行温度t下的局部搜索；

Step 2.1计算个体x的进、离港队列的even(s,FAQ)和even(s,FDQ)；

Step 2.2随机产出choice＝rand()％2，若choice＝0，则实施方案A,否则实施方案B，具体Step如下：

Step 2.3确定参与局部搜索的专用跑道r，在专用跑道中随机选择r，满足：若choice＝0且even(s,FAQ)＞even(s,FDQ)或者choice＝1且even(s,FAQ)＜even(s,FDQ)时，r为进港专用跑道，否则为离港专用跑道；

Step 2.4确定航班基因移出跑道R_out和移入跑道R_in，若choice＝0，则R_out＝r，R_in为任意混合跑道；若choice＝1，则R_out为任意混合跑道，R_in＝r；

Step 2.5在R_out中选取基因g，如果R_in为专用跑道，则基因g对应航班需要满足跑道使用属性；在跑道R_in的航班序列中随机产生一个位置，将基因g插入，得到新个体y；

Step 2.6计算x和y的适应值H(x)、H(y)，若H(x)＜H(y),则x＝y；若H(x)＝H(y)，转Step 3；

Step 2.7计算y劣于x时的接受概率pa＝exp(-(H(y)-H(x))/t)；

Step 2.8产生随机数pr＝random(0,1)，若pa＞pr，则x＝y，H(x)＝H(y)；

Step 3 k＝k+1，若k≤Lst，则转Step2继续执行，否则停止温度t下的局部搜索；

7)混合遗传算法的设计

将步骤6)中启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划；所述混合GA对MRADGHP进行求解的过程如下：

Step 1生成规模为popsize的初始群体pop，其中部分个体按航班使用跑道的计划时间先后次序产生，其余个体随机生成，计算个体的适应度函数值；设置模拟退火算法初始温度ts、终止温度te、温度下降率td以及Lst；设置最大进化代数maxgen、交叉概率Pc、变异概率Pm以及最优个体取代当前代中的最差个体数Subn，令代数g＝1；

Step 2使用上述适应度比例选择策略从pop中选取进入交配池的个体，并对交配池中的个体进行交叉、变异操作，生成新个体并组成临时种群temp_pop；

Step 3对所有x∈temp_pop执行模拟退火局部搜索；

Step 3.1初始化温度t＝ts；

Step 3.2使用步骤6)中局部搜索策略对x执行温度t下的模拟退火局部搜索，寻找适应度函数值更高、延误损失在进、离港队列之间分配更合理的个体代替x；

Step 3.3退温t＝td*t；

Step 3.4如果t＜te，结束个体x的局部搜索；否则转本步骤中所述Step3.2重新开始当前温度t下的局部搜索；

Step 4令pop＝temp_pop，得到新一代种群；

Step 5执行精华保留策略，以群体中的最优个体取代pop中Subn个最差个体；

Step 6 g＝g+1；

Step 7如果g＞maxgen，则结束算法，否则转本步骤中所述Step2继续执行。

本发明公开了一种基于混合遗传算法的多跑道机场航班起降协同优化方法，本发明相比现有技术具有以下优点：建立了一种多跑道进离港GHP优化模型，该模型以降低延误损失为目标，并通过航班优先系数的调节，将作为公共资源的混合跑道合理地分配给进离港队列，实现延误损失的协同优化。鉴于问题模型的复杂性，设计了一种启发式局部搜索算子，使用当量航班平均延误损失作为启发信息，引导局部搜索朝着既定的方向进行，从而避免了搜索的盲目性。将该算子嵌入GA，形成HGA对问题求解，通过对典型仿真算例进行的计算，结果表明了所提模型和问题解决方法对延误费用的协同优化有了明显的提高。

具体实施方式

实施例1

实施例1公开了一种基于混合遗传算法的多跑道机场航班起降协同优化方法，其特征在于，包括以下步骤：

1)描述航班列队组成

航班的单位时间延误成本反映了该航班被延误时将造成经济损失，重型机、国际航班等一般具有较高的单位时间延误成本，通常给予此类航班较高的跑道使用优先权。然而，这样会导致其他航班承担过多的延误损失，有失公允，所以单位时间延误成本同时还体现了该航班应该承担的延误损失。从而，进离港队列的航班组成可表示为相应队列中航班单位时间延误成本的叠加，为叙述方便，称该叠加为队列的服务需求量，其定义如下：

定义1设由M架航班组成队列FS，令CD_m表示FS中飞机m的单位时间地面延误损失系数，令

服务需求量反映了队列航班如果被延误则会造成的延误损失量，即队列航班使用跑道总的期望值，同时也体现了该队列航班应该承担的延误损失；

2)设置航班优先权

航班对跑道的使用优先权体现了飞行管制人员对航班类型的倾向性，通常按照先来先服务策略或者进港航班给以较高的优先权。然而，这些措施将无法降低航班的总延误损失，且没有考虑离港队列的航班组成。多跑道机场中起降航班的优先性考虑了以下两个因素：

a.队列服务需求量

队列服务需求量划分为两部分，即当前已服务的需求量和尚待服务的需求量，显然航班使用跑道的优先权正比于所在队列的总需求量以及尚待服务的需求量，反比于该队列已服务的需求量，因为已服务需求量体现了跑道资源在一段时间内被该队列使用情况；

b.专用跑道和混合跑道的构成

航班进行起降时，机场为其分配专用跑道或混合跑道，而机场中进、离港专用跑道以及混合跑道数可能存在差异，所以为了均衡航班队列的延误损失，航班在专用和混合跑道中选择一条合理的跑道进行起降；

因此，混合跑道rm上航班nrm的优先系数

其中，FRMA、FRMD和FRM分别为混合跑道上的进港航班、离港航班及所有航班，FAQ为进港队列，FDQ为离港队列；

其中，(2)式中将进港专用跑道视为一个系统，以Dtrans(FAQ)在专用和混合跑道上的分配比例作为相应航班的优先系数,来调节进港队列FAQ在专用、混合跑道上的分布；以Dtrans(FDQ)在专用和混合跑道上的分配比例作为相应航班的优先系数,来调节离港队列FDQ在专用、混合跑道上的分布；

实际中，由于进港专用跑道数RA和离港专用跑道数RD的不同，上述分布策略不尽合理。本实施例中以专用跑道上航班服务需求量的均值作为航班的优先系数，进一步优化得到进港航班优先系数为Dtrans(FRA)/RA/Dtrans(FAQ)，以均衡相应队列航班在专用跑道上的优先权，其中，FRA为专用跑道上进港航班；对于混合跑道，进港航班优先系数为其服务需求量与混合跑道服务总需求量的比例，即Dtrans(FRMA)/Dtrans(FRM)；以避免因为进港专用跑道航班优先系数的挤压，而使得混合跑道分担过多的进港航班；同理，可定义离港航班的优先系数。另外，混合跑道中航班优先系数的设定还可以根据分配在混合跑道上的进离港服务需求量，并以此来调整航班次序。现有技术通常将专用跑道进行整体考虑，会导致一些跑道负载过重，故根据每条跑道上航班的延误损失设定该跑道的优先系数，以达到均匀分配航班的目的。

3)设定单条跑道上航班的优先系数

令

采用cr(r)作为跑道r上航班的优先系数，当跑道r上航班延误损失较大时，其对应的优先系数则较大，反之亦然，所以通过系数cr(r)可调节跑道r的负载量；式中，表示跑道r上航班nr在时间使用跑道r时所产生的地面延误费用；kc为常量；因为值过小，引入常量kc；

4)建立多跑道机场进离港地面等待问题协同优化模型

以航班进离港专用跑道以及混合跑道的优先权为基础，建立多跑道机场进离港地面等待问题协同优化模型，目标函数描述如下：

式中，RA、RD分别为进港专用跑道数和离港专用跑道数；RM为混合跑道数；N_r为分配到跑道r上的航班数；表示飞机p在跑道r上进行起降时的分配下降时间；

5)设置协同优化评价标准

当GA通过遗传操作生成新的个体后，计算该个体的进、离港延误费用，记为CPA和CPD；实施例中旨在实现进、离港队列延误费用的协同优化，由于航班队列组成的差异，所以平均化CPA和CPD难以达到延误费用的合理分配。

由于所述定义1中Dtrans(FS)反映了队列FS的服务需求量，不能直观表达其航班组成，故在所述定义1的基础上，对现有的当量航班概念重新定义，定义如下：

定义2设FQ为一航班队列，任取航班p∈FQ，以其为基准，则航班q∈FQ的当量为两者单位时间地面延误费用之比：

ν(p,q)＝CG_q/CG_p (5)

FQ的当量航班总数说明了该队列的航班组成情况，从而进离港队列的航班组成差异可以通过队列当量航班总数之间的比较进行说明，记进、离港队列FAQ、FDQ的当量航班总数分别为V(p,FAQ)和V(p,FDQ)；

定义3队列的延误费用与其当量航班总数之比称为该队列的当量航班平均延误损失；

航班安排计划s下的进、离港队列当量航班平均延误损失分别为CPA/V(p,FAQ)、CPD/V(p,FDQ)，并分别记为even(s,FAQ)和even(s,FDQ)；当even(s,FAQ)与even(s,FDQ)的值越接近，说明s的延误费用分配越合理，反之则说明不公平；

定义4设even(s,FAQ)和even(s,FDQ)分别为s对应进、离港当量航班平均延误损失，令：distance(s)＝|even(s,FAQ)-even(s,FDQ)|，称distance(s)为计划s延误损失的分配均匀度偏差；

distance(s)的大小反映了s对应延误损失分配的合理性。在个体局部搜索过程中，可以通过航班基因的移动使得distance(s)趋于0；所以，distance(s)可作为进离港航班队列延误费用协同优化的评价标准。

6)提出启发式局部搜索策略

当even(s,FAQ)>even(s,FDQ)时，说明进港队列承担了过多的延误损失，此时需要调整作为公共资源的混合跑道使用权限，方案有两种：A、从进港专用跑道选取一航班移至混合跑道；B、从混合跑道选取一离港航班移至离港专用跑道；这两种方案都增加了进港航班对混合跑道的使用权限，若航班和目标位置选取合适，方案A可以降低进港队列的延误损失，方案B则在降低进港队列延误损失的同时，增加离港队列的延误损失，两种方法都可以缩小even(s,FAQ)与even(s,FDQ)的差距；当even(s,FAQ)<even(s,FDQ)时，说明离港队列承担了过多的延误损失，此时亦需要调整作为公共资源的混合跑道使用权限，调整方案：C、从离港专用跑道上随机选取一航班移至混合跑道的某一位置；D、从混合跑道上随机选取一进港航班移至进港专用跑道上的某一位置；相应地，这两种方案都增加了离港航班对混合跑道的使用权限，且在降低离港队列延误损失的同时，增加进港队列的延误损失，也均缩小了even(s,FAQ)与even(s,FDQ)的差距；

令个体x代表MRADGHP的一种航班飞行安排计划，其在温度t下的启发式局部搜索步骤描述如下，每个温度下的局部搜索次数为Lst：

Step 1初始化搜索次数k＝1；

Step 2执行温度t下的局部搜索；

Step 2.1计算个体x的进、离港队列的even(s,FAQ)和even(s,FDQ)；

Step 2.2随机产出choice＝rand()％2，若choice＝0，则实施方案A,否则实施方案B，具体Step如下：

Step 2.3确定参与局部搜索的专用跑道r，在专用跑道中随机选择r，满足：若choice＝0且even(s,FAQ)＞even(s,FDQ)或者choice＝1且even(s,FAQ)＜even(s,FDQ)时，r为进港专用跑道，否则为离港专用跑道；

Step 2.4确定航班基因移出跑道R_out和移入跑道R_in，若choice＝0，则R_out＝r，R_in为任意混合跑道；若choice＝1，则R_out为任意混合跑道，R_in＝r；

Step 2.5在R_out中选取基因g，如果R_in为专用跑道，则基因g对应航班需要满足跑道使用属性；在跑道R_in的航班序列中随机产生一个位置，将基因g插入，得到新个体y；

Step 2.6计算x和y的适应值H(x)、H(y)，若H(x)＜H(y),则x＝y；若H(x)＝H(y)，转Step 3；

Step 2.7计算y劣于x时的接受概率pa＝exp(-(H(y)-H(x))/t)；

Step 2.8产生随机数pr＝random(0,1)，若pa＞pr，则x＝y，H(x)＝H(y)；

Step 3 k＝k+1，若k≤Lst，则转Step2继续执行，否则停止温度t下的局部搜索；

7)混合遗传算法的设计

将上述启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划。遗传算子设计说明：

选择算子：采用适应度比例选择策略复制个体，高适应度个体以较高概率进行复制。另外，遗传算法的随机性可能导致一些优秀个体被丢失，所以结合精华保留机制，优秀个体取代群体中的最差个体，直接进入下一代。

交叉算子：本文针对问题的多跑道特征，采用文献“基于自适应多局部搜索memetic算法的多跑道地面等待问题求解[J].系统工程理论与实践,2012,32(11):2523-2532.”中的顺序交叉算子对个体进行交叉操作，详细设计过程参见该文献。

变异算子：在文献“An efficient genetic algorithm with uniform crossoverfor air traffic control[J].Computers&Operations Research,2009,36(1):245-259.”的基础上提出如下的变异算子：1)算法的前期，逆序随机选取的某跑道中两点间航班基因；算法的后期，交换随机选取的某跑道上的相邻基因；2)随机选取不同跑道中的两个基因，并交换他们的位置；或者将某跑道上的航班基因移至另一跑道航班序列的尾部。

交叉、变异概率：个体参与交叉、变异的概率采用固定形式。

将所述步骤6)中启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划；所述混合GA对MRADGHP进行求解过程如下：

Step 1生成规模为popsize的初始群体pop，其中部分个体按航班使用跑道的计划时间先后次序产生，其余个体随机生成，计算个体的适应度函数值；设置模拟退火算法初始温度ts、终止温度te、温度下降率td以及Lst；设置最大进化代数maxgen、交叉概率Pc、变异概率Pm以及最优个体取代当前代中的最差个体数Subn，令代数g＝1；

Step 2使用上述适应度比例选择策略从pop中选取进入交配池的个体，并对交配池中的个体进行交叉、变异操作，生成新个体并组成临时种群temp_pop；

Step 3对所有x∈temp_pop执行模拟退火局部搜索；

Step 3.1初始化温度t＝ts；

Step 3.2使用步骤6)中局部搜索策略对x执行温度t下的模拟退火局部搜索，寻找适应度函数值更高、延误损失在进、离港队列之间分配更合理的个体代替x；

Step 3.3退温t＝td*t；

Step 3.4如果t＜te，结束个体x的局部搜索；否则转本步骤中所述Step3.2重新开始当前温度t下的局部搜索；

Step 4令pop＝temp_pop，得到新一代种群；

Step 5执行精华保留策略，以群体中的最优个体取代pop中Subn个最差个体；

Step 6 g＝g+1；

Step 7如果g＞maxgen，则结束算法，否则转本步骤中所述Step2继续执行。

本实施例为了验证模型与算法的有效性，采用多组数据进行了测试，均取得了比较好的优化效果。本方案对有代表性的算例使用先来先服务FCFS、标准遗传算法(StandardGA,SGA)、无问题知识启发的随机局部搜索遗传算法(Stochastic Local Search GA,SLSGA)以及HLSGA进行计算，并对各算法计算结果作对比分析。

1、仿真算例及算法参数设置

以三条跑道机场航班数据为例，其中两条跑道分别用于进离港航班专用，另一条为混合使用跑道，选取25分钟内到达35个航班为算例，进港、离港以及续航航班数分别为17、18和5架。地面延误费用的计算采用现有技术中的航班延误显性成本计算公式：

航班p的CG_p由该航班的运营成本航空公司盈利损失以及乘客经济损失组成，式中p_p、v_p和h_p分别表示航班p的平均票价、平均利润率以及平均飞行时间，取值分别为750元、2.2％和2h，n_p表示乘客数，l_p表示每名乘客的平均延误成本，国内乘客为50元/h，国际乘客为100元/h；运营成本根据航班的机型(重型(H)、中型(M)、小型(S))分别设定为4167、2916、208元/h。续航航班最短转场时间TRM_h为20m，Sep(r,p1,p2)按国际民航组织规定的最小安全尾流间隔进行间隔，式(3)中系数kc取1.4。

HLSGA、SGA初始群体规模为180，其中按使用跑道时间先后顺序生成的个体数为18，精华保留参数亦为18。最大进化代数为50代，交叉概率、变异概率分别为0.94、0.25，适应度函数常量C＝50；模拟退火局部搜索算法参数，初始温度：100，终止温度：0.001，温度下降率：0.50，Lst＝10。本方案以C语言为工具实现算法，VC6.0中调试、运行。算例航班信息如表1所示，其中续号表示续航航班前后航班的对应号。

表1仿真算例航班数据

2、仿真结果及分析

对表1中的35个航班在25分钟内的进离港问题使用各算法进行排序，航班使用跑道的计划时间以及算法运行结果如表2所示。ETi表示航班使用跑道i的计划时间，时间采用格式：mm:ss，STA、GT、GC分别表示航班排序后的跑道使用时间、地面延误时间和费用，其中延误时间单位为s，延误费用单位为元，R代表航班使用的跑道。

表2仿真实验排序结果

(1)问题的优化效果

表1中所示进离港队列运输服务需求量分别为57.19、104.41，以21号航班为标准，则两队列的当量航班总数分别为21.41和39.09。表2中各算法排序结果统计如表3所示：

表3实验数据统计结果

表中s代表各算法的排序结果方案，为叙述方便，以下使用算法名称代表该算法对应的航班安排计划。由表3数据显示知：

1)SGA、SLSGA、HLSGA相对于FCFS算法，总延误成本分别降低了21.8％、50.5％和60.1％，HLSGA对应延误成本有了明显下降，且下降幅度最大。

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有所改善，但较微弱。

(2)延误损失协同优化分析

表4为FCFS安排下各跑道的航班序列，even(FCFS,FAQ)远高于even(FCFS,FDQ)。算例中进港专用跑道航班优先系数为0.93，混合跑道进港航班优先系数为0.47，由此产生了航班优先权的高压。所以HLSGA在跑道之间移动了部分进港航班，如FA₁₀、FA₁₅等，结果如表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。

表4 FCFS各跑道航班序列

表5 HLSGA各跑道航班序列

由上述表格数据的描述知，本方案实施例中所提模型及其求解算法HLSGA在降低总延误成本、进离港队列延误损失分配等方面均都取得了较显著的效果，求解过程说明了HLSGA良好的寻优能力以及收敛性。

Claims (1)

1.一种基于混合遗传算法的多跑道机场航班起降协同优化方法，其特征在于，包括以下步骤：

1)描述航班列队组成

航班的单位时间延误成本反映了该航班被延误时将造成的经济损失，单位时间延误成本同时还体现了该航班应该承担的延误损失；从而，进、离港队列的航班组成可表示为相应队列中航班单位时间延误成本的叠加，为叙述方便，称该叠加为队列的服务需求量，所述队列的服务需求量定义如下：

定义1设由M架航班组成队列FS，令CD_m表示FS中飞机m的单位时间地面延误损失系数，令

服务需求量反映了队列航班如果被延误则会造成的延误损失量，即队列航班使用跑道总的期望值，同时也体现了该队列航班应该承担的延误损失；

2)设置航班优先权

航班对跑道的使用优先权体现了飞行管制人员对航班类型的倾向性，多跑道机场中起降航班的优先性考虑了以下两个因素：

a.队列服务需求量

队列服务需求量划分为两部分，即当前已服务的需求量和尚待服务的需求量，显然航班使用跑道的优先权正比于所在队列的总需求量以及尚待服务的需求量，反比于该队列已服务的需求量，因为已服务需求量体现了跑道资源在一段时间内被该队列使用情况；

b.专用跑道和混合跑道的构成

航班进行起降时，机场为其分配专用跑道或混合跑道，而机场中进、离港专用跑道以及混合跑道数可能存在差异，所以为了均衡航班队列的延误损失，航班在专用和混合跑道中选择一条合理的跑道进行起降；

因此，混合跑道rm上航班nrm的优先系数

其中，FRMA、FRMD和FRM分别为混合跑道上的进港航班、离港航班及所有航班，FAQ为进港队列，FDQ为离港队列；

其中，(2)式中将进港专用跑道视为一个系统，以Dtrans(FAQ)在专用和混合跑道上的分配比例作为相应航班的优先系数,来调节进港队列FAQ在专用、混合跑道上的分布；以Dtrans(FDQ)在专用和混合跑道上的分配比例作为相应航班的优先系数,来调节离港队列FDQ在专用、混合跑道上的分布；

实际中，由于进港专用跑道数RA和离港专用跑道数RD的不同，进一步优化得到进港航班优先系数为Dtrans(FRA)/RA/Dtrans(FAQ)，以均衡相应队列航班在专用跑道上的优先权，其中，FRA为专用跑道上进港航班；对于混合跑道，进港航班优先系数为其服务需求量与混合跑道服务总需求量的比例，即Dtrans(FRMA)/Dtrans(FRM)；

3)设定单条跑道上航班的优先系数

令

采用cr(r)作为跑道r上航班的优先系数，当跑道r上航班延误损失较大时，其对应的优先系数则较大，反之亦然，所以通过系数cr(r)可调节跑道r的负载量；式中，表示跑道r上航班nr在时间使用跑道r时所产生的地面延误费用；kc为常量；

4)建立多跑道机场进离港地面等待问题协同优化模型

以航班进离港专用跑道以及混合跑道的优先权为基础，建立多跑道机场进离港地面等待问题协同优化模型，目标函数描述如下：

式中，RA、RD分别为进港专用跑道数和离港专用跑道数；RM为混合跑道数；N_r为分配到跑道r上的航班数；表示飞机p在跑道r上进行起降时的分配下降时间；

5)设置协同优化评价标准

当遗传算法(Genetic Algorithm,GA)通过遗传操作生成新的个体后，计算该个体的进、离港延误费用，记为CPA和CPD；由于所述定义1中Dtrans(FS)反映了队列FS的服务需求量，不能直观表达其航班组成，故在所述定义1的基础上，对现有的当量航班概念重新定义，定义如下：

定义2设FQ为一航班队列，任取航班p∈FQ，以其为基准，则航班q∈FQ的当量为两者单位时间地面延误费用之比：

ν(p,q)＝CG_q/CG_p (5)

FQ的当量航班总数说明了该队列的航班组成情况，从而进离港队列的航班组成差异可以通过队列当量航班总数之间的比较进行说明，记进、离港队列FAQ、FDQ的当量航班总数分别为V(p,FAQ)和V(p,FDQ)；

定义3队列的延误费用与其当量航班总数之比称为该队列的当量航班平均延误损失；

航班安排计划s下的进、离港队列当量航班平均延误损失分别为CPA/V(p,FAQ)和CPD/V(p,FDQ),并分别记为even(s,FAQ)和even(s,FDQ)；当even(s,FAQ)与even(s,FDQ)的值越接近，说明s的延误费用分配越合理，反之则说明不公平；

定义4设even(s,FAQ)和even(s,FDQ)分别为s对应进、离港当量航班平均延误损失，令：distance(s)＝|even(s,FAQ)-even(s,FDQ)|，称distance(s)为计划s延误损失的分配均匀度偏差；

6)提出启发式局部搜索策略

当even(s,FAQ)＞even(s,FDQ)时，说明进港队列承担了过多的延误损失，此时需要调整作为公共资源的混合跑道使用权限，方案有两种：A、从进港专用跑道选取一航班移至混合跑道；B、从混合跑道选取一离港航班移至离港专用跑道；这两种方案都增加了进港航班对混合跑道的使用权限，若航班和目标位置选取合适，方案A可以降低进港队列的延误损失，方案B则在降低进港队列延误损失的同时，增加离港队列的延误损失，两种方法都可以缩小even(s,FAQ)与even(s,FDQ)的差距；当even(s,FAQ)＜even(s,FDQ)时，说明离港队列承担了过多的延误损失，此时亦需要调整作为公共资源的混合跑道使用权限，调整方案：C、从离港专用跑道上随机选取一航班移至混合跑道的某一位置；D、从混合跑道上随机选取一进港航班移至进港专用跑道上的某一位置；相应地，这两种方案都增加了离港航班对混合跑道的使用权限，且在降低离港队列延误损失的同时，增加进港队列的延误损失，也均缩小了even(s,FAQ)与even(s,FDQ)的差距；

令个体x代表多跑道进离港地面等待问题(Multi-Runway Arrival-DepartureGround-holding Problem,MRADGHP)的一种航班飞行安排计划，其在温度t下的启发式局部搜索步骤描述如下，每个温度下的局部搜索次数为Lst：

Step 1初始化搜索次数k＝1；

Step 2执行温度t下的局部搜索；

Step 2.1计算个体x的进、离港队列的even(s,FAQ)和even(s,FDQ)；

Step 2.2随机产出choice＝rand()％2，若choice＝0，则实施方案A,否则实施方案B，具体Step如下：

Step 2.3确定参与局部搜索的专用跑道r，在专用跑道中随机选择r，满足：若choice＝0且even(s,FAQ)＞even(s,FDQ)或者choice＝1且even(s,FAQ)＜even(s,FDQ)时，r为进港专用跑道，否则为离港专用跑道；

Step 2.4确定航班基因移出跑道R_out和移入跑道R_in，若choice＝0，则R_out＝r，R_in为任意混合跑道；若choice＝1，则R_out为任意混合跑道，R_in＝r；

Step 2.5在R_out中选取基因g，如果R_in为专用跑道，则基因g对应航班需要满足跑道使用属性；在跑道R_in的航班序列中随机产生一个位置，将基因g插入，得到新个体y；

Step 2.6计算x和y的适应值H(x)、H(y)，若H(x)＜H(y),则x＝y；若H(x)＝H(y)，转Step3；

Step 2.7计算y劣于x时的接受概率pa＝exp(-(H(y)-H(x))/t)；

Step 2.8产生随机数pr＝random(0,1)，若pa＞pr，则x＝y，H(x)＝H(y)；

Step 3 k＝k+1，若k≤Lst，则转Step2继续执行，否则停止温度t下的局部搜索；

7)混合遗传算法的设计

将所述步骤6)中启发式局部搜索策略嵌入遗传算法GA，从而形成一种有效的混合GA对MRADGHP进行求解，所得最优个体即为满足要求的航班飞行计划；所述混合GA对MRADGHP进行求解的过程如下：

Step 1生成规模为popsize的初始群体pop，其中部分个体按航班使用跑道的计划时间先后次序产生，其余个体随机生成，计算个体的适应度函数值；设置模拟退火算法初始温度ts、终止温度te、温度下降率td以及Lst；设置最大进化代数maxgen、交叉概率Pc、变异概率Pm以及最优个体取代当前代中的最差个体数Subn，令代数g＝1；

Step 2适应度比例选择策略是一种典型的个体选择策略，高适应度个体以较高概率进行复制， 由于遗传算法的随机性可能导致一些优秀个体被丢失，所以结合精华保留机制，优秀个体取代群体中的最差个体，直接进入下一代， 使用此结合精华保留的适应度比例选择策略从pop中选取进入交配池的个体，并对交配池中的个体进行交叉、变异操作，生成新个体并组成临时种群temp_pop；

Step 3对所有x∈temp_pop执行模拟退火局部搜索；

Step 3.1初始化温度t＝ts；

Step 3.2使用步骤6)中局部搜索策略对x执行温度t下的模拟退火局部搜索，寻找适应度函数值更高、延误损失在进、离港队列之间分配更合理的个体代替x；

Step 3.3退温t＝td*t；

Step 3.4如果t＜te，结束个体x的局部搜索；否则转本步骤中所述Step3.2重新开始当前温度t下的局部搜索；

Step 4令pop＝temp_pop，得到新一代种群；

Step 5执行精华保留策略，以群体中的最优个体取代pop中Subn个最差个体；

Step 6 g＝g+1；

Step 7如果g＞maxgen，则结束算法，否则转本步骤中所述Step2继续执行。