航空运输规划课程报

基于启发式模拟退火算法的机组排班算法研究

报告

方杰1

（1 南京航空航天大学 民航学院，江苏省南京市，210016）

摘 要：首先分析了国内外机组排班算法和流程特点、我国民航局及航空公司关于机组排班的相关规定，构建了机组排班问题数学模型，研究了基于启发式模拟退火算法的求解方法。本文在模拟退火算法基础上，根据航班环生成的特点，重点研究了启发式算法，以缩小求解问题的解空间规模，修正冗余解，将不可行解转化为可行解，增强模拟退火算法的局部搜索能力，达到有效提高模拟退火算法收敛速度和提高机组编排质量、优化效果的目的。

关键词：机组排班；启发式模拟退火算法

1 引言

机组排班是遵守管理当局的机组适航条例和考虑机组的意愿，通过科学合理的排班，保证航班计划飞行任务的正常完成，并要求尽可能降低机组人力资源成本。一般分为两个子问题，即机组任务配对问题（Crew Pairing Problem ）和机组人员指派问题（Crew assignment or Crew Rostering Problem ）。本文机组排班问题主要侧重点在于机组配对问题的解决。

机组排班问题，重要的是生成符合适航要求的航班环。一个航班串是若干个航班根据时间和空间的先后顺序连接而成。如果航班串的起点和终点都是基地，生成的航班串即为航班环。在我国实际情况下，航班环是指一个在时间和空间上顺序连接，由一个机组在一天内完成的飞行航段有序序列，是机组排班的基本单位。航班环生成的质量对航班安全运行和提高航班运行效益有着决定性的影响。

[1]目前国内外针对机组排班问题开展的研究工作的学者主要有Shaw Ching Chang ，

[2][3] [4][5][6][7]M.Bazargan , Harry Kornilakis, Claude P. Medard, Niklas Kohl, Thomas Emden Weinert, 孙宏等。机组排班问题的解法主要有分为精确性解法和基于启发式解法两大类。基于精确性解法研究的

[2]主要有：M.Bazargan 利用单纯形法求解机组排班问题，但该算法无法在短时间内求解大规模整数规

[8]划问题；S.Yan 等人研究多基地、多机型、多乘务员等级的乘务员排班问题采用了分支定价法，即将分支定界法与列生成法结合求解整数规划问题，这无疑增加了求解过程的复杂度；且采用精确性解法求解问题时要求待解问题的目标函数和约束条件均必须为线性，但实际上机组排班问题的目标函数和约束条件往往不能完全满足线性要求，故采用精确解算法存在局限性。基于启发式解法研究

[9]的主要有：David Levine提出了混合式遗传算法以解决机组排班问题，但该算法在求解过程中可能

[10] 会丢失可行解，影响算法的收敛速度；R.Anbil 等人设计了一种全局优化的方法用于求解机组排班

[1]问题，但会出现不必要的Deadhead ，影响解的质量；Shaw Ching Chang 利用遗传算法解决区域机

[3]组排班问题，直接使用遗传算法处理巨变量整数规划问题存在收敛速度慢的问题；Harry Kornilakis

等人对遗传算法的初始解生成、选择和交叉操作进行优化后求解机组排班问题，但待解问题的解空

[6]间没有缩小，无法有效地提高算法收敛速度；Thomas Emden Weinert采用模拟退火算法与局部搜索

算法相结合以求解机组排班问题，但模拟退火算法控制参数的初始值及退火速度等参数设置过于依赖经验数据。 作者简介：方杰(1983-)，男，南京航空航天大学民航学院博士研究生，研究方向为智能运输系统建模、仿真与优化，电话：[1**********]，E-mail: [email protected]

鉴于以上研究方法的特点，本文采用分步求解策略，将航班机组排班问题分为若干步骤分别求解。其中航班环生成是机组排班的基础，首先生成高质量的航班环，以便获得高效的机组排班计划。诸多研究表明，模拟退火算法方法简单，鲁棒性好，全局搜索能力强，处理问题适应性广；另一方面，将待解问题设计为0-1整数规划问题，模拟退火算法可以直接求解。因此本文给出基于启发式的模拟退火算法对机组排班问题进行求解。

由于机组排班需处理的航班计划数据量大，导致难以在短时间内得到高质量的方案。本文在模拟退火算法的基础上，根据我国民航当局和航空公司相关规定及机组排班特点，设计启发式算法，缩小求解问题的解空间规模，修正冗余解，将不可行解转化为可行解，增强遗传算法的局部搜索能力，以克服遗传算法在求解大规模整数规划问题时难以在短时间内保证求解结果质量的缺陷。 2 机组排班

现将机组排班过程分成两个阶段：航班环生成阶段，以构建可能的航班环集合；航班环筛选阶段，根据航班环集合，筛选若干航班环以组成方案，要求生成的机组方案必须覆盖所有的航班集合。

2.1 机组排班的基本原则

根据我国民航当局及航空公司的相关规定，一个航班环中包含的航段应在飞行时间和飞行空间上连续，且航段之间的衔接时间满足最短过站时间要求；一个航班环的飞行时间和值勤时间应符合民航规定的最大时限而且一个航班环应尽可能回到始发基地。

2.2 机组编排问题的数学模型

机组编排问题可以归结为集合分割问题（Set Partitioning Problem）的求解[2] [7] [13]，现定义如下变量：

P ： 机型集合, 其中任一机型用p 表示，p ∈P

Lp ：机型p 的待飞航段集合，其中任一航段用i 表示，i ∈Lp

Dp ：机型p 的航班环集合，其中任一航班环用j 表示，j ∈Dp

Fj ： 航班环j 的飞行时间

Tj ： 航班环j 的值勤时间

⎧1 航班环j 包含航段i a =⎨ij ⎩ 0 航班环j 不包含航段i

设决策变量为：

⎧1 生成方案包含航班环j x =⎨ j ⎩ 0 生成方案不包含航班环j

根据航班运行成本最低和效益最高的期望，现设以下目标函数：

min e =(∑T j x j -∑F j x j ) /

j ∈Dp j ∈Dp j ∈Dp ∑T x , (1) j j

这里考虑式（1）为目标函数的单目标0-1型整数规划问题。

下面考虑约束条件。机组排班问题的约束条件是航段覆盖性约束，即在航班计划编排合理的条件下，任意航段i 应满足：

j ∈Dp ∑a x ij j =1 (∀i ∈L p ), (2)

式（2）左端表示方案中包含航段i 的航班环个数总和。其含义为：生成方案中，每一个航段必须被分配到一个航班环，且只能被分配在一个航班环中。

故问题的数学模型为：

min e =(∑T j x j -

j ∈Dp

ij j ∈Dp ∑F x ) /∑T x j j j j ∈Dp j s .. t

j ∈Dp ∑a x j =1 (∀i ∈L p ) ,

x j =0 或 1

3 启发式模拟退火算法

模拟退火算法的思想是1953年Metropolis N. 等人在研究二维相变时提出的，SA 算法最早分别由KirkPatrick 等人(1980)和Cerny V.(1981)独立地提出。传统的模拟退火算法的基本思想就是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比，试图模拟高温物体退火过程，找出优化问题的全局最优或近似全局最优解。在理论上模拟退火算法是以1的概率收敛，但是模拟退火算法的缺点也比较明显如：

(1)尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率0-1收敛于全局最优点, 但是由于算法的一些环节无法在实际设计算法时实现，因此SA 算法往往得不到全局最优解，或算法结果存在波动性。为了寻找最优解，算法通常要求较高的初温、较稳的降温速率、较低的终止温度以及各温度下足够多次的抽样，因而模拟退火算法往往优化过程较长，这个是算法的最大缺点。计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想；

(2)在每一温度下很难判定是否达到了平衡状态，即马尔可夫链的长度不易控制，反映到算法上，就是Metropolis 过程的次数不易控制。

本文为了能够平衡效果与时间之间的矛盾，考虑首先找到一个接近于最优解的解初始解，再运用模拟退火算法在局部范围搜索最优解。并且通过反复的实验找到一个效果与metropolis 过程次数的平衡点。

在模拟退火算法的基础上，本文根据航班环编排特点设计启发式算法，以提高算法收敛速度和求解结果质量。启发式模拟退火算法的主要步骤如下：

3. 1 编码

本文采用二进制编码方式描述机组排班问题。具体编码方式如表1所示：

生成方案 1 0 „ 1 1

L p1 1 0 „ 1 0

A

L p2 0 0 „ 1 1

„ „ „ „ „ „

L pn-1 0 1 0 1

L pn 0 1 0 0

3.2 模拟退火算法初始解

（1） 在备选航班环中出现频率最低的航班（包含航班i 的航班环个数越少，选中这些航班环的概

率越大）的那些航班环应优先编排。例如：一个航班只为一个航班环所包含，则该航班环必须被选中，概率为1。

（2） 当航班多次出现在不同航班环中时，可以考虑选取包含未编排航班最多的航班环。

（3） 在初始解生成阶段，包含航班个数最多的航班环优先选择，尽量减少航班环个数，降低航班

重复率。

（4） 所有选中的航班环必须保证包含所有的航班，而不需要考虑航班的冗余。

3.3 模拟退火算法的新解

（1） 将初始解生成的航班环方案进行变异（随机选取n 个位置，进行0-1的变异），选择变异的

航班环中包含的航班k i ，遍历所有包含该航班的航班环（可事先建立检索表），将其中一个航班环x j =1。

（2） 依次变异航班环中包含的所有航班（在这里留下了只能多不能少的弊病，就很有可能留下

Deadhead ）。

（3） 遍历所有的航班环，计算出冗余航班环（航班环中包含的所有航段的计数k i ≥2），x j =0。

3.4 Metropolis 准则

1、 先初始解生成的航班环方案定义为初始状态i ，该状态的能量是E i 。

2、 产生新解后，得到一个新状态j ，新状态的能量是E j 。

3、 如果E j E i ，则该新状态就作为“重要”状

态，要依据航班环方案出于该状态的几率来判断。

4、 航班环方案出于该状态的几率的比值等于相应的Boltzmann 因子的比值，即r =exp(E i -E j

kT ) ，

r 是一个小于1的数，用随机数发生器产生一个(0,1)区间的随机数ξ，若r >ξ，则新状态j 作为重要状态，否则舍去，k 为Boltzmann 常数，t 为控制参数。

5、 若新状态j 时重要状态，就以j 取代i 成为当前状态，否则仍以i 为当前状态，再重复以上新状

态的产生过程。

3.5 模拟退火算法的冷却进度表

冷却进度表是一组控制算法进程的参数用以逼近模拟退火算法的渐进收敛性态，使算法在有限时限执行过程后返回一个近似最优解。冷却进度表包括控制参数的初值、及其衰减函数、对应的Markov 链的长度和停止准则。它是影响模拟退火算法试验性能的重要因素，其合理选取是算法应用的关键。

1、 控制参数t 0的初值

算法进程在合理时间里应搜索尽可能大的解空间范围，只有足够大的初值才能满足这个要求，应让初始接受率近似等于1。由Metropolis 准则推得t 0应该足够大（1000℃）。

2、 Markov 链的长度

实现方法为，制定接受次数指标i （当接收次数等于i ，该控制参数下的Markov 链结束，控制参数值减小）和接受率q （记录该控制参数值下迭代的总次数和被接受的次数，接受率不

小于q 时，Markov 链结束，控制参数值减小）。接受率q 这类方法，L k 、与控制参数t k 的取值相关，由于接受率随t k 的递减而减小，通常选取t k 的小衰减量以避免过长的Markov 链。

3、 控制参数的衰减函数

控制参数的小衰减量还可能导致算法进程迭代次数的增加，因而可以期望算法进程接受更多的变换，访问更多的邻域，搜索更大范围的解空间，返回更高质的最终解，当然也花费更多的CPU 时间。试验表明，只要衰减函数选取恰当，就能在不影响CPU 时间合理性的前提下，较大幅度的提高最终解的质量。

常用的衰减函数：

（1）t k +1=αt k ，其中α=0.5~0.99

（2）t k =L -k ⋅t ，其中L 为算法控制参数下降的总次数 L

在上述两类衰减函数中，第(1)种具有随算法进程递减的衰减量，因而可以减小控制参数值递减的速率，从而延缓了变换接受概率随算法进程递减的态势，这无疑有利于模拟退火算法试验性能的稳定。

4、 停止准则

算法收敛于最优解集是随控制参数t 值的缓慢减小而渐进进行。只有在t “充分小”时，才有可能得出高质的最优解。因此，t “充分小”在某种程度上可以替代“最终解质量”的判据，为停止准则所用。一是让控制参数t 值小于某个充分小的正数ε，直接构成停止准则的判断式t

常用的选取停止准则的另一个途径是不改进规则控制法，以算法进程所得到的某些近似解为衡量标准，判断算法当前解的质量是否持续得到明显提高，从而确定是否终止算法，如在若干个相继的Markov 链中解无任何变化就可以终止算法。这类方法同样兼顾最终解质量和CPU 时间，在t k 和L k 等参数的配合下，不仅可望得到高质量的最终解，而且对于CPU 时间有相对控制作用(即CPU 时间随问题规模的增大而增大) ，解质相对稳定。

1、让控制参数值小于某个充分小的正数（零度法）；

2、接受概率（接受概率控制法）；

3、循环总数控制法，总的下降次数为一定值40~200。

3.6 启发式模拟退火算法

机组排班面临的主要困难是待处理的数据量大，故难以在短时间内保证解得方案的质量。若能在不影响结果的前提下缩小待解问题的解空间规模，无疑将提高算法的收敛速度和求解结果的质量。

合法航班环的飞行航段序列在时间和空间上均需满足多种限制。如：航班环执飞航段的时空连续性，且航段之间的衔接时间满足最短过站时间要求；同时，一个航班环的飞行时间和值勤时间不得超过民航规定的最大时限。因此，机组排班过程中存在航段i 被唯一航班环j 包含。即：

j ∈Dp ∑a ij =1 (∃i ∈L p ),

则方案必包含航班环j ，否则丢失航段i ，得到不可行方案。因此，令x j ≡1。

同时，约束条件要求：“每一个航段均被执飞一次且只被执飞一次”，故若存在航班环j ’与上述航班环j 包含相同航段i ’，即：

a =a =1 (∃i '∈Lp , ∃j '、j ∈Dp , x j '≡1), i 'j i 'j '

则航班环j ’不应被方案选中，否则违反约束条件。故令x j '≡0。

值得注意的是，该算法应循环调用，直至找到所有被唯一包含的航段i 。采用上述启发式算法可有效缩小机组排班问题的解空间规模，故模拟退火算法的收敛速度明显加快，且方案的质量得到改善。

4 算例分析

本文以某航空公司航班计划为例，利用Matlab 进行仿真实验。

该航空公司A320机型每天有八十余个航班，分别以上海、南京、无锡为基地。航班计划以国内航班为主，且含有部分国际航班，本文在机组排班时设置扩编飞行机组属性，将国内航班和国际航班统一编排，以提高机组资源的利用率。

由于遗传算法具有随机性，应在时间允许的情况下多次求解，故分别采用遗传算法和启发式遗传算法进行十次机组排班，且设置相同参数，主要参数为：初始种群大小为350个，迭代次数为400代。

4.1算法流程图

具体算法流程如图1所示。

图1

4.2 实验结果

模拟退火算法

启发式模拟退火

算法 2130 2111 5.4 0 8.9 0 27.01 8.39

表2

模拟退火算法无法缩小求解问题的解空间规模，而且解方案出现反复。而启发式模拟退后算法通过启发式算法将解空间规模缩小了218倍，故遗传算法平均求解耗时是启发式遗传算法的3.42倍；且模拟退火算法求得结果的质量劣于启发式模拟退火算法：经过10次求解，模拟退火算法解得的方案均出现不同程度的航段丢失和航段重复的情况，未解得合理的方案，并且方案的平均效率低于启发式模拟退火算法求解的方案。综上所述，启发式模拟退火算法能够在可接受的时间内合民航规定且高质量的机组排班方案。

参考文献

[1] Shaw Ching Chang. A New Aircrew-scheduling Model for Short-haul Routes[J]. Journal of Air Transport Management,

2002, Vol.8: 249-260

[2] M.Bazargan. Airline Operations and Scheduling[M]. Ashgate Publishing Limited, 2004.

[3] H. Kornilakis and P. Stamatopoulos. Crew Pairing Optimization with Genetic Algorithms[M]. Springer-Verlag Berlin

Heidelberg, Springer Berlin / Heidelberg, 2002.

[4] Claude P. Medard and Nidhi Sawhney. Airline crew scheduling from planning to operations[J]. European Journal of

Operational Research, 2007, Vol.183, Issue 3: Pages 1013-1027.

[5] Niklas Kohl, STEFAN E. KARISCH. Airline Crew Rostering: Problem Types, Modeling and Optimization[J].Annals of

Operations Research, 2004, 127: 223–257

[6] Thomas Emden Weinert T and Proksch M. Best Practice Simulated Annealing for the Airline Crew Scheduling Problem

[J]. Journal of Heuristics, 1999, Vol.4: 419-436.

[7] 孙宏，文军. 《航空公司生产组织与计划》[M]，西南交通大学出版社， 2008年5月第1版.

[8] S. Yan,T.-T. Tung,Y .-P. Tu. Optimal Construction of Airline Individual Crew Pairings [J]. Computers & Operations

Research, 2002, Vol.29: 341-363.

[9] David Levine. Application of A Hybrid Genetic Algorithm to Airline Crew Scheduling [J]. Computers Ops Res. 1996, Vol.

23, No. 6: 547-558.

[10] R.Anbil, R.Tanga, E.L.Johnson. A Global Approach to Crew-pairing Optimization [J]. IBM SYSTEMS JOURNAL,

1992, Vol. 31: NO 1.

[11] 中国民用航空总局, 《大型飞机公共航空运输承运人运行合格审定规则》, 1999.5.5.

[12] 中国民用航空总局, 《一般运行和飞行规则》, 2007.2.14.

[13] Nadia Souai, Jacques Teghem. Genetic algorithm based approach for the integrated airline crew-pairing and rostering

problem[J]. European Journal of Operational Research, In Press, Corrected Proof, Available online 13 April 2008.