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

Research on unit optimization scheduling problem based on improved heuristic algorithm

机组排班问题是航空公司运营规划中较为复杂的问题之一。基于极其复杂的航空运营组织大环境,航空公司为提高运输效率、降低运营成本也在不停的寻求合理的分配方案。航空公司机组人员大多数工作时间不够统一,在一定程度上比较分散,如果没有妥善进行排班工作可能会导致浪费人力资源而增加成本,或者影响工作人员的休息时间。本文主要考虑航班运营过程中的航线规划、人员分配和运营成本等因素,并提出了一种基于改进的贪婪算法、局部搜索法和模拟退火算法结合使用的求解方法,创新性地提出了机组人员“组合”与“分解”的编码过程。求得结果后,对最终解中的机组人员分配情况进行了实例分析测试。结果说明,改良后的启发式算法可在机组人员指派问题中得到更高质量的解,以达到对人力充分分配和降低成本的目的。

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.