基于遗传算法的航班串优化方法研究

贾宝惠，杜建勋，李耀华

（中国民航大学航空工程学院，天津 300300）

基于遗传算法的航班串优化方法研究

贾宝惠，杜建勋，李耀华

（中国民航大学航空工程学院，天津 300300）

分析研究了航班串编制问题，考虑了飞机载客量与航班平均客流量的关系，构造了航班旅客溢出成本指数因子，建立了改进后的基于最小成本的航班串优化模型，并构造了遗传算法求解模型。利用Matlab遗传算法工具箱进行仿真研究。应用航空公司实际航班数据对上述模型和算法进行验证，所得优化结果良好，证明该航班串优化模型及方法切实可行。

遗传算法；航班串；生产计划

随着中国民航业的飞速发展，航空公司的航班量快速增长，传统的人工或半人工排班方式由于其排班效率低下已难以满足航空公司日常的飞机排班要求。而智能高效的航班串求解和优化方法，不仅有助于航班的安全、正点运行，更将直接提高机队的利用率，进而加大航空公司的经济收益，对航空公司提高自身竞争力具有重要意义[1]。

近年来，国内外学者将具有更高效率的智能化启发式算法引入飞机排班的求解和优化中，并取得了良好效果。Tung-Kuan等[2]针对航班延误及恢复问题，提出了一种新的多目标优化方法，即评价取向遗传算法（EPGA），在面对航班调度突发状况时能迅速得到高品质解决方案。Torsten等[3]将贪婪启发式算法进行改进，创建了RSFFB算法，并将其用于对ARP模型的求解优化，获得了较好效果。詹志辉等[4]针对飞机抵达机场排序和调度问题，提出了一种带有滚动时域控制的蚁群算法，即RHC-ACS-ASS算法，该算法具有很强的全局搜索能力，对飞机排班调度问题具有高效率和较好的鲁棒性。Burke[5]针对航班调度问题，提出了一种改进的文化基因算法（multi-meme memetic algorithm），该算法通过同步飞行时间和飞行路径得到目标的改善，形成一个更具可靠性和灵活性的航班指派计划。

尽管国内外已取得了较多成果，但仍存在一定的不足之处。本文从大型航空公司的飞机排班角度出发，考虑了机型载客量与航班平均客流量的关系，构造了航班旅客溢出成本指数因子，建立了改进后的基于最小成本的航班串优化模型，最后通过Matlab遗传算法工具箱对初始航班串进行了优化。

1 研究与方法

1.1 问题描述

航班串的编制是指将航空公司一天、一周或一个季度的航班信息通过合理的方法编制为若干个航班串，即将一个到港航班和一个离港航班在符合各方面约束的情况下生成可以由一架飞机去执行的航班连接，且其起点和终点都应在基地机场。航班串的生成算法包括航班连接网络的构造算法和航班任务串搜索算法。通常在航班数量较少的情况下，通过手工编制航班串即可达到良好的效果。近年来随着中国航空公司的规模日益增大，手工编制航班串已难以达到要求，而借助计算机高性能的搜索算法和优化算法完成编制航班串的工作已逐渐趋于主流。

对于初始航班串的优化工作，需要先建立具有优化目标的数学模型，当前已被提出的各种数学模型的优化目标主要包括：以机组规模最小为目标，以执勤时间最短为目标，以飞行时间均衡为目标，以机组利用率最大为目标等。本文通过建立以成本最小为目标的数学模型，并基于遗传算法工具箱对航班串进行优化。

航班串生成所要考虑的准则主要包括：

1）初始航班的出发时间需由航空公司确定；

2）相衔接的两个航班在间隔时间、机型、载客量、飞行区域上都需要严格遵守相关规定；

3）基地机场需具有一定的维修能力。

1.2 建立模型

关于最小成本为目标的航班串模型，国内外学者已研究出多种优化方案[6-7]，分别从不同角度对问题进行了描述，所涉及的约束包括航班衔接约束、航班串成本约束、飞机过站约束等。本文建立了如下以客流量差异值最小为目标函数的航班串编制模型

其中：n为待做计划的总航班数，i，j∈n；m为总航班串数，k为第k个航班串，k∈m；nk为第k个航班串内包含的航班数；ck为第k个航班串的总溢出成本；为第 k个航班串内第 i个航班的旅客溢出成本（passenger overflow cost）；Li为第i个航班到达机场代码；Dj为第j个航班出发机场代码；B为具有一定维修能力的机场，b∈B；xijk，xk为0-1决策变量

式（1）要求优化后航班串成本最小；式（2）要求航班串数最少；式（3）保证第k个航班串的总溢出成本由相连航班的溢出成本组成；式（4）保证每个航班只能且必须存在在一个航班串内；式（5）保证航班衔接要求；式（6）保证航班串k的首个航班出发机场与最后一个航班到达机场必须一致且是具有一定维修能力的机场。旅客溢出成本指数经过大量数据仿真研究，取值如表1所示（其中T为相邻航班机上座位差异数量）。

表1 旅客溢出成本指数表Tab.1 Travellers overflow cost index

1.3 算法设计

1.3.1 算法原理

遗传算法（GA）是由美国密歇根大学的JH Holland教授于1975年创立的，该算法是通过模仿自然界生物进化机制发展起来的一种高效、全局、并行的优化方法[8]。近年来国内外学者通过对遗传算法的编码方式、控制参数的确定、遗传算子的设计等方面的改善，对遗传算法在航班串优化问题的应用进行了大量的研究工作，提出了各种改进后的遗传算法[9-10]。

采用基于Matlab的遗传算法工具箱GUI对航班串进行优化，染色体基因型数据结构如式（7）所示，整个种群存储在的矩阵中，行代表个体，列代表个体上的基因。

依照此原理，对航班串初始群体用线性规划方法进行优化。如式（8）和式（9）所示，根据航班信息形成矩阵Am×n，其中纵坐标j代表航班串，横坐标i代表航班，即Am×n表示m个航班，n个航班串。通过Am×n·X= B求出1组X=（x1，x2，…，xn）使其覆盖Am×n。

1.3.2 操作方法的改进

选择、交叉、变异是遗传算法的核心内容，如何针对具体问题改进3种操作方式将对优化结果产生重要影响。下面具体介绍文中遗传算法3种重要操作的改进方法。

选择操作的主要目的是防止种群遗传基因的丢失，算子选择不当会造成种群进化停滞不前或过早收敛，直接关系到遗传算法的计算效率和计算结果。本文所选取的选择方式为无放回余数随机选择，这种选择方式可保证适应度大于平均适应度的优秀个体能够被遗传到下一代，选择误差较小。

遗传算法的收敛性主要取决于交叉算子，合理的交叉算子在种群进化中能够增加群体分布的多样性。文中所选取的交叉算子为算术交叉，算术交叉是指父代个体经过线性组合产生2个子代个体。假设对2个父代个体进行算术交叉，则交叉后所产生的新个体为

其中，参数α需根据问题或进化代数决定。

变异操作是产生种群新个体的一种有效方法，它和交叉算子相互配合可对搜索空间进行有效的全局搜索和局部搜索。从而使遗传算法能够以良好的搜索性能完成对问题的优化。文中选用高斯变异的变异操作方法。高斯变异是指进行变异操作时用符合均值为P、方差为P2的正态分布的一个随机数来替换原有的基因值。由搜索方式可见，高斯变异与均匀变异较为相似。算法过程如下所示：

1）首先根据航班串优化模型中的目标函数编写M文件；

2）根据具体数据编制Aeq、Beq矩阵；

3）在GUI界面中初始化算法参数：确定种群类型和大小，适应度函数，变量个数，Aeq、Beq矩阵，算法终止准则，选择算子概率，交叉算子概率，变异算子概率，适应度排序方式，绘图函数等；

4）通过设定的遗传算法参数进行种群优化，根据终止准则判断所得当前最优解是否满足条件，如不满足返回3），继续进行优化，如满足继续5）；

5）输出算法最优解作为航班串优化问题的最优解。

2 结果与分析

本文仿真数据选取某航空公司某一天的部分航班派遣计划数据，如表2所示。

表2 航班信息Tab.2 Flight information

计划共20个航班，维修基地机场为天津机场，机型为B737、B757和A330，其座位数分别为150座、200座和250座。首先采用深度优先搜索算法生成初始可行航班串数据，如表3所示。

对初始航班串进行优化，工具箱GUI界面中定义参数为：精英选择，精英数量为2，选择操作为余数选择，交叉算子为算术交叉，变异为高斯变异，终止准则为进化到70代终止，绘图选择最佳个体和最佳适应度。调用目标函数M文件进行运算，得出结果如图1所示。

图1显示了种群每代所对应的适应度值，当种群迭代到70代左右时适应度值较为优异，且已稳定在6.097 4。图2显示了适应度值达到最优时所对应的最优变量值所在的位置，图中的当前代最佳个体表示优化后的航班串序号，即{J2，J5，J7，J8，J9，J11，J14}，对应的航班序号为{F1-F2-F19-F20，F3-F4-F17-F18，F5-F6，F7-F8，F9-F10，F11-F12-F15-F16，F13-F14}，对应的航线为：津—穗—津—昆—津，津—沪—津—亚—津，津—蓉—津，津—香—津，津—深—津，津—宁—津—松—津，津—厦—津。优化后的航班串最小成本指数为7.424 7，CPU运行时间约为3.22 s，航班串近优解相对稳定，计算效率较高，结果满足航班覆盖要求。

表3 初始航班串Tab.3 Initial flight strings

图1 适应度值的变化Fig.1 Changes of fitness value

图2 当前代最佳个体Fig.2 Best individual of current generation

目前航空公司的生产计划部门对航班串的编制过程多为人工编制，上述航班串计划需要用数小时完成一个可行计划，而本文采用的模型和算法只需不到1 min即可对所有航班进行有效编制。相比人工手动编制，不仅求解结果精确有效，且求解效率大幅提高，有效节省了人力资源。

3 结语

通过对遗传算法数据原理进行分析，建立了基于最小成本的航班串优化模型，能够满足航班运行需要。并通过Matlab遗传算法工具箱对模型进行求解。通过实际航班信息对上述模型算法进行验证，所得遗传算法优化结果较好，能够满足航空公司日常需要，并有效降低运营成本。

[1]杨卉竹.基于多Agent的飞机排班系统设计与实现[D].南京：南京航空航天大学，2011.

[2]LIU TUNG KUAN，LIU YU TING，CHEN CHIU HUNG，et al.Multiobjective Optimization on Robust Airline Schedule Recover Problem by Using Evolutionary Computation[C]//IEEE，Montreal，October 7-10，2007：2396-2401.

[3]TORSTEN R，JULIAP，MAROSZEK，et al.IntegratedAircraft Scheduling Problem：An Auto-Adapting Algorithm to Find Robust Aircraft Assignments for Large Flight Plans[C]//2012 45thHawaii International Conference on System Sciences，Maui Jannary 4-7，2012：1267-1276.

[4]ZHAN ZHIHUI，ZHANG JUN，LIU OU，et al.An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J].IEEE Transactions on Intelligent Transportation Systems，2010，11（2）：399-412.

[5]BURKE，EDMUND K，DE CAUSMAECKER，et al.A multi-objective approach for robust airline scheduling[J].Computers and Operations Research，2010，37（5）：822-832.

[6]HAOUARI M，AISSAOUI N，MANSOUR F Z.Network flow based approaches for integrated aircraft fleeting and routing[J].European Journal of Operational Research，2009，193（2）：591-599.

[7]BARD J，YU G，ARGÜELLO M.Optimizing aircraft routings in responsetogroundingsanddelays[J].HETransactions，2001（33）：931-947.

[8]HOLLAND J H.Adaptation in Nature and Artificial Systems[M].Michigan：The University of Michigan Press，1975.

[10]曹 嵩，孙富春，胡来红，等.基于分布估计算法的离港航班排序优化[J].清华大学学报，2012，52（1）：66-71.

（责任编辑：党亚茹）

Research on optimization method of flight string based on genetic algorithm

JIA Bao-hui，DU Jian-xun，LI Yao-hua
（College of Aeronautical Engineering，CAUC，Tianjin 300300，China）

Flight string problem is analyzed，and the connection between flights'average traffic volume and aircraft passenger capacity is considered.The factor of airline passenger overflow cost index is structured，and the optimized model of flight string based on minimum cost is proposed.At last GA based on Matlab is used to study the model. The simulation result with flight data shows that the model and algorithm are practical and effective.The optimization of flight string is meaningful to the airlines.

genetic algorithm；flight string；production planning

V271

：A

：1674-5590（2014）05-0045-04

2013-09-03；

：2013-10-13

：国家自然科学基金项目（U1233107）

贾宝惠（1971—），女，山西运城人，教授，硕士，研究方向为复杂工业过程建模、智能求解算法.