遗传算法在机型配置中的应用

陈蓉

摘  要：航班机型配置关系到航空公司的行业竞争力，是航空公司长期关注的问题。针对航空运力过剩及机型比例失调等问题，考虑航班规模增加及机型配置需求增多对航空公司的影响，引入多重约束，建立基于航空收益最大化的航班机型配置优化模型。采用遗传算法求解该模型，并设置算法中的选择、交叉、变异等算子，获得一段时间内机型配置连线最优方案。研究表明，提出的多重约束优化模型和遗传算法，能够提高航空公司机型配置时效性与科学性。

关键词：机型配置;多重约束;航空收益;遗传算法

中图分类号：TP399     文献标识码：A

Abstract： Fleet assignment， a long-term concern of airlines， has much to do with the competitiveness of airlines. Considering the impact of increased flight scale and increased fleet assignment demand on airlines， this paper introduces multiple constraints and establishes a fleet assignment optimization model based on maximizing aviation revenue， aiming at the problems of overcapacity and imbalance of aircraft types. The genetic algorithm is used to solve the model， and the selection， crossover， mutation and other operators in the algorithm are set to obtain the optimal solution for fleet assignment connection scheme within a period of time. Research shows that the proposed multi-constraint optimization model and genetic algorithm timely and scientifically improve fleet assignment model.

Keywords： fleet assignment; multiple constraints; aviation revenue; genetic algorithm

1   引言（Introduction）

國内外航空市场竞争日益激烈，各航空公司为了提升竞争力，对增加航班规模、优化航班资源配置、精细化管理提出越来越多的要求。其中，机型配置是航空运输中不可缺少的一部分，也是提升航空市场竞争力的一个有效方法。机型配置是航空公司在航班时刻表的基础上进行现有机型的分配，它根据不同的机型具有的不同座位数、客运需求、最大空缺率、运行成本、最大耗油量等，配置不同的机型给设定好的航班，从而使航空公司获得最大收益。此外，飞机座位是“易腐的”，在航班离港前没有出售就会造成浪费，因此最理想的决策就是将“合适的座位数”以“合适的价格”提供给“合适的乘客”。本文主要从“合适的座位数”出发，优化航班的机型配置。

机型配置是一项长期研究的问题，过去的研究大多集中于机组任务问题上，定义一个便利且高效的目标函数[1]，开发高效算法来解决复杂的资源配置问题[2]，或者研究问题的动态性质[3]，也有研究问题的随机性[4]、鲁棒性[5]的。常见的机型配置问题可通过整数规划建立数学模型或建立时空网络图[6]来解决，包括引入乘客需求、运营成本、票价、时间窗、航班频率等因素[7-9]。

机型配置规划中不同的机型及限制条件不同，模型算法有所不同。胡明华等提出改进的启发式算法用于解决多元受限航班优化模型[10];李福娟等采用紧急搜索法对航空公司航线计划优化模型进行求解，使利润达到最大[11];WEI等采用一种原始的集成优化方法对机队分配进行求解[8]。但当问题规模较大时，上述模型求解比较困难，因此，遗传算法等智能搜索算法也被用于问题求解。

研究表明，机型配置规划对航空运输具有非常重要的意义，目前研究大多集中于某个因素或多个因素约束构成的综合模型，或者对重大规模现有模型进行算法优化。本文在已有的理论上进行深入探究和发展，首先基于飞机座位数、尺寸、效率、成本、耗油量等因素建立以收益最大化为目标的多重约束机型配置模型;然后采用遗传算法对其进行优化求解，使机型配置模型求得适应度最优的解;最后结合具体情况，验证机型配置模型的可行性和有效性，以及遗传算法用于解决机型资源配置的高效性。

2   机型配置模型（Fleet assignment model）

2.1   问题描述

机型配置是航班计划的重要研究内容。我国现有航空公司中，每个航空公司不止一种机型，每种机型的飞机架数、座位容量、油耗、成本（维修成本及乘客溢出成本）等都是不同的，且在不同的航线上，不同的机型产生的运营成本也是不同的，故机型配置是为了确定每一条航线上使用的机型，并使得整体利益最大化。

要解决的问题及基本假设：

（1）机型配置要确定每一条航线应该使用哪一种飞机或机队，使收入减运营成本最大化。

（2）航班时刻表是已知的，是一组具有指定起飞和到达时间的航班段。

（3）收入是细分市场需求，运营成本取决于飞机的尺寸和效率，以及航段的距离。

（4）机场必须有飞机可以飞行，且每个机场必须在一周开始和结束时分配相同的飞机。

（5）满足覆盖约束：确保每个单航程只分配一种机型;满足计数约束：每个机型指定的飞机架数必须等于该机型在所有时间内可用的飞机总数;容量限制约束：分配到单一航程的所有乘客数量不能超过分配到该航程机型的容量;平衡约束：中转服务飞行必须将两个航段分配给相同的飞机;行程约束：机型分配航程时要注意机型路程类型，短途机不能分配给中长航段，中途机不可以分配给长航段。

2.2   模型构建

2.2.1   模型参数

机型配置模型所需参数及变量定义如表1所示。

其中，目标函数（5）是机型配置下运输成本与收入的绝对值最大化，即使得收益达到最大。约束条件（6）确保每一次“真正”的飞行都有一架指定的飞机，即每一个航段都有一个机型来覆盖。约束条件（7）确保每个机型的每架飞机只能从伪出发航班集及伪到达航班集起飞一次。约束条件（8）确保飞机必须在同一个地方开始和结束。约束条件（9）确保满足最大座位空缺率，如果MS=0.1，航班的需求为100，则可溢出的乘客最多不超过10人，即必须使用座位容量大于90的机型。约束条件（10）强制在中转飞行中，航段要使用相同的设备机型。约束条件（11）和（12）确保飞机必须在机场才能被分配给航段且机型相同，其中，对于将要

从某机场出发的航班，是在该机场航班可以衔接的到达航班集合，且满足航班衔接的时间要求;，即在航班

前从该机场出发的航班集合。约束条件（13）和（14）确保机型与航班之间类型的兼容性，其中，即长途机型可以进行长、中、短途飞行;，即中途机型可以进行中、短途飞行，短途机型只能飞短途。

3 遗传算法的应用（Application of genetic algorithm）

由于航空运输规模的扩大，且机型配置模型是大规模数学组合模型，为了在短时间内得到最优解，本文采用遗传算法对机组配置模型求解，采用适合的编码方式及约束条件的处理方式，选取适应度函数和选择、交叉以及变异方法，最后以某航空公司的数据为例，代入机组配置模型进行研究，计算使得机组航班资源最优的配置方案。

3.1   编码

采用遗传算法对机组配置问题进行求解，需要编码确定研究问题所表达的含义。本文采用直接编码法对其进行编码，其中机型编号为1—，航段为染色体上的基因位数，即为染色体长度。假设机型有3种，航段数为6，在进行编码时3种机型的编号为1、2和3，规划方式为36种选择，假设一条染色体上基因的排列为（1，3，2，3，1，1），则解为：

3.2   初始化数据

求解模型中所需的数据格式，确定交叉概率和变异概率，选择一个机型配置结果作为初始群体，即为模型求解结果的假设集合，模型的最优解将通过这些初始解进化而求出。选择初始解，可以采用随机选取或优化算法选取，本文采用的是随机选取。

选取初始群体后确定每个个体的适应度，适应度函数是根据目标函数来区分的。对每个航班所选择的机型的编码串进行解码处理后得到个体的表现型，通过个体表现型可计算机出对应个体的目标函数值，根据机型配置模型的目标函数转换出个体的适应度。

3.3   选择、交叉与变异

遗传算法是一个优胜劣汰的寻优算法，选择操作的目的是为了将不够优的个体从群体中挑出，也就是在将机型分配给航段的个体中选择适应度较高的个体进行演化。本文采用最佳保留选择算法，按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。

对于选中的用于演化的个体，随机选择两个个体相同的位置进行交叉操作得到新的个体，然后根据变异算子的概率对某些个体的某些位置执行变异操作，增加全局优化特性，确保得到全局最优解。

4   算列分析（Example analysis）

每条飞机连线上的航班视为一个航班块，每一个航班块包括序号、出发地和出发时间、目的地和到达时间、乘客需求及票价。决策变量为0—1的整数，即每一个决策变量只能取0或1。以表2和表3数据为例，涉及230个航班的3个机型，其中表2为航班块集合（由于篇幅限制，仅展示部分信息），表3为机组信息集合。

根据表4、表5可以得出：（1）引进遗传算法得到的最优解成本劣于混合整数线性规划得到的最优解成本，但是随着迭代次数的增大，GB也随着减小，这证明了遗传算法引入的有效性，且所提出的算法不受问题空间的限制，因此遗传算法能在可接受时间内产生较优航空资源配置。（2）遗传算法的引进增加了算法运行时间，但这个运行时间在成本取得较优的情况下可以忽略不考慮，且时间的增加在可接受范围内。

5   结论（Conclusion）

考虑到航空公司规模的不断扩大，机型配置问题也愈发复杂，遗传算法的引进解决了航班资源配置问题。首先，考虑乘客需求、运行成本、飞行距离、票价、耗油量等因素的影响，根据航班集合信息及机队信息，建立收益最大化的机组配置优化模型;其次，考虑大规模问题，引进自适应遗传算法，为调度、机组分配问题创建可行的初始解，设计制定遗传算子，改进初始解，得到全局较优解;最后，以航空公司数据为例，将采用遗传算法后的资源配置结果和最初的资源配置结果进行对比。结果表明，引进遗传算法的优化模型可以得到全局最优解，实现了飞机停机调度约束的统一，通过对不同个体的适应度分析，得到全局效益最优解，且该优化模型灵活可变，方便后续相关约束的加入，能够通过建立线性约束条件，较为方便地加入、修改、取消相关约束，进而实现约束的动态优化。

参考文献（References）

[1] DUMAS J， AITHNARD F， SOUMIS F. Improving the objective function of the fleet assignment problem[J]. Transportation Research Part B： Methodological， 2009， 43（04）：466-475.

[2] YAN S Y， TANG C H， FU T C. An airline scheduling model and solution algorithms under stochastic demands[J]. European Journal of Operational Research， 2007， 190（01）：22-39.

[3] JIANG H， BARNHART C. Dynamic airline scheduling[J]. Transportation Science， 2009， 43（03）：336-354.

[4] CADARSO L， CELIS R D. Integrated airline planning： Robust update of scheduling and fleet balancing under demand uncertainty[J]. Transportation Research Part C： Emerging Technologies， 2017， 81（02）：227-245.

[5] JIANG H， BARNHART C. Robust airline schedule design in a dynamic scheduling environment[J]. Computers & Operations Research， 2013， 40（03）：831-840.

[6] HANE C A， BARNHART C， JOHNSON E L， et al. The fleet assignment problem： Solving a large-scale integer program[J]. Mathematical Programming， 1995， 70（02）：      211-232.

[7] YAN S， TSENG C H. A passenger demand model for airline flight scheduling and fleet routing[J]. Computers and Operations Research， 2002， 29（11）：1559-1581.

[8] WEI K J， VAZE V， JACQUILLAT A. Airline timetable development and fleet assignment incorporating passenger choice[J]. Transportation Science， 2020， 54（01）：139-163.

[9] SERRANO-HERNANDEZ A， CADARSO L， FAULIN J.     A strategic multistage tactical two-stage stochastic optimization model for the airline fleet management problem[J]. Transportation Research Procedia， 2020， 47（04）：473-480.

[10] 胡明華，朱晶波，田勇.多元受限的航班时刻优化模型与方法研究[J].南京航空航天大学学报，2003，35（03）：326-332.

[11] 李福娟，王鲁平，刘仲英.航班计划优化模型及其应用研究[J].计算机工程，2007，33（11）：279-281.

作者简介：

陈   蓉（1970-），女，硕士，经济师.研究领域：航空公司数字化转型及智能系统建设.