收稿日期：2018-07-20
作者简介：赛秋玥（1993—），女，河北邯郸人，研究生，研究方向为交通运输智能自动化。通讯作者：毕军（1973—），男，山东济宁人，博士，教授，博士生导师。E-mail: 。
基于离散时空网络的不正常航班
可行路径生成算法
赛秋玥1，刘祎1，毕军1，张俊2
（1.北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京100044；
2.云南航信空港网络有限公司，云南昆明650051）
摘要：不正常航班是航空运输面临的重要问题，为减少不正常航班给航空公司及旅客出行带来的负面影响，充分考虑航班
的时空特性和运行环境，设计了不正常航班离散时空网络的构建算法，并且基于所构建的离散时空网络提出可行路径的生成算法。通过该算法可以为不正常航班下的可用飞机生成可行路径集合。基于航班时
空网络图设计算例对提出的算法进行验证，实验结果表明通过可行路径算法可以为不正常航班飞机生成可行路径，所提出的算法具有可行性。
关键词：不正常航班；离散时空网络；可行路径；算法设计中图分类号：U8
qq飞车消费券文献标识码：A
0引言
航空公司在执行航班任务时，由于受到恶劣天气等突发事件的影响而无法按照原计划执行的航班被称为不正常航班。不正常航班一直是困扰世界各大航空公司的难题，能否及时有效地处理和恢复不正常航班是影响航空公司运营效益和服务水平的重要因素之一。随着航空运输业的发展，不正常航班问题越来越受到社会和学界的关注，而实现不正常航班有效恢复的先决条件是当不正常航班出现时，能够根据当前条件确定不正常航班的可行路径，为制订不正常航班恢复方案奠定基础。目前，国内航空公司大多采用辅助人工决策的航班调整系统确定可行路径，其效率已无法满足日益复杂的航班运行环境。因而，研究如何建立有效的不正常航班可行路径生成方法对于实现航班恢复意义重大。
为降低不正常航班带来的负面影响，国内外学者针对不正常航班恢复问题进行了相关研究。Teodorovi ć和Guberi⁃ni ć首次提出以航线网络的旅客延误时间最小为目标建立航班恢复模型，并采用分支定界法
求解模型[1]。Bratu 和Barn⁃hart 提出了一种以减少航空公司的总运营成本为目标的不正常航班恢复模型和算法[2]。白凤等将通过建立多商品网络流模型对不正常航班问题进行研究[3]。张力菠等对现有的不正常航班调度模型和算法进行总结研究，并在现有的网络基础上增加了考虑摆渡飞机的情况，同时提出了并行的GRASP 算法[4]。Li 和Wallace 提出一种连续时间的飞机路线模型，以航班延误成本最小为目标，模型结果可以获得航班路线的近似最优方案[5]。张旭将不确定理论引入不正常航班恢复问题中，建立基于旅客失望信度和成本最小的不确
定航班恢复模型[6]。Maher 通过整合时间表、机组和飞机恢复阶段，提出了完整的不正常航班恢复模型，采用行列生成算法进行求解[7]。
纵观现有研究，没有充分利用航班计划的时空特性，并且在确定航班可行路径时通常采用遍历、非线性建模等方法，求解复杂且计算量大，无法保证恢复方案的实时性和有效性。为此，本文将基于离散时空网络提出一种不正常航班可行路径生成算法。充分考虑航班计划的时空特性和运行环境，提出不正常航班离散时空网络的构建算法，在构建离散时空网络的基础上，设计不正常航班飞机可行路径生成算法，为航空公司制订不正常航班恢复方案提供决策支持。
1离散时空网络建立
离散时空网络是将发生故障的时间段按照一定的时间间隔进行离散化，并以每段时间的起点时间来代
表整个时段，即将故障时段转化为许多的时间点。聚合每个时间段内各机场的活动，包括此时段内所有可能到达和离开的航班。最终输出一个二维平面的网络，网络中的每个节点都有两个坐标（横坐标为机场，纵坐标为时间点），表示在特定时间段内某个机场的可能活动[8]。离散时空网络可以通过节点和弧来表示航班计划表中所有航班的网络结构[9]，通过节点和弧的参数可以反映出航班的各项基本要素，如起降机场、起降时间等。不正常航班的离散时空网络需要在原航班计划表的基础上综合考虑导致不正常航班的原因、恢复期的时间段、恢复期开始时飞机的初始状态、恢复策略及其成本等，同时构建过程中还需要满足航班计划编排的
儿童学英语167
各项约束条件。考虑飞机故障和机场关闭这两种情形，建立不正常航班离散时空网络的步骤如下。
（1）数据输入。需要输入的数据包括机场数据、航班数据、飞机数据和其他数据，具体信息如表1～表4所示。
表1机场数据
符号
Airport_no
Curfew_time (Clo_starttime,Clo_endtime)
含义
机场名称
机场宵禁时间
机场关闭时间区间，指在该时间段内受天气或者航空管制等影响，从该机场出发的航班不能起飞、原计划到达该机场的航班不能降落或机场内不能有飞机停留。
表2航班数据
符号Flight_no
Depart_airport Depart_time Arrive_airport Arrive_time Duration
含义
航班号
出发机场
计划出发时间
怎么样谈恋爱到达机场
计划到达时间
飞行时间表3飞机数据
符号Aircraft_no
Available_airport Available_time
含义
可用飞机编号
可用飞机在恢复期开始时停留的机场
可用飞机在恢复期开始时的初始可用时间
表4其他数据
符号
Delay_cost()
Cancel_cost() (Recovery_starttime,Recovery_endtime) MCT（Minimize Connection Time）
含义
一只贝航班延误成本函数航班取消成本函数恢复期区间
最短联程时间培训手册模板
（2）生成离散时空网络。遍历可用飞机集合，对每一个可用飞机，根据其初始状态生成一个源节点。从源节点出发，按照一定的规则生成从该节点出发的航班弧，根据延误时间计算方法计算出每条航班弧的延误成本，并保存新生成的中间节点。以此循环，直到恢复期结束不再有新的中间节点生成。根据输入的数据生成机场集合、航班集合、可用飞机集合，离散时空网络的构建算法具体步骤如下：
Step1：定义源节点集合SourceNodes，中间节点集合Nodes，沉没节点集合SinkNodes，航班弧集合Arcs，沉没弧集合SinkArcs，并初始化这些集合；
Step2：初始化源节点集合SourceNodes，根据飞机的初始状态，生成一个源节点n，令源节点n的节点标记时间等于飞机的初始可用时间，将新生成的节点n放入中间节点集合，判断新生成的节点n是否在源节点集合中，更新节点n的可用时间，将新生成的节点n加入源节点集合；Step3：将源节点集合中的节点以节点标记时间Marktime的大小为条件升序排序；
Step4：开始生成中间节点和航班弧，从集合SourceNodes中移除第一个节点l，记录l的节点标记时间和所在机场，判断节点l的标记时间加中转时间是否在机场s 的关闭时间段，更新节点λ的可用时间，将节点l加入到源节点集合；
Step5：对于每个原计划从机场s出发的航班φ，生成相应的弧，记录航班φ的目的地机场、飞行时间，计算航班φ的实际出发时间，判断实际出发时间是否在机场s的宵禁时间，计算实际到达时间，判断实际出发时间加飞行时间是否在机场s′的关闭时间，计算实际到达时间，判断实际到达时间减飞行时间是否在机场s的宵禁时间，生成航班φ到达机场s′的相应中间节点γ，将节点加入到中间节点集合，连接节点λ和节点γ，生成一条航班弧α，计算航班弧α的延误时间，将航班弧加入到航班弧集合中，判断实际到达时间加MCT是否在机场的宵禁时间，判断节点是否在源节点集合，更新节点γ的可用时间，将节点加入到源节点集合；
Step6：将源节点集合中的节点以节点标记时间的大小为条件升序排序；
Step7：生成沉没弧，连接节点k与相应的沉没节点，生成一条沉没弧σ，将沉没弧σ加入到沉没弧集合中。
（3）后续处理。将每个源节点和中间节点连接到对应机场的沉没节点生成沉没弧，至此离散时空网络构建完毕。
2可行路径生成算法
飞机的可行路径代表了一个可以由飞机执行的航班列表。可行路径是基于离散时空网络中的节点和弧生成的，在生成的过程中应满足航班实际运行中的各项约束条件。首先需要找出飞机初始状态所在的节点，以此为起点将后续的航班弧进行组合形成可行路径。具体的算法流程如图1所示。
根据如图1，该算法的具体步骤如下：
Step1：定义飞机k在时空网络G中的可行路径集合R k 和单条路径中已执行航班集合F0；
Step2：根据恢复期开始时期飞机所在的节点确定飞机可能执行的第一条航班弧，将每一条从该节点出发的航班弧作为该飞机可行路径的第一个构成元素，以每个元素为起点寻找与之相连的多条初始可行路径；
Step3：定义飞机k当前任意一条可行路径为r0，逐个
将可行路径r0添加到集合R
k
中，并更新每条可行路径r0的已执行航班集合F0，确定该路径已经执行的航班列表，防止产生航班执行多次的情况；
168
Step4：针对R k 集合中的每条可行路径r 0，根据其最后
一个航班弧连接的节点，继续为路径r 0寻找下一个所有可能执行的航班弧；
Step5：判断每一条可能执行的航班弧代表的航班是否
在集合F 0中，将不在集合F 0中的可能执行的航班弧分别增
加到当前路径r 0的结尾处，形成一条新的可行路径r ，添加到可行路径集合R k 中，并更新可行路径r 的已执行航班集合F 0；
Step6：如果原可行路径r 0的新的可行路径r 都生成完
毕，则删除可行路径集合R k 中的原可行路径r 0。否则，跳转到Step4；
Step7：如果R k 集合中每条可行路径r 的最后一个航班
弧连接的是沉没节点，则停止为可行路径r 寻找下一条可执行的航班弧，并将r 作为最终的可行路径，输出最终的可行路径集合R k 。否则，跳转到Step4；
Step8：结束。
3算例
为验证可行路径生成算法的可行性，以图2构建的离散时空网络为例对该算法进行验证。
图2中，恢复期开始时有2架可用飞机，所在源节点分别为节点1和节点12。采用可行路径生成算法分别找出从节点1和节点12出发的所有可行路径，其中从节点1出发的可行路径个数为84个，从节点12出发的可行路径个数为53个。部分结果如表5所示。表中给出了源节点的部分可行路径及其对应的航班集合，以及根据每条航班弧的延误成本确定的可行路径总延误成本。
表5可行路径及相关（部分）
节点
1
12
可行路径
'arc1','arc19','arc34','arc36''arc1','arc19','arc34','arc37''arc1','arc19','arc34','arc38''arc2','arc6','arc10','arc18',
'arc41''arc2','arc3','arc11','arc22',
'arc31','arc43'
……
'arc46','arc35''arc47','arc27','arc42'
'arc45','arc13','arc33','arc38''arc48','arc49','arc52','arc35''arc48','arc49','arc53','arc28',
'arc40'
……
航班集合'22','21','11','14''22','21','11','23''22','21','11','12'
'11','12','31','34','
33''11','21','22','12','
excel表格怎么画斜线
33','32''24','21''33','32','31''13','21','22','12''31','32','24','21''31','32','33','34','
24'总成本（＄）169001670020800690013200
8200129001640082001500
实验结果表明，通过提出的基于离散时空网络的不正
常航班可行路径生成算法可以针对不正常航班得到飞机的可行路径，算法具有较好的可行性。
4结论
本文针对不正常航班问题，充分考虑航班的时空特性
和运行环境，设计了不正常航班离散时空网络，并且基于
图1飞机可行路径生成流程
图2算例时空网络图169
离散时空网络提出一种不正常航班下的飞机可行路径生成算法。通过该算法可以为不正常航班恢复提供可用路径集合，试验结果验证了算法的可行性。本文在考虑离散时空网络的复杂性时没有包含全部成本，仅对不正常航班的可行路径进行研究，未从航空公司效益和旅客出行满意度等多层面建立不正
常航班恢复优化模型。在今后的研究中，将会在本文提出方法的基础上进一步考虑多目标下的不正常航班恢复问题，建立时空网络下的多目标优化模型。
参考文献：
[1]TEODOROVIĆD,GUBERINIĆS.Optimal Dispatching
Strategy on an Airline Network After a Schedule Perturba-tion[J].European Journal of Operational Rearch,1984,15
(2):178-182.
[2]BRAUTU S,BARNHART C.Flight Operations Recov-
ery:New Approaches Considering Pasnger Recovery[J].
Journal of Scheduling,2006,9(3):279-298.
雷锋做过什么好事[3]白凤，朱金福，高强.基于列生成法的不正常航班调度
[J].系统工程理论与实践，2010，30（11）：2036-2045.[4]张力菠，鲍和映.基于离散时空网络的不正
常航班调度
模型[J].系统工程，2013（12）：60-68.
[5]LI W,WALLACE M.Disruption Management for Com-
mercial Aviation[J].Economics&Management Series, 2012:1-34.
[6]张旭.不正常航班恢复问题的不确定规划方法[D].天
津：中国民航大学，2015.
[7]MAHER S J.Solving the Integrated Airline Recovery
音像制品经营许可证Problem Using Column-and-Row Generation[M].IN-FORMS,2016.
[8]YAN S Y,SHIH Y L.A Time-Space Network Model for
Work Team Scheduling after a Major Disaster[J].Journal of the Chine Institute of Engineers,2007,30(1):63-75. [9]KLIEWER N,MELLOULI T,SUHL L.A Time–Space
Network Bad Exact Optimization Model for Multi-De-pot Bus Scheduling[J].European Journal of Operational Rearch,2006,175(3):1616-1627.
（编辑：张彦敏）
170
