研究基地人员分布不均衡的机组任务半环生成问题

Crew partial pairing problem under heterogeneous distribution of resources among bases

国内很多航空公司多基地间存在机组人员和航班任务数量不匹配的情况,导致各基地生成的任务环在机组派遣阶段难以被很好地执行,因此需在任务环生成阶段生成适量的可满足机组人员跨基地支援的任务半环,而传统的生成完整任务环的方案难以适用于该情况。在该问题中,通过顺序方法找到全局最优解是不可能的,因为在配对问题中做出的决策减少了机组分配问题的决策域。对此,创新性地提出了任务半环生成方案,并且创建基于时空网络的集合划分模型,分析任务半环生成总量约束的子问题目标函数项对列生成求解框架的影响,提出可以有效消除该影响的分治策略,采用实际数据验证算法可行性和有效性。与传统的方法相比,可显著节省成本并更好地满足机组人员分配不平衡问题。

The mismatch between the number of crew and flight duties is widely occurred in airlines with multiple bases, which results in bad assignment at crew rostering stage. This problem can be fixed by generating partial pairing across bases, which is not considered in the traditional crew pairing generation method. Finding a globally optimal solution via the sequential approach may be impossible because the decision domain of the crew assignment problem was reduced by decisions made in the pairing problem. This paper proposes a new study of a crew pairing problem with partial pairing. A set partitioning model with partial pairing constraint based on segment time-space network firstly developed. To eliminate the effect on objective in subproblem caused by the additional constraint, a divide and conquer strategy was put forward. Finally, an empirical study was presented to validate the efficiency of the proposed algorithm. Compared with the traditional method, the method in this paper can significantly save costs and better meet the problem of crew mismatch.