基于经济损失的航班延误恢复模型研究

刘艳红，高 林，李耀华

（中国民航大学航空工程学院，天津 300300）

基于经济损失的航班延误恢复模型研究

刘艳红，高 林，李耀华

（中国民航大学航空工程学院，天津 300300）

分析了航班延误的恢复调度问题，并针对问题提出了一种机场大面积航班延误恢复模型，模型考虑了航班延误的延误时间，还考虑了不同机型对航班延误经济损失造成的影响。构造了基于免疫机制的免疫遗传算法来求解模型，此算法保留了标准遗传算法随机全局并行搜索的特点，又在相当大的程度上避免了未成熟收敛。用实际的航班信息进行仿真研究结果表明，文中的模型和算法切实可行。

航班延误经济损失；免疫机制；免疫遗传算法

改革开放以来，随着航空运输业的迅速发展，空中交通网络的拥塞现象日益严重。拥塞导致起飞航班的延迟，影响到达航班的顺序，给用户带来不便，造成航空公司的巨大损失，甚至影响了飞行的安全性。据统计，美国在20世纪90年代初，每年因航班延误造成的延误损失就高达2.5亿美元。近几年美国每年的延误损失甚至高达了30亿美元[1]。本世纪初，Mark Hansen研究了延误后如何尽快恢复的理论和模型，他以洛杉矶机场为例，使用线性和非线性回归模型的方法分析了美国几大机场的航班延误及飞行时间正常化程序，但对国内大多数航空公司的航班恢复调度并不太适用[2]。

目前，中国在进行航班延误恢复时的航班调度上基本采用先到先服务算法（FCFS），虽然对于管制员比较容易实施和操作，但是调度的效率低，因此建立合理的恢复模型已大势所趋。徐肖豪等学者也对延误恢复问题进行了全面研究，提出了各种地面等待模型，但这些模型多以延误时间作为衡量地面等待策略的标准，没考虑不同机型对航班延误经济损失造成的影响[3]。文献[4]针对延误航班恢复模型定义了航班影响因子，考虑航班延误的经济效益，但没有考虑机场容量的限制。本文提出了一种机场大面积航班延误恢复模型，该模型可以提供航班延误恢复时机场出发航班的最优分配方案，使延误损失最小，大幅提高航空运输的经济效益，并构造了一种基于免疫机制的遗传算法来求解此模型。

1 航班延误恢复模型

1.1 问题描述

航班延误是指航班由于某种原因没有按照公布的时刻出发或到达，即属于不正常航班。正常航班符合以下条件：

1）在班期时刻表公布的离站时间后15 min（北京、上海、广州、深圳25 min）之内正常起飞的航班；

2）在班期时刻公布的到达时间开舱门的航班。不正常航班：不符合正常航班全部条件的航班。造成航班延误的因素很多，一是天气等自然因素造成的延误；二是航空公司自身的原因造成的延误，如飞机出现机械故障、飞机调配、发行计划安排出现问题等；三是空中流量饱和，空管对飞机起飞进行控制造成的延误。其中天气原因是主要原因。

航班延误不仅给旅客带来诸多不便，也使航空公司蒙受经济损失，而且严重威胁到机场及空域的安全。航空延误所带来的问题[1]包括：①导致运行成本上升0.9%～2.3%（因航空公司规模不同而不同）；②导致高价值商务旅客流失；③使航空公司在旅客面前失去诚信；④增加地面和客舱服务难度；⑤引发旅客投诉和法律纠纷；⑥飞机利用率下降、机组利用率下降；⑦对飞行安全不利。

1.2 航班延误经济损失的构成

航班延误经济损失通常包括显性损失和隐性损失两部分。显性损失包括航空公司经济损失和旅客经济损失，航空公司经济损失由延误航班运营成本和延误航班盈利损失两部分组成。隐性损失主要指航空公司的形象和名誉的损失，由于这些隐性损失的不确定性，因此，本文在计算航班延误经济损失的时候并没有考虑这些隐性损失。

1.2.1 航空公司经济损失

1）延误航班的运营成本

延误航班的运营成本与延误航班的机型有着直接联系，起飞质量越大的飞机，其停场费、起降费、旅客服务费等就越高，相应的地面等待成本也就越高。本文根据国际民航组织（ICAO）的标准，按照飞机的尾流强弱将飞机分3类分别讨论运营成本，如表1所示。以中型飞机B737－300为例，据计算，1架飞机每年花费的租赁费、税金、停场费、飞机维护费用和相应的航材费用等固定性费用为2 500万元，按1年有365天计算，1天的成本约为7万元。为了方便分析，本文假设重型机、中型机和轻型机延误的运营成本分别为10万元/天、7万元/天和5 000元/天，各机型每小时延误运营成本a0的值如表1所示。

对于不同的机型，其延误运营成本c0（t）为

式中：t为延误时间。

2）延误航班的盈利损失

表1 各类飞机每小时延误运营成本Tab.1 Operating costs of different aircraft per hour

航空器作为航空公司的主要生产工具，其目的除了要为旅客提供优质的服务外还要为航空公司创造利润，因此，当航班发生延误时，航空公司的盈利也会受到直接影响，造成航空公司的经济损失。延误航班的盈利损失与航班最大载客人数、航班客座率和航空公司的净利润率密切相关。根据2004年英国《商业航空》[2]的统计可得出中国航空公司的平均净利润率r约为2.98%。从中国实际情况出发，假设航班客座率s为75%，平均票价a为750元，平均飞行时间f为2 h，因此，令m表示航班最大载客人数，则各航空器每小时可为航空公司赚取的利润an为

延误航班的盈利损失为

1.2.2 旅客经济损失

航班延误造成的旅客经济损失与飞行的等级相关。国外相关机构就航班延误对旅客造成的经济损失做过较为系统的分析（如表2所示），得到旅客的平均时间价值为 28.6$·h－1，其中最低时间价值为23.8$·h－1，最高时间价值为 35.6$·h－1。

表2 国外旅客延误时间价值Tab.2 Delay time values of foreign passengers

根据国外旅客延误时间价值并结合中国飞行的分类，中国民航运输中对于普通国内航班飞行每名旅客平均延误经济损失约为50元·h－1，对于国际航班和重要客人的飞行每名旅客平均延误经济损失约为100元·h－1。航班延误造成的旅客经济损失cp（t）为

式中：ap为航班单位每名旅客的平均延误经济损失。

1.3 航班延误恢复模型建立

航班延误恢复调度（recovery scheduling of flight delays，RSFD）是指由于某些原因造成了大面积的航班不能正常起飞，当延误恢复时，要重新调度这些延误了的航班。调度的任务是给出一种航班调度方案，使所有延误的航班在尽可能短的时间内起飞，并使得延误造成的经济损失尽可能小。在文献[4]的研究成果基础上，进行了深入研究，并对模型进行了改进，这样，建立了如下航班延误的恢复模型

式中：F为所有航班的总延误经济损失；n为延误航班总数；c（tj）为航班的总延误经济损失；c0（tj）、cn（tj）、cp（tj）分别为航班fj的运营成本、盈利损失和旅客经济损失，具体计算已在前面提出；tj为航班fj的延误时间，由实际起飞时刻和计划起飞时刻决定，而实际起飞时刻由航班延误恢复时刻和航班延误恢复调度方案决定；将执行航班恢复的时间平均分成若干段，每段用Δtj表示；aΔtj表示航班fj的预计降落时间所在的时间段值；dj表示航班fj降落后允许的最大延误时间；lij=0表示航班fj未在Δtj时间段降落，等于1则表示航班fi在Δtj时间段降落；mΔtj表示在时间段Δtj的机场的容量值。

目标函数（5）保证延误造成的总经济损失最少；约束条件（6）即保证了航班fj在其预计降落时间之前的时间段不允许降落，又保证了航班延误不能超过其最大延误值；约束条件（7）保证了在时间段Δtj降落的航班不能超过其机场容量值。

目前，解决航班恢复调度问题主要采用的是顺延的办法，即先来先服务（FCFS）策略，其思路为延误恢复时按照航班原来的起飞顺序调度航班，该法虽然简单，但没有考虑航班、航空公司和旅客的各种因素，因此，往往不能令人满意。本文尝试采用免疫遗传算法来求解该问题。

2 航班延误恢复调度模型求解算法

2.1 抗体结构

抗体编码采用自然数编码方式，所有延误的航班按照时刻表中的顺序设置标号分别为1、2、3、…、n，即：X={1，2，3，…，n}。每个抗体基因为 M，M={a1，a2，a3，…，an}，其中 ai∈X 且 ai≠aj，即 M 表示航班恢复调度的一个排列序列；还定义输出变量数k，k表示适应值或聚合适应值。如上所述，每个抗体均由一个（1×h）矩阵表示，其中h=n+k，其机构如图1所示。假设免疫系统由N个抗体组成（即群体规模为N），整个群体的数据结构便是一个N×（n+k）的矩阵。

图1 抗体的数据结构Fig.1 Data structure of antibody

2.2 免疫遗传算法

免疫遗传算法是基于生物免疫机制提出的一种改进的遗传算法[4]，其将实际求解问题的目标函数对应为抗原，而问题的解对应为抗体。基于免疫原理的遗传算法与标准遗传算法相比，具有如下显著特点：①具有免疫记忆功能，该功能可以加快搜索速度，提高遗传算法的总体搜索能力；②具有抗体的多样性保持功能，利用该功能可以提高遗传算法的局部搜索能力；③具有自我调节功能，这种功能可用于提高遗传算法的全局搜索能力，避免陷入局部解。免疫遗传算法即包括标准遗传算法中的选择、交叉、变异等功能，又包括免疫机制的免疫记忆、多样性保持、自我调节等功能，它们都是针对抗体进行的。

在本算法中定义了下列名词：多样度、亲和度、浓度。多样度是抗体的多样性测度。抗体基因座j的信息熵Hj（N）可定义为其中pij为第i个符号出现在基因座j上的概率，且可定义为：pij=在基因座j上出现第i个符号的总个数/N。由此可得平均熵H（N）

两个抗体u和v之间的亲和度定义为Au，v，则

Au，v取值范围为 0～1，Au，v越大，表示 u、v 两个抗体越亲和，Au，v=1则表示u，v两者基因完全一致，若将两个抗体之间的亲和度概念扩展到整个群体，则得到群体亲和度A（N）。抗体的浓度ci即群体中相似抗体所占的比重，即

ci=和抗体i具有很大亲和度的抗体数/

抗体总数N （10）

2.3 算法步骤

1）初始化种群，根据所要求解的问题，随机生成N个个体作为初始种群As。

2）计算当前种群中所有个体的适应值。

3）对当前的种群Ak进行交叉操作，得到种群Bk，然后对种群Bk进行变异操作，得到种群Ck。

4）根据式（9）计算当前种群Ck的抗体信息熵H和群体亲和度A，与阀值A0比较。若A>A0，则转至步骤5）；若不成立，则转至步骤2），迭代代数加一。

5）随机产生P个新抗体，与种群Ck结合，产生新种群 Dk，此时抗体总数为（P+N）；根据式（10）计算抗体浓度及聚合适应度。

6）基于抗体浓度更新群体，并对记忆单元进行更新。

7）判断当前代数是否达到进化截止代数或当前群体的抗体平均浓度是否达到稳定，若达到截止代数或稳定，则输出最优解，算法结束；否则转至步骤2），迭代代数加一。

3 仿真研究

选取中国某枢纽机场的80个航班数据进行试验，将时间划分成若干时间段，每段为15 min。假设上午9：00开始出现了不利于飞行的大雾天气，造成了机场旅客滞留、大面积航班延误。直到11：00天气条件转好，才可以进行正常飞行。延误航班数据如表3所示[5]。

表3 航班数据Tab.3 Scheduled flight data

为了验证算法，本文采用标准遗传算法和免疫遗传算法来求解航班恢复模型，进行了比较研究。在算法求解中，本文算法选取参数如下：抗体规模N=20，随机产生的新抗体个数一般为群体规模的40%[6]，即P=8，相似度常数λ=0.9，阀值A0=0.25，交叉和变异的概率分别为0.15和0.1，算法结束准则为连续迭代100代。标准遗传算法的参数选取如下：抗体规模N=20，交叉概率为0.15，变异概率为0.1，算法结束准则为连续迭代100代。根据表3的数据，结果收敛图如图2所示，两种算法最优目标函数值分别为1 512 606和1 541 079，标准遗传算法也可以求得可行解，但比免疫遗传算法结果较差，从图2中还可以看出，免疫遗传算法使结果快速地向最优结果靠近，在种群上整体寻优性能优于标准遗传算法，收敛速度更快（图中曲线1表示免疫遗传算法的求解适应值曲线，曲线2表示标准遗传算法的求解适应值曲线）。

为了验证本文模型和算法的实用性，利用传统的FCFS策略和本文的免疫遗传算法分别得到的航班排序和总延误经济损失对比如表4所示。免疫遗传算法的结果比FCFS策略节约了207 224元，因此按照免疫遗传算法的排序结果调度航班，可以更为有效地减少经济损失。

表4 FCFS和免疫遗传算法的恢复结果Tab.4 Recovery results of FCFS and immune genetic algorithm

4 结语

本文对航班延误恢复调度进行了研究。为使航班延误恢复调度更加合理，目标函数设计综合考虑了航班延误的多项经济损失，较详细地分析了各项经济损失的计算过程，并结合实际的约束条件构建了一种新的航班延误恢复模型。同时，构造了免疫遗传算法对模型进行求解。通过实际数据进行应用研究，结果表明本文建立的模型和算法切实可行，产出的恢复调度序列效果良好，可降低航空公司的运营成本和提高运作效率。

[1] 彭莉娟，吴 鹍.基于累积延误损失算法的GHP模型[J].系统仿真学报，2008，20（17）：44-46.

[2]张 静.2004年世界前100家航空公司经营状况[J].中国民用航空，2005，6（11）：27-31.

[3]徐肖豪，李 雄.航班地面等待模型中的延误成本分析与仿真[J].南京航空航天大学学报，2006，38（1）：115-120.

[4] 丁建立，王新茹.航班延误恢复调度的混合粒子群算法[J].交通运输工程学报，2008，8（2）：19-22.

[5] 丁建立，计金玲.基于免疫机制的航班延误快速恢复模型及实现[J].计算机工程与设计，2008，29（19）：29-32.

[6] 陈丽安，张培铭.免疫遗传算法在MATLAB环境中的实现[J].福州大学学报，2004，32（5）：55-59.

Study on Recovery Model of Flight Delays Based on Economic Loss

LIU Yan-hong，GAO Lin，LI Yao-hua
（Aeronautic Engineering College， CAUC， Tianjin 300300，China）

The recovery scheduling of flight delays is analyzed， a rapid recovery model of large-scale airport flight delays is presented， the model considers not only time of flight delays， but also economic loss of flight delays of different aircraft types.And an immune genetic algorithm is suggested to solve the model，which is improved immune system based on immune system，reserves the feature of stochastic global parallel search of genetic algorithm，and avoids immature convergence considerably.The simulation result with flight data shows that the model and algorithm suggested are feasible and effective.

economic loss of flight delays；immune system；immune genetic algorithm

TP29

A

1674－5590（2010）02－0046－05

2010-06-10；

2010-07-16 基金项目：中国民航大学青年骨干教师基金项目（062084）

刘艳红（1970—），女，河南确山人，副教授，硕士，研究方向为飞机结构设计与修理技术，智能结构设计与控制技术.

（责任编辑：杨媛媛）