Robust Airline Crew Pairing: Move-up Crews
Robust Airline Crew Pairing: Move-up Crews
复制标题
强大的航空公司机组人员配对：升级机组人员
作者：
Sergey Shebalov;D. Klabjan
由于作业不规律，月尾的船员成本通常比计划中预计的船员成本高得多。我们假设飞逝的和飞机的路线决定已经做出。我们提出了一个模型和解决方案方法，可以在计划中产生可靠的机组时间表。除了最小化船员成本的目标之外，我们还引入了最大化提升船员数量的目标，即在操作中可能被交换的船员。为了解决由此产生的大规模整数程序，我们使用延迟列生成和拉格朗日松弛相结合的方法。利用拉格朗日松弛和延迟列生成中使用的与拉格朗日乘子相对应的受限主问题的“对偶”来求解受限主问题。我们报告了计算实验，证明了使用鲁棒乘员计划代替传统计划的好处。我们通过产生随机中断来评估不同的机组时间表，然后运行机组恢复模块。我们比较了直接船员成本和间接成本的解决方案，如未覆盖的腿、保留的船员和死头。主要结论是，鲁棒性可以降低操作人员的成本；然而，在规划时，需要在膨胀的直接机组成本和鲁棒性之间权衡取舍。
Due to irregular operations, the crew cost at the end of a month is typically substantially higher than the crew cost projected in planning. We assume that the fleeting and the aircraft routing decisions have already been made. We present a model and a solution methodology that produces robust crew schedules in planning. Besides the objective of minimizing the crew cost, we introduce the objective of maximizing the number of move-up crews, i.e., the crews that can potentially be swapped in operations. To solve the resulting large-scale integer program, we use a combination of delayed column generation and Lagrangian relaxation. The restricted master problem is solved by means of Lagrangian relaxation and the “duals” of the restricted master problem, which are used in delayed column generation, and correspond to the Lagrangian multipliers. We report computational experiments that demonstrate the benefits of using the robust crew schedule instead of the traditional one. We evaluate various crew schedules by generating random disruptions and then running a crew recovery module. We compare solutions with respect to the direct crew cost and indirect costs such as uncovered legs, reserved crews, and deadheading. The main conclusion is that robustness leads to reduced operational crew cost; however, in planning the trade-off between the inflated direct crew cost and robustness needs to be exploited judicially.