不正常航班及其调度问题数学建模论文.doc

1、不正常航班及其调度问题一、 摘要本文构建了以延误成本最小最短为目标函数的航班恢复模型，航空公司可以根据需要选择不同的目标函数；细分了延误成本并采纳了旅客失望溢出成本和失望溢出率概念；采用启发式方法并调用匈牙利算法对模型求解，给出了算法的运行步骤，并与问题一及问题二的初步分析作比较，说明了模型和算法的可行性关键词:不正常航班调度；航班延误；旅客失望溢出成本;匈牙利算法二、问题的提出随着国民经济的高速发展和航空运输市场需求量的不断增长，国内各家航空公司相应加大了运力的投入。目前，我国空中交通流量分布不均衡，起降架次排名前十位机场的总起降次数占到全国总起降次数的一半以上，京、沪、穗机场到达终端区和华

2、东部分区域空中交通容量已基本处于饱和状态，致使航班延误不断增加，给航空运输企业和旅客带来了不小的直接和间接经济损失。航空公司之间的竞争日益剧烈，如何在不正常情况下实时地对航班进行调度，对飞机、机组人员进行重新优化指派，对旅客行程进行优化安排，对增加航空公司利润和提高竞争力显得尤为关键。本文由航空公司给出的不正常航班及其调度简化模型以及部分飞机飞行路线、时间、可交换机型、飞机延误、机场关闭等数据，通过个人查找资料以及给出的赔损措施设计合理的航班恢复计划，使航空公司在出现不正常的航空问题时，可以及时使对外亏损减到最小。问题一：航班ZLXY在13：00-15：00以及ZGKL在19：00-21：00

3、被迫关闭两个小时的情况下，设计一个航班恢复计划，使得航空公司损失达到最小。问题二：2153飞机14：35在机场ZSPD过站检查时发现机务故障，估计飞机当天不可使用，5145飞机14：00在机场ZGHA过站检查时发现机务故障，估计16：00可以使用。试设计一个航班恢复计划，使得航空公司损失达到最小。问题三：同时考虑机场临时关闭和发现机务故障的情况下，建立数学模型，给出一个航班恢复计划。使得航空公司损失达到最小。三、问题分析由于一架飞机在一天中要执行多个航班，各航班之间存在前后衔接关系，因此，一个航班的延误会波及到下游许多其他航班。局部的航班延误很容易演化为大面积的航班不正常。当不正常情况出现时，

4、运行调度人员会根据航班的计划时间、飞机的航线、飞机的维护和保养计划，以及机组的编排计划等一系列信息，考虑飞机资源的重新分配，提出飞机计划的调整方案，尽量使航空公司的航班能在较短的时间内恢复正常。调度人员在人工决策时，一般的指导原则是，采用最简单的调整方案，使得受影响的航班最少。我国航空公司机队规模小，飞机资源稀缺，国内航空公司在不正常航班的恢复调整中一般都采取能延误则延误，迫不得已再取消的策略，而且通常不会对计划的恢复设时间限制，只要求调整方案保证在飞行日结束恢复原计划的机型配置，尽可能不影响次日计划的执行。从解决不正常航班问题的过程来看，计划的调整主要是进行飞机的调配和机组的调配，飞机的调配

5、是为了重新部署飞机的资源，使得在未来的某一个时刻，各架飞机能够在所要求的时间处于正确的机场位置，满足更改后航班的需要。本文主要研究飞机的调配。一般来说，解决不正常航班有以下五种策略：（1）、航班顺延;（2）、飞机置换;（3）、调飞机;（4）、取消航班;（5）、合并航班。对于题中的问题，我们可以按照给出的五个方面进行分析。四、条件假设（1） 假设每一个机场中没有空闲或者备份的飞机；（2）延误成本等于单个延误事件带来成本的总和；（3）每个延误事件带来的成本是延误时间的线性函数，即：延误成本=延误时间飞机的单位时间运营成本；（4）假设无论是否发生紧急情况，飞机从一地到另一地所用时间都不会改变；（5）

6、假设航班计划没有为应对各种意外的变化留下松弛时间，即机场中飞机的降落于起飞之间的时间差恒定不变；（6）假设题目中给定的每个旅客延误一分钟的成本为一元包含航空公司的地面延误损失、空中延误损失、食宿调机损失和旅客的时间价值损失等的平均值，不包含各种情况所带来的隐性成本；（7）机场关闭期间可以正常进行飞机检修等各项飞前准备工作；（8）飞机发生机务故障检修成功后即可不必再由准备工作而直接进入正常航行；（9）假设方案尽量不打乱飞机的平衡流；（10）假设ZGKL在19:0021：00被迫关闭两个小时;（11）假设两种飞机的单位时间内运营成本相同。五、符号约定 参考文献【4】的优化处理方案，为了简化叙述，下

7、面定义一些参数和集合：是飞机指示；是航班下标；集合： ：执行航班的飞机；：替换航班，的飞机；：可用飞机的就绪时间集合；：最早延误航班之后的航班原计划到达时间集合；：最早延误航班之后的航班集合；：最早延误航班之后可用飞机集合；：能够执行，航班任务的机型集合；：能够在机场维修的机型为，的飞机集合；：当天可调用飞机的集合；变量：时间对到，的航班；：取消航班f的标志，为1取消，为0不取消；：航班上的旅客失望溢出成本，其中；：时刻就绪的飞机执行时刻的航班及后续航班的延误成本，第一项是旅客失望溢出成本，第二项是调运可使用飞机的成本；：把航班指派给可使用飞机的成本；：O，1变量，当天可用飞机指派给航班为1，

8、否则为0。六、模型建立1、航班顺延 我们考虑到：航班延误不仅造成了飞机成本，而且也带来了隐性损失。因而应结合各部分，把延误成本分为两部分：显性成本和隐性成本。显性成本即航班延误给航空公司造成的直接经济损失，其中又包括航班地面延误成本、空中延误成本和由于航班延误而导致的旅客食宿问题等。隐性成本即航班延误对航空公司声誉及形象造成损坏，航班频繁延误使航空公司在旅客面前失去信誉，这是导致高价值商务旅客流失的主要原因。（1）显性成本计算：由于基本上所有的损失都是付与待机旅客，因此为了简化问题，参考航空公司运营经验，每个旅客延误一分钟的成本为1元，取消航班按延误8小时计算延误成本。根据假设，首先计算单个航

9、班延误带来的单位时间内的飞机运营成本，然后用这段延误时间去乘上单位时间内的飞机运营成本，得到单个航班的飞机延误成本。再把航空公司飞机在该机场延误时间段的各个飞机的延误成本相加即得延误成本总和。A）单位时间内飞机运营成本计算：（标记飞机型号，为单位时间耗油，为油价）经查资料计算，飞机的单位时间内运营成本分别约为300 元/分钟。B）单个航班的飞机延误成本：，（意义同上，为该机延误时间段）C）延误总成本：，( 意义与上同)（二）隐性成本计算：由于诸多原因导致航空公司航班不能正常的在规定的航线上按时航行，这将导致旅客朋友们不能按原计划到达目的地，这势必影响到航空公司在旅客心目中的形象。甚至让选择该航

10、空公司的旅客对该航空公司产生失望情绪，导致下一次消费时放弃选择该公司的航班而选择其它公司的航班或者改用其它交通工具队对公司造成的损失旅客失望率定义：由于航班延误使旅客对航空公司信誉失望，在下一次消费选择时不选该公司航班的概率，旅客失望与延误时间有关。旅客失望溢出成本函数与旅客人数、票价和旅客失望率有关。最大失望溢出成本为本航班上的所有旅客在下一次消费是都不选择该公司的航班，此时旅客失望溢出成本为：乘客人数平均票价，旅客失望率为1，极度失望，下一次100%不选择该公司的航班。旅客失望溢出成本采用公式：。参考文献【2】，作者根据专家意见制定了旅客失望溢出率调查表，在候机厅发放调查表1000份，回收

11、有效表970份，通过曲线拟合，得到旅客失望率计算函数：，是延误时间（min）的函数。 综上所述，航班顺延不但造成飞机延误成本，还涉及旅客失望溢出成本问题。2:飞机置换飞机置换即当某一航班发生延误时,由本机场的飞机来替代延误飞机执行航班任务。简单的说即由该机场时刻航班由执行时刻航班的飞机来执行任务，其成本模型的计算类似于航班顺延成本的计算。用数学语言来描述它，即时刻航班由时刻航班的飞机来执行，则不存在飞机的等待成本但是旅客航班则延误了时间，则长生延误成本，其中成本包含旅客食宿，旅客失望溢出成本则其中为延误时间内的为旅客提供食宿费用，为航班延误的旅客失望溢出成本。同样如果飞机置换的过程中机型改变了

12、，则成本中应再加入机型改变成本这一项。3：调飞机调飞机就是从某一机场调配一架飞机到异地执行任务。在业务上考虑到成本的因素，调集一般以就近为原则，选择邻近的异地机场飞机执行任务。其中也涉及到机型是否改变问题，与飞机置换策略考虑的问题类似。由假设如果飞机出现紧急故障，可以采用调机策略来解决。飞机由其他机场调运到当前机场的成本决定于两机场之间的距离和飞机每公里运营成本两个因素，飞机每公里运营成本由其中飞机每公里运营成本由机型决定，则调飞机成本Cre表达成数学模型为：Cre调运距离机型每公里运营成本其中每种机型的飞机运营成本和年运输里程数据都可以搜集到。用各种机型的飞机的年运营成本分别除以各自的运输飞

13、行里程，即可得到各种机型的单位里程飞行运营成本。4：取消航班 取消航班及飞机不执行飞行任务，这对旅客造成的影响很大，也会给航空公司带来比较大的经济损失。因此通常尽量少取消航班。但具体到实际问题有时也不得不取消航班。因此本题取消航班可作为一个基本策略。具体如下： 取消航班成本也分为显性承办现金赔偿和隐性成本顾客失望溢出成本。由题意航空公司取消航班则要给旅客赔偿金额按八小时延误计算。顾客失望溢出成本的计算在航班顺延中已经通过调查统计得到。问题一：根据题目中的条件，航班ZLXY在13：00-15：00以及ZGKL在19：00-21：00被迫关闭两个小时，由附表中2010年6月20日整天的部分机场和路

14、线飞行路线表知：在13：00-15：00期间于ZLXY机场降落或者起飞的飞机共有两趟，其情况如下表：航线航 班起 飞机 场起 飞 时 间降 落机 场降 落 时 间2686B738ZSPD F9203ZSPD201006201000.00ZLXY201006201235.00F9282ZLXY201006201410.00ZBAA201006201555.00F9281ZBAA201006201700.00ZLXY201006201840.00F9210ZLXY201006202100.00ZSPD201006202250.005130B738ZLXYF9202ZLXY201006201300.

15、00ZSPD201006201450.00F9183ZSPD201006201550.00ZYTX201006201800.00F9184ZYTX201006201850.00ZSPD201006202050.00F9741ZSPD201006202130.00VTSP201006210210.00根据已知定义，如果考虑调飞机或者置换飞机显然不仅要求飞机延误，还要增加调飞机或者置换飞机的成本，使得航空公司的损失会更大，因此这两种方案予以舍弃。只能考虑其他三种方案。 由于此种情况比较简单，因此我们可以对各种情况进行分析。首先从表中我们得知5130航线中B738机型的飞机在13:00时已从机场ZL

16、XY起飞，再次回到ZLXY的时间为18：00。即该航线该机跳过了该机场的关闭时间。因此只考虑表中的2686航线：（a）对于航班顺延的方案：F9282航线的B738飞机，它的航班延误时间为,又由假（5），F9281、F9210航线只能依次往后延误，因此它的延误显性成本为（每个人的延误时间为,三个航线的人数依次为、，每个旅客延误分钟的成本为）隐性成本（旅客失望溢出成本）为（为该机该次的乘客数量，该机该次票价，为失望率，）此公式是在充分调研旅客溢出成本的基础上给定的。由上文的公式（）可得到（，）总的调运成本为：91437元（b）再考虑取消航班的情况：依假设（）如果我们只取消航班，由于取消航班后不需再

17、付出那一部分运营成本，故而其显性成本为（、的意义与上同，且取860480分钟，B738机型每分钟耗油体积，油价为）隐性成本（旅客失望溢出成本）为（其中为该机该次的乘客数量，该机该次票价，为失望率且取1，）由假设（5）可知，其它情况均没有上述两种情况优良。故而可以确定出在问题一的情况下不正常航班调度的恢复方案。总的调运成本为：118679元比较与可知： 延误方案可以把不正常航班的损失减少到最小。问题二: 2153飞机14：35在机场ZSPD过站检查时发现机务故障，估计飞机当天不可使用，5145飞机14：00在机场ZGHA过站检查时发现机务故障，估计16：00可以使用。根据题目中附表得到这两趟航班

18、的情况如下：航线航班起飞机场起 飞 时 间降落机场降 落 时 间2153B738RKSIRKSI201006201250.00ZSPD201006201435.00ZSPD201006201540.00VMMC201006201820.00VMMC201006201910.00ZSPD201006202140.00ZSPD201006202240.00VVNB201006210200.005145B738ZSPDZSPD201006201210.00ZGHA201006201400.00ZGHA201006201455.00ZSPD201006201630.00ZSPD201006201730

19、.00ZJHK201006202025.00ZJHK201006202120.00ZSPD201006202340.00由于飞机出现机务故障后的恢复情况有很多种,下面分航线分问题逐一简单讨论:先考虑航线2153,依表中数据可知该机B738于14：35在机场ZSPD过站检查时发现机务故障，这一情况将直接或间接影响到后继航线的正常运行。因为该机估计当天不可使用，故而航班顺延和航班取消有相同的效果:(a)航班取消（航班延误）：同问题一中情况有：由于取消航班后不需再付出那一部分运营成本，故而其显性成本为：（飞机飞过各航线的时间分别为、,三个航线的人数依次为、，每个旅客延误分钟的成本为，且取8分钟，机型

20、每分钟耗油体积，油价为）隐性成本（旅客失望溢出成本）为：（其中为该机该次的乘客数量，该机该次票价，为失望率且取1，3）总成本为P=17204元（b）飞机置换：由于该航线上的飞机B738 发生故障当天14:35分以后就不能在进入飞行系统。简单的考虑的话，我们只能选择能够在14:35分以后能经过机场ZSPD的飞机且航班较少的飞机进行置换，经过数据整理，符合条件的只有两架，分别为航线5140上的B738和航线上2500上的B767，由于5140航线的终点为VDPP，考虑到尽量不影响第二天的航线运营系统，我们予以大胆舍弃。现在考虑2500航线飞机B767：由于该机在14:35分后第一次到达机场ZSPD

21、的时间为19:10分，此时它已经完成了自己所在航线的任务。那么它可以至少执行两个航班（ZSPDVMMCZSPD）那么此期间飞机延误损失和置换飞机所用的费用为 ，由问题一中飞机延误成本的计算方法可得=108992元由于时间充足，B767飞机可以有两种选择：（1）就此等待第二天原来航线的任务；（2）继续执行2153航线的任务。那么总损失在两种情况下分别为（）、（），为取消航班ZSPDVVNB的损失，为执行此任务然后返回的损失，其中=54675元=44567元经比较第二种情况下的损失较少，因此排除第一种情况。（c）调飞机：在第（b）种情况中，B767飞机已经完成了原来的计划，而其他机种如果调过来使用

22、的话，那么显然它所需费用至少大于等于（b）种情况，因此我们可以不予考虑。我们在考虑航线5145，在机场ZGHA于下午14:00-16:00发生机务故障不可使用，考虑以下几种情况：(1)航班延误（航班取消）：计算方法与问题一中相同，可得航空公司的成本损失为:P5=104526元P6=96570元(2)航班置换、航班合并：由于只有知一架飞机到达此机场，因此考虑此种情况是没有意义的。由本问题航线2153中调飞机的分析可得，在延误时间比较少的情况下调飞机是完全没有意义的。本文对第二题的求解是基于分析分情况解得的，如果综合上述各种情况的话，问题将变得十分的复杂，更加精确的解题方法将在第三题当中予以给出。

23、经过比较上述结果易知，在假设情况下的问题二的分析中航班取消的方案较为优良。问题三： 此问题比较复杂，因此我们根据Jonathan Bard和Gang Yu等提出的时间段优化模型思路，将时间段的思想用时间点代替，能够得到精确的延误时间；提出时间对概念，每个时间对是一个航班在本地机场和目的地机场的两个时间点，一个时间对代表一个航班的起讫点；模型考虑了机型要求，每个用于替换的机型是原机型的子集，即属于可替换机型；目标函数是使延误成本最小化，最终选择哪个目标函数生成的方案由运控人员根据需要决定其中根据符号假设，以延误成本最少为目标的函数表示如下： （1）Subject to： （flight cove

24、r） （2）（aircraft cover） （3）（aircraft type requirement） （4） （5）式（1）是目标函数，使总的延误成本最小；式（2）是保证没一条航线都有航班覆盖；式（3）是保证每个航班都有飞机执行，否则就取消航班；式（4）是飞机型号的要求，保证需要替换的飞机满足型号要求；式（5）是整数约束，保证每条航线上要么有航班（取1），要么没有航班（取0）。七、模型求解对模型求解的思路是：把所有处于最早延误航班之后到达或停驻该枢纽机场的飞机、及其它可使用飞机都作为调度对象，将这些飞机重新指派给航班，使延误成本最低。得出所需要的方案对模型的求解采用启发式方法搜索置换矩阵

25、，调用匈牙利算法解决指派问题，匈牙利算法是由匈牙利科学家柯尼格(Koning)首先提出的，它是求指派问题的非常有效和简便的算法指派问题的最优解具有这样的性质，若从系数矩阵()的一行(列)各元素中分别减去该行(列)的最小元素，得到新的()矩阵，那么以新的()为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。首先构造延误时间置换矩阵其中表示时刻航班的飞机执行第时刻航班的任务所延误的时间。根据延误时问置换矩阵计算延误成本置换矩阵，表示时刻航班的飞机执行第时刻航班的任务所产生的延误成本。航班调整算法具体步骤如下：Stepl初始化1)建立延误航班表YW(已延误和即将延误的航班，字段包括：航班号、飞机

26、型号、后续旅客人数、平均票价、原计划进出港时间、延误结束时间)，对YW表中按进港时间升序排列；2)建立可用飞机总表BY(在当天机场关闭之前可以恢复使用的延误飞机，字段包括：飞机型号、航班号(初始为空)、停驻机场、到达时间、成本(初始为空)、后续旅客数(为0)；3)建立置换飞机表ZH(从航班信息表中检索在延误航班原计划到达时间之后的所有航班，字段包括：飞机型号、航班号、进、出港时间、票价及旅客数)，将ZH表追加到YW表4)建立机型表AS，表中内容是机型AS；(是i时间点出发航班的飞机机型)和它的可置换机型；Step2计算调运(ferry)飞机的成本打开YW表，for =1，打开BY表，如果BY,

27、for =l，计算BY表中的调运成本，=调运距离每公里成本；if =0，则使用该飞机执行航班，从BY表中删除记录，从YW表中删除记录，跳出循环将存入BY表中第条记录中的成本字段+，直到BY表到底Step3建立置换矩阵 将运算后的BY表追加到ZH表中，对ZH表中的航班作置换操作，是为了建立置换矩阵和打开ZH表，for =l， 1)比较ZH表中的飞机型号与记录中飞机型号是否属于可置换关系，是，则按照成本函数的公式计算溢出成本，其中：延误时间=第k条记录的到达时间一第条记录的到达时间，第条记录的旅客数和航班平均票价，将结果存入矩阵的位置行第列中，将延误时间存入的位置行第列中，否则，在矩阵只第位置(按

28、行排列)填入一相对极大数，表示此置换不可执行； 2) +，直到备用表到底，如果是备用航班，即后续旅客为0的航班，要将的调运成本加入延误成本中这样就生成了置换矩阵的第一行； 3) +，直到YW表到底最终生成了行列的置换矩阵Step4调用匈牙利算法调用匈牙利算法，进行任务指派，得到优化方案Step5输出调整后的航班表八、结果分析 通过设置问题的初始值问题三的条件与问题一的条件相同，得到的结果基本相同，这说明了该模型的正确性。九、优缺点 优点：采用时间段优化模型思路，可以同时解决各方面综合情况的问题。 缺点：由于时间仓促，且自身知识系统还有待完善，可能有些地方不太全面。附：参考文献【1】杨慧敏，不正

29、常航班调度的模型研究，中山大学应用数学专业硕士学位论文；【2】赵秀丽、朱金福、郭梅，系统工程理论与实践，2008年第28卷第4期；【3】唐小卫、高强、朱金福、吴薇薇，不正常航班恢复模型的启发式算法研究，航空运输与安全技术分论坛，2008年10月；【4】Argello M F;Bard J F;Yu G A GRASP for aircraft routing in response to groundings and delays 1997；【5】Jonathan Bard;Yu G Optimizing aircraft routing in response to groundings and delays 2001(10)。14