航空公司飞行机组排班问题研究

摘要

The flight crew scheduling is an important part of the entire airline flight production plan ,and al‐so the key to improving the operational efficiency of airlines .A graph coloring model of flight crew schedu‐ling is set up by analyzing the flight crew assignments and converting the assignment of flight crew tasks into graph coloring ,and the vertex coloring algorithm is designed to solve the model ,then this graph‐theo‐retic algorithm is applied to specific instances of airline flight crew scheduling .%飞行机组排班是整个航空公司制定航班生产计划中的一个重要环节，是提高航空公司运营效率的关键。通过对飞行机组排班问题中飞行机组任务分配的分析，把飞行机组人员任务的分配转化为图着色，建立飞行机组排班问题的图着色模型，设计顶点着色算法来求解模型，最后将此图论算法模型应用到具体航空公司飞行机组排班的实例中。