Abstract:

Aimed at an integrated problem of flight timetabling and fleet assignment under fluctuated multi-segment service demands in commercial airline service market, considering airline service attractiveness to consumers, a mixed integer linear programming model is constructed by replicating flights with multiple optional take-off time periods and using a time-space network. By predefining a discrete distribution for fluctuating demands as input data, flight timetabling and fleet assignment are taken as a whole and solved by CPLEX. Then a diving heuristic algorithm is designed and six examples are generated with 10 to 20 airports respectively for simulation test. The computational results show that when an example scale exceeds 12 airports, calculation speed and target value for the algorithm are better than CPLEX. Finally, sensitivity analysis is applied to verify the robustness of the algorithm, which indicates that the algorithm can help airlines find faster and better real-time decision-making solutions than CPLEX.

Key words:

multi-segment service demand, flight timetabling, fleet assignment, diving heuristics

摘要：

针对航班时刻表安排与机型分配集成问题，考虑多航段服务市场需求波动情形，引入航空服务对消费者的吸引力，复制多个可选起飞时段的航班，借助时空网络理论，构建了混合整数线性规划模型。将航空服务市场需求波动的多种情形按照离散分布作为输入数据，将航班时刻表安排与机型分配问题集成，使用优化求解器CPLEX进行求解。设计一种潜水启发式算法，生成包含10~20个机场的6个算例进行仿真测试，结果表明：当算例的规模超过12个机场时，该算法在速度和目标值上都优于CPLEX。最后，灵敏度分析验证了该算法的鲁棒性，说明该算法可以帮助航空公司找到比CPLEX更快更优的即时决策解决方案。

关键词:

多航段服务需求, 航班时刻表安排, 机型分配, 潜水启发法