基于滚动时域算法框架下的机组配对扩展问题研究

A Rolling Horizon Approach Scheme for an Extended Airline Crew Pairing Problem

文中以最小化机组配对成本为目标,在经典模型基础上,提出考虑航班延误及储备员工分配的机组配对数学模型,使得航空公司可以在较低运营成本下生成具有稳定性的机组配对解。为降低运行时间,采用将列生成算法嵌入到滚动时域算法框架中对模型求解。基于Kasirzadeh等人2017年提供的开源数据集,分别获取考虑航班延误以及储备员工的机组配对数学模型和经典机组配对数学模型所产生的结果。实验结果表明,文中所提出的模型生成解的传播延误时间明显低于经典模型所产生的。基于考虑航班延误和储备员工的机组配对模型所产生的总成本也低于经典模型所生成的。

With the objective of optimizing the airline crew schedule at the lower operating cost,this paper proposes a new mathematical programming model that considers flight delays and reserved crew based on an extension of a classical airline crew pairing model.To reduce computational time,this study develops a column generation algorithm which is embedded in a rolling horizon framework.Based on the benchmark data provided by Kasirzadeh et al.(2017),computational experiments are conducted to validate that the propagated delay time obtained by the proposed model is much lower than the classical crew pairing model.Moreover,the total operating cost achieved by our extended crew pairing model that considers flight delays and the assignment of the reserved crew is also lower than that generated by the classical model.