《基于匈牙利算法的航班延误模型》由会员分享，可在线阅读，更多相关《基于匈牙利算法的航班延误模型（5页珍藏版）》请在金锄头文库上搜索。
1、基于匈牙利算法的航班延误模型问题三：问题分析：我们从我国航空运控操作的实际出发，将延误成本分为三部分：飞机置换、飞机调运、航班取消，我们需要在这些成本之间寻找一个平衡，以延误成本最小化（或延误时间最小化）作为目标函数构造不正常航班调度问题的数学模型。此外，我们还提出了旅客失望溢出成本和旅客失望率的概念，以便于对模型作出合理的说明。其中旅客失望溢出成本和旅客失望率定义如下：旅客失望溢出成本：由于航班延误使旅客不能按原计划到达目的地，旅客对航空公司的信誉失望，导致在下一次的消费选择时放弃该公司的航班而选择其它公司的航班或选择其它交通方式时对该公司造成的损失。旅客失望率：由于航班延误使旅客对航空公司
2、信誉失望，在下一次的消费选择时不选择该公司航 班的概率，旅客失望率与延误时间有关。其中，旅客失望溢出成本函数与旅客人数、票价和旅客失望率有关。最大失望溢出成本为本航班上的所有旅客在下一次消费时都不选择该公司的航班，此时的旅客失望溢出成本为：乘客人数平均票价，此时旅客极度失望，旅客失望率为 1，下一次 100不选择该公司的航班。旅客失望溢出成本采用公式“”计算， v 是该航班上的乘客数， w 是该航班上的平均票价， u 是P=vwu旅客失望率。通过查阅相关文献可得到旅客失望函数 ， u 是23u=(t/60)9延误时间 t（min）的函数。时间对：每个时间对是一个航班在本地机场和目的地机场的两个
3、时间点，一个时间对代表一个航班的起始时间点与终止时间点。我们把把所有处于最早延误航班之后到达或停驻该枢纽机场的飞机、备用飞机和当天可以恢复使用的飞机都作为调度对象，将这些飞机重新指派给航班，使延误成本最低（或延误时间最短） 。模型建立与求解：1、 模型建立我们根据将时间段用时间点代替，能够得到精确的延误时间，即时间对起止点之差。下面定义一些参数和集合：下标和指示：i 是飞机指示；f 是航班下标。集合：:执行航班 f 的飞机； fa：替换航班 f 的飞机；fa：可用飞机的就绪时问集合；iT：最早延误航班之后的航班原计划到达时间集合；iF：最早延误航班之后的航班集合；：最早延误航班之后可用飞机集合
4、；A：能够执行，航班任务的机型集合；i：能够在 m 机场维修的机型为 I 的飞机集合；iZ：当天备用飞机和修复飞机的集合；变量：时间对 i 到 j 的航班；fijx：取消航班 f 的标志，为 1 取消，为 0 不取消；fy：航班上的旅客失望溢出成本， ；fP 其 中23 f ii（ t/6）P=vw ,t=T-9:i 时刻就绪的飞机执行 j 时刻的航班及后续航班的延误成本；ij，第一项是旅客失望溢出成本，第二项是调运备用或修bjijff Z=+cx复飞机的成本；：把航班 f 指派给备用飞机的成本；bfc：O，1 变量，当天可用飞机 b 指派给航班，为 1，否则为 0；：航班在时间对 i 和 j
5、 之间经过的机场数。fn目标函数表示如下：或者 （1）i,jif F TmiPi,jff F Tmint约束条件：（2）fifi A Ux+y=1,f（3）fif F ,（4）fIi Imif bi A,（5）I ff f iy 0,1 x 0,1式(1)是目标函数，使总时间延误最小或总延误成本最小；约束条件(2)是保证每个时间对上都有航班覆盖；(3)是保证每个航班都有飞机执行，否则就取消航班；(4)飞机型号要求，保证用于替换的飞机型号满足替换要求；(5)是整数约束，保证每个时间对上的航班取 0 或 1。2、 模型求解我们对模型的求解采用启发式方法搜索置换矩阵，调用匈牙利算法解决指派问题。匈牙
6、利算法是由匈牙利科学家柯尼格首先提出的，它是求解指派问题非常有效和简便的算法。指派问题的最优解具有这样的性质，若从系数矩阵的一行（列）各元素中分别减去该行（列）的最小元素，得到新的 矩阵，ijP ijP那么以新的 为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。ij首先构造延误时间置换矩阵 ：ijT 121n2ij m12mntttT=ttti1 ,2,n ;j1 ,2,m 其中表示 i 时刻航班的飞机执行第 j 时刻航班的任务所延误的时间，根据延误时间置换矩阵 计算延误成本置换矩阵 ：ijTijP121n22ij m12mnppP=pp 其中 表示 i 时刻航班的飞机执行第 j 时刻航
7、班的任务所产生的延误成ij本下面是航班调整算法具体步骤1、 初始化：1)建立延误航班表 YW(已延误和即将延误的航班，字段包括：航班号、飞机型号、后续旅客人数、平均 票价、原计划进出港时间、延误结束时间)，对YW 表中按进港时间升序排列；2)建立备用飞机总表 BY(在当天机场关闭之前可以恢复使用的延误飞机和空闲的备用飞机，字段包括：飞机型号、航班号(初始为空)、停驻机场、到达时间、成本(初始为空)、后续旅客数(为 0)；3)建立置换飞机表 ZH(从航班信息表中检索在延误航班原计划到达时间之后的所有航班，字段包括： 飞机型号、航班号、进、出港时间、票价及旅客数)，将 ZH 表追加到 YW 表；4
8、)建立机型表 AS，表中内容是机型 (i 是时间点出发航班的飞机机型)和iAS它的可置换机型。2、 计算调运(ferry)飞机的成本：打开 YW 表，for i=1，打开 BY 表，如果 ,BWfor j=1，计算 BY 表中的调运成本 ， =调运距离每公里成本；if fCf=0，则使用该飞机执行航班 i，从 BY 表中删除 j 记录，从 YW 表中删除 i 记fC录，跳出循环。将 存入 BY 表中第 j 条记录中的成本字段。j+，直到 BY 表fC到底。3、 建立置换矩阵：将运算后的 BY 表追加到 ZH 表中，对 ZH 表中的航班作置换操作，是为了建立置换矩阵 和 打开 ZH 表，for
9、k=1，ijPijT1)比较 ZH 表中 k 的飞机型号与 i 记录中飞机型号是否属于可置换关系，若不是，则在矩阵 第 i 位置(按行排列)填入一相对极大数，表示此置换不可执ij行；若是，则按照成本函数的公式计算溢出成本。其中，延误时间=第 k 条记录的到达时间一第 i 条记录的到达时间 ，将结果存入矩阵 的位置 i 行ijP第 k 列中，将延误时间 存入的位置 i 行第 k 列中。ijT2)k+，直到备用表到底，如果 k 是备用航班，即后续旅客为 0 的航班，要将 k 的调运成本加入延误成本中,这样就生成了置换矩阵的第一行。3)i+，直到 YW 表到底最终生成了 i 行 k 列的置换矩阵 i
10、jP4、 调用匈牙利算法进行任务指派，得到优化方案我们以南方航空公司某日的航班为例，以延误成本最小为目标函数，依据上述模型具体分析其航班延误后的调度方案。该航空公司有 4 个始发航班，8个到达航班，其基本数据如表 1 所示。【表（一） 】构造延误时间置换矩阵 ：Tij 4f7f9f1fR 54ij791f016/280/63/06/ 74T=finf/2/ i 18fifinf0矩阵第一行分别表示由 的飞机执行工的任务时的延误时间为 0 小时，执5f行 的任务延误时间为(160/60)小时,inf 表示航班不能起飞，不能置换。利用7f计算 可得：ijTijP ij 0 64 1390528072827164=inf 35 iifinf0对矩阵 采用匈牙利算法处理，得到的最优置换方案如下:ijP其中，1 表示可以置换，矩阵 表示 的飞机由的 飞机执行， 不ijP5f7f4f变， 的由 执行， 的由恢复飞机 R 执行， 的不变。7f9f9f 1f4f7f9R1 54ij79100fP=f 100
