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

本文针对Hub-spoke结构航空公司在制订航班计划时机型指派问题，根据航空公司历史数据导出的旅客需求概率分布以及航班成本，设计了一种基于航班成本优化模型的表上作业法，提出了一种便于航班计划专员手工计算和调整机型的启发性算法，解决了航空公司机型指派0-1规划问题。该算法集成了匈牙利算法和回溯算法的思想，从航班成本最小值出发，根据航班优化的约束条件，按照深度优先搜索可行解，在不满足航班约束的节点处进行回溯，直到找到满足航班边界约束条件的航班成本最小值，得到最佳的机型指派，并给出了理论证明。通过案例对比验证该启发性算法有效性，通过表上作业法手工计算发现10架B737和5架B757方案总成本为409860美元，是所有方案中最低的，证明机型合理搭配可以使得公司运行效果更好；与传统的运筹学算法相比该算法构造直接和优化机理自然，简单实用，便于理解和掌握，便于大型航空公司计算机应用或分公司进行航班计划手工制订和调整。