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

◆陈肯 张广伟

（中国民用航空飞行学院空中交通管理学院 四川 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]。……