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.