基于匈牙利算法的航班延误模型

基于匈牙利算法的航班延误模型

问题三： 问题分析：

我们从我国航空运控操作的实际出发，将延误成本分为三部分：飞机置换、飞机调运、航班取消，我们需要在这些成本之间寻找一个平衡，以延误成本最小化（或延误时间最小化）作为目标函数构造不正常航班调度问题的数学模型。此外，我们还提出了旅客失望溢出成本和旅客失望率的概念，以便于对模型作出合理的说明。其中旅客失望溢出成本和旅客失望率定义如下：

旅客失望溢出成本：由于航班延误使旅客不能按原计划到达目的地，旅客对航空公司的信誉失望，导致在下一次的消费选择时放弃该公司的航班而选择其它公司的航班或选择其它交通方式时对该公司造成的损失。

旅客失望率：由于航班延误使旅客对航空公司信誉失望，在下一次的消费选择时不选择该公司航 班的概率，旅客失望率与延误时间有关。

其中，旅客失望溢出成本函数与旅客人数、票价和旅客失望率有关。最大失望溢出成本为本航班上的所有旅客在下一次消费时都不选择该公司的航班，此时的旅客失望溢出成本为：乘客人数×平均票价，此时旅客极度失望，旅客失望率为1，下一次100％不选择该公司的航班。旅客失望溢出成本采用公式“P=vwu”计算，v是该航班上的乘客数，w是该航班上的平均票价，u是

旅客失望率。通过查阅相关文献可得到旅客失望函数u=29，u是延误时间t（min）的函数。

时间对：每个时间对是一个航班在本地机场和目的地机场的两个时间点，一个时间对代表一个航班的起始时间点与终止时间点。

我们把把所有处于最早延误航班之后到达或停驻该枢纽机场的飞机、备用飞机和当天可以恢复使用的飞机都作为调度对象，将这些飞机重新指派给航班，使延误成本最低（或延误时间最短）。 模型建立与求解：

1、 模型建立

我们根据将时间段用时间点代替，能够得到精确的延误时间，即时间对起止点之差。下面定义一些参数和集合：

下标和指示：

i是飞机指示； f是航班下标。 集合：

af:执行航班f的飞机；

af'：替换航班f的飞机；

Ti：可用飞机的就绪时问集合；

Ti’：最早延误航班之后的航班原计划到达时间集合；

F：最早延误航班之后的航班集合；

A：最早延误航班之后可用飞机集合；

Ai：能够执行，航班任务的机型集合；

Aim：能够在m机场维修的机型为I的飞机集合；

Z：当天备用飞机和修复飞机的集合； 变量：

f

：时间对i到j的航班； xij

yf：取消航班f的标志，为1取消，为0不取消；

,其中t=Ti-Ti’； P

f：航班上的旅客失望溢出成本，Pf=

Pij:i时刻就绪的飞机执行j时刻的航班及后续航班的延误成本；

Pij=Pf+

bjcfxb，第一项是旅客失望溢出成本，第二项是调运备用或修复b∈Z

飞机的成本；

b

：把航班f指派给备用飞机的成本； cf

ｊ

：O，1变量，当天可用飞机b指派给航班，为1，否则为0； ｘｂ

nf：航班在时间对i和j之间经过的机场数。

目标函数表示如下：

minPij 或者min

f∈Fi∈Ti,j∈Tj

f∈Fi∈Tj∈T

i,

nft （1）

j

约束条件：

xifi∈A∪Uxiff∈F

+yf=1,∀f∈F （2）

≤1,∀i∈A （3）

xifbfIf∈F

=1,∀i∈AIm,I∈Ai （4）

yf∈0,1,bfI∈0,1,xif∈0,1 （5）

式(1)是目标函数，使总时间延误最小或总延误成本最小；约束条件(2)是保证每个时间对上都有航班覆盖；(3)是保证每个航班都有飞机执行，否则就取消航班；(4)飞机型号要求，保证用于替换的飞机型号满足替换要求；(5)是整数约束，保证每个时间对上的航班取0或1。 2、 模型求解

我们对模型的求解采用启发式方法搜索置换矩阵，调用匈牙利算法解决指派问题。匈牙利算法是由匈牙利科学家柯尼格首先提出的，它是求解指派问题非常有效和简便的算法。指派问题的最优解具有这样的性质，若从系数矩阵Pij的一行（列）各元素中分别减去该行（列）的最小元素，得到新的Pij矩阵，那么以新的Pij为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。

首先构造延误时间置换矩阵Tij：

t11t12



t21t22Tij=tm1tm2

t1n



t2n

 i1 , 2 ,tmn

,n ; j1 , 2 ,,m

其中表示i时刻航班的飞机执行第j时刻航班的任务所延误的时间，根据延误时间置换矩阵Tij计算延误成本置换矩阵Pij：

p11p12



p21p22Pij=pm1pm2p1n

p2n

 pmn

其中Pij表示i时刻航班的飞机执行第j时刻航班的任务所产生的延误成本． 下面是航班调整算法具体步骤

1、 初始化：

1)建立延误航班表YW(已延误和即将延误的航班，字段包括：航班号、飞机型号、后续旅客人数、平均 票价、原计划进出港时间、延误结束时间)，对YW表中按进港时间升序排列；

2)建立备用飞机总表BY(在当天机场关闭之前可以恢复使用的延误飞机和空闲的备用飞机，字段包括：飞机型号、航班号(初始为空)、停驻机场、到达时间、成本(初始为空)、后续旅客数(为0))；

3)建立置换飞机表ZH(从航班信息表中检索在延误航班原计划到达时间之

后的所有航班，字段包括： 飞机型号、航班号、进、出港时间、票价及旅客数)，将ZH表追加到YW表；

4)建立机型表AS，表中内容是机型ASi(i是时间点出发航班的飞机机型)和它的可置换机型。

2、 计算调运(ferry)飞机的成本： 打开YW表，

for i=1，打开BY表，如果BW≠ ,

for j=1，计算BY表中的调运成本Cf，Cf=调运距离×每公里成本；if Cf

=0，则使用该飞机执行航班i，从BY表中删除j记录，从YW表中删除i记录，跳出循环。将Cf存入BY表中第j条记录中的成本字段。j++，直到BY表到底。

3、 建立置换矩阵：

将运算后的BY表追加到ZH表中，对ZH表中的航班作置换操作，是为了建立置换矩阵Pij和Tij．打开ZH表，for k=1，

1)比较ZH表中k的飞机型号与i记录中飞机型号是否属于可置换关系，若不是，则在矩阵Pij第i位置(按行排列)填入一相对极大数，表示此置换不可执行；若是，则按照成本函数的公式计算溢出成本。其中，延误时间=第k条记录的‘到达时间’一第i条记录的‘到达时间’，将结果存入矩阵Pij的位置i行第k列中，将延误时间Tij存入的位置i行第k列中。

2)k++，直到备用表到底，如果k是备用航班，即后续旅客为0的航班，要将k的调运成本加入延误成本中,这样就生成了置换矩阵的第一行。 3)i++，直到YW表到底．最终生成了i行k列的置换矩阵Pij

4、 调用匈牙利算法进行任务指派，得到优化方案．

我们以南方航空公司某日的航班为例，以延误成本最小为目标函数，依据上述模型具体分析其航班延误后的调度方案。该航空公司有4个始发航班，8个到达航班，其基本数据如表1所示。

【表（一）】

构造延误时间置换矩阵Tij：

f4

f7 f9 f11 R

f5 0 160/60280/60390/60f4

 0140/60260/60370/60Tij=f7inf0120/60230/60



f9 infinf0110/60f11inf0 infinf

360/60

340/60200/60



80/600

矩阵第一行分别表示由f5的飞机执行工的任务时的延误时间为0小时，执行f7的任务延误时间为(160/60)小时,inf表示航班不能起飞，不能置换。利用

Tij计算Pij可得：

 0

 0

Pij=inf



 inf inf 60064 [***********]

68826 [***********] [**************]1



inf[1**********]infinf00

对矩阵Pij采用匈牙利算法处理，得到的最优置换方案如下:

其中，1表示可以置换，矩阵Pij表示f5 的飞机由的f7 飞机执行，f4 不变，f7 的由f9 执行，f9 的由恢复飞机R执行，f11 的不变。

f4 f7 f9 f11 R

Pij

f5f4=f7

f9f11

01000

1

[1**********]001

000 10