2017年中国研究生数学建模竞赛C题

2017年中国研究生数学建模竞赛C题

航班恢复问题

1. 背景

随着经济的发展，航空出行已成为越来越多旅客的选择。但众所周知，飞机航班如果不能按原计划执行，不仅会给航空公司造成巨大的经济损失，同时还会给旅客出行带来极大的不便。在造成航班不正常的种种因素中，有些是不可抗阻的自然因素，如暴风雪、飓风等，有些是不可预测的突发事件，如突发恐怖袭击、飞机机械故障等等，还有些是因为管理手段的落后，比如飞行员缺位、空中管制，等等。下表是FlightStats网站公布的今年二月份世界主要航空公司和部分中国航空公司航班准点率的比较。可以看出，虽然中国的航班准点率很低，但其他国家和地区也不乐观，比如美国本土的平均航班准点率也只有77%。

航空公司 Iberia Singapore (新航) Delta (美三角) American (美航) 名次 1 2 3 6 准点率% 92.45 88.14% 87.54 86.2 航空公司 United (美联航) Cathy Pacific (国泰) Air China (国航) China Eastern (东航) 名次 19 30 38 39 准点率% 81.99 75.03 66.55 61.74 需要指出的是，由于目前中国航空公司在国内主要航线上航班安排已经比较稠密，一旦某个航班出现故障，就有可能造成一系列的连锁反应，影响成千上万旅客的出行。一些航空公司没有把航班延误作为要事来抓，缺乏有效应对手段。如果抱着“等着瞧”的消极态度，不仅可能造成更多的没有必要的延误，而且还会导致最终产生一个失败的决策。例如航空公司在等待3个小时后，最终决定取消该航班，部分旅客被安置到此后2小时以后的某航班上。这样的结局显然不如一开始就宣布取消该航班，把旅客延迟到某航班上。

世界范围内，近年来快速增长的航空旅客数量已超过了很多主要机场的容量，加上近年气候的反常变化和安全突发事件的增多，航班恢复问题越来越受到各国民航管理机构和各大航空公司的重视，中国主要航空公司也已经把航班恢复的自动化提到了议事日程上了。

最近发生的美国联航乘客被打事件，表面上是一个旅客服务管理问题，但本质上是航班恢复管理不慎造成的结果。联航为了避免外地航班机组人员缺位，紧急从芝加

1

哥基地调遣机组前往。由于机组缺位造成的航班中断有扩散到整个网络的可能，联航赋予了他们很高的登机优先级。这些都是正确的决策并且被正确地执行了，但在最后环节，联航工作人员没有能把座位―拍卖‖坚持到最后时刻，从而导致了世界民航史上的这一重大事件的发生，给联航造成了不可挽回的重大损失。

其实，航班恢复问题的“难”除了相关因素的复杂，更主要的原因在于恢复方案的即时性。航班紊乱发生后，恢复方案的决定和实施是越早越好。在手工调整的情况下，调度员只能考虑到影响飞行安全的一些基本因素，很难考虑到全局网络的优化，更别说11了。举个最简单的例子，假如飞行网络中有一架飞机出现故障需要检修，受影响的航班可能不超过10个，具有多年调度经验的调度员大概需要几十分钟甚至1~2小时进行航班手工调整。可以想象，如果飞行网络出现大面积紊乱，受影响的航班可能有几十个甚至上百个，期望调度员手工在十几分钟甚至几分钟内完成整个网络的调整一定是异想天开，但借助于计算机求解数学优化模型却是可行的。

要最终可行，还有两个关键因素必须解决：1.如何创建合适的数学模型；2.如何用合适的算法快速求解这个数学模型。学术界研究航班恢复问题已经很久，取得了很好的进展，但业界至今还很少有实际的应用解决方案。因为理论研究一般都局限于有限的时间和空间，运行约束也仅仅是实际约束的部分子集，这样的方法很难被航空公司的运控部门采纳而直接用于生产实践。目前世界上提供解决航班恢复问题的产品寥寥无几，具有完整功能、满足各种实际需求的产品还只有Sabre一家。本赛题就是针对以上这两个问题而设计的。Sabre公司通过在高校开展学术竞赛来提高学术界对不正常航班的恢复研究的关注度。更多相关的资料可以在以下网页浏览下载， http://page.sabreairlinesolutions.com/orcompetitions。 总而言之，创建合适的数学模型和采用行之有效的算法求解是解决航班恢复问题的关键。目前，学术界一般采用decomposition（例如Bender’s Decomposition或者Column Generation）的方法来求解这一类整数规划模型【1】【4】，更好的算法还有待于发现.

2. 问题介绍

航班恢复问题本质上是运营恢复问题的一部分。或者说，广义的航班恢复就是运营恢复，包括（狭义的）航班恢复（Flight Recovery）、机组恢复（Crew Recovery）和旅客行程重新规划（Passenger Re-accommodation）三部分，它们相互约束，构成一个

2

整体上超大规模的运筹优化问题。这个优化问题具有难以想象的复杂度，不是工业界目前已有计算机的计算能力所及。在实际运营过程中，航空公司是按流程次序先考虑航班恢复，然后在此基础上机组恢复，最后重新规划旅客的行程，把他们送往各自的目的地。相应地，采用运筹优化方法解决运营恢复问题也是按这三步把整个大问题按阶段次序分解成子问题【1】，即首先求解航班恢复问题，在此基础上求解机组恢复问题和旅客行程再规划问题。

需要指出的是，由于缺少信息交互，虽然每个子问题的求解可以达到局部最优，但整体最优却得不到保证，甚至有出现不可行解的可能。已经有学者证明，整合两个或者三个子问题成一个单一数学模型，可以得到更好质量的解【4】。所以本赛题作为航班恢复问题由四个子题目组成，从最基本的单一机型的航班恢复，多机型恢复，最后到考虑旅客行程重新规划的航班恢复。为了避免过于复杂化，本赛题不考虑机组人员的恢复，也不考虑旅客行程重新规划。

针对航班恢复问题，通常有三种航班调整方法：航班延误、飞机置换和航班取消。航班延误和飞机置换可以同时发生。 航班延误

如果选择航班延误，还需要给出具体的延误时间（以分钟为单位）。通常航空公司对延误都有最大延误时间约束，本赛题规定航班最大延误时间为5小时，即延误超过5小时时一定取消该航班。以间隔10分钟为一个决策单位，那么一个航班就有30个延误决策可选。航班延误的代价除了旅客满意度降低外，更重要的是联程旅客可能赶不上下趟航班。

本赛题规定，飞机的飞行时间不会因延误而受影响。 飞机置换

飞机置换就是将航班安排给不同于原计划执行飞机的其他飞机去执行。如下图所示，按计划，航班1连接航班3由飞机A执行，航班2连接航班4由飞机B执行。但由于延误，飞机A执行完航班1后没有足够时间间隔，无法及时执行航班3。于是，调度员将航班3安排给飞机B，航班4安排给飞机A去执行。

3

飞机A 航班1 航班3 调整后： 飞机A 航班1 航班4 飞机B 航班2 航班4 飞机B 航班2 航班3 图一：飞机置换

飞机置换并不需要在完全相同的飞机之间进行，航空公司可以安排给满足约束条件的任何其它飞机。实际操作中，一般安排给同机型家族（比如A320 ），或者同子机型（比如A320-200）的任何一架飞机。飞机置换通常是最佳航班恢复方案，只要能满足最小飞机间隔时间就行。但这种机会不总是存在。

飞机间隔时间是指同一架飞机在执行完上一趟航班到执行下一趟航班前的地面停留时间。本题规定最小飞机间隔时间是45分钟。 航班取消

众所周知航班取消的含义，这里就省略解释。航班取消的代价显然是最严重的。

3. 数学模型示例

下面给出一个充分简化了的航班恢复问题的线性规划模型，供参赛者理解本赛题。参赛者可以在本模型的基础上完善并引入本赛题的具体目标和约束，比如最小飞机间隔时间，恢复期开始时航班的衔接，等等。但需要指出的是，建模方法很多（比

Airport a0

??1 ??1

??1+Fly??1 ??2 Time

图二：时空网络（符号参照数学模型）

Airport a Airport a1

??2

??2+Fly??2

4

如参考文献里模型就不一样），针对同一数学模型的算法也可以很多，具体采用什么模型和算法，以期在算法复杂度、解的质量和模型简洁方面达到平衡，由参赛者自己决定。

最小化 CancelCost??? 1????? + DelayCost??? ???Dpt?? ??????? ??∈????∈????∈????约束条件 ??= ??,???∈?? ????????∈??????????= ????????,???∈??,???∈?? ??∈??????????= ??∈?????? Dpt??≤??

5

的延误决策间隔降低至1分钟（完全灵活地调整延误时间），这个问题将变得更加复杂。

除了上述时空网络的数学模型外，也可以将安排给某架飞机的所有航班考虑为一个有效路径，用列生成的方法去求解。这样可以减少因为延误时间而产生的大量决策变量【2】。

4. 赛题

本赛题有如下几个要求和规定：

1. 附件里时间的表达均为Unix格式，即从1970年1月1日0时0分0秒算起的秒数。从Unix时间格式到一般时间格式的转换可参考附件中Excel表格里的转换公式，比如 (((B2/60)/60)/24) + DATE(1970,1,1)。另外，所有时间均假设为UTC国际标准时间。

2. 所有航班只能延误，不能提前，最早起飞时间不能早于原计划的起飞时间。 3. 各航班的飞行时间是常量，即航班数据中的到达时间减去起飞时间。

4. 保证每架飞机的连续航班能首尾相连，即前一航班的到达机场与后一航班的起飞机场必须相同，而且前一航班到达时间与后一航班起飞时间之间的最小间隔时间为45分钟。

5. 所有飞机的第一个航班要满足如下两个条件：（1）航班的起飞机场与飞机的起点机场一致，（2）航班的起飞时间不早于飞机的最早可用时间。 6. 所有飞机的最后一个航班的到达时间不能晚于飞机的最晚可用时间。

7. 航班延误的决策时间点间隔为10分钟（比如，安排给X飞机并按计划起飞，安排给X飞机并延误10分钟，安排给X飞机并延误20分钟，安排给X飞机并延误30分钟，以此类推）。如果参赛者有能力通过其他的数学模型找出更灵活的延误时间可以不考虑这一假设。

8. 不考虑机场可停留飞机的容量。理论上所有机场可以全天24小时工作。 9. 同行旅客是指一起订票并且行程完全一致的旅客，他们共享同一个旅客号，并作为一个整体考虑，即不能分乘不同的航班。

10. 所有航班，包括机场OVS关闭时段内的航班，它们的延误时间都需要被考虑到。为了最大可能保护航班，尽量不取消航班。

11. 数据结果提交的格式要求：参赛者除了在论文中必须叙述如何解读结果外，还

6

必须提交完整的新航班计划并作为附件与论文一起发送指定邮箱。提交的新航班计划有如下格式要求：

（1）虽然输入数据的时间都是Unix格式，所有输出数据的时间必须都是一般格

式，比如，4/22/16 16:15 表示2016年4月22日16时15分。

（2）可以在原航班数据（见后）格式的基础上，添加“新机型号”、“新飞机尾

号”、“新起飞时间”、“新到达时间”和“延误时间”。列的次序按下表示例。如有需要，参赛者还可在后面添加新列。新起飞时间和新到达时间与原时间如有不同，请用亮色标出。

（3）将问题一、问题二、问题三、问题四的新航班计划结果分别放在输出Excel

总表格的Sheet1、Sheet2、Sheet3、Sheet4中。该Excel总表格的文件名为“C参赛队号.xls”。表格各页的格式如下示例：

航班唯一编号 起飞时间 新起飞时间 到达时间 新到达时间 起飞机场 到达机场 飞机型号 新飞机型号 飞机尾号 新飞机尾号 延误时间 ……

（4）特别注意在该Excel总表格除外部文件名外，表格内容中不能有参赛队的任

何信息，否则会当废卷处理。

另外需要指出，虽然好的算法设计应该考虑到输入数据的各种不同可能性，本赛题局限于求解附件里的具体案例。

由于受到暴风雪的影响，管理部门决定在2016年4月22 日的18:00到21:00之间关闭机场OVS。在该时间段内该机场不能起飞或降落任何航班，而该时间段之前的所有航班都处于正常状态，该时间段之后机场可立即恢复正常起降。因此，原定在该日18:00至21:00之间（不包括18：00和21：00这两个时刻）起降的所有航班都需要重新安排，而且它们的重新安排可能造成关闭后其它航班的重新安排。由于OVS机场的跑道限制，该机场每5分钟最多能起飞5架飞机，同时降落5架飞机。例如在21:00 - 21:05之间（不包括21:05时间点）最多有5个起飞航班和5个降落航班，其起飞和降落时间都可以按21:00计算；在21:05 - 21:10之间（不包括21:10时间点）最多有5个起飞航班和5个降落航班，其起飞和降落时间都可以按21:05计算；以此类推。其它机场不需要考虑跑道限制。

7

附件中给出了该航空公司在相关时间段内所有航班计划、飞机和旅客信息。摘录部分如下以便理解。

航班数据（Schedules）示例

航班唯一编号 174774150 174774124 174777506 174777482 174777574 174773996 … 起飞时间 1461341700 1461351000 1461393900 1461403200 1461413400 1461325560 … 到达时间 1461348120 1461356760 1461399900 1461409500 1461422400 1461335280 … 起飞机场 OVS LEH OVS FUK OVS GAZ … 到达机场 LEH OVS FUK OVS KMM OVS … 飞机型号 9 9 9 9 9 9 … 飞机尾号 41098 41098 41098 41098 41098 51098 … …… 飞机数据（Aircrafts）示例

飞机尾号 41098 51098 32098 42098 82098 23098 14098 44098 64098 15098 75098 … 飞机型号 9 9 9 9 9 9 9 9 9 9 9 … 最早可用时间 1461333600 1461325560 1461330660 1461302220 1461326400 1461330000 1461326820 1461325620 1461323880 1461326220 1461323700 … 最晚可用时间 1461426000 1461426000 1461445800 1461424200 1461428400 1461444600 1461428700 1461423900 1461482400 1461510000 1461445800 … 起点机场 OVS GAZ VOR OVS OVS QSM OVS OVS OVS OVS OVS … 座位数 87 87 87 87 87 87 87 87 87 87 87 … …… 旅客数据（Paxinfo）示例

旅客号 航班唯一编号 1 1 2 2 3 3 4 174777880 174781120 174773867 174778110 174778406 174777718 174777706 8

同行旅客数量 14 14 7 7 10 10 11 4 … 174777942 … 11 … 如果一个旅客号对应多个记录表示该旅客号搭乘多个联程航班，例如旅客号1搭乘了航班174777880和航班174781120。如果一个旅客号只对应一个记录则表示该旅客号只搭乘一个直飞航班。该数据只用于求解第四问。 流控数据（Airportclosures）示例

机场 OVS 关闭开始时间 1461348000 关闭结束时间 1461358800

第一问：不考虑旅客信息，如何重新规划机型9（不考虑其他机型）的航班计划，制定起飞时间表（给出延误分钟），使得所有原计划安排给机型9的航班尽可能不被取消，同时保证机型9的所有航班总体延误时间最短？此题可参考文献【3】。

第二问：不考虑旅客信息，假定同一机型的所有飞机的载客量相同，其间航班调整没有成本，但在不同机型间调整有成本。比方说飞机DIBPV属于320机型，飞机COBPV属于321机型，航班174774110原计划是安排给飞机DIBPV执行，如果将174774110分配给飞机COBPV执行则需要产生额外的成本。假设此额外成本等价于航班延误半小时（置换和延误有可能会同时发生，则成本叠加）。在这样的假设下如何重新规划飞机航班（包括所有机型的所有航班），制定起飞时间表（给出延误分钟）使原计划航班尽可能不被取消，同时保证所有航班总体延误时间最短？

第三问：进一步考虑飞机的载客量，假设在不同机型间调整航班的成本除了航班本身延误半小时外，还要加上不能登机旅客的成本（这里仍不考虑旅客的联程信息，即假定旅客行程都是直达的，并假设所有航班都是100%的上座率）。比如飞机DIBPV的载客量是140人，COBPV的载客量是170人。如果将飞机COBPV的航班分给DIBPV去执行，将会有30名旅客因没有座位而无法登机。但如果将DIBPV的原计划航班分配给COBPV去执行则没有这种情况。假设一名旅客无法登机与该旅客延误2小时的成本相当，该如何重新规划航班以保证旅客总体延误时间最短？

第四问：在第二题的基础上，假设在不同机型间调整航班不考虑成本。我们在旅客数据中提供了旅客的行程信息，包括旅客号，同行旅客数量，和相应的航班。每个旅客行程中的相连航班间最少需要45分钟间隔时间用于中转，如23日的航班174778458（02:05 JOG—03:00 OVS）与23日的航班174777524 (05:50 OVS – 08:10 XVS) 的间隔时间为2小时50分钟。旅客的延误按照旅客计划到达最终目的地时间为

9

基准计算。例如在案例中旅客号为6的旅客计划到达XVS时间是23日08:10，如果不晚于该时间到达则延误为0，如果到达XVS时间是23日08:40则延误时间是30分钟，考虑旅客号为6的同行旅客数量为8，则总体延误时间是8*30=240分钟。假定旅客号为6的旅客最终不能到达目的地相当于总体延误了8*24小时。该如何重新规划航班以保证旅客总体延误时间最短？如果某旅客号对应的航班号在航班表里找不到相应记录则不需要考虑该旅客。如果某航班没有对应的旅客信息，可认为该航班目前没有乘客，则延误该航班没有成本代价。

参考文献

[1] Jon D. Petersen, Gustaf S?lveling, John-Paul Clarke, Ellis L. Johnson, and Sergey

Shebalov (2012). An Optimization Approach to Airline Integrated Recovery. Transportation Science, 46(4), 482-500

[2] J. M. Rosenberger, E. L. Johnson, G. L. Nemhauser(2003). Rerouting Aircraft for Airline Recovery. Transportation Science, 37(4), 408–421.

[3] Ahmad I. Z. Jarrah, Gang Yu, Nirup Krishnamurthy, and Ananda Rakshit (1993). A Decision Support Framework for Airline Flight Cancellations and Delays. Transportation Science, 27(3), 266-280.

[4] Stephen J. Maher (2015). Solving the Integrated Airline Recovery Problem Using Column-and-Row Generation. Transportation Science, 50(1), 216-237

10

本文来源：https://www.bwwdw.com/article/u6rr.html