基于改进二进制粒子群算法的机组配对优化

张文成, 熊 静, 张 虹, 严 宇

(上海工程技术大学 航空运输学院, 上海 201620)

随着民航运输业的发展,航空公司机组排班问题复杂性和规模性显著增加.机组排班研究被众多学者认为是一个十分困难的组合优化问题(NP-hard)[1],而机组配对(Crew pairing)是其中一个子问题.

机组配对问题是指在满足中国民航局规定以及航空公司特殊要求下,生成一个覆盖所有航班并达到目标最优的配对(Pairing)集合.机组配对优化目标可以定义为机组成本最小[2]、飞行员工作量均衡[3]、配对数量最少、机组资源利用率最大等.

国内外机组配对优化研究成果很丰富,大部分研究思路是先生成配对再寻优.学者们常用遗传算法来解决机组配对寻优问题,并提出改进方案以获得高质量解:以Yen等[4]提出的模型为基础,李建[5]对机组配对问题进行描述,使用改进遗传算法对其进行算法设计;石丽娜等[6]将遗传算法同时应用在机组任务选择和配对阶段;Demirel等[7]开发基于改进动态遗传算法的启发式算法和代价较低的替代配对搜索方法;Deveci等[8]基于遗传算法优化过程,选择成本最低的最佳配对.

遗传算法实现复杂,部分学者将目光投向其他优化算法:Agustin等[9]提出可变邻域搜索方法;Tsubasa等[10]提出一种在特殊增强条件下应用部分优化两级分解算法(POPMUSIC);于海波等[11]提出使用离散型粒子群算法来解决飞机排班问题,该算法涉及参数少,全局搜索能力强,常被作为寻优研究的重点.为提高该算法寻优效率,各种改进策略被提出,如引入经验因子[12]等.

本文在实现机组配对时,将机组资源利用率最大作为优化目标.先采用深度优先搜索(DFS)算法产生所有满足约束的配对结果,再使用二进制粒子群优化(BPSO)算法选择产生配对集合一个子集,选择过程中为避免陷入局部最优,设计改进二进制粒子群优化(IBPSO)算法参与寻优.

1 机组配对数学模型

在航空公司总营运成本组成中,机组人员成本仅次于航油成本.我国航空公司机组成本主要由基本工资、飞行小时津贴、外站过夜补贴费用和机组成本等组成,基本工资通常固定不变.在机组配对时应该提高机组资源利用率,着力降低人员成本,从而达到总成本最优的目的.机组配对原则如下:

1) 同一配对中机型必须统一;

2) 配对中前序航班到达站和后序航班出发站必须相互衔接,相邻航段经停时间或航班交接时间一般至少40 min;

3) 配对飞行路径应尽可能为封闭回路,避免机组在外待过长时间,减少不必要的机组成本;

4) 为保证飞行安全,机组飞行任务时间不能违反民航当局相关规定.具体要求为:每日历周飞行时间要少于40 h;每日历月飞行时间要少于100 h;每日历年飞行时间要少于1 000 h;增加一名正驾驶的单套机组最多飞行时间不得超过10 h,值勤时间不得超过16 h.

以上述配对原则及成本最优目标为出发点,在仅考虑单套机组(可增加一名正驾驶)情况下,拟构建以机组资源利用率最大为基本优化目标的数学模型.机组资源利用率定义为总飞行时间与总值勤时间之比.对于给定航班计划,每个航班飞行时间是定值,因此将求解机组资源利用率最大转化为求解总值勤时间最短,构建数学模型的目标函数为

(1)

式中:目标函数(1)为最短总值勤时间;目标函数(2)为最少机组配对数;i为第i个航班;j为第j个配对;tj为第j个配对值勤时间;F为所有航班集合;D为所有配对集合;xj为机组配对0-1决策变量,如果机组配对j被选择,xj=1,其他则为0;[aij]为0-1矩阵,aij=1表示配对j中包含航班i,aij=0则表示航班i不在配对j中.

2 机组配对生成

2.1 构建航班连接网络

机组配对生成分两步:第一步是构建航班连接网络图;第二步是根据相关法规限制条件从网络图中搜索可行机组配对.

构建航班连接网络图时,首先在航班计划表中依次将每个离港机场作为根节点,得到所有以该机场为出发机场的航班集合;然后用衔接边将其航班节点与根节点连接起来,用航班边将其与航班连接起来,构建单层航班树;在基地机场航班树基础上遍历叶节点,将各到达机场出发航班树连接到该节点,逐级连接,直到没有满足规定的后续航班为止,完成航班连接树构建;在航班树基础上,增加基地机场(或过夜机场)终节点,用衔接边将各叶节点与终节点连接起来,构造成航班连接网络.

2.2 机组配对搜索

机组配对搜索采用图论中DFS算法[13],它是用于遍历搜索树或图的数据结构算法.DFS算法过程描述如下:

1) 将基地机场作为起始点放入栈中,并标记为已访问;

2) 当栈不为空时,若当前栈中第1个航班节点后序所有航班存在未被访问的,任意选择其一作为下一个访问航班,并将该航班节点入栈并标记为已访问,重复此过程至栈为空,转过程4);

3) 若当前访问节点为终节点,则将其出栈,并重复过程2);

4) 若栈为空,则算法结束.

第1次DFS得到的配对值勤时间较短,即机组资源利用率不高,需要将第1次配对编号,再构造航班树进行第2次DFS.在两次搜索过程中,航班之间衔接时间必须满足要求,记录路径上的飞行时间和值勤时间,保证得到的初始可行配对符合配对原则.DFS结束后,对孤立航班进行手工编排.

3 机组配对寻优

3.1 粒子群优化算法

1995年,Eberhart和Kennedy从鸟群觅食行为中得到灵感,提出粒子群优化(Particle Swarm Optimization,PSO)算法.PSO算法是通过设计一种无质量粒子来模拟鸟群中的鸟,该粒子仅具有速度和位置两个属性,分别代表移动的快慢和方向.算法具体流程如图1所示.

3.2 改进二进制粒子群优化(IBPSO)算法的实现

机组配对寻优是一个约束离散优化问题,在使用PSO算法时需要对算法解的编码方式、粒子位置和速度更新做出相应改进.Kennedy和Eberhart在1997年最先设计出针对离散空间约束优化问题的离散二进制粒子群优化算法(BPSO)[14],BPSO容易陷入局部最优,本文对其进行改进.

在设计适应度值时,主要考虑模型中目标函数值.针对违反约束条件的粒子,设计指数型增长惩罚因子p,违反程度越大,惩罚力度也越大,公式为

图1 PSO流程图Fig.1 Flow chart of PSO

(2)

p=round(elength(C(aij·xj～=1)))

(3)

其中:fitness为适应度值;C为航班覆盖向量,其元素个数反映不满足约束条件的程度;length函数为返回C向量中元素个数;round为四舍五入函数.

为更加接近算法寻优实际进化状态,本文提出基于余弦自适应惯性权重w,计算公式为

(4)

式中:wmin、wmax分别为惯性权重最小值、最大值;t为迭代次数;tmax为最大迭代次数.改进后算法在寻优早期w较大,具有较强全局探索能力;在寻优后期w较小,局部开发能力更强.

原始BPSO算法中S形映射函数基本公式为

(5)

(6)

式中:rand()为分布在[0,1]的随机数;S(vj)为xj取1的概率,S(vj)为Sigmoid函数.为使函数S(vj)不靠近端点值,粒子速度限定在[-vmax,vmax].映射函数曲线如图2所示.

由图2及强制性位置更新程序可知,正方向速度不断增大,位置向量取值为1的概率也不断增大;反之,负方向速度不断增大,位置向量取值为0的概率不断增大.

图2 映射函数曲线Fig.2 Curves of mapping function

原始BPSO算法在迭代后期容易局部收敛,为使算法更符合粒子运动规律,本文将种群进化过程等分成收敛和跳出局部最优两个阶段.迭代前期采用无速度限制S形映射函数,以促进算法稳定收敛;后期采用正弦映射函数以加速收敛,并且粒子位置更新采用非强制性更新程序,即当概率值大于随机数时,位置取其原位置向量的补集,否则粒子位置向量保持不变.

正弦映射函数图像如图2中虚线所示,公式为

(7)

本文改进IBPSO算法步骤如下:

1) 粒子种群随机初始化操作;

2) 设置种群参数;

3) 惯性权重自适应调整;

4) 粒子速度更新,公式为

(8)

5) 粒子位置更新,前期采用无速度限制S形映射函数与强制性位置更新程序,后期采用正弦映射函数与非强制性位置更新程序;

6) 重复步骤3)～步骤5),直至满足终止条件;

7) 满足终止条件,输出最优解及相应适应度值,算法结束.

4 航班算例实证

本文选取某航空公司波音737机型,以某天虹桥机场基地运营航班数据进行机组配对优化实例研究,部分航班信息见表1.

表1 某航空公司波音737航班信息表Table 1 Boeing 737 flight information sheet for an airline

4.1 算例配对生成

假设配对第一个航班起飞之前和最后一个航班落地之后花费时间为1 h,根据限制条件,本文算例中所得单一配对最多飞行时间不得超过10 h,每个配对中第一个航班起飞到最后一个航班落地时间(即本文所指值勤时间)不超过15 h.

为测试算法实际优化效果,从表1中选取航班规模为24(算例1)和50(算例2)的两组数据进行机组任务配对,两组算例第1次DFS分别生成14、37个配对,第2次DFS分别生成31、126个配对.

4.2 算例配对寻优

1) 算法参数设置

配对寻优时,为对比分析本文设计的IBPSO算法性能,选取原始BPSO和另外3种改进BPSO算法参与优化.原始BPSO粒子最大速度为0.2;NEWBPSO1在原始BPSO基础上设置粒子最大速度为0.6,惯性权重基于余弦自适应变化;NEWBPSO2在NEWBPSO1基础上放开粒子速度限制;NEWBPSO3在NEWBPSO2基础上采用正弦映射与非强制性位置更新程序.

根据文献[15],算法迭代次数固定为1 000,学习因子c1、c2均设置为2,惯性权重最大值为0.9,最小值为0.4.考虑到粒子种群规模会影响算法性能,选择100和200两种种群规模做对比试验.

本文算例仿真环境为Win10系统,使用Matlab 2016编程.硬件环境为INTEL酷睿处理器I5-6200U,主频为2.30 GHz,内存为8 GB.

2) 配对寻优结果分析

两组算例采用5种算法在种群规模为100和200情况下分别独立运行30次,获得适应度值的均值和方差,见表2,最优值加粗表示.观察表2,配对寻优中4种测试条件下IBPSO算法都具有最好的均值和方差,其求解稳定性更好,具有更好的收敛能力,原因在于:惯性权重基于余弦自适应变化,根据粒子种群进化时期特点,采取两种不同映射方式更符合粒子运动规律,从而提高寻优能力和解的质量.

表2 5种算法配对寻优仿真结果Table 2 Simulation results of five algorithms for pairing optimization

同一算例中,初始种群规模的增加虽然会使收敛时间增大,但能增强全局搜索能力,有效提高解的质量,使算法寻优更稳定.对比两组算例,航班规模增加使得问题求解维度明显增大,适应度值方差明显扩大,算法求解稳定性和质量有所下降.

4种测试条件下5种算法总体收敛曲线图如图3所示.由图可以发现,所有算法都会出现收敛曲线呈直线的情况,即陷入局部最优.NEWBPSO1由于提高了粒子最大速度和惯性权重自适应变化,其收敛速度会快于BPSO,表2中数据可看出其得到的解也优于BPSO;NEWBPSO2对粒子速度无限制,提升算法全局搜索能力,其收敛速度快于NEWBPSO1,容易获得较稳定的解;NEWBPSO3采取正弦映射和非强制性位置更新程序,收敛速度加快,算例1中得到的解会差于NEWBPSO2,但增加算例航班规模后其解明显优于NEWBPSO2;IBPSO结合NEWBPSO2和NEWBPSO3优点,算例1中其收敛速度不逊色于NEWBPSO3,并获得更优秀和稳定的解,算例2中迭代前期其收敛速度介于NEWBPSO2和NEWBPSO3之间,后期明显比NEWBPSO3收敛更快,且更容易跳出局部最优,得到更好的解.

算例1采用IBPSO得到的最优配对见表3.

表3 算例1机组配对结果Table 3 Crew pairing results of example 1

算例2由于增加航班规模,使得优化问题维度明显提高,表现出启发式算法局限性,即算法寻优解会靠近最优解.算例2采用IBPSO得到的最优配对见表4.

图3 5种算法总体收敛曲线图Fig.3 Overall convergence curves of five algorithms

表4 算例2机组配对结果Table 4 Crew pairing results of example 2

5 结 语

针对BPSO算法易陷入局部最优等问题,本文采用IBPSO算法寻优实现机组配对优化.两组不同规模航班算例表明,IBPSO从整体上提高算法收敛速度,求解稳定性好,并得到很好的机组配对结果,为优化机组排班提供理论基础.后续研究应考虑更复杂的实际航班配对约束,关注航班规模扩大使求解不稳定的问题,以提升算法应用能力.