Column Generation for Airline Problems

该项目旨在为航空公司面临的两个重要的资源分配问题：机组人员规划和机队分配找到近于最佳的解决方案的计算实用方法。机组人员计划涉及找到机组往返旅行的最低成本集，每个机组往返旅行的起点和终点都是机组基地，以确保必须飞行的每段飞行只有一名机组人员。机队分配是找出几种不同类型的飞机对必须飞行的航段的最小成本分配。要解决的主要技术挑战将是找到模型的整数解，对于这些模型，线性规划必须通过列生成来求解。解决这两个问题的成功也很容易推广到其他行业的类似模式。

This project aims to discover computationally practical methods for finding near-optimal solutions to two of the important resource allocation problems faced by an airline: crew planning and fleet assignment. Crew planning involves finding the minimum cost set of crew round-trips, each beginning and ending at a crew base, that insures exactly one crew on each flight leg that must be flown. Fleet assignment invilves finding the minimum cost assignment of the available aircraft, which are of several different types, to the flight legs that must be flown. The main technical challenge to be tackled will be that of finding integer solutions to models for which the linear program must be solved by column generation. Success with these two problems would also be easily transferable to similar models in other industries.