朱 博，朱金福，吴薇薇

(南京航空航天大学 民航学院，江苏 南京 211100)



飞机路线恢复问题的两阶段随机规划方法研究

朱 博，朱金福，吴薇薇

(南京航空航天大学 民航学院，江苏 南京 211100)

针对飞机故障修复时间的不确定性，建立了飞机路线恢复的两阶段随机优化模型:第一阶段模型为飞机资源指派模型，以延误和取消成本之和最小为目标函数；第二阶段补偿模型根据飞机故障修复时间的随机情景，以航班时间重排恢复策略的期望成本最小为目标函数。针对随机模型的结构，设计随机启发式算法。算例结果表明，采用随机模型和算法可以有效地提高不正常航班恢复方案的可行性，比确定型模型节约5.8%左右的恢复成本。

航班计划运行；飞机路线恢复；两阶段随机模型；贪婪模拟算法

航空公司的航班计划是在假设其能正常实施的前提下制定的，然而实际运行中，航空运输系统会面临各种不确定因素的扰动，使得航班无法按原计划执行，大大增加了航空公司的运行成本，给旅客带来极大不便，降低了航空运输系统的运行效率。对不正常航班恢复的研究至今已有约60年的历史，其中飞机故障造成短缺情况下的飞机路线恢复问题(aircraft rerouting problem, ARP)是研究的重点之一。TEODOROVIC等建立了受扰航班网络，对飞机故障时的路线恢复问题进行了研究，设计分支定界算法求解模型，是对扰动问题的开创性研究之一[1]。YAN等在动态网络计划扰动模型的基础上，利用网络流算法、拉格朗日松弛和次梯度法进行求解[2]。……