基于改进启发式算法的机组优化排班问题研究  

Research on unit optimization scheduling problem based on improved heuristic algorithm

作　　者：宋启航 张丽[1] SONG Qihang;ZHANG Li(School of Air Transport,Shanghai University of Engineering Science,Shanghai 201600,China)

机构地区：[1]上海工程技术大学航空运输学院,上海201600

出　　处：《智能计算机与应用》2024年第2期55-61,共7页Intelligent Computer and Applications

摘　　要：机组排班问题是航空公司运营规划中较为复杂的问题之一。基于极其复杂的航空运营组织大环境,航空公司为提高运输效率、降低运营成本也在不停的寻求合理的分配方案。航空公司机组人员大多数工作时间不够统一,在一定程度上比较分散,如果没有妥善进行排班工作可能会导致浪费人力资源而增加成本,或者影响工作人员的休息时间。本文主要考虑航班运营过程中的航线规划、人员分配和运营成本等因素,并提出了一种基于改进的贪婪算法、局部搜索法和模拟退火算法结合使用的求解方法,创新性地提出了机组人员“组合”与“分解”的编码过程。求得结果后,对最终解中的机组人员分配情况进行了实例分析测试。结果说明,改良后的启发式算法可在机组人员指派问题中得到更高质量的解,以达到对人力充分分配和降低成本的目的。The crew scheduling problem is one of the more complex issues in the operational planning of airlines.In the context of the exceedingly complex organizational environment of aviation operations,airlines continuously seek reasonable allocation schemes to improve transport efficiency and reduce operational costs.The majority of airline crew members have rather inconsistent working hours,which are quite dispersed to some extent.Improper scheduling may lead to the wastage of human resources and increased costs,or it could affect the crew's rest time.This paper primarily considers factors such as flight operation routing,personnel distribution,and operational costs,and proposes a solution method that combines an improved greedy algorithm,local search,and simulated annealing.It innovatively proposes the coding process of"combination"and"decomposition"for crew members.After obtaining the results,an empirical analysis of the crew allocation in the final solution was conducted.The trial results indicate that the improved heuristic algorithm can yield higher quality solutions to the crew assignment problem,achieving the objectives of full human resource allocation and cost reduction.

关 键 词：混合整数规划 贪婪算法 模拟退火算法 局部搜索算法 机组排班 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] V355[自动化与计算机技术—计算机科学与技术]