0.   引言

航班延误已成为困扰各航空公司和广大旅客的世界性难题, 因此, 一些研究人员开始探讨解决航班延误的方法, 以改善空中交通管理现状。马正平等给出了一种机场航班延误优化模型, 将机场的到达和出发视为密切相关的两个过程, 对几个小时内可能的延误进行预测、分析和处理^[1]。徐肖豪等研究了遗传算法在终端区跑道分配以及飞机排序中的应用, 建立了多条跑道多架飞机排序的数学模型, 以减少延迟时间^[2]。航班延误快速恢复是一个复杂的综合调度过程, 目前, 国际、国内航班延误快速恢复在理论方法与实际应用上均没有很好地解决办法。粒子群算法简单易实现, 鲁棒性好, 可并行计算, 已经成功地用于解决旅行商问题^[3]、作业车间调度问题^[4-6]、交通量多路径分配问题^[7]和综合运输通道客运结构配置^[8]等复杂问题, 在优化航班延误恢复调度时也具有极大的潜力。本文从航班延误的经济效益和社会影响出发, 尝试将混合粒子群算法用于优化航班延误恢复调度过程中。

1.   航班延误经济损失的构成

航班延误经济损失通常包括显性损失和隐性损失两部分^[9], 见图 1。

图  1  航班延误经济损失的构成

Figure  1.  Economic loss constitution of flight delays

下载: 全尺寸图片 幻灯片

1.1   航班延误的显性损失

本文假定显性损失与航班的延误时间成线性关系。

1.1.1   航空公司经济损失

(1) 延误航班的运营成本

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

表  1  各类飞机每小时延误运营成本

Table  1.  α₀ of different aircrafts

机型	代表符号	最大起飞质量/t	尾流类型	α0/ (元·h-1)
重型机	H	> 136	重型尾流	4 167
中型机	M	7~136 (含)	中型尾流	2 916
轻型机	L	≤7	轻型尾流	208

下载: 导出CSV 

| 显示表格

对于不同的机型, 其延误运营成本C₀ (t) 为

$C{}_0(t)=\alpha {}_{0}t(1)$

式中: t为延误时间。

(2) 延误航班的盈利损失

航空器作为航空公司的主要生产工具, 其目的除了要为旅客提供优质的服务外还要为航空公司创造利润, 因此, 当航班发生延误时, 航空公司的盈利也会受到直接的影响, 造成航空公司的经济损失。延误航班的盈利损失与航班最大载客人数、航班客座率和航空公司的净利润率密切相关。

根据2005年英国《商业航空》^[10]的统计可得出中国航空公司的平均净利润率r约为2.98%。从中国实际情况出发, 假设航班客座率s为75%, 平均票价a为750元, 平均飞行时间f为2 h, 因此, 令m表示航班最大载客人数, 则各航空器每小时可为航空公司赚取的利润α_n为

$\alpha {}_{\text{n}}=msar/f(2)$

延误航班的盈利损失C_n (t) 为

$C{}_{\text{n}}(t)=\alpha {}_{\text{n}}t(3)$

1.1.2   旅客经济损失

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

表  2  国外旅客延误时间价值

Table  2.  Delay time values of foreign passengers $·h^-1

旅客类型	平均时间价值	最低时间价值	最高时间价值
休闲旅客	23.3	20.0	30.0
商务旅客	40.1	32.1	48.1

下载: 导出CSV 

| 显示表格

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

航班延误造成的旅客经济损失C_p (t) 为

$C{}_{\text{p}}(t)=\alpha {}_{\text{p}}smt(4)$

式中: α_p为航班单位时间每名旅客的平均延误经济损失。

1.2   航班延误的隐性损失

航班延误除了会造成有形的显性损失之外, 还会导致无形的隐性损失, 如航班延误对航空公司形象和声誉的损害。航班不正常使航空公司在旅客面前失去诚信, 也是导致高价值商务旅客流失的最主要原因。再如, 航班延误还会造成很多间接的经济损失, 很多商务谈判或交易不得不因为航班的延误而延期或取消, 很多旅行社不得不处理并非缘于自身责任的投诉、索赔等。由于这些隐性损失的不确定性, 因此, 本文在计算航班延误经济损失的时候并没有考虑这些隐性损失。

1.3   航班延误的总延误经济损失

为了便于对航班延误造成的经济损失进行定量的分析, 本文在计算航班延误经济损失的时候并未考虑航班延误的隐性损失。在计算航班延误经济损失时, 航线对于恢复调度的影响也是不容忽视的, 航线密度大, 恢复调度时就应该优先考虑。对于首都机场, 所有航线对应的目的机场总数为99个, 其中, 密度大的航线的目的机场主要集中在上海虹桥机场、广州白云机场、上海浦东机场、深圳宝安机场、大连周水子机场、成都双流机场和昆明巫家坝机场, 而其他92个机场的航线密度相对小一些。通过对首都机场的航班数据进行分析, 本文定义了航线影响因子来衡量航线所对应的目的机场的重要性。机场和航线影响因子的对应关系见表 3。

表  3  各机场所对应的航线影响因子

Table  3.  Airline impact factors of airports

机场名称	航线影响因子
上海虹桥机场	0.103
广州白云机场	0.059
上海浦东机场	0.049
深圳宝安机场	0.040
大连周水子机场	0.038
成都双流机场	0.041
昆明巫家坝机场	0.024
其他机场	0.007

下载: 导出CSV 

| 显示表格

航班延误造成的总延误经济损失C (t) 为

$C(t)=(1+\chi )[C{}_0(t)+C{}_{\text{n}}(t)+C{}_{\text{p}}(t)](5)$

式中: χ为航班的目的机场所对应的航线影响因子。

2.   航班延误恢复调度模型

航班延误恢复调度(recovery scheduling of flight delays, RSFD) 是指由于某些原因造成了大面积的航班不能正常起飞, 当延误恢复时, 要重新调度这些延误了的航班。调度的任务是给出一种航班调度方案, 使所有延误了的航班在尽可能短的时间内起飞, 并使得延误造成的经济损失尽可能小。

对于延误航班序列F₁、F₂、…、F_N, 设T₁、T₂、…、T_N为航班的计划起飞时刻, R_t为航班延误恢复时刻, t₁、t₂、…、t_N为航班的延误时间(由实际起飞时刻和计划起飞时刻决定), 实际起飞时刻由航班延误恢复时刻R_t和航班延误恢复调度方案决定; M₁、M₂、…、M_N为航班的尾流类型, 航班的运营成本由飞机的尾流类型决定; A₁、A₂、…、A_N为航班的目的机场, 航线影响因子由目的机场决定。本文所研究的航班全为国内航班, 旅客平均延误经济损失按照国内航班的标准进行计算, P₁、P₂、…、P_N为对应航班的最大载客人数, 航班的盈利损失和旅客的经济损失都和航班的最大载客人数相关。

以前面提出的航班延误经济损失构成为基础, 航班延误恢复调度模型建立为

$\begin{array}{l}\min F=\min {\displaystyle \sum _{j=1}^{{\rm N}}C}(t{}_j)=\min {\displaystyle \sum _{j=1}^{{\rm N}}(}1+\chi {}_j)\cdot \\ [C{}_0(t{}_j)+C{}_{\text{n}}(t{}_j)+C{}_{\text{p}}(t{}_j)](6)\end{array}$

式中: F为所有航班的总延误经济损失; N为延误航班总数; C (t_j) 为航班F_j的总延误经济损失; χ_j为航班F_j的目的机场所对应的航线影响因子; C₀ (t_j)、C_n (t_j)、C_p (t_j) 分别为航班F_j的运营成本、盈利损失与旅客经济损失。

目前, 解决RSFD主要采用的是顺延的办法, 等同于先来先服务(FCFS) 策略, 其思路为延误恢复时按照各航班原来的起飞顺序调度航班, 该法虽然简单, 但没有考虑航班、航空公司和旅客的各种因素, 因此, 往往不能令人满意。本文尝试采用混合粒子群算法(HPSOA) 来求解该问题。

3.   混合粒子群算法优化航班延误恢复调度

3.1   基本粒子群算法

粒子群算法(PSOA) 是由Kennedy和Eberhart于1995年提出的一种基于迭代的进化计算算法。算法中, 数量为P_c的粒子构成了粒子群。在每一次迭代中, 所有的粒子通过追随当前的最好极值在D维空间中“移动”, 以搜索全局最优解。粒子的速度向量和位置向量由以下更新公式确定

V ${}_i^{k+1}$ =V ${}_i^k$ +c₁r₁ (P ${}_i^k$ -X ${}_i^k$) +c₂r₂ (P_g^k-X ${}_i^k$) (7)

X ${}_i^{k+1}$ =X ${}_i^k$ +V ${}_i^{k+1}$ (8)

式中: i为粒子的序号; k为迭代次数; V_i为第i个粒子的速度向量; X_i为第i个粒子的位置向量; c₁和c₂为学习因子, 通常取c₁=c₂=2.0;P_i为第i个粒子迄今为止搜索到的个体极值点向量; P_g为整个粒子群迄今为止搜索到的全局极值点向量; r₁、r₂分别为2个独立的介于[0, 1]之间的随机数。

3.2   位置和速度的表示

所有延误了的航班按照航班时刻表中的顺序设置标号分别为1、2、3、…、N。位置向量表示为问题的一个解序列, 即

$\mathit{X}=(a{}_1,a{}_2,\cdots ,a{}_l,\cdots ,a{}_{{\rm N}})$

式中: a_l为第l个要调度的航班标号。速度向量可表示为位置向量的交换序^[4], 交换序的作用是通过交换位置向量的元素来得到新的位置向量。引入交换序后, 基本粒子群算法的更新公式为

V ${}_i^{k+1}$ =V ${}_i^k$ ♁α (P ${}_i^k$ -X ${}_i^k$) ♁β (P_g^k-X ${}_i^k$) (9)

X ${}_i^{k+1}$ =X ${}_i^k$ +V ${}_i^{k+1}$ (10)

式中: ⊕表示交换序的合并运算; 符号+具有新的含义, 表示将交换序作用到位置向量上; α、β分别为介于[0, 1]之间的随机数。

3.3   算法步骤描述

为了提高粒子群算法的搜索效率, 本文将局部搜索方法引入到粒子群算法中。采用的局部搜索方法为: 对于每个粒子随机多次交换位置向量的2个元素, 如果交换后的位置向量的适应值好于粒子的当前个体极值点的适应值, 则更新当前个体极值点。在局部搜索完成以后, 由所有粒子的当前个体极值点更新当前全局极值点。综上所述, HPSOA的算法步骤描述如下。

步骤1:设定粒子的总数P_c和最大迭代次数k_max, 给每个粒子赋一个随机的初始解和一个随机的交换序, 并初始化P_i和P_g。

步骤2:对每个粒子的位置向量进行多次交换, 如果交换后的位置向量的适应值好于粒子的当前个体极值点的适应值, 更新粒子的当前个体极值点向量P_i。

步骤3:如果某个粒子的个体极值点的适应值比当前的全局极值点的适应值好, 则用此个体极值点更新当前P_g。

步骤4:如果当前迭代次数等于k_max, 转步骤6。

步骤5:对于每个粒子, 根据式(9)、(10) 计算新的速度和位置, 及新位置的适应值, 如果其比粒子的当前个体极值点的适应值好, 则用新的位置更新当前个体极值点, 转步骤2。

步骤6:输出求得的最优解及其适应值。

HPSOA的算法流程见图 2。

图  2  HPSOA流程

Figure  2.  HPSOA flow

下载: 全尺寸图片 幻灯片

4.   仿真结果分析

首都机场的航班数据见表 4, 本文采用HPSOA进行仿真, 算法参数设置如下: P_c为30, k_max为50, R_t为10∶20∶00。为了调度的快速和安全, 航班调度的时间间隔设置为2 min, 局部搜索中的交换次数为4。

表  4  航班数据

Table  4.  Scheduled flight data

航班号	机型	计划起飞时刻	目的机场	最大载客人数
1	H	8∶00∶00	上海虹桥机场	420
2	H	8∶05∶00	上海虹桥机场	440
3	M	8∶10∶00	海口美兰机场	138
4	M	8∶10∶00	西安咸阳机场	189
5	M	8∶15∶00	海口美兰机场	189
6	M	8∶15∶00	兰州中川机场	189
7	M	8∶20∶00	昆明巫家坝机场	162
8	H	8∶25∶00	西安咸阳机场	440
9	M	8∶30∶00	福州长乐机场	189
10	H	8∶30∶00	上海虹桥机场	335
38	M	10∶00∶00	上海虹桥机场	180
39	M	10∶05∶00	广州白云机场	180
40	M	10∶05∶00	杭州萧山机场	189
41	H	10∶10∶00	大连周水子机场	290
42	M	10∶15∶00	广州白云机场	180

下载: 导出CSV 

| 显示表格

根据表 4中的数据, FCFS策略和HPSOA的排序结果见表 5。HPSOA结果比FCFS策略节约了53 650元, 延误经济损失减少4.2%, 因此, 按照HPSOA的排序结果调度航班, 可以更有效地减少延误经济损失。

表  5  HPSOA和FCFS策略的排序

Table  5.  Sequencings of HPSOA and FCFS strategy

下载: 导出CSV 

| 显示表格

为了比较算法, 本文采用单一PSOA和进化策略(ES) 算法, 来优化航班延误恢复调度。其中, ES算法采用(μ, λ) 策略, 策略系数μ、λ分别为30、50, 采用基于航班号的编码方式, 重组操作采用次序杂交算子。突变算子采用扩展“倒位”操作的方法, 个体突变采用2点位置外侧子串交换的方法, 即在进行突变的个体中, 随机选择2点位置, 并将此2点位置外侧的子串进行交换, 从而得到新的个体。

本文设定PSOA的参数和HPSOA的相同, ES的最大迭代次数也为50次。在Pentium 4、2.26 GHz、256 MB的计算机上, 利用HPSOA、PSOA和ES分别连续优化10次得到的结果见表 6~8。从表 6~8可以看出, HPSOA的最好结果为1 224 727元, 最差结果为1 236 867元, PSOA的最好结果为1 249 071元, ES的最好结果为1 248 396元, HPSOA连续10次计算的优化结果都明显比PSOA和ES的优化结果好, 而且HPSOA的最差结果比PSOA和ES的最好结果要好, HPSOA求解RSFD的寻优能力比PSOA和ES要强。由于HPSOA采用了局部搜索方法, 在计算时间方面比另2种算法要长, 但这些时间是可以接受的。HPSOA的最好结果比PSOA节约了24 344元, 比ES节约了23 669元, HPSOA比PSOA、ES平均减少损失2.0%左右, HPSOA所花费的时间是值得的。

表  6  HPSOA优化结果

Table  6.  Optimization results of HPSOA

优化次数	总经济损失/元	计算时间/s
1	1 231 251	221
2	1 235 379	222
3	1 224 727	261
4	1 231 018	196
5	1 235 816	254
6	1 236 313	133
7	1 227 700	231
8	1 236 849	252
9	1 232 421	148
10	1 236 867	251

下载: 导出CSV 

| 显示表格

表  7  PSOA优化结果

Table  7.  Optimization results of PSOA

优化次数	总经济损失/元	计算时间/s
1	1 250 798	48
2	1 254 921	48
3	1 255 222	38
4	1 249 071	39
5	1 258 400	46
6	1 249 601	20
7	1 254 439	37
8	1 254 224	42
9	1 253 272	52
10	1 258 059	32

下载: 导出CSV 

| 显示表格

表  8  ES优化结果

Table  8.  Optimization results of ES

优化次数	总经济损失/元	计算时间/s
1	1 254 392	61
2	1 251 608	34
3	1 256 148	76
4	1 252 655	79
5	1 259 735	43
6	1 253 079	73
7	1 251 740	82
8	1 249 876	55
9	1 253 875	68
10	1 248 396	54

下载: 导出CSV 

| 显示表格

HPSOA、PSOA和ES求得最好结果时的收敛过程见图 3。从图 3可以看出, HPSOA算法使整个粒子群快速地向最优结果靠近, 在种群的整体寻优性能上优于其他2种算法。HPSOA采用了局部搜索方法, 能够有效地跳出局部最优, 从而找到更优的结果, HPSOA和PSOA的收敛过程比较可以证明这一点。

图  3  收敛过程

Figure  3.  Convergence processes

下载: 全尺寸图片 幻灯片

5.   结语

本文围绕混合粒子群算法在航班延误恢复调度中的应用进行了研究。为了使航班延误恢复调度更加合理, 目标函数设计综合考虑了航班延误的经济效益和社会影响, 把航班延误的经济损失成本分为显性成本和隐性成本, 尤其在很难确定的航班延误隐性航线损失上, 参考了航线价值及航线航班数量定义了航线影响因子, 从而构建了一种新的航班延误恢复调度模型。为提高算法的求解精度, 将局部搜索方法引入到粒子群算法中, 提出了求解航班延误恢复调度问题的混合粒子群算法。并针对首都机场的某时段离港航班数据进行了仿真试验, 结果表明, 混合粒子群算法与目前使用的FCFS调度方法相比, 可以减少航班延误损失, 而与基本粒子群算法、进化策略2种算法对比, 混合粒子群算法求解精度上优于其他2种算法, 并且随着航班延误恢复规模的增加, 算法优势会更明显。

航班延误的恢复调度是一个综合的复杂系统, 怎样设置航线影响因子, 衡量和评估航班延误的经济损失, 有待进一步研究。本文重点考虑了离港延误的情况, 而与其相对的到港延误以及相关的飞机、机组、地面服务、空中流量等综合因素的分析, 也是值得未来深入研究的。