机组排班的混合集合规划方法研究

《机组排班的混合集合规划方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第２期运筹与管理Ｖｏｌ．２３，Ｎｏ．２２０１４年４月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＡｐｒ．２０１４机组排班的混合集合规划方法研究蓝伯雄，　张米（清华大学经济管理学院，北京１０００８４）摘要：机组成本是仅次于燃料成本的第二大直接运营成本，合理的进行机组人员排班对降低航空公司运营成本有着重要意义。然而，机组排班问题是复杂性非常高的组合优化问题，属于ＮＰ难题。本文在分析机组排班问题研究进展的基础上，采用混合集合规划方法，综合考虑多种约束，建立了更具有实用性的机组排班优化模型。本文将运筹学理论与

2、业务逻辑相结合，设计了高效的求解策略。利用多组航空公司真实数据对模型进行测试，测试结果表明，模型可以在较短时间内有效求解达到实际应用规模的机组排班问题。关键词：机组排班；混合集合规划；集合分割；对象化建模中图分类号：Ｏ２２　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０２-０１７５-０８MixedSetProgrammingforCrewPairingＬＡＮＢｏ-ｘｉｏｎｇ，ＺＨＡＮＧＭｉ（SchoolofEconomicsandManagement，TsinghuaUniversity，Beijing１０００８４，China

3、）Abstract：Ｃｒｅｗｃｏｓｔｓａｒｅｔｈｅｓｅｃｏｎｄｌａｒｇｅｓｔｄｉｒｅｃｔｏｐｅｒａｔｉｎｇｃｏｓｔｓｉｎａｎａｉｒｌｉｎｅ’ｓｅｘｐｅｎｓｅｓ，ｏｎｌｙｎｅｘｔｔｏｆｕｅｌｃｏｓｔｓ．Ｈｏｗｅｖｅｒ，ｃｒｅｗｐａｉｒｉｎｇｉｓａｈｉｇｈｌｙｃｏｎｓｔｒａｉｎｅｄａｎｄｃｏｍｐｌｅｘｐｒｏｂｌｅｍ，ｗｈｉｃｈｍａｋｅｓｉｔｅｘｔｒｅｍｅｌｙｄｉｆｆｉｃｕｌｔｔｏｆｉｎｄｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｍｉｘｅｄｓｅｔｐｒｏｇｒａｍｍｉｎｇ（ＭＳＰ）ｉｓｐｒｏｐｏｓｅｄｆｏｒｔｈｅｆｉｒｓｔｔｉｍｅｔｏ

4、ｂｕｉｌｄｔｈｅｍｏｄｅｌ．Ｑｕｉｔｅｄｉｆｆｅｒｅｎｔｆｒｏｍｍａｔｈｅｍａｔｉｃａｌｐｒｏｇｒａｍｍｉｎｇ，ＭＳＰｓｕｐｐｏｒｔｓｇｌｏｂａｌｒｅａｓｏｎｉｎｇｏｖｅｒａｍｉｘｅｄｄｏｍａｉｎｏｆｒｅａｌｎｕｍｂｅｒｓ，ｉｎｔｅｇｅｒｓ，ｂｏｏｌｅａｎｓ，ａｎｄｓｅｔｓ．Ｓｅｔｐａｒｔｉｔｉｏｎｉｎｇｍｏｄｅｌａｎｄｒｏｕｔｉｎｇｍｏｄｅｌａｒｅｔｈｅｃｏｒｅｐａｒｔｓｏｆｏｕｒｍｏｄｅｌ．Ｃｏｍｐｕｔａｔｉｏｎａｌｔｅｓｔｓｈｏｗｓｔｈａｔｐｒｏｂｌｅｍｓｏｆｒｅａｌ-ｗｏｒｌｄｓｉｚｅｃａｎｂｅｓｏｌｖｅｄｅｆｆｉｃｉｅｎｔｌｙｗｉ

5、ｔｈｉｎｒｅａｓｏｎａｂｌｅｔｉｍｅ．Keywords：ｃｒｅｗｐａｉｒｉｎｇ；ｍｉｘｅｄｓｅｔｐｒｏｇｒａｍｍｉｎｇ；ｓｅｔｐａｒｔｉｔｉｏｎｉｎｇ；ｏｂｊｅｃｔ-ｏｒｉｅｎｔｅｄｍｏｄｅｌｉｎｇ０　引言作为重要的现代交通运输方式，航空运输在国民经济生产生活中有着重要意义。在航空运输业中，机［１］组的人工费用是航空公司直接运营成本的第二大组成部分，仅次于燃料成本，但机组成本却比燃料成［２］本具有更好的可控性。航空公司每年所支出的人工费用达上亿元，机组成本每降低一个百分点，将为航空公司每年节约上百万甚至千万元的开支。为保证飞行安全，航空业对

6、机组飞行能力、飞行时间等有非常严格的规定和管理制度，因此，机组排班过程需满足大量约束，这使机组排班模型的结构非常复杂，优化求解极其困难。正是如此，对机组排班问题的研究引起了工业界和学术界的高度关注。下面引入三个概念：机组排班计划问题（ＣｒｅｗＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ，ＣＳＰ），机组排班问题（ＣｒｅｗＰａｉｒｉｎｇＰｒｏｂｌｅｍ，ＣＰＰ）和机组人员指派问题（ＣｒｅｗＲｏｓｔｅｒｉｎｇＰｒｏｂｌｅｍ，ＣＲＰ）。机组排班计划问题（ＣＳＰ）即传统意义上机组人员飞行计划的制定，根据每个航班的飞行属性，为航班指派相应的机组人员，来完成航班的飞

7、行［３］［４］作业，其本质是确定哪个航班由哪些人员来执飞。机组排班计划问题由两个子问题组成：机组排班问题（ＣＰＰ）和机组人员指派问题（ＣＲＰ）。机组排班问题的主要任务是：按照航空管理部门的相关条例，将收稿日期：２０１３-１０-１１作者简介：蓝伯雄（１９５０-），男，黑龙江人，教授，博士生导师，研究方向：大系统优化理论与算法、供应链优化、收益管理；张米（１９８７-），女，山东人，博士生，研究方向：优化理论与算法。１７６运筹与管理　　　　　　　　　　　２０１４年第２３卷机组飞行任务匹配成从飞行基地出发并能返回基地的任务环（术语中称为“Ｐａｉｒｉ

8、ｎｇ”），这些任务环将覆盖全部待执行航班。机组排班问题的优化目标是飞行成本的最小化，该问题有一定的理论难度，可为航空公司带来显著效益。机组人员指派问题则在机组排班问题的基础上，将