基于时域分解技术的机组排班最优决策方法

An optimal decision method for crew scheduling based on time-domain decomposition

机组排班决策是根据航空公司的月度航班计划和飞机运营计划,制定机组人员一个月内的航班执勤计划,即机组排班计划.机组排班决策作为航空运营管理中的重要一环,是航空公司降低运营成本,提高运营效率和服务质量的关键.然而,由于机组排班问题的规模往往很大,同时还需要考虑航空业相关法规条例的严格限制,因此很难做出最优的决策.提出了一种基于时域分解技术的最优决策方法,该方法采用时域分解技术和分支定价算法求解机组排班问题,能够以较低的计算成本得到最优的机组排班计划.在北美一家大型航空公司的实际数据集上测试和验证了该方法的可行性和有效性.

Based on the airline’s monthly flight plan and aircraft operation plan,the crew scheduling decision formulates the monthly flight duty plan for the crew,namely,crew scheduling plan.As an important part of airline operation management,the crew scheduling decision is the key for airlines to reduce operation costs,improve operating efficiency and service quality.However,due to the scale of the crew scheduling problem is often large and restricted by stringent regulatory of the aviation industry,it is difficult to make an optimal decision.This paper proposed an optimal decision method based on the time-domain decomposition that uses the time-domain decomposition technology and branch-and-price algorithm to solve the crew scheduling problem,which can obtain the optimal crew scheduling plan with low computational costs.In this paper,the feasibility and effectiveness of the proposed method were tested and validated on a real dataset from a large North American airline.