陶 蕾 彭 怡

(南京航空航天大学民航学院 南京 211106)

考虑期望恢复成本的鲁棒性飞机排班模型

陶 蕾 彭 怡

(南京航空航天大学民航学院 南京 211106)

为了减少不正常航班给航空公司生产计划的实际运行带来的影响，在经典飞机排班模型的基础上，考虑航班的期望恢复成本和航班计划的鲁棒性2个因素，对飞机排班模型作了改进.从延误、取消、飞机交换和调机4种恢复措施讨论了航班期望恢复成本的构成，以总运行成本最小和总鲁棒性最大建立了双目标的鲁棒性飞机排班模型.在AIMMS软件中实现了该模型的求解，算例结果表明，在总运行成本增加不多的情况下，该模型能有效提高飞机排班计划的鲁棒性.

飞机排班；鲁棒性；恢复成本；AIMMS

0 引 言

航空公司通常以效益最大或运行成本最小来制定生产计划，但在实际运行的时候，这些生产计划往往不是最优的，因为航班计划的执行会受到天气、流量控制、飞机故障、机场关闭等不确定因素带来的扰动.这些因素导致的航班延误或取消会造成航班运行混乱、旅客不满意度增加,以及航空公司巨大的经济和声誉损失.

学术界对航班计划的优化与管理研究分为2方面，一是“事前研究”，即从航班制定的角度，通过增加航班过站时间或飞机交换机会，提高航班计划的鲁棒性.Smith等[1]提出机场纯度的概念，通过限制各机场的机型数量以增加飞机交换的机会，从而增加了航班计划的灵活性.朱星辉等[2]在此基础上提出航班纯度的概念，建立了基于航班纯度的鲁棒性机型指派模型. 二是“事后研究”，即从航班恢复的角度，考虑航班发生不正常情况后的补救措施，在一定的恢复期内使航班运行恢复到正常状态.Rosenberger等[3]建立了飞机路线的恢复模型，在目标函数中同时考虑路线分配成本和航班取消成本，并运用启发式搜索算法求解.乐美龙等[4]建立了飞机流和旅客流一体化恢复模型，让旅客、飞机、机组这3种资源的总成本最小.Peterson等[5]则建立了飞机、旅客和机组路线的一体化恢复模型.虽然相关研究较多，但并未将“事前研究”与“事后研究”联系起来.

1 飞机排班问题

1.1 时空网络图

在研究航空运输规划问题时，为了直观的表达飞机在时间和空间上的移动，方便构建相应的数学模型[6]，研究人员往往借助于时空网络图,见图1.

图1 时空网络图

时空网络图由节点与有向边组成.每个节点代表1架飞机在某个时刻从某机场起飞或到达某机场，有向边包括航班边、停场边和过夜边.航班边从出发机场节点指向到达机场节点；停场边在同一机场由上一个节点指向下一个节点；过夜边在同一机场的最后一个节点指向第一个节点，表示飞机在该机场过夜.在时空网络图中可以清楚地看出飞机路径(即航班衔接)，所以它在飞机排班问题中应用较广.

1.2 经典的飞机排班模型

飞机排班是根据由市场需求确定的航班时刻表(包括时刻、起降机场、班次、机型等)、飞机维修计划，以及飞机的技术状况，为每一架飞机安排一连串需执行的航班，即飞机路径.该问题可构造成一个集合分割问题，具体描述如下：S为飞机路线集合；F为航班集合；参数Cs为飞机路线S的运行成本；参数ais是0-1类型，航班i在飞机路线s中时值为1，否则为0；决策变量xS是一个0-1变量，当飞机路线s被选中时值为1，否则为0.假设飞机均满足维修计划的要求，则可建立如下的飞机排班模型.

min ∑s∈SCSxS

(1)

s.t. ∑s∈Saisxs=1,∀i∈F

(2)

xs={0,1}

(3)

式(1)为目标函数，为计划运行成本最小；式(2)航班覆盖约束，为每一个航班都仅在一个飞机路线中；式(3)为决策变量是一个0-1变量.该问题的变量数远远超过约束条件数，列生成算法已经可以很好地求解.值得注意的是，航班恢复模型与飞机排班模型非常相似，只需要增加一个航班取消的决策变量，并在目标函数中相应地增加航班取消的成本即可[7].

2 航班的恢复成本

2.1 延误成本

一般来说，航空公司的延误成本可以从P，A，C 3个方面计算，即旅客延误成本、飞机延误成本、机组延误成本.航空公司的延误成本结构见图2.

图2 航空公司延误成本结构图

由于航班延误成本是一项长期变动成本，航空公司通过历史财务数据的统计，将延误成本分摊在每个旅客上，得到单位时间内平均每旅客延误成本Unit Costdelay，则航班的延误成本可表示为

Cdelay=UnitCostdelay×N×T

式中：N为平均旅客数；T为平均延误时间.

2.2 取消成本

航班取消会对航空公司带来极大的经济损失，而且在实际运行中航班通常是成对取消的(即同时取消往返程)，以保证飞机路线中其他航班的可恢复性.在计算取消成本时引入机会成本的概念，即取消成本相当于航班不取消时航空公司可获得的收益，则取消成本可表示为：Ccancellation=N×P.式中：N为平均旅客数；P为平均票价.

2.3 飞机交换成本

飞机交换是指当航班发生延误时，由暂时闲置的飞机代替延误的飞机执行后续飞行任务，从而减少延误的波及，交换过程见图3～4.原计划中航班f1与f3衔接，f2与f4衔接.当f1发生延误，其到达时间晚于f2，那么可以将先到达的f2与f3衔接，后到达的f1与f4衔接，即2个任务串交换了执飞的飞机.这样可以相应地减少航班延误的时间.飞机交换成本与机型有关，同种机型的交换对航班计划影响较小.在在单机型飞机交换的情况下，假设发生一次飞机交换的成本为Cswap.

图3 原飞机任务串

图4 飞机交换后飞机任务串

2.4 调机成本

调机是指从某机场调运一架闲置飞机到其他机场执行飞行任务.当飞机出现机械故障，短时间内无法修复，则调运飞机可以帮助航班恢复运行[10].调机成本与2个机场之间的航程以及飞机的机型有关，用Cferrying表示平均调机成本.

2.5 飞机路线的期望恢复成本

在飞机排班过程中，在对每个航班指派机型之后，可生成所有可行的飞机路线集合，通过历史数据的统计与分析，可以计算出每个航班发生不正常情况后分别运用延误、取消、飞机交换、调机这4种恢复策略的概率pdelay，pcancellation，pswap，pferrying，从而该航班的期望恢复成本可以表示为

ERecoveryCost=[CdelayCcancellationCswapCferrying]·

3 考虑期望恢复成本的鲁棒性飞机排班模型

3.1 飞机排班计划的鲁棒性

在飞机排班计划的制定阶段就考虑航班延误的影响，使飞机排班计划具有一定的抗干扰能力，这就是飞机排班计划的鲁棒性.具有鲁棒性的飞机排班计划有以下4个特点：减少航班延误发生的概率，提高航班衔接的正常率；出现航班延误等不正常现象时能够快速恢复；能够有效吸收不正常现象的波及；一定程度上降低航空公司的运行成本[11].提高飞机排班计划的鲁棒性的方法包括增加航班过站时间裕度、增加飞机交换机会和采用小循环的飞机路线等.

3.2 飞机排班计划鲁棒性的定量计算

通常，航班延误分为固有延误(inherent delays)和波及延误(propagated delays).固有延误是在理想状态下航班计划本身就有的独立延误，而波及延误是由于前序航班的延误而导致的，与飞机路线有关.实际延误(actual delays)是航班计划在实际运行中产生的延误，包括固有延误和波及延误.航班计划的鲁棒性，即航班计划的可靠性，可以用固有延误和实际延误的比值表示[12].

对飞机路线s上航班I来说，鲁棒性可以定量表示为

∀i∈F,s∈S

对一条飞机路线s来说，鲁棒性可以定量表示为

∀s∈S

对整个飞机排班计划来说，鲁棒性可以定量表示为

3.3 模型提出

在经典的飞机排班模型基础上，考虑航班的恢复成本因素，以及飞机排班计划的鲁棒性，可以建立起双目标的飞机排班鲁棒性优化模型.

(4)

(5)

s.t.∑s∈Saisxs=1,∀i∈F

(6)

xs={0,1}

(7)

目标函数(4)是最小化飞机排班计划实际总运行成本，包括计划运行成本和期望恢复成本；目标函数(5)是最大化飞机排班计划鲁棒性；约束(6)表示每一个航班都仅在一个飞机路线中；式(7)表示决策变量是一个0-1变量.

3.4 模型求解

这是一个双目标规划问题，求解难度较大，可将其转化为单目标规划问题再求解.求解步骤如下.

步骤1 先求解问题式(4)，得到满足约束条件的目标函数的最小值Cmin.

步骤2 要求加入鲁棒性因素后飞机排班计划总体成本增加的比例不超过r，那么可将目标函数式(4)化为约束条件，从而得到单目标规划模型.

∑s∈Saisxs=1,∀i∈F

xs={0,1}

4 实例分析并运用AIMMS软件求解

4.1 数据

由于缺乏航空公司的真实数据，文中设计了一个算例，航班计划见表1.

表1 航班时刻表

根据表1中的航班时刻表，可以构造出所有可行的飞机路线，见表2.

表2 飞机路线集合

4.2 使用AIMMS建模并求解

AIMMS(advanced integrated multidimensional modeling software)是一款能够快速完成建模与求解的软件，它拥有集成的开发环境、求解器和图形化用户界面，为运筹学领域的研究人员提供了有效的研究工具.运用AIMMS完成算例的建模与求解过程，模型声明与求解结果分别见图5和表3.

图5 模型声明

飞机路线步骤1步骤2R1R21R31R4R5R6R7R81R9R10R111R12R13R141TotalCost22372323TotalRobustness6．28．0

模型中的各参数和变量的定义见图5，Flight和Route分别代表航班和飞机路线的集合；参数ais是0-1类型，航班i在飞机路线s中时值为1，否则为0；参数Robustness(s)表示飞机路线s的鲁棒性；参数OperationCost(s)和EstimatedRecoveryCost(s)分别代表飞机路线的运行成本和期望延误成本；参数r表示加入鲁棒性因素后成本增加的最大比例，一般由航空公司的计划制定人员设定；参数Cmin表示步骤1计算出来的最小成本；变量xs是0-1变量，当飞机路线s被选中时值为1，否则为0；变量TotalCost表示飞机排班计划的总成本，包括运行成本和期望延误成本；变量TotalRobustness表式飞机排班计划的总鲁棒性值；约束FlightCoverage(i)是航班覆盖约束，表示每一个航班i都要在一条飞机路线中；约束CminConstraint表示加入鲁棒性因素后飞机排班计划总体成本增加的比例不超过r；最后是两个目标函数，MinTotalCost和MaxTotalRobustness分别代表总运行成本最小和总鲁棒性最大.

4.3 结果分析

上述算例中，步骤1的最优解为飞机路线R3，R11和R14，加入飞机路线的期望恢复成本之后的总运行成本为2 237，总鲁棒性为6.2；步骤2设定加入鲁棒性因素后飞机排班计划总成本增加的比例不超过5%， 最终求得最优解为飞机路线R2和R8，总成本为2 323，总鲁棒性为8.0.可以发现，加入鲁棒性目标后，虽然总成本上升了3.8%，但是飞机排班计划的鲁棒性增加了29.0%，从而使排班计划更好地吸收不正常航班带来的影响.

5 结 束 语

航班受到外界因素的干扰发生延误的现象是不可避免的，为了能够在飞机排班计划的制定阶段就考虑可能会发生的航班不正常现象，在模型的目标函数中同时计算计划运行成本和期望恢复成本，以总运行成本最小建立飞机排班模型.在此基础上，为了提高计划的鲁棒性，加入了总鲁棒性最大化的目标函数，从而建立起双目标的鲁棒性飞机排班模型，并运用功能强大的AIMMS软件进行求解.

不足之处是模型中只考虑了航空公司的直接恢复成本，未考虑不正常航班带来的旅客忠诚度降低等间接成本.不正常航班如何影响旅客以后的航班选择行为是未来的研究方向.

[1]SMITH C, JOHNSON L. Robust airline fleet assignment: imposing station purity using station decomposition[J]. Transportation Science,2006,40(4):497-516.

[2]朱星辉,朱金福,高强.基于航班纯度的鲁棒性机型指派问题研究[J].预测,2011,30(1):71-74.

[3]ROSENBERGER M, JOHNSON L, NEMHAUSER L. Rerouting aircraft for airline recovery[J]. Transportation Science,2003,37(4):408-421.

[4]乐美龙,李晓岚.飞机和旅客流一体化恢复模型[J].工业工程,2013,16(5):113-119.

[5]PETERSEN D, SÖLVELING G, CLARKE J P, et al. An optimization approach to airline integrated recovery[J]. Transportation Science,2016,46(4):482-500.

[6]朱金福.航空运输规划[M].西安:西北工业大学出版社,2009.

[7]CLAUSEN J, LARSEN A, LARSEN J, et al. Disruption management in the airline industry-concepts, models and methods[J]. Computers & Operations Research,2010,37(5):809-821.

[8]ANDERSSON G T. The flight perturbation problem[J]. Transportation Planning & Technology,2004,27(2):91-117.

[9]赵文智,刘博.航班延误成本测算方法研究[J].交通运输工程与信息学报,2011,9(1):5-9.

[10]王春林.基于灰色理论的非正常航班运行研究[D].广汉:中国民用航空飞行学院,2013.

[11]何敏.航班计划的鲁棒性设计[D].南京:南京航空航天大学,2012.

[12]JASENKA P. Beyond airline disruptions[M]. America:Ashgate Publishing,2009.

Robust Modeling for Aircraft Scheduling Problem by Considering the Estimated Recovery Cost

TAO Lei PENG Yi

(CollegeofCivilAviation,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106,China)

In order to reduce the impact of disrupted flights on the actual operations of airlines, the traditional aircraft scheduling model is improved by considering the estimated recovery cost of flights and robustness of the schedule. The constituents of the recovery cost are discussed based on four recovery strategies: delay, cancellation, swap and ferrying. A two-objective robust aircraft scheduling model is presented, which aims to minimize the total actual operation cost and maximize the total robustness of the scheduling model. AIMMS software is applied to solve the model. The results show that the model could effectively enhance the robustness of schedule without much increase on cost.

aircraft scheduling; robustness; recovery cost; AIMMS

2016-08-27

F560

10.3963/j.issn.2095-3844.2016.06.033

陶蕾(1992—)：女，硕士生，主要研究领域为航空运输系统优化