乐美龙;马彬
【摘 要】由于天气、交通流量、飞机故障等因素影响,航班推迟甚至取消经常发生.导致航班延误的因素一旦解除,航班恢复工作必须立即执行,为此航班优化建模求解方法的高速高效尤其重要.首先系统简要地回顾了航班优化恢复的研究现状.在此基础上,提出了飞机和机组一体化恢复的数学模型.之后通过构建飞机恢复和机组恢复的可行路径和可行配对作为输入,对建立的优化模型进行优化求解,以使其在合理的时间内,获得整合恢复的优化解.为了获得飞机恢复和机组恢复的可行路径和可行配对,设计了专门的递归算法和配对存储树方法.为了进一步提高计算速度,对计算数据进行了预处理,即将恢复限制在受扰航班中进行.这样不仅提高了求解速度,同时也最大限度地减少了受扰航班数.计算试验表明,该方法较之飞机、机组分阶段优化恢复,优度明显提升,而且求解速度快,可用于航空公司中小规模的航班恢复. 【期刊名称】《南京航空航天大学学报》
【年(卷),期】2015(047)004
【总页数】10页(P487-496)
【关键词】航班恢复;飞机恢复;机组恢复;运作优化;启发式算法
【作 者】乐美龙;马彬
【作者单位】南京航空航天大学民航学院,南京,210016;上海唯智信息技术有限公司,上海,200051
【正文语种】中 文
【中图分类】V355.2
由于天气、机场容量、航路交通流量、军事活动、飞机故障、机组人员和旅客缺位等因素影响，航班推迟甚至取消经常发生。据报道，2014年，中国全民航系统航班正常率只有68%，重要机场的航班正常率只有40%左右。每航班的平均延误时间超过1 h。航班一旦发生延误和取消，不仅让航空公司蒙受巨额经济损失，同时对机场、空管等相关方的平稳运作，尤其是对旅客的出行造成不便。有些长延误航班甚至已经影响到了社会的。为此，开展航空公司航班的优化恢复研究十分必要。
Jedlinsky[1]大概是最早开展航班优化恢复研究的学者。自此之后，从飞机、机组、旅客单一资源恢复到双资源整合恢复，再到飞机、机组、旅客整体恢复，开展了一系列研究。
1.1 飞机优化恢复研究
Teodorovic等 [2]是早期致力于解决飞机恢复问题的学者。文献[2]在考虑不增加飞机原有数量的前提下，建立了最小化乘客延误总时间的数学模型，并采用分支定界法进行了求解。但其只考虑航班的交换和延误，没有将航班取消纳入模型。
野外焊接钢轨台湾学者Yan 和Yang[3]的研究则着眼于在飞机故障情况下为调度员开展飞机恢复建立一个基本模型框架。通过改变目标函数或边界约束来修改模型。该模型与前人最大不同在于引入了调机策略。
Kanafani[4-5]首次采用了时空网络。他们将飞机恢复问题转换为一个时空网络模型。时空网络的应用还出现在Bard等[6]对飞机短缺情况的研究中。
Arguello等 [7]是研究飞机恢复的集大成者，其研究开启了应用启发式算法解决该问题的先河。文献[7]提出了应用贪婪随机自适应搜索算法(Greedy randomized adaptive search pro桑叶采摘器
cedure, GRASP)解决在飞机短缺情况下的飞机重指派问题，同时将飞机流量平衡纳入约束考虑范围。2000年，Thengvall等[8]提出在目标函数中考虑航空公司调度人员的偏好，在此基础上建立同时考虑延误和取消策略并带边界约束的网络模型。当无法获得整数解时，通过线性松弛得到最优解或次优解。2001年，Thengvall等[9]将单一机队扩展到多机队，对在枢纽机场关闭这种航班中断程度较为严重时的飞机恢复问题进行了研究，提出了3个多商品流网络模型。3个模型均考虑延误、取消和调机策略。前两个为纯网络模型，以最大化航空公司的利润为目标；最后一个为离散时空网络模型，以最小化延误成本和取消成本为目标。通过比较求解时间和解的质量，证明第一个模型明显优于其他两个模型。2003年，Thengvall等[10]设计了集束方法来解决枢纽机场关闭问题。
Rosenberger[11]及Bisaillon[12]分别提出了飞机选择启发式算法和大规模邻域搜索启发式算法来解决此问题。Rosenberger的贡献还在于将飞机恢复问题视为带有时间窗和时槽的集覆盖问题。最新的研究是Hua和Froyland的研究。Hua等[13]在重新安排航班时，考虑了旅客换乘所需时间。Froyland等[14]则将恢复研究从“事后”转为“事前”，通过建立易恢复的飞机鲁棒指派来简化飞机恢复。
废液处理
在中国国内，也有不少学者开展了飞机恢复研究。朱金福在《航空运输规划》里系统阐述了航空运输规划和恢复问题，是目前中国国内少有的详细介绍航空运输规划的著作。与其有异曲同工之妙的是由邵龙等翻译的《航空公司运营规划与管理》一书。后者对航空公司不正常运营中飞机恢复问题作了较为详尽的案例分析。
姚韵[15]在其博士论文中，针对航班计划和飞机恢复问题，建立了时空网络模型，并设计了一种基于路径置换的调度算法，文章考虑了单航班、多航班及多机型置换情况。通过算例证明了该算法的有效性、可优性及可控性。 唐小卫等 [16]就飞机恢复问题考虑了飞机流不平衡，设计了贪婪模拟退火算法。赵秀丽等[17]提出了逐延误指派算法。白凤等[18]则采用列生成算法来解决该问题。笔者课题组也对飞机恢复问题进行了一定的研究[19-20]。
1.2 机组优化恢复研究
机组优化恢复，简称机组恢复。在该研究领域，Johnson等[21]起到了很好的引领作用。文献[21]中讨论了解决单一机组恢复问题的数学模型和方法。之后，Wei等[22]提出了一个多商品网络流模型，采用深度优先搜索算法求解。为了提高求解效率，算法对修改机组配对的数量、受影响的航班数量进行了限制。该算法更加灵活，更能满足航空公司的需求。
Lettovsky等[23]设计并实施了一种全新的机组恢复解决框架。该框架的核心在于应用预处理技术提取原航班计划中的受扰子集，重新指派给机组，并利用“机组配对产生器”枚举可行机组。
Yu等[24]为美国大陆航空公司开发了机组优化器决策支持系统，该系统可产生全局最优或局部最优的机组恢复方案。利用该系统，美国大陆航空公司据称一年可以节约大约4000万美元的运营成本。同样，Abdelghany等[25]为采用轴辐式航线网络的航空公司设计了机组恢复决策工具。该决策支持工具按航班出发顺序采用滚动方法指派机组。
Guo等[26]设计了机组恢复的遗传算法，将受中断的机组看作进化过程，同时为了提高收敛性，将局部提高方法应用其中。Guo[27]在其博士论文中将机组恢复问题视为集分割问题，在目标函数中为机组不按原配对执行任务设定惩罚值，在求解算法加入了列生成算法。
Nissen等[28]专门针对欧洲航空公司的需求提出了基于执勤期的机组重调度模型，可应用于不同程度的中断场景。模型采用分枝定价法求解。
国内单纯研究机组问题的较少，赵秀丽等[29]建立机组重调度问题的约束规划模型，并用IL
OG 优化器和模拟退火算法、禁忌搜索算法进行了求解。笔者所在的课题组也从不同的角度开展了一些研究[30-32]。
专门的旅客行程恢复的研究相对较少。开展的研究大多是从营收管理的角度出发的。此时，旅客的行程恢复一般视为多商品网络流问题，以最大化旅客行程的恢复。
1.3 航班整合优化恢复研究
航班整合优化恢复，简称整合恢复，是同时考虑飞机、机组、旅客中的二者或三者的恢复。其中，以飞机、机组二者的整合恢复研究为多。
Teodorovic等[33]是较早开展整合恢复研究的学者。文献[33]采用字典式优化技术建立航班计划一体化恢复模型，将飞机航线、飞机维修、机组配对全部纳入考虑范畴。求解时依照目标优先级依次进行优化。优化顺序依次为最小化取消的航班数、最小化乘客的延误时间。
Lettovsky等[34]提出的综合恢复模型涉及飞机、机组和乘客三者。文章的重点在于机组的恢复。除了将机组成员作为一个整体看待外，还扩展到机组人员分割情况，即将机组分为
飞行人员和乘务人员进行恢复。尽管该文提出了飞机、机组、乘客一体恢复的框架及Benders分解求解方案，但文章没有实际求解。
Abdelghany等[35]为航空公司整合恢复提供了一项航班表恢复工具DSTAR，旨在对飞机和机组进行集成恢复操作。DSTAR集成了航班表仿真模型和资源分配优化模型。首先由航班表仿真模型模拟航班运行，列出受干扰的航班，其次资源分配优化模型测试可能的资源交换和航班重排，以生成使得航班延误和取消最少的恢复计划。
Petersen等[36]是综合恢复的集大成者，包括飞机、机组和乘客行程恢复及在此基础上的航班表恢复。文章建立了统一的恢复模型SRM，然后采用Benders分解，将问题分解为3个子问题模型，即ARM,CRM和PRM，形成以SRM主问题及5种类型的Benders分解割，即ARM可行割、CRM可行割、CRM优化割、PRM可行割及PRM优化割。文章开展了缩减规模的实际问题的优化求解。
近期，不少学者开始从计划航班表本身的鲁棒性来考虑航班恢复问题。通过增加航班表的鲁棒性，来达到航班抗干扰能力。如Dunbar等[37]提出的基于典型场景的飞机、机组鲁棒调度。
国内对于整合恢复的研究主要有：
周志忠[38]在其博士论文中也提出了与Lettovsky[34]相同的实时一体化恢复框架，包含航班计划、飞机、机组、旅客行程，并设计了伪并行遗传算法。但文章并没有对具体算例进行分析和验证。
刘德刚[39]将资源分配模型和时空离散网络模型结合起来，在求解算法上提出了飞机航班恢复的列生成算法和机组恢复问题的迭代式方法，得到的满意解容易估计与最优解下界的差距。由于所用算例规模较小，也没有利用国内的数据，因此无从知晓该模型和算法是否适合中国航空公司的实际需要。
赵秀丽等[40]以航空公司人工恢复为参照，采用最小化航班延误和取消成本为目标，对航班恢复进行了比较系统的研究。由于采用了启发式算法，模型的求解速度大大提高。
笔者所在的课题组对整合恢复也进行了一定的研究[41-42]。
速记教程
本文在上述研究基础上，重点对飞机、机组整合复原进行了进一步探索。模型采用一体化建模。在模型的求解上，采用分解分步策略，即分别采用配对存储树和递归算法在缩减集金纳米颗粒
合内确定机组、飞机指派可行集，再进行优化求解。
2.1 符号定义
油泵法兰(1)集合
H：飞机集合，h∈H；
R：可行的飞行路线，r∈R；
F：航班集合，f∈F；
K：机组集合(包括备份机组)，k∈K；
P：可行的机组任务，p∈P；
Q：航班衔接集合，q∈Q；
S：机场集合，s∈S；
Smaint：维修机场集合，Smaint∈S；
Sclose[t1，t2]：在时间窗[t1，t2]内关闭的机场集合，Sclose∈S；
THdef[t1，t2]：飞机故障时间窗；
(2)参数
crh：指派路线r给飞机h的成本；
cpk：指派配对p给机组k的成本；
cf：取消航班f的成本；
df：航班f的加机组成本；
apf：当配对p包含航班f时等于1，否则等于0；
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议