基于混合遗传算法的航班串优化模型研究

李耀华，秦如如

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

飞机排班是民航企业优化调度中的一个重要问题，也是航空公司日常生产经营中的一项重要活动，制定合理的排班计划，对有效地组织航空运输生产活动具有重要意义。欧美的许多大型航空公司从20世纪80年代开始在生产中广泛采用专门的飞机调度管理系统来管理这项工作，而国内民航针对飞机排班优化调度方面的研究基本还处于起步阶段。文献[1]以航班串过夜次数最少及航班串数目最少为目标，提出针对航班覆盖问题的遗传算法，但模型没有考虑机型限制、维修限制等约束条件。文献[2]以使用飞机数最少为目标，研究了航班串的生成与筛选问题，但只考虑了单日航班运营方案的编制。文献[3]以飞行成本最小为目标，建立了航班串的优化模型，但没考虑到航班衔接所带来的其他收益。

本文针对国内航空公司飞机排班问题的现状，分析了飞机排班计划的编制流程，并针对其中的航班串编制问题进行研究及建模，同时，构造了一种精英自适应混合遗传算法对模型进行求解及优化。

1 航班串编制模型

1.1 问题描述

飞机排班是航空公司生产计划中的一项控制性工作，其实质就是根据市场部下达的航班计划、每架飞机的技术状况以及飞机调度指令，为每个航班指定一架具体执行的飞机，在排班的过程中，必须确保飞机安排的合法性、飞机排班的可行性及飞机使用的均衡性，并应尽力以最小的成本完成所有的航班任务，因此以人工或半人工方式完成排班计划的工作模式已不能满足当前航空公司的需求，借助计算机进行飞机排班并对结果进行优化成了一个亟待解决的问题。

飞机排班的流程可以划分为三个部分：①航班串的编制，就是根据公司的航班信息，将一个到港航班与另一个离港航班衔接起来，生成若干个可以由一架飞机去执行的航班连接；②飞机指派，就是为每一个编好的航班串指派一架具体执行的飞机；③机组指派，就是为每个航班串和执行飞机指派空勤机组，三者互有影响和联系。本文主要针对其中的航班串编制问题进行研究，这个问题需要考虑的主要约束包括四方面：①相邻航班的机场、时间约束，即同一航班串内前一航班的到港机场与后一航班的离港机场必须相同，且需满足过站时间的限制；②同一航班串内相邻航班的平均载客量不能相差太多；③同一航班串内相邻航班的飞行区域自然条件不能相差太多；④同一航班串首个航班出发地和最后航班的到达地都要求是具有一定维修能力的基地机场[4]。

1.2 航班串模型的建立

航班串编制问题是一个组合优化问题，规模大，需要进行分层优化，本文将其归结为一个车辆路径问题，每个航班作为一个顾客，每个航班串作为一个车辆，车辆路径问题本身要求相同的起点和终点作为一个回环，并且不能出现子回环，因此构造虚拟航班0和约束条件（6）以满足问题要求，本文考虑采用启发式规则方法在给定航班串数目的前提下，以各个航班串内航班之间的总惩罚值最小为目标，最终建立的航班串编制优化模型如下

Li为第i个航班到达机场代码；Dj为第j个航班出发机场代码；Lnkk为第k个航班串内最后一个航班到达机场代码；D1k为第k个航班串内首个航班出发机场代码；DTj为第j个航班出发时间；LTi为第i个航班到达时间；Tmin为同一飞机两个航班之间的最小过站时间；Tmax为同一飞机两个航班之间的最大过站时间；mmin为最小航班串数目；fi为第i个航班的飞行小时；fave为航空公司所有可用飞机的平均飞行小时。

航班串数的最小值由式（7）确定，即

式中：int表示取整。

目标函数（1）使各个航班串内的航班之间的差异惩罚最小，约束条件（2）保证每个航班必须被分配到一个航班串内，而且只能分配到一个航班串内，约束条件（3）保证同一航班串内相邻航班的到港机场和离港机场为同一机场，约束条件（4）保证同一航班串内相邻航班之间的时间间隔满足过站时间要求，约束条件（5）保证同一航班串的执行飞机能够返回基地机场，约束条件（6）是为了避免模型在进行仿真研究时编码中出现子回环问题。其中航班间时间联接、载客量、飞行区域的差异惩罚值，经过大量数据仿真研究，选取数值分别如表1～表3所示（其中：航班i、j处于同一航班串内且前后相接，LTi为航班i到达时间，DTj为航班j出发时间，Pi为航班i平均客流量，Pj为航班j平均客流量，Ri为航班i飞行区域代码，按飞行区域等级代码用 1、2、3、4、5 来表示）。

表1 航班时间连接惩罚系数表Tab.1 Penalty coefficient of turnover time between flights

表2 相邻航班客流量惩罚系数表Tab.2 Penalty coefficient of passengers between adjacent flights

表3 相邻航班飞行区域差异惩罚值Tab.3 Penalty coefficient of flying area between adjacent flights

2 航班串模型的求解算法

航班串编制问题是一个NP-难问题，采用数学方法求取精确解有很大难度，而遗传算法是智能优化方法中应用最为广泛也最为成功的算法，在求解复杂优化问题方面具有巨大的潜力，本文在基本遗传算法的基础上，构造了一种基于精英选择策略的精英自适应混合遗传算法对提出的模型进行求解及优化[5]。

2.1 染色体编码方式

本文采用相关文献中关于车辆路径问题[6]的遗传算法的编码方式并对其进行适当修改，使其自动满足约束条件（2）和约束条件（6）。

1）初始化染色体 K=（s1，s2，…，sm×n），令各个航班串中的航班数目 numi=0（i=1，2，…，m），当前计划中航班的总飞行小时 loi=0（i=1，2，…，m），航班串的长度约束为 L，各航班的状态为 fi=0（i=1，2，…，n）（表示航班没有做入航班串）。

2）j=1。

4）判断fl的状态，如果fl=0，则航班l仍为自由航班，此时如果lok＜L，则将航班l加入航班串k，numk=numk+1（numk即为当前航班l在航班串k中的次序号），lok=lok+航班 l的长度，fl=1；如果 lok＜L 不成立，则转5）；如果fl=0不成立，则直接转5）。

5）j=j+1，转 3），直到 j=m × n+1。

最后，检查所有航班的状态标志fi（i=1，2，…，n），如果全为1表明所有航班都按要求分配到航班串中，否则，认为是一个不可行解，重新进行处理。

2.2 基于精英选择的新染色体生成方法

本文构造的基于精英选择策略的自适应混合遗传算法，是一种特殊的遗传算法，其设定每个父代染色体可以遗传出Ns（可根据需要自行设定）个子代染色体，然后再从整个家庭成员中选择最优的个体进入遗传群体，由于这种精英选择过程已经保证子代个体必然会不差于父代个体，因此基本遗传算法[7]中的依比例概率选择过程已经不再适用，另外，在遗传过程中，如果使用不变的遗传参数来控制遗传进化，很容易导致早熟而影响算法的搜索效率，因此采用根据种群的进化情况自适应地调整遗传参数pc和pm的方法提高算法的性能[8]。pc和pm的调整公式如下

其中：pc、pm分别代表当前的交叉、变异概率；pc0、pm0分别代表初始交叉、变异概率；fmin、fmax、fave分别代表每一代群体的最小适应度值、最大适应度值、平均适应度值；α、β为取值在0～1之间的常数。

2.3 混合遗传算法求解步骤

1）输入求解模型所需数据。

2）根据式（7）确定最小航班串数目m=mmin。

3）算法参数的初始化：确定算法种群数目、结束最大循环代数、每一代父辈遗传的子辈数目Ns、基因交叉、基因变异的初始概率pc0、pm0，然后根据种群数目给出初始染色体，作为当前代染色体。

4）计算当前代染色体的函数适应值，记录最优个体作为当前最优解，并判断是否满足结束准则，如是，则停止转10）；否则，进行下一步5）。

5）对当前染色体进行概率的自适应动态调整，按公式计算基因交叉概率pc、基因变异概率pm。

6）对当前染色体进行遗传操作：对所有父辈染色体随机配对，每一对父辈染色体以设定的Ns数、概率pc、pm依次进行基因交叉、精英选择、基因变异操作，得到新一代的染色体。

7）将所得新一代染色体作为当前代染色体，转4）。

8）输出当前最优解作为当前航班串数目下算法的最优解。

9）航班串数目 m=m+1，转 3）。

10）输出所有航班串数目下算法的最优解作为整个航班串编制问题的最优解。

3 仿真研究

本文采用某航空公司一周140个航班信息作为编制航班串的数据实例进行计算，以验证所提出的模型及算法的可行性。原始数据如表4所示，由于篇幅原因表中仅列出部分数据。

本文的混合算法选择的参数为：种群规模为10，每个染色体在精英选择时所产生的后代染色体个数为Ns=10，初始交叉概率为pc0=0.95，初始变异概率为pm0=0.15，最大迭代次数为100，概率调整公式中的α取为0.6，β取为0.75，为了比较本文算法的有效性，同时采用基本遗传算法进行计算研究，基本遗传算法的参数选择为：种群规模为10，交叉概率为pc=0.95，变异概率为pm=0.15，算法停止准则为连续迭代100代，两种算法采用相同的评价函数，其适应值函数随迭代次数的变化趋势分别如图1、图2所示，本文算法最终获得的目标函数最优值为140000，航班串数目为9，航班串编制的结果如表5所示，不同航班串之间用逗号分隔，具体数值代表航班序号，表中数据代表航班的衔接顺序，如周一的数据15-43代表指派的飞机在完成航班15时继续执行航班43，而普通遗传算法最终获得的目标函数值为16000，由图1和图2可知，本文算法较普通遗传算法优化效果更好，且随迭代次数的增加，优化效果也会越来越明显，但计算时间也会相应增加。

表4 实际航班信息Tab.4 Actual flight information

目前，许多航空公司还由人工编制航班串，排班人员编制上述规模的航班串通常需2～3天的时间，并且不能同时考虑各类约束，而本文建立的模型及算法在短短几分钟内就能完成所有工作，和人工排班方式相比，工作效率高，优化结果好，能够提高航空公司的管理自动化水平。

表5 航班串编制结果Tab.5 Results of flight string

4 结语

本文分析了飞机排班的流程，主要研究其中关于航班串的编制问题，通过分析研究建立了一个航班串编制优化模型，其主要考虑航班衔接的要求和过站时间要求等约束条件。对此优化模型的求解方法，构造了一种基于精英选择策略的混合自适应遗传算法。采用实际数据经仿真验证，证明所提出的模型及算法切实可行，可降低航空公司运营成本，增加企业效益。

[1]沈中林，李廷朵.遗传算法在航班覆盖问题中的应用研究[J].中国民航大学学报，2008，26（6）：5-9.

[2]付维方，张伟刚，孙春林.航班排班中航班串生成与筛选问题的算法与实现[J].中国民航学院学报，2006，24（5）：4-6.

[3]都业富.航班串优化方法[J].系统工程理论与实践，1995，8：75-80.

[4]李耀华，谭 娜，郝贵和.飞机排班航班串编制模型及算法研究[J].系统仿真学报，2008，2（3）：612-615.

[5]江 健.精英自适应混合遗传算法及其实现[J].计算机工程与应用，2009，45（27）：34-35.

[6]姜大立，杨西龙，杜 文，等.车辆路径问题的遗传算法研究[J].系统工程理论与实践，1999，6：40-45.

[7]刘定理.遗传算法综述[J].中国西部科技，2009，8（25）：41-43.

[8]李耀华，谭 娜.飞机排班调度中机组指派优化模型及算法研究[J].计算机工程与应用，2008，44（34）：243-245.