约束编程与线性规划混合技术在机组排班中的应用

摘要

航空公司机组排班问题是大规模优化问题,通常利用列生成求解。子问题是典型的约束最短路问题。但是随着航空公司规模增大,使得问题结构很难完全的表达,限制了列生成的应用。本文利用约束编程作为子问题算法,将子问题建模为约束满足问题,表达性更强。最后利用航空公司实际数据,解决日机组排班问题,论证混合技术的优越性。