数学建模论文航班调度.doc

不正常航班及其调度 【摘要】 本文将不正常航班恢复抽象为动态规划中的动态网络模型,采用整数0-1规划表述。我们以航空公司恢复不正常航班的成本最小为目标函数，采用动态网络技术建模。跟据下文论证推论（1）在恢复不正常航班采用路径调整策略总路径延误时间具有不变性，建立不正常航班恢复模型。本文中三个问题可以用同一个模型阶段，只是在不同问题的情况下有不同的初始延误数据与不同的飞机的调度。最后利用lingo软件根据不同问题的实际情况赋予不同初始数据解得三个问题的最优解并给出解决不正常航班调度的最佳方案。 第一问，在数据处理阶段为使时间容易处理将每个航班的起始时间与终点时间以每天按1440分钟算（某航班起始时间12:00，记为720），在赋予初始延误数据时同一航班可能会有几个延误时间我们可取平均值。在动态网络模型中通过给飞行弧（见下文解释）添加平行的飞行弧表示不同时间的延误选择，在恢复航班的调整方案一15分钟间隔添加延误选择弧。在考虑机场zlxy在13：00-15：00以及zgkl在17：00-19：00被迫关闭两个小时的情况下，可以先分析该机场影响的所有航班及其导致它们的延误时间，再利用模型及算法求得最优解。 第二问，考虑2153飞机14：35在机场zspd过站检查时发现机务故障，飞机当天不可使用，5145飞机14：00在机场zgha过站检查时发现机务故障，16：00可以使用。在利用建立的模型求解可以把2153号飞机影响的后续航班视为取消航班，再利用模型及算法求得最优解。 第三问，综合考虑上述两种情况时不正常航班的恢复，可以将机场与飞机不正常情况的时刻重叠，再利用lingo软件求得最优解。 最后本文还对实际的不正常航班恢复的具体方案给出了建议，对建立的模型在实际中的应用价值进行讨论，并提出了改进方案。关键字： 不正常航班 动态网络模型 航班延误 航班恢复 匈牙利方法1 问题重述 随着国民经济的高速发展和航空运输市场需求量的不断增长，国内各家航空公司相应加大了运力的投入。据美国波音公司预计，到2020年我国民航对各种类型客机的需求将达到3000架左右。运力的增长使航班量迅速增加，根据测算，“十五”期间，民航飞行班次年均增长13.5%，到2020年年均增长8.7% 。目前，我国空中交通流量分布不均衡，起降架次排名前十位机场的总起降次数占到全国总起降次数的一半以上，京、沪、穗机场到达终端区和华东部分区域空中交通容量已基本处于饱和状态，致使航班延误不断增加，给航空运输企业和旅客带来了不小的直接和间接经济损失。 航空公司为提高市场竞争力和最大化利用飞机资源，航班计划基本上没有为应对各种意外的变化留下松弛时间（slack time）。因为飞机资源的备份成本极高，也没有一家航空公司愿意专门为应付航班变化而让一架飞机空闲待命。这也是造成不正常情况下运力调配困难的主要原因之一。对于一个航空公司来说，不正常航班相关运行成本可能花费每年收人的3%，因此节省的潜能和空间是明显的。 航空公司之间的竞争日益剧烈，如何在不正常情况下实时地对航班进行调度，对飞机、机组人员进行重新优化指派，对旅客行程进行优化安排，对增加航空公司利润和提高竞争力显得尤为关键。 附件中列出飞机路线表、可飞机场表、机场时间表、机型交换成本表，在不考虑宵禁的情况下给出下列问题的解决方案。问题1： 对于附件中给定的实际问题，考虑机场zlxy在13：00-15：00以及zgkl在17：00-21：00被迫关闭两个小时的情况下，设计一个航班恢复计划，使得航空公司损失达到最小。参考航空公司运营经验, 每个旅客延误1分钟的成本为1元, 取消航班按延误8小时计算延误成本。问题2： 对于附件中给定的实际问题，考虑2153飞机14：35在机场zspd过站检查时发现机务故障，估计飞机当天不可使用，5145飞机14：00在机场zgha过站检查时发现机务故障，估计16：00可以使用。试设计一个航班恢复计划，使得航空公司损失达到最小。问题3： 同时考虑机场临时关闭和发现机务故障的情况下，给出一个航班恢复计划。使得航空公司损失达到最小。2 问题分析 本题是研究航空公司在遇到三种不同的情况下的不正常航班，怎样在使整个航空系统恢复正常而损失达到最小即恢复成本最小。联系实际，航空公司在恢复不正常航班时主要考虑重要航班与顾客人数多的航班延误的时间尽量少且尽量不要取消航班。在本文航空公司在恢复不正常航班主要考虑航空公司恢复成本最小。 仅考虑机场的短时间的关闭，导致航空公司的飞机在特定的时间不能离港与进港，如果该机场不是主干线机场影响的航班不多，很可能是不需要调动其它航班的飞机。若该机场影响的航班多，则就要调动其它航班的飞机。 在考虑飞机出故障需要停飞检修一段时间甚至整天停飞，则需要根据恢复成本最小的情况下调动其它飞机。 在同时考虑机场的关闭与飞机的停飞时，需要分析机场的关闭与飞机停飞在时间与空间的重叠，这样会更好的得出初始各个航班延误时间与可能的延误时间。3 模型假设1假设各航班不重名；2假设不考虑有vip航班，只考虑恢复系统的最小成本，所有的航班平等对待；3假设不考虑机组的人员配备；4假设调动飞机的成本平均为8000元，即飞机从已在机场到所需机场的空机飞 行成本；5假设没有故障飞机的飞行正常，会正常起飞与降落；6假设不考虑飞机在空中可以加速，要按照正常的速度飞行；7假设不考虑飞机在机场检修时占用航道，其他飞机可以正常进入机场。8假设机场关闭一般提前两个小时通知航空公司，机场关闭导致的不正常的航班有航空公司负担。9假设当航空公司遇到不正常航班时，按每个旅客延误1分钟的成本为1元, 取消航班按延误8小时计算延误成本。 4 符号说明 e：机型集合； f：所有机场到机场航班弧的集合； r：所有调机弧的集合； i：动态网络中中间过渡节点（机场）的集合； h：航班号集合； ：调机变量，当机型e执行的航班弧f是调机任务是取值1，否则为0； ：航班执行变量，当航班弧f由机型e执行时取值1，否则为0； ：航班弧f的取消变量，当航班弧f取消时取1，否则为0； ：航班弧f由机型e执行的调整成本； ：航班弧f取消成本； ：节点i对机型e的供应量； ：从节点i出发且机型为e的航班弧集合； ：进入节点i且机型为e的航班弧集合； 5 航班恢复模型的建立 本節主要研究航班恢復動態網路數學模型與演算法。主要根據航空公司的航班恢復成本最小建立模型。5.1动态网络模型的简介 动态网络也叫时空网络，动态网络中的每个连接都代表时间空间的变动，从当前时点t的地点转移到时点t+x的另一个地点，其中时间变动值x大于零。在动态网络中可以用几种方式表示，首先是通用的二维时空网络，以航空公司航班调度问题为例，空间（机场）是一维的，而时间是另一维。第二种是复杂的二维时空网络，在这个网络，在这个网络中时间被进一步细分，如划为飞机到达的时间、飞机离开机场的时间。这两种表示方式的主要差别在于，复杂网络可以同时解决航空公司同时解决飞机指派问题和飞机路径问题，而通用网络首先解决飞机的指派问题，然后解决飞机路径问题，最后通过使用网络流分解方法获得所需要的调度方案。 下面我们利用介绍的复杂的二维的时空网络方法分不正常航班的调度问题。在调度问题中，每个网络节点指代在一个特定时间的特定机场。每一个弧的连接与网络中不同时间事件相关联。航班调度问题时空网络中的主要节点和弧有： 1、飞行弧 飞行弧连接飞机的出发和到达节点，只是指代一个可能的飞行。通常弧上的流量为1，飞行弧的成本由机型和路程长度或飞行时间（本文采用时间）决定。 2、调机弧 调机弧表示在不正常航班情况下，调动飞机到某个机场去服务而不携带任何旅客。调机弧从一个供给节点连接被调用飞机所在的节点到所有需要的节点。该弧总流量设置为小于等于1。 3、延误弧 延误弧表示可能采用的延误策略，通过在原计划的飞行弧上添加带离散时间间隔的平行弧。例如，假设航班在12:00am离开a机场且于14:00pm到达c机场，若以15分钟为延误方案间隔，则可以在a机场12:15am，12:30am，12:45am等时刻添加延误弧，相应地连接到c机场14:15pm，14:30pm，14:45pm时间点上。本文考虑延误费用为旅客的服务费与操作费用等，每个旅客延误1分钟的成本为1元。 4、飞机到达节点 飞机在特定的时间到达特定的机场，则该节点记录了到达时间和机场，在网络中，一个航班的连接将汇集在到达节点。 5、飞机离港节点 飞机在特定的时间离开特定的机场，则该节点记录了离开时间和机场。在网络中，一个航班的连接将从该节点连接到其他的机场。 6、供给节点 供给节点表示拥有一定可使用飞机数量的特定时刻。供给时刻可位于一天的起始时刻，或是经过修复后飞机的所在时刻。 7、需求节点 需求节点可以认为是事件节点，如果出现在一天中间的时刻，则表示在某个机场的这个时刻出现飞机短缺。5.2不正常航班恢复的数学模型 根据题目的要求，本文以航空公司恢复不正常航班的成本最小为目标函数。飞机的调动模型及相关的符号定义描述如下： e：机型集合； f：所有机场到机场航班弧的集合； r：所有调机弧的集合； i：动态网络中中间过渡节点（机场）的集合； h：航班号集合； ：调机变量，当机型e执行的航班弧f是调机任务是取值1，否则为0； ：航班执行变量，当航班弧f由机型e执行时取值1，否则为0； ：航班弧f的取消变量，当航班弧f取消时取1，否则为0； ：航班弧f由机型e执行的调整成本； ：航班弧f取消成本； ：节点i对机型e的供应量； ：从节点i出发且机型为e的航班弧集合； ：进入节点i且机型为e的航班弧集合； 式（1）为目标函数，第一项是航班调整成本，其中包括延误成本和机型置换成本。若该航班有原机号执行，则只由延误成本构成。第二项是航班取消成本，第三项执行调机飞行的成本。式（2）飞机的平衡约束；式（3）式（5）为变量的取值约束。5.3航班恢复算法5.3.1航班计划调整的机理分析 对于一个给定机号的飞机，该机号的路径为时间上连续、符合规定过站时间标准的多个航班所构成的航班串。由于航班延误具有传递性，当路径上某个航班发生延误，如果不进行调整，路径上后继航班的延误时间将不会少于当前的延误时间。记航班f的延误时间为，为了方便描述算法，先给出一个定义： 定义、机号的路径延误时间：设路径上有航班（环）、，是的后继。若在计划调整过程中，与其它路径的航班（环）发生了置换，则执行完置换航班后再次执行的预期离港时间与原计划离港时间的差值称为机号的路径延误时间。可以取负值，表示空闲等待。 定义路径延误的意义在于：如果路径的后继航班不发生调整，则路径延误时间为后继航班的实际延误时间。在实际调度中，出于机组、旅客中转等因素考虑，路径的调整需要进可能保持进过停的航班与联程航班的衔接，借助路径延误的定义可以帮助评估方案调整对后继航班的影响。 再给一个命题： 命题：设机号原计划离港时刻为，因故需延误至，在延误期内有n个机号参与置换，且，则。 证明：设参与置换的航班的飞行时间为， 则对，有 对于，有 对i求和，有证毕。 根据命题给出一个则为本节算法应用依据的推论： 推论（1）：采用路径调整策略，总路径延误时间具有不变性。推论表明，对于计划调整的过程是一个在各条路径上分配延误时间的过程。依据推论表明，假如不使用取消航班的策略，要想减少某些航班的延误时间则必须增加另外一些航班的延误时间或是对无延误的航班分配延误时间。若调整过程中决定取消航班，则在取消的时刻重新计算当前所有路径上航班的分配。5.3.2航班计划调整的成本分析（1） 单航班情况 本文利用整数规划中的匈牙利方法处理不同路径置换算法。首先构造置换成本矩阵c，表示第i个机号以第j个出发时间执行当前航班的后继路径成本，并假设路径成本和等待成本是时间的增函数。于是置换成本矩阵有如下性质： 假设有一航班的飞机a离港时刻为1000，因故需要延误到1130，在时间段1000,1130内有三架飞机可供置换，其中第一机飞机b离港时间是1000，第二架飞机c离港时间是1030，第三架飞机d离港时间是1100，令等待成本为0,则其置换成本矩阵如图（2）所示。由匈牙利法可以获得最优解，因此对于单个机号路径的置换而言，可以获得置换成本最小的指派。 假设有航班飞机离港时刻为1200，在时间段1000,1130内比原来多了一个可以参加置换的飞机记为e离港时间为1145，则新的置换矩阵如图（3）所示。分析成本矩阵的变化不难看出，即使新增的机号是空闲矩，采用匈牙利法的出的关于延误120分钟的指派方案总置换成本不会少于延误90分钟的情况。 上面图（1）与图（2）为置换成本 示意图。图（4）不失一般性，机号a延误时间所对应的置换集为af，成本矩阵为另一延误时间所对应可供置换的矩阵机号数量，成本矩阵。记利用匈牙利法对两个矩阵进行指派获得的成本为，则有：推论（2）： 利用数学归纳法证明（参考文献3:96-97有说明）。（2） 多航班情况 在同一机场往往不止一个航班受到影响而制使多个航班出现延误。此时，进行航班（环）置换会面临一个机号有多种置换选择的情况，这是一个求集合无关子簇的问题。假设机场p在某时段内有n个不同机号的航班任务出现延误，总共有m个不同机号的飞机可供置换，该问题的数学描述如下： 可供置换的飞机集合， ； 延误的航班集合，；对每个利用匈牙利法求出参与置换的机号集合，；所产生的效用值；由含有的所组成的集合；：集合隶属变量，若则取值1，否则取值0； 上述最优选择置换的飞机模型： 需要指出的是，发生延误的机号也可以属于其它机号的置换集合，即给已经延误了的航班再次分配新的延误。这类情况在实际的调度并非少见，例如为了保证旅客多的航班的出行，航空公司必须让其它航班延误。求解问题（6），其实是一个将机号与航班任务间多对多的映射规范为多对一映射的过程，因此可通过删除多余的对应关系和更改映射的集合来进行。 算法以在中去除所造成的成本增加值作为效用值，求解按以下步骤进行：步骤1：将同时属于多个置换集合的提取出来存入集合paf。步骤2：对paf中的每个计算，找到最大数值对应的机号，记为，将所含有的置换集合存入中。步骤3：对每个分别计算从置换方案去掉所导致的成本值的增加值为，记在置换指派中分配给的延误时间为，则就是关于的单位时间成本增加值。找出对应的置换方案，记为。步骤4：依据更改机号路径、延误信息和时刻表。若仍有延误航班未进行置换，返回步骤1。若，算法结束。 求解步骤2、3是删除多余映射分支的步骤，中保留可以使该次置换产生最大的成本削减。5.3.3航班恢复的算法描述 基于路径调整的算法主要指导思想是分阶段优化，具体步骤如下：step1：记航班运行时刻表为ts。为当前已延误和即将延误的航班建立初始延误列表dl，记录如下数据：机号，航班号，机场信息，时间信息，机型信息，旅客信息，延误时间。建立置换限制信息表lcl。step2：将dl按机场分类存入pl，对每个机场所有延误航班出发时间求均值，均值的机场p0先调整。step3：求解（6）（8），更新ts、dl与lcl。step4：，返回执行step2。若处理完毕，对第i阶段调整方案进行变换。对于每个变换的方案，递归调用本算法，考察方案的成本、延误数量、延误时间分布等信息，选出符合条件的满意方案存入，存储相应的ts、dl和lct。step5：令。选取一个，更新dl，将每个延误机号路径上当前航班信息更新为其继后航班的延误信息，若后继无航班，则在dl中删除该机号的项。若更新后的非空，将之作为新的dl执行step2。若所有更新后的多为空，算法结束，输出调整后的时刻表及各项延误信息。 在每个优化的阶段中，基于路径调整的算法只对所有发生延误机号路径上的一个航班（环）进行置换调整，因此算法总优化阶段数不会超过最长一条发生延误的机号路径上航班的总数。6 机场关闭导致不正常航班恢复（问题一） 本节讨论机场关闭导致不正常航班恢复，首先分析机场关闭导致那些机号的飞机的飞行与航班的延误，再分析延误的航班与可能后继延误航班，给出算法所需初始延误时间与机号置换表lcl。6.1问题一的讨论 先通过图分析zlxy在13：00-15：00被迫关闭两个小时的情况下导致的不正常航班的情况： 图（6） 图（7）图（8）由上图图可知航班zlxy在13：00-15：00关闭两个小时的情况下，影响机号为2686号与5130号飞机的飞行与其相应的航班f9282、f9282、f9210、f9202、f9183与f9741航班。如果航空公司在两个小时前接到zlxy机场要关闭，航空公司可以选择正常飞行如果遇到机场关闭则等待，那么有f9282、f9282与f9210航班将延误50分钟，这三个航班人数可以等待，否则就要2686号飞机和其他飞机置换。同样如果航空公司选择等待f9202、f9183与f9741航班将延误120分钟这三个航班人数可以等待，否则就要5130号飞机和其他飞机置换。机场zgkl在17：00-21：00被迫关闭两个小时的情况下，按上述情况分析。6.2使用lingo软件问题一考虑航班zlxy在13：00-15：00以及zgkl在17：00-21：00被迫关闭两个小时的情况下，有2686号、5330号与5130号三架飞机执行航班受到影响。计划恢复航班前航班延误表为： 表（1）计划恢复航班前航班延误表268685023139b73850390f92811392 5130 9502089b738120267f918412214 53301035870b73850402f93997917 延误列表中的列从左到右分别代表：机号，原计划出发时间，到达机场代码，航班的人数，机型代码，延误时间，路径所有后继航班总人数，航班号，出发机场的代码。航空公司恢复航班系统的成本按假设按每个旅客延误1分钟的成本为1元, 取消航班按延误8小时计算延误成本。 根据给出的延误列表dl，对机场2所有延误航班进行置换指派： 表（2）机场延误航班的置换选择表机号替换机号目的地航班号出发时间后继人数延误时间机型航班人数215321671710f807800272050b738139216726882f9182750408137.33120b738139200526881f83011004083270b738722686514716f845720272137.610b738702688513117f9281780409inf100b738695076533011f84784034937.3340b738985077268830f919010203462.2550b73876513051857f91611050408inf45b7381335131514334f920611003493630b738125518551482f9178116034653.560b738120532053932f954411302732040b738875330536813f9392720216inf95b73879 表（2）中第一列表示发生延误的机号。第二列表示参与替换的机号 ，由表可知机号2688是机号2167与2005的置换集合。 表（3）机号置换判断表机号延误时间后继选择数2167137.331206200532702表（3）中第四列的后继选择数表示第一列的机号如果不在本机场进行调整，顺延到下个机场可能拥有的置换选择，该列数据在算法中不使用，只是在人工干预的情况下可供航空公司作为决策参考。由算法得的结果： 表（4） 三种调度策略的结果比较 不调整航班选择1选择2选择3航班恢复成本 581000450060426100399500航班延误504055450.153530401515,30203525530,6002000由上表我们可知最优选择为三，在问题一2686号飞机应该与5137号飞机置换；5131号飞机与5141号飞机置换。7 飞机停飞闭导致不正常航班恢复（问题二）7.1问题一的讨论 本节讨论飞机在某时间段停飞导致不正常航班恢复，首先分析飞机停飞导致那些航班的延误，再分析延误的航班与可能后继延误航班，给出算法所需初始延误时间与机号置换表lcl。 图（9）图（10） 由上图图可知飞机2153在14：35-00：00停飞情况下，影响的航班为f807、f808、f819航班。如果航空公司可以等待即取消三个航班，这样的话对航空公司的短期利益与长远利益都是相当不利的。那么按上述给的不正常航班恢复模型与算法法可以给出较好的利用其他飞机的置换这路航班。5145号飞机在14：0016:00停飞的话，如果航空公司选择等待，那么航班f9392、f9059与f9060将会均延误65分钟。也可以按照述给的不正常航班恢复模型与算法法可以给出较好的利用其他飞机的置换这路航班。7.2使用lingo软件问题二计划恢复航班前航班延误表为： 表（5）计划恢复航班前航班延误表215394014480b73850384f80812845145 8953265b738120301f93929616延误列表中的列从左到右分别代表：机号，原计划出发时间，到达机场代码，航班的人数，机型代码，延误时间，路径所有后继航班总人数，航班号，出发机场的代码。航空公司恢复航班系统的成本按假设按每个旅客延误1分钟的成本为1元, 取消航班按延误8小时计算延误成本。根据给出的延误列表dl，对机场2所有延误航班进行置换指派： 表（6）机场延误航班的置换选择表机号替换机号目的地航班号出发时间后继人数延误时间机型航班人数2153200517f8078002720480b738139216750762f82975040812120b738139200526881f83011004083270b767722686514716f845720272137.610b738702688513117f93637804090100b738695076215311f847840349inf40b738985077268630f919010203462.2530b73876514551857f91611050408065b7381335131514334f920611003493630b738125518551432f91771160346inf60b738120532053932f95441130273640b738875330536813f93927202161.595b73879 表（6）中第一列表示发生延误的机号。第二列表示参与替换的机号 ，由表可知机号5143是机号5131与5185的置换集合。 由算法使用lingo软件得的结果： 表（7） 两种调度策略的结果比较 不调整航班选择1选择2航班恢复成本 877090650060626100航班延误5065550.1540454015,3010101030,600100由上表我们可知最优选择为三，在问题二2153号飞机应该与2005号，5131与2688号飞机置换，不取消航班可是航空公司恢复成本最小。8机场关闭与飞机停飞闭同时导致不正常航班恢复（问题三）该问题是上述两问题的综合考虑，分析与上面有很大的相似处，则给出结果。由算法使用lingo软件得的结果： 表（8） 三种调度策略的结果比较 不调整航班选择1选择2选择3航班恢复成本 881090750060726100734500航班延误4806555450.153530401515,302010251030,6002000由上表我们可知最优选择为三，在问题三2153号飞机应该与2005号，5131与2688号飞机置换，2686号飞机应该与5137号飞机置换；5131号飞机与5076号飞机置换。在不取消航班时是航空公司恢复成本最小。9 模型改进方向 由于题中信息有限，所以本文模型在实际应用时仍存在改进空间，若信息充足，则为使模型更具实用性，可在如下四方面进行改进：(1)在恢复不正常航班时可以考虑有一些vip航班（含有一些重大事件的应急航班）；(2)在模型中考虑飞机过站（机场）的时间；(3)在模型中还可以考虑机组的人员安排,因为在航空公司机组人员，特别是飞行员是一个较缺的资源。(4)计划恢复的一体化研究，现阶段的计划恢复通常是分阶段进行。参考文献1 卢开澄. 单目标、多目标与整数规划. 北京：清华大学出版社, 1999.2 王庚, 王敏生. 现代数学建模方法.北京：科学出版社, 2008.3 范玉妹等. 数学规划及其应用（第3版）.北京：冶金工业出版社, 2009. 9.4 w. l. winston, 杨振凯等译. 运筹学：应用范例与解法(第4版). 北京：清华大学出版社. 2006. 8.5 田晓东.如何提高航班运行的正常性j.中国民用航空。2004（8）：23256 giffer b.,thompson g.l.algorithms for solving porduction scheduling problemj operations reseach,1960,8(4