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

《2017年中国研究生数学建模竞赛c题》由会员分享，可在线阅读，更多相关《2017年中国研究生数学建模竞赛c题（10页珍藏版）》请在金锄头文库上搜索。

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

2、平均航班准点率也只有 77%。航空公司 名次 准点率% 航空公司 名次 准点率%Iberia 1 92.45 United (美联航) 19 81.99Singapore (新航) 2 88.14% Cathy Pacific (国泰) 30 75.03Delta (美三角 ) 3 87.54 Air China (国航) 38 66.55American (美航) 6 86.2 China Eastern (东航) 39 61.74需要指出的是，由于目前中国航空公司在国内主要航线上航班安排已经比较稠密，一旦某个航班出现故障，就有可能造成一系列的连锁反应，影响成千上万旅客的出行。一些航空公司没

3、有把航班延误作为要事来抓，缺乏有效应对手段。如果抱着“等着瞧”的消极态度，不仅可能造成更多的没有必要的延误，而且还会导致最终产生一个失败的决策。例如航空公司在等待 3 个小时后，最终决定取消该航班，部分旅客被安置到此后 2 小时以后的某航班上。这样的结局显然不如一开始就宣布取消该航班，把旅客延迟到某航班上。世界范围内，近年来快速增长的航空旅客数量已超过了很多主要机场的容量，加上近年气候的反常变化和安全突发事件的增多，航班恢复问题越来越受到各国民航管理机构和各大航空公司的重视，中国主要航空公司也已经把航班恢复的自动化提到了议事日程上了。最近发生的美国联航乘客被打事件，表面上是一个旅客服务管理问题

4、，但本质上是航班恢复管理不慎造成的结果。联航为了避免外地航班机组人员缺位，紧急从芝加2哥基地调遣机组前往。由于机组缺位造成的航班中断有扩散到整个网络的可能，联航赋予了他们很高的登机优先级。这些都是正确的决策并且被正确地执行了，但在最后环节，联航工作人员没有能把座位“拍卖” 坚持到最后时刻，从而导致了世界民航史上的这一重大事件的发生，给联航造成了不可挽回的重大损失。其实，航班恢复问题的“难”除了相关因素的复杂，更主要的原因在于恢复方案的即时性。航班紊乱发生后，恢复方案的决定和实施是越早越好。在手工调整的情况下，调度员只能考虑到影响飞行安全的一些基本因素，很难考虑到全局网络的优化，更别说旅客的行程

5、规划或根据旅客价值信息确定航班恢复的优先级了。举个最简单的例子，假如飞行网络中有一架飞机出现故障需要检修，受影响的航班可能不超过 10 个，具有多年调度经验的调度员大概需要几十分钟甚至 12 小时进行航班手工调整。可以想象，如果飞行网络出现大面积紊乱，受影响的航班可能有几十个甚至上百个，期望调度员手工在十几分钟甚至几分钟内完成整个网络的调整一定是异想天开，但借助于计算机求解数学优化模型却是可行的。要最终可行，还有两个关键因素必须解决：1. 如何创建合适的数学模型；2. 如何用合适的算法快速求解这个数学模型。学术界研究航班恢复问题已经很久，取得了很好的进展，但业界至今还很少有实际的应用解决方案。

6、因为理论研究一般都局限于有限的时间和空间，运行约束也仅仅是实际约束的部分子集，这样的方法很难被航空公司的运控部门采纳而直接用于生产实践。目前世界上提供解决航班恢复问题的产品寥寥无几，具有完整功能、满足各种实际需求的产品还只有 Sabre 一家。本赛题就是针对以上这两个问题而设计的。Sabre 公司通过在高校开展学术竞赛来提高学术界对不正常航班的恢复研究的关注度。更多相关的资料可以在以下网页浏览下载，http:/ decomposition（例如 Benders Decomposition 或者Column Generation）的方法来求解这一类整数规划模型【1】 【4】 ，更好的算法还有待于

7、发现.2. 问题介绍航班恢复问题本质上是运营恢复问题的一部分。或者说，广义的航班恢复就是运营恢复，包括（狭义的）航班恢复（Flight Recovery） 、机组恢复（Crew Recovery）和3旅客行程重新规划（Passenger Re-accommodation）三部分，它们相互约束，构成一个整体上超大规模的运筹优化问题。这个优化问题具有难以想象的复杂度，不是工业界目前已有计算机的计算能力所及。在实际运营过程中，航空公司是按流程次序先考虑航班恢复，然后在此基础上机组恢复，最后重新规划旅客的行程，把他们送往各自的目的地。相应地，采用运筹优化方法解决运营恢复问题也是按这三步把整个大问题按阶

8、段次序分解成子问题【1】 ，即首先求解航班恢复问题，在此基础上求解机组恢复问题和旅客行程再规划问题。需要指出的是，由于缺少信息交互，虽然每个子问题的求解可以达到局部最优，但整体最优却得不到保证，甚至有出现不可行解的可能。已经有学者证明，整合两个或者三个子问题成一个单一数学模型，可以得到更好质量的解【4】 。所以本赛题作为航班恢复问题由四个子题目组成，从最基本的单一机型的航班恢复，多机型恢复，最后到考虑旅客行程重新规划的航班恢复。为了避免过于复杂化，本赛题不考虑机组人员的恢复，也不考虑旅客行程重新规划。针对航班恢复问题，通常有三种航班调整方法：航班延误、飞机置换和航班取消。航班延误和飞机置换可以

9、同时发生。航班延误如果选择航班延误，还需要给出具体的延误时间（以分钟为单位） 。通常航空公司对延误都有最大延误时间约束，本赛题规定航班最大延误时间为 5 小时，即延误超过5 小时时一定取消该航班。以间隔 10 分钟为一个决策单位，那么一个航班就有 30 个延误决策可选。航班延误的代价除了旅客满意度降低外，更重要的是联程旅客可能赶不上下趟航班。本赛题规定，飞机的飞行时间不会因延误而受影响。飞机置换飞机置换就是将航班安排给不同于原计划执行飞机的其他飞机去执行。如下图所示，按计划，航班 1 连接航班 3 由飞机 A 执行，航班 2 连接航班 4 由飞机 B 执行。但由于延误，飞机 A 执行完航班 1

10、 后没有足够时间间隔，无法及时执行航班 3。于是，调度员将航班 3 安排给飞机 B，航班 4 安排给飞机 A 去执行。4航班 1 航班 3航班 2 航班 4飞机 A飞机 B调整后：航班 1航班 3航班 2航班 4飞机 A飞机 B图一：飞机置换飞机置换并不需要在完全相同的飞机之间进行，航空公司可以安排给满足约束条件的任何其它飞机。实际操作中，一般安排给同机型家族（比如 A320 ） ，或者同子机型（比如 A320-200）的任何一架飞机。飞机置换通常是最佳航班恢复方案，只要能满足最小飞机间隔时间就行。但这种机会不总是存在。飞机间隔时间是指同一架飞机在执行完上一趟航班到执行下一趟航班前的地面停留时

11、间。本题规定最小飞机间隔时间是 45 分钟。航班取消众所周知航班取消的含义，这里就省略解释。航班取消的代价显然是最严重的。3. 数学模型示例下面给出一个充分简化了的航班恢复问题的线性规划模型，供参赛者理解本赛题。参赛者可以在本模型的基础上完善并引入本赛题的具体目标和约束，比如最小飞机间隔时间，恢复期开始时航班的衔接，等等。但需要指出的是，建模方法很多（比1Airport a图二：时空网络（符号参照数学模型）1+1212 2+2TimeAirport a0 Airport a15如参考文献里模型就不一样） ，针对同一数学模型的算法也可以很多，具体采用什么模型和算法，以期在算法复杂度、解的质量和模

12、型简洁方面达到平衡，由参赛者自己决定。最小化 (1)+()约束条件 =,=,=, , , 变量定义 : 0-1 变量，用来表示航班 是否运营. : 0-1 变量，用来表示航班 是否在时间点 起飞. : 0-1 变量，用来表示航班 是否在时间点 由飞机 起飞. : 0-1 变量，用来表示飞机 在时间点 是否停在机场 . 参数符号 : 时间轴上所考虑时间点的集合: 所有航班的集合: 所有机场的集合: 所有飞机的集合: 航班 的所有允许起飞时间点集合. : 航班 的最早允许起飞时间点, . =: 航班 的飞行时间 : 所有到达机场为 的航班集合. : 所有起飞机场为 的航班集合 . : 取消航班 的

13、成本 . : 航班 的每分钟的延误成本. 下面举例说明这个线性规划模型的复杂度。假设一个拥有 架飞机的子 |=100 机型网络有 600 个航班需要执行。最大延误时间 5 小时，每个航班有 个延误 |=30 选择，每个延误选择可以安排给 100 架飞机里的任意一架。这样大致估计共有个选择变量 。如果把这样一个有几百万 |=60030100=1.8106 个选择变量的 0-1 整数规划问题采用商用求解器（如 CPLEX 或 GUROBI）直接求解，绝无可能保证在允许的时间限制内求得最优解。实际上，这样的问题完全有可能运行6几天甚或几年才能结束。如果我们的航班恢复问题考虑到多个子机型，或者将 10

14、 分钟的延误决策间隔降低至 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. 所有飞