基于粒子群优化算法的机场群航班优化配置研究

朱金福 ，马睿馨,2，彭安娜，严 琛

(1. 南京航空航天大学 民航学院，江苏 南京 211106; 2. 中国航发商用航空发动机有限责任公司 上海 200241)

0 引 言

2016年，中国民用航空局发布的《中国民用航空“十三五”规划》指出，北京、广州、上海机场国际枢纽竞争力仍需提高，建设成适合京津冀、珠三角、长三角城市群的世界级机场群，并不断提高机场群整体效率。然而，随着我国机场群的不断发展，机场群内各机场发展并不协调。

从当前的发展势态来看，我国三大机场群普遍存在一级国际枢纽机场始终处于龙头地位、容量日益饱和的现象，如京津冀机场群内的北京首都国际机场、长三角机场群内的浦东国际机场和虹桥国际机场以及珠三角机场群内的广州白云国际机场。机场群内其他机场则存在旅客吞吐量低、与枢纽机场航线同质化严重而造成旅客分流的现象。长此以往将不利于机场群各机场之间协调发展，形成恶性竞争。如果能够对我国机场群的航空资源进行有效整合，在合理定位机场群内机场角色与分工的基础上，疏解一级国际枢纽机场的航班时刻资源，调整低效航线航班至周边机场，为符合战略的航班腾出空间，减少因拥堵引发的航班延误，则可以改善当前发展不平衡的现状，提高机场群整体运输效率和航空公司经济效益[1]。

关于航线航班时刻资源优化的国内外研究成果较多。在单个机场航班频率、 航班时刻资源分配研究方向，A. I. CZERNY[2]、H. FUKUI[3]、D. WILKEN等[4]、P. PELLEGRINI等[5]、K.G.ZOGRAFOS等[6]、A. JACQUILLAT等[7]、齐莉[8]、陈梵驿等[9]分别从拥堵、延误、航空公司公平性、旅客需求、航班波等多个不同角度展开研究，通过建立数学模型，进行优化与调配，使得单机场的航班时刻优化建模更加贴近实际应用。另有许多国内外学者从空管的角度进行航线航班优化，如王倩[10]、朱承元等[11]、杨新湦等[12]分别针对航路容量、航路点冲突、流量限制、地面排队等待、空域仿真等问题入手，进行单机场或机场群航班时刻优化。在以机场群为整体的研究领域中，R. D. NEUFVILLE[13]、韦薇[14]、夏玉中[15]、陈欣等[16]、曹香玲[17]从协同发展的角度，提出我国机场群协同发展还处于探索的初期，应注重于合作模式、发展路径，批量调整航线航班，为我国航线航班的优化提出了新思路。在数学模型建模与优化求解中，DENG Wu等[18]、陈娴等[19]利用粒子群优化算法，求解了各种优化模型，为笔者的求解方法提供了思路。

现有的国内外航班时刻优化研究大多是从单机场角度出发，未能考虑机场群整体与各机场诉求，没有在机场群发展的战略层面上依据机场的功能定位进行航班时刻的优化。而国内外关于机场群的研究仍处于探索阶段，部分研究机场群的学者应用多种评价模型发现了我国机场群发展不均衡的问题，在管理制度上提出了建议。基于目前对机场群航班时刻优化的研究较少等问题，笔者构建了以机场群效益最大化的航班时刻优化模型，并运用粒子群优化算法进行求解，最后以长三角机场群为例进行实例验证。

1 航班时刻优化原则

笔者以疏散一级国际枢纽机场航班为目标，将超出机场容量、运行效果差的航班按照机场群内各机场功能定位重新分配起降机场和起降时刻。以此为优化原则，从机场、航空公司和旅客三方角度出发，采用机场准点率、航空公司市场占有率、旅客损失时间、机场功能定位这4个指标评价航班运行效果并作为航班时刻优化目标。

1.1 机场准点率

机场准点率是反映机场实际运行中拥堵情况的重要标准之一。容量饱和、航班时刻资源拥挤的机场，准点率会大大降低。对于准点率较低的机场，有可能是由于容量饱和引起的，应考虑进行航班流量疏散。但由于机场准点率不仅与资源利用是否饱和相关，也与流量控制、天气等因素有关，故利用起降机场年平均准点率作为指标。

1.2 航空公司市场占有率

航空公司市场占有率体现了航空公司在航线规划上的战略部署。每一家航空公司均对目标航空市场有所规划，并希望不断扩大航线上的市场份额。各航空公司在战略航线上加大运力投放，更有利于本航空公司构建战略航线网络和形成航班波，从而提升航空公司竞争力。

1.3 旅客损失时间

旅客损失时间，即旅客预计出发(或到达)时间和实际出发(或到达)时间的偏差，旅客一般都会选择与预计时间最近的航班，它体现了航班是否能够满足旅客出行的需求。同时在现实航班时刻的编排过程中，航班时刻资源变更的困难较大，少有航班时刻能够进行较大变动。

1.4 航班功能定位

根据民航局对机场群内各机场的功能定位，一级国际枢纽机场为具有国际竞争力的国际航空枢纽，二级枢纽机场为以国内点对点航班和国际优质远程航线为主的区域枢纽，而机场群内其他干线机场主要发展国内航线航班。

2 航班时刻优化模型

为了有效解决机场群内资源不均衡、航线网络结构不符合发展要求的矛盾，同时兼顾机场运行容量、航空公司战略发展、旅客需求、机场战略定位的条件，笔者以现有航班时刻表为基础，通过重新分配各航班的起降机场和起降时刻，使各机场容流平衡、减少同质化航线航班，以满足机场群战略规划的要求。

2.1 模型假设

模型包括以下假设条件：

1)机场群内各机场归属于同一个机场管理集团，航班时刻资源由机场管理集团统一调配。机场管理集团内行政阻碍少，机场协作制度健全，航空公司能够配合机场管理集团的资源规划。

2)不改变航班的执飞航空公司，即重新分配起降机场和时刻的航班仍由原航空公司执飞。

3)优化前后航段飞行时间不变。

4)不考虑对方机场的容量限制。

2.2 目标函数

根据第1节所述航班时刻优化原则，以机场群内准点率、航空公司市场占有率、旅客损失时间和机场功能定位4个角度指标最大化为目标，建立机场群航班时刻优化模型如式(1)、式(2)：

(1)

(2)

2.3 约束条件

2.3.1 航班唯一性约束

航班唯一性约束即一个航班只能有一个起降机场和起降时刻，如式(3)、式(4)：

(3)

(4)

2.3.2 高峰小时容量限制

机场的进离港架次存在容量限制，一旦超出容量容易发生航班堆积和拥堵。因此调整航班时应考虑到起降机场的容量限制情况。笔者以5 min时间片的机场容量为单位进行约束，如式(5)：

(5)

2.3.3 满足航班连续性约束

作为一个航班串任务内的连续性航班，必须对航空器在机场中转时最小中转时间和最大中转时间进行约束，如式(6)、式(7)：

(6)

(7)

式中：

3 模型求解

3.1 粒子群优化算法概述

粒子群优化算法(PSO)是基于群体的进化算法，起源于对鸟类捕食行为的仿真模拟。当PSO应用于求解优化问题时，问题的解与粒子在搜索空间中的位置相对应。每个粒子包含粒子的位置和速度(决定飞行的方向和距离)以及设计的优化函数适应度值两个属性。在每次迭代过程中，粒子通过记忆跟踪两个极值来更新自身的位置：一个是粒子自身搜索到的最优解，称为个体极值点(用Pid表示其位置)；另一个是整个粒子组群体找到的最优解，称为全局极值点(用Pg,d表示其位置)。在找到这两个最优解后，粒子将根据式(8)、式(9)，更新其速度和位置：

(8)

(9)

式中:Vid为第i个粒子在第d维度上的速度；w为惯性权值；η1和η2为学习参数；rand()定义为(0,1)之间的随机数。粒子群初始速度随机产生，重复应用式(1)和式(2)进行迭代，直到找到满意的解。

3.2 改进的粒子群优化算法设计

针对研究的问题，设计的粒子群优化算法包括算法编码、初始解、适应度函数设计和更新规则。

3.2.1 算法编码

由于笔者涉及到机场群内某个机场和起降时刻两个维度，同时还涉及到多个航班统一调配，直到找到最佳方案，因此在改进的粒子群算法中，一个粒子的位置表示待求解的航班集合，粒子zi构造如式(10)：

zi=[(x1,v1),(x2,v2),…,(xn,vn)]

(10)

式中：zi为粒子群中的第i个粒子；(xn,vn)为第n个航班于时刻vn从机场群内机场xn起降。

3.2.2 初始解

粒子群优化算法对初始解有较强的依赖性。初始解较差则可能降低粒子群优化算法的收敛速度。笔者将初始的航班数据作为初始可行解。

3.2.3 适应度函数设计

适应度函数是对每个粒子是否最优的评价。笔者以模型中的目标函数，作为适应度函数。

由于模型中4个指标的权重为1，但各自度量单位不同，需要把有量纲表达式变成无量纲表达式，使不同单位或量级的指标能够进行比较和加权。因此，应当根据标准化原则对4个指标进行标准化处理后，再计算适应度函数，如式(11)：

(11)

同时，为了有效约束新生成的粒子在可行解范围内，将不满足约束粒子的适应度值加上无限大的惩罚值M。即每个粒子zi的适应度函数构造如式(12)：

(12)

式中：M=10 000；ui为0-1变量，当粒子z满足模型约束条件时ui=0，不满足时ui=1。

3.2.4 更新规则

粒子的位置和速度更新规则为式(8)、式(9)，其中c1=c2=2，w作为惯性权重系数，很大程度上影响粒子群的全局搜索能力。由程序反复试验确定改进的粒子群算法中采用0.9～0.4线性递减的策略，如式(13)：

(13)

式中：wini为初始惯性权重系数，取wini=0.9；wend为迭代至最大次数时的惯性权重系数，取wend=0.4；Gmax为最大迭代次数，取Gmax=100;k为当前迭代次数。

算法步骤如下：

Step 1依据初始航班数据生成1个粒子，并随机产生49个粒子，组成一个粒子群。其中粒子的位置zi代表一组解。

Step 2计算每个粒子的适应度值，根据式(12)计算。

Step 3由式(14)更新每个粒子的最好位置：

(14)

(15)

Step 4更新所有粒子的位置和速度，根据式(8)、式(9)计算。

Step 5重复Step 2到Step 4，直到最大迭代次数和相邻两次迭代的差值满足最小阀值的终止条件。

Step 6输出最终结果。

4 实例应用

4.1 样本选取和参数设计

以2019年长三角机场群运行情况为例，上海虹桥机场与浦东国际机场的旅客吞吐量占整个机场群旅客吞吐量的49%，起降架次占比达43%。长三角机场群内其他机场的旅客吞吐量和起降架次却不足17%。浦东国际机场旅客中转率达12%，没有达到规划中的15%～20%，还未建设成具备拥有国际竞争力的中转枢纽。浦东国际机场的通航点中，与周边机场重复的通航点占37%。虹桥国际机场的通航点中，有62%的通航点与周边机场重复。可见机场群内各机场存在航线同质化程度高、运输效率低等问题。

笔者以长三角机场群内的浦东国际机场、虹桥国际机场、杭州萧山国际机场、南京禄口国际机场(机场编号i=1，2，3，4)4个机场作为研究对象，从OAG公布的2017年11月的国内外航班时刻表作为历史数据，从飞常准网站公布的机场准点率作为准点率数据，以民航局公布的国内主要机场小时容量数据作为容量限制数据。其中，各机场5 min高峰航班起降架次容量为C1=6架次/5 min，C2=3架次/5 min，C3=3架次/5 min，C4=3架次/5 min。4个机场的进离港准点率为D1=73.01%,D2=77.1%,D3=61.35%,D4=64.18%。

4.2 模型验证

由于对全天的航班时刻进行优化，数据量大、模型复杂，故先选取小范围数据进行模型验证，再应用于大范围的全天航班时刻优化。以2017年11月21日08:00—09:00长三角机场群4个机场共142个航班时刻为对象进行模型验证，其中上海浦东国际机场(PVG)共70个航班，上海虹桥国际机场(SHA)37个航班，杭州萧山国际机场(HGH)16个航班，南京禄口国际机场(NKG)19个航班。部分初始数据如表1。

表1 长三角机场群航班时刻数据(部分)Table 1 Flight schedule data of Yangtze River Delta multi-airportsystem (partial)

采用Python进行粒子群优化算法编程求解。粒子群适应度值变化曲线如图1。当迭代至40次左右，适应度值基本保持不变，粒子群算法收敛，对所研究问题的适用性较强。

图1 适应度值变化曲线Fig. 1 Change curve of fitness value

4.3 结果分析

根据计算结果，上海两场08:00—09：00的107个航班中，共调整了其中的18个航班。18个航班的调整优化情况如表2。

表2 航班时刻优化结果Table 2 Flight schedule optimization results

以FM9415航班为例，原航班应于08:00从上海虹桥国际机场起飞，现调整为08:20从杭州萧山国际机场起飞。原航班应于09:30到达连云港白塔埠机场，经优化后由于航段飞行时间不变，调整为09:50到达。图2显示了长三角机场群4个机场优化前后的航班数量变化情况。由图2可以看出，上海浦东国际机场调整量较大，其中国际航班保留不变，优化的均为将国内航班疏解至周边机场，符合预期的优化策略。同时，南京禄口国际机场航班增幅略微大于杭州萧山国际机场。分析原因是由于南京禄口机场的准点率高于杭州萧山机场，所以大部分航班会优先分配到南京禄口机场。

图2 长三角机场群08:00—09:00机场航班数量变化Fig. 2 Flight number change of Yangtze River Delta multi-airportsystem from 08:00 to 09:00

图3描述了各机场优化前和优化后航班时刻分布情况和变化趋势。优化前各机场起降架次波动幅度较大，某些时刻下航班起降架次过于突出。经过优化调整后，各机场起降架次较相对稳定，航班在各时刻分布相对平均。起降架次基本控制在机场容量范围内，避免因为某时刻航班量过大而引发延误。

图3 长三角机场群优化前后时刻表变化Fig. 3 Change of flight schedule of Yangtze River Delta multi-airport system before and after optimization

由图3可以看出，用笔者模型算法调整机场群航班时刻比较符合实际情况，能够合理配置机场群航班时刻资源。但模型验证中选择的数据集模型较小，仅为1 h内数据(08:00—09:00)，不能反映该天内航班计划优化情况，故选取2017年11月21日全天共2 707个航班数据再次进行优化求解。

对该天长三角机场群运行情况进行调研，将重要的机场运行特征数据进行统计，如表3。由表3可以看出，在1 d为周期范围内，浦东国际机场与虹桥国际机场航班架次远远超过该机场的起降容量，而南京禄口机场和杭州萧山机场仍有起降架次的增长空间。

表3 长三角机场群运行特征数据统计Table 3 Statistics of operation characteristics of Yangtze River Deltamulti-airport system

通过粒子群优化算法求出，长三角机场群单位时间窗的最大调整量为45架次，航班调整总量为143架次。其中，浦东国际机场调整量为128架次，虹桥国际机场的调整量为15架次。

使用Python进行编程求解，将长三角机场群该天24 h优化前后的航班时刻优化方案输出如图4。

图4(a)展现了优化前后上海浦东国际机场的航班时刻分布情况，由对比可知，单位时间窗的高峰架次经优化由121调整为76。优化前09:00—11:00和21：00—22：00是上海浦东国际机场的繁忙时段，优化后09:00—22:00的进离港架次较为平均。图4(b)展现了优化前后的上海虹桥国际机场航班时刻分布情况，对超出机场容量的12:00—14:00和15:00—16:00两个时段航班计划进行了优化，各时段架次得到有效控制。图4(c)、图4(d)分别是杭州萧山机场和南京禄口机场优化前后的航班时刻分布情况。由图4(c)～(d)可以看出，在部分不繁忙时刻增加航班量分担了上海浦东和虹桥机场超负荷运行的航班，同时也不超过自身机场的运行容量限制，分担了枢纽机场高峰时段航班运行压力。

图4 长三角机场群全天航班时刻表Fig. 4 All day flight schedule of Yangtze River Delta multi-airport system

综上所述，经航班时刻优化，长三角机场群各时段架次均得到有效控制，各机场高峰时段航班架次分布更均衡，有效缓解枢纽机场超负荷运行造成航班延误的压力，高峰时段航班架次显著降低。

5 结 语

我国三大机场群自规划建设以来，始终缺乏统一的航班时刻资源调整与分配。机场群内一级国际枢纽机场旅客吞吐量处于机场群内龙头地位，但各机场之间航线同质化程度高，如此发展难以达到机场群规划中的战略要求。笔者建立的模型，从机场群内航空公司、机场、旅客3个角度出发，以解决不平衡发展为目的，将一级国际枢纽机场运行效果差的航班资源合理配置至周边机场。设计改进的粒子群优化算法进行求解，并以长三角实际数据进行了案例研究，优化后长三角机场群的各机场起降架次普遍控制在容量限制范围内，航班在各时刻分布较为均衡，为机场群航班时刻资源配置提供优化手段和参考依据。