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

Crew Pairing Optimization Based on Improved Binary Particle Swarm Optimization Algorithm

以机组资源利用率最大作为优化目标进行机组配对研究,根据航班计划表构建航班连接网络图,基于深度优先搜索(DFS)算法产生初始配对结果,提出改进二进制粒子群优化算法(IBPSO)进行寻优.IBPSO引入指数型增长惩罚因子和基于余弦自适应惯性权重,种群进化前期采用无速度限制S形映射函数与强制性位置更新程序,后期采用正弦映射函数与非强制性位置更新程序.两组不同规模航班算例验证表明,IBPSO能克服原始算法收敛慢、迭代后期局部开发能力差的缺点,在维数增加时依然能有效提高算法寻优速度和解的质量.

Taking the maximum utilization of unit resources as the optimization objective,the study of crew pairing was carried out.According to the flight schedule,the flight connection network diagram was constructed,and the initial pairing results were generated based on the depth-first search(DFS)algorithm.An improved binary particle swarm optimization(IBPSO)algorithm was proposed for optimization.The penalty factor for exponential growth and adaptive inertia weight based on cosine were introduced by IBPSO.In the early stage of population evolution,S-shaped mapping function without speed restriction and mandatory position updating program were used,and in the later stage,sine mapping function and non mandatory position updating program were used.Two groups of flight examples with different scales show that IBPSO can overcome the shortcomings of slow convergence of original BPSO and poor local development ability in the later stage of iteration,and can effectively improve the speed of optimization and the quality of solution while increasing the dimension.