一种基于Hub-Spoke结构航空公司机型指派的实用启发性算法  

Based on Hub-Spoke Network a Practice Heuristic Algorithm Applied to Airline Fleet Assignment

作　　者：吴国华 Wu Guohua(Department of Strategy&Development,Air China,Beijing 101312,China)

机构地区：[1]中国国际航空股份有限公司规划发展部,北京101312

出　　处：《中国管理科学》2024年第1期158-167,共10页Chinese Journal of Management Science

基　　金：国家自然科学基金民航联合重点项目(U2233214)。

摘　　要：本文针对Hub-spoke结构航空公司在制订航班计划时机型指派问题,根据航空公司历史数据导出的旅客需求概率分布以及航班成本,设计了一种基于航班成本优化模型的表上作业法,提出了一种便于航班计划专员手工计算和调整机型的启发性算法,解决了航空公司机型指派0-1规划问题。该算法集成了匈牙利算法和回溯算法的思想,从航班成本最小值出发,根据航班优化的约束条件,按照深度优先搜索可行解,在不满足航班约束的节点处进行回溯,直到找到满足航班边界约束条件的航班成本最小值,得到最佳的机型指派,并给出了理论证明。通过案例对比验证该启发性算法有效性,通过表上作业法手工计算发现10架B737和5架B757方案总成本为409860美元,是所有方案中最低的,证明机型合理搭配可以使得公司运行效果更好;与传统的运筹学算法相比该算法构造直接和优化机理自然,简单实用,便于理解和掌握,便于大型航空公司计算机应用或分公司进行航班计划手工制订和调整。The fleet assignment problem of Hub-spoke network airlines in making flight schedules is addressed.According to the demand distribution of passengers and resulting in the flight costs from the airline's historical data,an optimization algorithm by tabular operation method based on the flight cost model is designed,and an heuristic algorithm is proposed for flight planning specialist to facilitate manual calculation and to adjust aircraft types,which solves the airline fleet assignment 0-1 integer programming problem,The algorithm integrates the ideas of Hungarian algorithm and backtracking algorithm.Starting from the minimum cost of fl ight optimiza⁃tion,the algorithm searches the optimal value by the depth-first-search method subject to the optimization constraints,and backtracks in the nodes when the aircraft constraints are not met,finds the minimum flight cost that meets the aircraft side constraints,and obtains the optimal fleet assignment and hence gives a theoretical proof.The effectiveness of the heuristic algorithm is obtained through case study.The total cost of ten B737 and five B757 scenarios is found to be the lowest among all scenarios by manual calculation using the tabular method,reaching$409,860,which proves that a reasonable mix of aircraft types can make the company oper⁃ate better.Compared with the traditional operations research algorithm this algorithm is straightforward in construction and natural in optimization mechanism,which is simple and practical,also easy to understand and master,especially for small airlines or branches to manually formulate and adjust flight schedules.

关 键 词：0-1整数规划 航空公司机型指派 启发性算法 表上作业法 回溯法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]