• 唯一百姓论文网官方网站(其他网站均属假冒)。工作时间9:00-17:00,周末休息,QQ:1647439496。电话联系:15389037508(同微信)
当前位置:首页 > 论文列表 > 机组排班问题的两阶段建模方法

机组排班问题的两阶段建模方法

机组排班问题的两阶段建模方法
朱 理
同济大学经济与管理学院,上海 200092
摘要:机组排班作为航空运营管理中的重要一环, 是航空公司降低成本, 提高运营效率的关键。机组排班通常需要考虑航空公司的航班计划和飞机运营计划以及所有的机组人员, 问题规模往往很大, 同时需要考虑航空业相关管理规定的严格限制, 求解困难。本文基于两阶段法, 将机组排班问题分解为机组组环问题和人员指派问题并提出了相应的建模方法。
关键词:机组排班问题; 机组组环问题; 人员指派问题; 建模方法
中图分类号:O221  文献标识码:A
Two-stage modeling for the crew scheduling problem
Li Zhu
School of Economics and Management, Tongji University, Shanghai 200092
Abstract: As an important part of airline operation management, crew scheduling is the key to reduce cost and improve operation efficiency of airlines. Crew scheduling usually needs to consider the airline's flight plan and aircraft operation plan as well as all the crew members. The scale of the problem is often very large, and it also needs to consider the strict restrictions of relevant management regulations of aviation, making it difficult to solve. Based on the two-stage method, this paper decomposes the crew scheduling problem into the crew pairing problem and the crew rostering problem, and proposes the corresponding modeling.
Keywords: crew scheduling problem; crew pairing problem; crew rostering problem; modeling

0 引言
机组排班(Crew Scheduling)是指航空公司依据航班和飞机的运营计划, 在符合航空管理局、工会和航空公司等组织的法规、条例和协议的相关规定下, 确定机组人员一定时期内的工作安排。作为最早将运筹优化技术与其运营管理紧密结合的行业之一, 越来越多的航空公司将运筹优化技术应用于机组排班问题(Crew Scheduling Problem, 简称CSP), 以提高收益, 降低成本, 实现利润最大化。
孙宏等人于2007年[1]的研究显示, 航空公司的总成本包括燃油/滑油成本、机场服务成本、航路成本、机组成本和飞机维修成本等。美国航空运输协会于2008年[2]公布的数据表明, 机组成本占航空公司总成本的比重仅次于燃料费用, 为23.4%。于新才于2020年[3]的研究指出, 机组成本是我国三大航空公司(中国国航、南方航空和东方航空)的第二大成本。因此, 在当今竞争激烈的航空业中, 降低机组成本是航空公司的一项重要任务, 其能为航空公司节省大量的开支。值得注意的是, 随着越来越多廉价航空公司的出现, 航空业价格竞争的压力日益增加, 航空公司降低机组成本的重要性逐渐凸显。航空公司的机组排班计划与其机组人员的值勤效率、服务质量和工作满意度息息相关。因此, 机组排班问题是航空公司最重要的计划问题之一。
然而, 解决机组排班问题面临着巨大的挑战。一方面, 随着全球航空客运需求的稳定增长, 民航领域业务量及规模持续上涨, 航空公司不断开拓新航线, 扩张机队规模, 尽管飞行员队伍也在不断扩大, 但仍然难以满足高涨的民航需求和快速的机队扩张, 飞行员缺口仍然存在。另一方面, 为确保飞行安全, 《CCAR-121R5》中对机组排班部分制定了细化且复杂的工作规则, 《CCAR-121R6》又在此基础上进一步提高了机组运行标准和安全保障要求, 使得机组排班的难度和复杂度越来越高。
1 机组排班问题分解
由于大多数航空公司的机组排班计划都是月度的, 航空公司的机组排班问题涉及航班和飞机的月度运营计划以及所有的机组人员, 规模往往很大。幸运地是, 航空公司的机组排班问题可以被划分为多个规模较小的机组排班问题。首先, 由于驾驶舱的机组人员(cockpit crews)与乘务舱的机组人员(cabin crews)是互不相干的, 航空公司的机组排班问题可以被划分为飞行机组的排班问题和乘务机组的排班问题。其次, 由于驾驶舱的机组人员只能操作特定类型的飞机, 飞行机组的排班问题可以按不同的飞机类型进行划分。此外, 由于乘务舱的机组人员能在同一机族(如波音和空客等)任意机型的飞机上工作, 乘务机组的排班问题可以按机族划分。然而, 尽管航空公司的机组排班问题可以被划分为多个规模较小的机组排班问题, 但是这些问题仍可能包含成千上万条航段, 同时必须考虑多方法规、条例和协议的相关规定, 仍然难以解决。因此, 如何快速有效地求解划分后的机组排班问题仍然是一项极具挑战性的问题。为此, 现阶段通常采用两阶段法(详见于Barnhart等人于2004年[4]以及Gopalakrishnan和Johnson[5]对机组排班问题做的文献综述), 将划分后的机组排班问题进一步分解为两个子问题, 即机组组环问题(Crew Pairing Problem, 简称CPP)和人员指派问题(Crew Rostering Problem, 简称CRP)并依次解决。
2 机组组环问题
机组组环问题的主要任务是依据航班和飞机的运营计划, 生成一组总成本最低的恰好覆盖各运营航班一次的航班环(Pairing), 即组环方案。其中, 航班环从同一个基地开始和结束, 由一系列的执勤日(Duty)及其之间的休息期(Layover)组成。执勤日指代一天的飞行任务, 由一系列连续的运营航班、置位航班(用于转移机组人员的航班)及其之间的连接(Connection)组成。航班环和执勤日的可行性均受到航空业相关管理规定的限制, 常见的规定包括:每个航班环最多包含4个执勤日、每个执勤日最多覆盖4个运营航班、每个执勤日的计薪时间不能超过8小时、每个执勤日的持续时间不能超过12小时、每个连接的持续时间不能少于0.5小时、每个休息期的持续时间不能少于9.5小时等。接下来, 本文将机组组环问题抽象为对应的数学模型。
假设已知为所有运营航班的集合。令表示所有可行的航班环的集合; 表示航班环的成本; 表示航班未被覆盖的惩罚成本; 为0-1参数, 表示航班是否被航班环覆盖; 为0-1决策变量, 表示是否选择航班环为0-1决策变量, 表示航班是否未被覆盖。本文采用如下集合划分模型(Set Partition Model)表示机组组环问题:

 


在上述模型中, 每一个航班环都对应一个决策变量, 每一个运营航班都对应一个决策变量和一个集合划分约束。目标函数(3-1)为在尽量保证航班均被覆盖的情况下最小化组环方案的总成本; 约束(3-2)为集合划分约束, 确保了各运营航班均最多被航班环覆盖一次; 约束(3-3)和约束(3-4)确定了决策变量的取值范围。
3 人员指派问题
人员指派问题的主要任务是依据解决机组组环问题得到的组环方案, 在考虑机组人员的工作满意度(例如航班偏好、假期需求等)的情况下, 产生一组恰好覆盖组环方案中各航班环一次的个人排班计划, 即机组排班计划。其中, 个人排班计划由计划期(一般为1个月)内一系列的航班环、假期和培训期及其之间的连接组成。个人排班计划的可行性同样受到航空业相关管理规定的限制, 例如执勤时间限制和连续执勤天数限制等。接下来, 本文将人员指派问题抽象为对应的数学模型。
假设已知为所有运营航班的集合; 为所有机组人员的集合; 和分别为机组人员偏好的航班和需求的假期集合; 为组环方案中所有航班环的集合; 为航班环的成本。令表示机组人员可选择的所有可行的个人排班计划的集合; 表示机组成员选择个人排班计划的成本; 表示航班环所需机组人员的数量; 表示航班环无法满足机组人员数量要求的单位惩罚; 表示机组人员执行其偏好的航班的奖励; 表示机组人员得到其需求的假期的奖励; 表示机组排班计划满足机组人员的航班偏好的最小数量要求; 表示机组排班计划满足机组人员的假期需求的最小数量要求; 为0-1参数, 表示航班环是否被个人排班计划覆盖; 为0-1参数, 表示航班是否被个人排班计划覆盖; 为0-1参数, 表示假期是否被个人排班计划覆盖; 表示航班是否被航班环覆盖; 为0-1决策变量, 表示机组人员是否选择个人排班计划为决策变量, 表示航班环的机组人员数量缺口。本文采用如下集合划分模型表示人员指派问题:

 

 

 

其中, 机组成员选择个人排班计划的成本由排班计划中航班环的总成本以及机组人员得到其偏好的航班和假期的奖励,可表示为:

在上述模型中, 每一名机组成员可选择的个人排班计划都对应一个决策变量, 每一个航班环都对应一个集合划分约束。目标函数(4-1)为最小化机组排班计划的总成本, 实际上就是尽量满足机组人员的航班偏好和假期需求, 最大化其工作满意度。约束(4-2)为集合划分约束, 确保了组环方案中各航班环均被个人排班计划覆盖一次。约束(4-3)确保了机组排班计划满足机组人员航班偏好的数量达到最低要求。约束(4-4)确保了机组排班计划满足机组人员假期需求的数量达到最低要求。约束(4-5)确保了每一名机组人员都只能选择至多一个个人排班计划。约束(4-6)和约束(4-7)确定了决策变量的取值范围。
4 结论和展望
将机组排班问题分解为机组组环问题和人员指派问题能够有效降低问题规模和求解难度, 本文分别对机组组环问题和人员指派问题进行了详细的阐述并提出了相应的建模方法。值得注意的是, 尽管采用两阶段法求解机组排班问题可以有效降低求解难度, 提高求解效率, 但存在一个潜在的缺陷, 即机组组环问题和人员指派问题的目标并不完全一致, 前者往往只考虑航班环的成本, 而后者更多的关注机组人员的偏好和需求以及任务分配的公平性, 这就可能导致最终制定出全局次优或不可行的机组排班计划。因此, 未来需要考虑如何弥补或消除这一缺陷, 例如在解决机组组环问题时考虑人员指派问题的一些指标(可参考Quesnel等人于2020年的研究[5])或者将两个问题集成起来并采用适当的方法解决(可参考Zeighami和Soumis于2019年的研究[6])等。
参考文献
[1]孙宏,李锋,黎青松.民用航空航班直接运行成本测算分析[J].交通运输工程与信息学报,2007(1):1-5.
[2]于新才.中美航空公司经济效益结比较研究[J].民航学报,2020,4(02):1-4.
[3]Barnhart C, Cohn A, Johnson E, Klabjan D, Nemhauser G, Vance P. Airline crew scheduling[C]. Handbook of Transportation Science, International Series in Operations Research and Management Science. US: Springer,2004:517–560.
[4]Gopalakrishnan B, Johnson E. Airline crew scheduling: State-of-the-art[J].Annals of Operations Research, 2005,140(1): 305-337.
[5]Quesnel F, Desaulniers G, Soumis F. Improving air crew rostering by considering crew preferences in the crew pairing problem[J]. Transportation Science, 2020,54(1):97-114.
[6]Zeighami V, Soumis F. Combining Benders decomposition and column generation for integrated crew pairing and personalized crew assignment problems[J].Transportation Sci,2019,53(5):1479-1499.

期刊巡展

合作流程 | 定制论文 | 论文发表 | 联系我们 | 关于我们 | 付款方式 | 隐私保护
百姓论文网-首页-唯一官方网站,联系电话:029-84193340, E-mail:baixinglunwen@163.com
Copyright © 2005 - 2022 EOcom. All Rights Reserved.百姓论文网-首页-唯一官方网站.职称论文发表,论文发表价格,职称论文发表价格 版权所有  陕ICP备11011549号-1
在线客服