基于文化基因算法的机组排班问题研究

◆陈肯 张广伟

（中国民用航空飞行学院空中交通管理学院 四川 618300）

机组排班是根据航班计划和机型属性等要求，为航班指派相应的机组人员（包括机长、副驾驶、机械员、领航员、通信员等）并实施航班飞行任务的过程[1]。机组排班问题主要分为任务环生成（Crew pairing problem，CPP）和机组人员指派（Crew assignment problem，CAP)。CPP 问题主要是任务的生成，发现一组往返飞行航线并且覆盖所有的航班。CAP 问题是任务的分配，主要是将已分割完成的任务派遣给各组机组人员执行[2]。本文的研究主要针对机组排班中最核心的问题任务环生成（CPP）问题。

Budi Santosa[3]提出了一种基于遗传算法的简单迭代变异(SIMA)方法来解决航空公司机组排班问题。在排班的质量与时间上均取得较好结果。Frédéric Quesnel[4]提出了一种启发式分支定价算法解决了带有语言限制的机组排班问题。张米[5]系统分析提出了机组排班问题模型并考虑了延误因素，运用列生成算法计算，取得了较好的优化结果。

本文提出了一种基于动态文化基因算法的中型航空公司任务环配对问题的求解方法。目标是找到成本最低的机组人员配对。

1 文化基因算法

机组排班问题是典型的NP_hard 问题，受系统复杂性和多种约束条件的限制[6], 求解非常困难，常用算法有分支定价算法、分支切割算法、列生成算法以及遗传算法等启发式算法。其中遗传算法是求解机组排班问题的经典算法，有着相对成熟的理论体系。本文选用遗传算法的改进算法文化基因算法进行求解，遗传算法已被大量运用于此问题的研究中并证实效果显著[7]。但标准遗传算法会过早向目标函数的局部最优解收敛且算法对初始种群的选择具有一定的依赖性[8]。而文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合算法。

文化基因算法是一种框架,可以采用不同的搜索策略可以构成不同的文化基因算法,如全局搜索策略可以采用遗传算法、进化规划等,局部搜索策略可以采用爬山搜索、贪婪算法、禁忌搜索等[9]。这种局部与全局的混合搜索机制可以在某些问题领域比传统遗传算法快几个数量级。文化基因算法基本框架如图1所示。

图1 文化基因算法框架图

2 问题模型

2.1 航空公司排班基本原则和约束

在机组排班过程的任务环生成阶段，依据中国民航局制定的飞行运行手册和各民航公司内部制定的排班规则[10]，来组合任务环。包括飞行时间限制、值勤时间限制、航段个数限制、人员搭配限制以及机组资源本身的限制。现将主要规则整理如表1所示：

表1 限制条件汇总

2.2 数学模型

通过分析国内外机组排班流程算法的特点、我国民航局及航空公司的相关规定,构建了机组排班问题的数学模型

式中cp代表任务环p的成本，包含机组的飞行津贴，撘机机组成本以及在外过夜成本[5]。xp是决策变量，0 代表任务环未被选中，1代表任务环被选中。afp=1 表示p任务环中包含i航班，否则afp=0。

式（1）目标函数为最小化总任务环成本。式（2）确保每个航班至少被覆盖一次。式（3）限制了决策变量的可行域。

3 用深度搜索算法生成飞行任务环池（pairsALL）

本文利用启发式算法来产生初始机组任务，事先考虑航班连接时的限制条件，在航班连接时避免了穷举算法所有可能的无效率性，在处理实际问题时，可快速产生可行初始机组任务。

3.1 构建航班网络

构建航班联接的网络图时，需要考虑的因素包括航班联接的物理地点约束与时间约束。前导航班与后续航班的起降时间满足最短、最大转换飞机时间约束，最短休息时间约束且前机的降落机场为后机的起飞机场本文便称这两个航班之间存在合法连接。对每个航班建立航班树（图2），运用c++的链表结构进行编程，在以后碰到求航班的后续可行航班只要根据网络查找下一个航班的航班树，这样可以减少计算量。本文构建的航班连接的网络图示例如下：

图2 航班网络图

1）节点。节点代表不同的航班。每个节点包含有航班的起止机场与时间信息。

2）连接线。每根连接线都代表节点与节点之间的合法连接，需要满足包括时间、地点的约束等等。

如图所示，图中有三个航班树，航班树相连构成航班网络，航班1 的合法连接航班有3、4、5、6，航班3 的合法连接航班为4、6、7，航班6 的合法连接航班为2、8。在搜寻过程中，可以由航班1 的航班树定位到航班6 的航班树，可形成1、6、2 和1、6、8 两个合法任务环，其余同理。

3.2 根据生成的勤务组组成飞行任务环池

任务环生成方法是一个递归的过程，借助3.1 提出的航班网络，采用递归的方式进行搜索。在第一阶段，所有的航班都按照主要程序进行审查。对于从基地开始的任务，将执行搜索算法进行递归，可以将符合条件的任务环加入到主集中。需要满足的约束有：

时间约束：在外过夜不超过3 天，即同一个任务环最多包含4天的勤务

地点约束：下一个勤务起始的机场需要是上一个勤务终止的机场。

算法一：生成所有任务环

4 选择初始子集（pairsActive）

本文利用启发式算法生成一个随机任务环子集（从主集中选择），这个子集中包含的任务环可以覆盖所有航班，并不要求初始子集为最优子集，只需保证可行性，在后续会通过启发式算法对子集进行更新优化。下面开发了一种启发式算法来生成初始子集。伪代码如下：

1 对每一个航班在任务环总集（pairAll）中搜索包含该航班的任务环加入到子集中（pairsActive）。

2 在航班集合中寻找下一个未被覆盖航班。

3 重复1 步骤，直到所有航班均被覆盖。

上述三小节是为了产生成用于生成染色体的任务环子集（pairsActive），该集合任务环将作为遗传算法的解空间。该集合越大，迭代选取到最优组合的概率越大，但会增加算法无效的计算量，选取合适数量的子集有助于减少迭代到最优的次数。

5 文化基因算法

5.1 基因编码

本文基因编码采用01 编码，每一个染色体位代表任务环总体中相对应的任务环是否被选中，0 代表任务环未被选入，1 代表该任务环被选入。

5.2 生成初始种群

初始种群是文化基因算法的第一阶段。这个群体中的每一条染色体都代表了该问题的一个可行解决方案。本文开发了一种启发式方法覆盖每一次飞行任务，生成一个可行的初始种群。

算法二：初始化种群

5.3 适应度

适应度采用最小化成本

式中cj代表任务环j的成本，包含飞行固有成本加机组责任时间成本。nj代表任务环j 包含的过夜次数，hj代表旅店成本，xj表示任务环是否包含在该染色体中，0 表示未包含，1 表示被包含。si代表单次航班i的花费，yi表示i航班是否为撘机航班，若是则为1，不是则为0。aij表示航班i是否被任务环配f 包含，若是，则为1，否则为0。

5.4 选择算子

采用二元锦标赛选择法，在锦标赛选择法中，从种群中随机挑选两个个体，然后将适应度最优的个体选出进入下一代。这个过程重复进行直到子代种群数量达到规定数量。

5.5 交叉算子

在选择祖先(母亲和父亲)染色体产生新的孩子后，可以利用交叉算子可以有助于将优良个体的染色体片段遗传给后代,同时交叉算子一般起全局搜索的作用,可以开采未知的空间。本文采用单点遗传方法。

（1）先产生随机数确定交位点；

（2）交叉位点后的基因实现单点交换；

（3）交叉完成。

5.6 突变算子

采用位翻转变异算子保证算法不捕捉局部最大值和局部最小值点。设置突变概率为0.2。

（1）随机确定突变点位；

（2）突变点位的值由0 变1，或由1 变0。

5.7 启发式修补算法

经过遗传交叉变异后的个体可能无法满足航班约束（每一航班至少被覆盖一次），所以需要设计一种启发式算法修复子代染色体，使之满足航班约束。本文设计了一种任务环选择指标，保证成本较低的任务环进入到解集中。

任务环选择指标=任务环P 的成本/集合中未被覆盖的航班数量，伪代码如下：

（1）遍历染色体，搜索未被覆盖航班；

（2）在子集（pairActive）中搜寻包含该航班的任务环；

（3）选择任务环选择指标最小的任务环加入染色体中。

5.8 局部启发式搜索算法

局部启发式搜索算法是文化基因算法的一个重要特征，用局部启发式搜索可以模拟由大量专业知识支撑的变异过程,以使解决算法更有效率。这一过程目的减少无用的任务任务环，确保了染色体的适应度优化的同时保证满足航班约束。伪代码如下：

算法四：局部搜索算法

（1）选择染色体解集中的任务环，将该任务环从染色体中移除；

（2）若解集中航班覆盖约束不被满足（不是所有航班都被覆盖），则将该航班重新加入；

（3）重复上述两步，直到遍历所有解集中的任务环。

5.9 种群替代策略

文化基因算法的最后一步是种群置换。在这一步，父代和子代的染色体需要通过一种选择策略确保种群数量的固定。因为种群的数量是固定的，所以种群替代策略可以确保种群的数量保持不变。种群更替阶段使用的两种主要方法是世代法和稳态法。本研究采用稳态方法。在这种方法中，在每次迭代中生成一个或两个子代。然后，这个后代的染色体取代了种群中最差的个体。

6 文化基因算法伪代码

文化基因算法伪代码如下：

（1）对每个个体计算适应度

（2）while 终止标准不满足do

（3）Parent1 ←Select-Parent(population,tour-size)

Parent2 ←Select-Parent(population,tour-size)//应用锦标赛算法选择父代

（4）Child1 ← Apply-Crossover(one-point ceossover, Parent1,Parent2)

Child2 ←Apply-Crossover(one-point ceossover,Parent1,Parent2)

（5）Child1′←Apply-Mutation(bit-flip random,Child1)

Child2′←Apply-Mutation(bit-flip random,Child2)//进化算子

（6）Child1′←局部搜索(lc,Child1′),Child2′←局部搜索(lc,Child2′)

（7）将种群中最差的两个个体替换为父代和子代中最好的两个//种群替代；

end while

7 优化方案和实现部分

通过c++语言，在visual studio 平台上进行程序编写。设置迭代次数为1800 次,每迭代100 进行一次更新搜索空间算法。锦标赛选择法行程为2，交叉概率为0.9，突变概率为0.2，设置种群规模为20。机组飞行小时津贴为400 元/小时，每个机组的任务津贴为1000 元/天，机组在外过夜的旅馆成本为500 元/天。航班加机组成本，每个航段的成本是不相同的，这里为了研究方便，假设加机组成本都是一个固定值500/小时[13]。选用国内某中型航空公司一周的航班数据，分别用Kornilakis 所提遗传算法[14],更新解空间的遗传算法与本文所提算法进行实验（表2所示分别用算法一二表示）。该公司一周共有航班549 架次，通过深度搜索算法产生了1683 个勤务组和79862 个任务环。实验结果如下：

表2 对照实验算法

表3 对其他作者开发的遗传算法和本文所提算法进行的测试结果。在两项实验中分别对最优解的在外过夜次数，撘机次数，撘机总时间总花费（元）等关键绩效指标进行了统计。在评估解决方案的优劣时需要参考的三个重要参数为执勤总时间、撘机总时间和在外过夜次数。比较遗传算法，所提的更新搜索空间策略能有效缩减解空间大小，且在减少撘机次数和过夜次数方面有显著效果。对比遗传算法与所提算法可以看出，局部搜索策略能够起到小幅优化效果。通过对这三个重要参数的比较且同时参考比较三种种算法的其他KPIs 表明，本文所提出的算法比之前的研究产生了更好的结果，该算法具有良好的性能。

表3 机组排班实验数据

表4 列出了三个重要的参数：执勤总时间、撘机总时间和在外过夜次数在迭代过程中的优化趋势。在600到800次迭代之后趋于收敛。

表4 所提算法不同迭代次数的最优解KPIs

图4 为两种算法的适应度变化曲线，可以看出本文所提算法在解决机组排班问题上具有更优的性能。

图4 适应度变化曲线图

8 结束语

针对航空公司机组人员配对问题，本文提出了一种基于动态文化基因算法的改进算法。由于机组任务环配对是排班过程中成本识别的主要环节，如何降低机组成本、增加机组效用、实现最优机组配对具有重要意义。所以本文的优化从关键绩效指标(KPIs)，如撘机时间、勤务天数和在外过夜次数等与机组任务环优化相关的成本指标着手，提出了基于动态文化基因算法的改进算法。实验结果显示，与现有方法相比，本文所提出的算法生成了更优解。所提出的更新搜索空间的算法对减少撘机时间和减少过夜停留次数有显著效果。

本研究的主要贡献如下：

第一项贡献是利用动态遗传算法和每次迭代的染色体长度变化来解决任务环配对问题。该算法基于文化进化理论，采用全局搜索与局部搜索相结合，有效加快了基因进化的速度。

第二项贡献是利用深度优先搜索算法结合航班网络设计了用于快速生成可行任务环的启发式算法。经试验该算法可生成大量可行的任务环。

综合考量来看，本模型综合考虑了机组人员撘机次数、过夜次数、机组人员的成本等问题，解决了传统排班方法无法给出的算法模型，为航空公司机组排班算法的进一步研究提供了良好的理论依据，对实际应用提供了较好的参考。