基于多枢纽的时间带离散近似不正常航班恢复模型与算法研究

The time-band approximation model(TABM) on irregular operations aircraft routing recovery problem is based on the time-space network when the time horizon is partitioned into time bands of fixed length; delay costs can be approximately obtained by choosing one of airline copy arcs; then the Time-Band Approximation Model can be seen as a kind of integral linear programming model. But the opportunity costs of passengers delay and the superiorities of the hub-spoke airlines in China were not taken into consideration in computing recovery costs in TBAM.. The time-band approximation model based on the multi-hub-spoken airlines is developed in this research, the simplex group cycling in the hub-spoke airlines and the opportunity passengers delay costs will be considering. Subsequently, we provided the hybrid genetic algorithm by combining the branch-and-bound algorithm with the egenetic algorithm, during the process of which branches take shape by group cycling in the whole searching area, random numbers which satisfied some random distribution are used to relax the fitness function in every branch, and then we do selecting,recombining and mutting; The simulated data were constructed with different levels of disruption by the real airlines data and passengers data of the multi-hub-spoken airlines. then the simulated testing was conducted to substantiate the validity of the time-band approximation model and the rapidity and efficiency of the hybrid genetic algorithm.

时间带离散近似不正常航班恢复模型(TBAM)通过离散时间构建了时空网络，利用航班复制弧代替延误航班可能采用的执行方案，使得可以近似计算航班延误费用，从而将时间带离散近似不正常航班恢复模型归结为整数线性规划模型。但TBAM在计算恢复费用时没考虑乘客的机会延误费用，也没考虑我国多枢纽运营航空公司的优势。本研究拟考虑多枢纽运行航空公司的单纯小组循环优势，增加单纯小组循环决策元；并在不正常航班恢复费用中考虑乘客的机会延误费用，进而构建基于多枢纽的TBAM。随后针对TBAM的特点，结合分支定界算法和遗传算法的优点，在整个搜索区域上利用小组循环进行分支，每个分支内采用符合某种随机分布的随机数松弛适应度函数，然后进行选择、交叉和变异操作，构建混合遗传算法；拟利用多枢纽运营航空公司的真实航班数据和实际乘客数据，构建不同延误程度的仿真数据，进行仿真试验，验证时间带离散近似模型和混合遗传算法的有效性和快速性。

不正常航班恢复模型的资源指派模型是一般的整数规划模型，求解非常困难；而多商品流模型目标中的延误费用无法精确确定，并且可能不存在真正的可行解；时间带离散近似模型则是通过时空网络近似计算航班延误费用，从而将不正常航班恢复模型归结为一个整数规划模型。但是时间带离散近似模型在计算延误费用时没有考虑旅客因素的延误费用和飞机空中飞中时间的浮动，也未考虑我国多枢纽运营航空公司的小组环优势策略。因此，利用多枢纽运行航空公司的单纯航班小组环等优势策略和乘客差异机会延误费用，构造符合我国多枢纽的时间带离散近似不正常航班恢复模型和快速求解该模型具有非常重要的现实意义。.本研究首先研究了正常航班生产的典型流程和影响正常航班的空域、场面因素分析；其次研究了多枢纽运营航空公司正常航班的单纯航班小组环方案及多枢纽航空公司不正常航班恢复的策略；再次研究了航空公司不正常航班恢复的目标和约束，建立基于不同角度的时间带离散近似不正常航班恢复模型；随后研究了一般混合整数规划松弛优化问题的精确算法，并且试图利用精确算法和遗传算法的优点构造平衡二者优点的混合算法；最后开展了基于真实航班数据和实际旅客信息的大规模数值测试。.通过一系列的研究，本团队得到了考虑飞机飞行时间浮动的时间带离散近似不正常航班恢复模型和基于旅客信息的时间带不正常航班恢复模型，并且得到了针对基于时间点和时间带的不正常航班恢复模型的差异性对比和基于单纯小组循环的不正常航班恢复模型。并且还得到一般连续优化问题的精确算法及收敛率结果；600次数值测试结果表明了基于离散时间带近似不正常航班恢复模型的松弛问题的解为整数的现象；于是可以很快地通过解松弛问题得到基于离散时间带近似不正常航班恢复模型的解。通过基于真实航班数据的各种不正常航班恢复模型的仿真实验，表明了所构建模型的有效性，可用于借鉴指导实际航班恢复生产，具有实际参考价值。