如何减小航班的延误、尽力恢复航班正常目前是各航空公司运行控制中心最主要工作目标之一。随着各航空公司规模不断扩大，飞机数量在增加，航班量不断增多，以往通过签派员手工调整的方式渐渐变得困难和不能实现调整利益最大化，因此有必要建立数值化评估系统，根据航班运行情况为签派员计算出航班调整预案的运行控制系统。

传统的指派问题（Assignment Problem简称AP）是这样的：有n项工作欲安排n个人去做，每个人安排且仅安排一项工作，已知第i个人做第j项工作的效益为c_ij（i，j=1,2，……，n），试确定使总效益最大的最优指派。AP要求工作数与人数相等，它可用著名的“匈牙利算法求解”^[1]。

1.航班调整方案中评价指标体系的建立

指标的设定关系着最终的调整结果，科学地确定各项指标，建立合理的指标体系是得出科学综合调整的关键所在。影响航班调整主要有以下几个因素：安全、成本、运行环境、社会影响。航班调整评价指标体系是一个多层次、多指标的层次结构体系^[2]。

    本文使用航班延误时间代表航班调整评估指标，按照航班延误时间假设，首先计算单架飞机执行单个航班延误带来的损失，然后把单架飞机执行特定时间内后续航班延误损失求和，即得出该飞机执行特定时间内后续航班延误总损失。

(1)单个航班延误损失  y_k=（tk-△t）*c_k  （1）  式中：y_k为航班k单位时间延误损失；t_k为航班延误时间；△t为延误航班后续过站等可追回时间；c_k为航班小时延误成本。

    (2)单架飞机特定时间内延误总损失  Yi=_k（2）式中：Y_i为飞机注册号为i的飞机在特定时间内的延误总损失；y_k航班k的延误损失；m为飞机e在特定时间内预计执行航班班次；k为航班数，k=1,2,……，m。

    (3)航班调整前飞机i后续执行航班环j（将航班往返程或航班衔接不可拆分  的航班视为一个航班环，航班环内航班数量不等。）时的延误损失为Y_ij

2.指派问题的描述及数学模型

在航班生产过程中，当多架飞机出现不同程度的延误时，航空公司需要将这些延误飞机执行的后续航班进行调整。指派问题可描述为：此时则有n个航班环A1, A2, …, An，需要n架飞机B1, B2, … Bn来执行，每个航班环由仅由一架飞机来执行，每架飞机只执行其中一个航班环。已知第i架飞机执行第j个航班环时的航班延误损失为Y_ij（i，j=1,2，……，n），在此航班延误损失最小，为航班调整最佳方案。指派每架飞机执行每个航班环，使总航班延误损失最小。总航班延误损失数值和越小，航班调整方案越佳，试确定航班延误损失最小的指派方法。

设指派问题变量为 x_ij, 则共有n² 个变量，且变量取值为：xij= (3)

 3.使用匈牙利算法进行求解

设 Y=(Y_ij)是一个效率矩阵，若可行解x*=(x_ij)的 n个1所对应的 n个 Y=(Y_ij)均为0，则x* 是最优解。

对于指派问题，效率矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解。设给定了以 Y=(Y_ij)为效率矩阵的指派问题 G，现将 Y的元素Y_ij 改变为：  Y’ij=Yij- αi-bj，其中： α_i, b_j 为常数。(5)  则以Y’=(Y’_ij) 为效率矩阵的指派问题G’ 与 G有相同的最优解。

据此，可以对矩阵做如下改变，目的是找出Y 中的 n个不同行不同列的0元素：

将 Y的每一行减去该行中的最小元素，得到Y’矩阵 ，则Y’ 的每行中均至少出现一个0元素，且所有Y_ij³0 。同样，对Y 的列亦进行如此计算，由此，我们完全可以从原效率矩阵 出发，得到一个新的效率矩阵 ，使 Y的每行每列中均至少存在一个0元素，而不改变问题的最优解。不同行不同列的0元素，称为独立0元素,当矩阵中含有n个独立0元素时即得解。设矩阵Y中含有0元素，那么划去Y中所有0元素所需的最少直线数等于Y中独立0元素的个数。

步骤如下：

Step 1.  每行减去该行的最小数, 每列减去该列的最小数，使矩阵每行每列均有0元素；

Step 2. 寻找独立0元素， 从单个0元素的行(列)开始，给0加圈，记作◎，然后划去所在列(行)的其它0元素，记为Ø；重复进行，直到处理完所有列(行)的单个0元素；若还存在没有画圈的0元素(同行或同列中的0元素多于1个)，则从剩余的0元素最少的行(列)开始，选0元素画圈，然后划掉同行同列的其它0元素，反复进行，直到所有0元素均被圈出或划掉为止；若◎元素的数目m=n，则该指派问题的最优解已经得到，否则转入Step 3；

Step 3. 设有 m<n 个◎, 找最少覆盖所有0的直线；1)  对没有◎的行打√；2)  对已打√行中含Ø所在列打√；3)  对已打√列中含◎所在行打√；4)  重复2)-3), 直至没有要打√的行和列为止；5)  对没有打√的行划横线, 对打√的列划竖线，得到最少覆盖所有0的直线数l。若l<n，则转Step 4；若l=n，则转Step 2重新派；

Step 4. 设未被这些直线覆盖的元素中的最小值为α。 对未划线的行减去α，划线的列加上α。转Step 2。

4.结语

航班调整的目的是为了保障航空公司航班的安全、顺利运行，更是为了保障旅客能安全、迅速到达目的地。本文以因天气造成航班延误做为实例，使用匈牙利算法求解航班调整过程中指派问题。需要说明的是，航班调整是航空公司运行控制日常工作中的一项复杂的系统工程，在航班调整过程中涉及安全、旅客、机型、机组、效益以及航班运行限制等多种因素，因此如何更合理设置航班调整评价体系，使用匈牙利算法求解多目标广义指派问题是一项长期的研究课题。

参考文献：

[1]宋业新 陈绵云 郑之松 多目标广义指派问题的模糊匈牙利算法求解 海军工程大学学报 2000年第5期

[2]雷瑞德 山航不正常航班恢复策略评估体系研究 2013年山东大学硕士学位论文

[3]钱颂迪 运筹学 清华大学出版社 1990

[4]柳毅 佟明安 匈牙利算法在多目标分配中的应用 火力与指挥控制 2010年10月