Integrated Operations Planning Models and Algorithms for the Airline Industry

这笔赠款提供资金用于开发数学模型，这些模型将用于整合机队分配，飞机路线和机组人员调度等航空公司运营规划问题，并设计和测试有效的解决方法。为此，将研究三种模型。第一个将研究航班调度和机队分配的整合，以同时确定有多少乘客接受每条路径使用基于行程的需求，并考虑航空公司夺回，灵活的飞行时间和时间表的平衡。第二个模型将采用一种替代性的飞行网络建模范式，以取代传统的时空网络，从而在考虑直达航班的同时，进一步整合飞机航线的设计。第三个模型将考虑机队分配、飞机航线和机组调度过程的更全面的整合。将开发精确和启发式分解解决方案，其中包括多面体分析，以产生有效的不等式，稳定的分支和价格和切割，拉格朗日松弛，模型增强使用的重新公式化线性化技术，以科普大规模的模型配方。模型和解决方案的程序将通过计算实验进行测试和验证的真实数据提供的联合航空公司和突尼斯航空公司。如果成功，这项研究的结果将产生积极的影响，航空公司的盈利能力和服务质量。这个项目的主要目标是展示的好处，同时考虑时间表规划，机队分配和路由，机组人员调度。通过认识到这些运营规划问题之间的相互作用，并将它们整合到统一的模型中，航空公司将能够做出比传统的顺序流程更有利可图的决策，这些流程分别检查这些相互关联的问题。为解决大规模模型而开发的解决方法也将有助于解决其他相关调度和离散优化问题的概念和方法。

This grant provides funding for the development of mathematical models that will serve to integrate the airline operational planning problems of fleet assignment, aircraft routing, and crew scheduling, and to design and test effective solution methodologies. Three models will be investigated for this purpose. The first will study the integration of flight scheduling and fleet assignment to simultaneously determine how many passengers to accept on each path using itinerary-based demands and considering airline recapture, flexible flight times, and schedule balance. The second model will adopt an alternative flight network modeling paradigm in lieu of the traditional time-space network to additionally integrate the design of aircraft routes, while taking heed of through-flights. The third model will consider a more comprehensive integration of the fleet assignment, aircraft routing, and crew scheduling processes. Exact and heuristic decomposition solution approaches will be developed, which will include polyhedral analyses for generating valid inequalities, stabilized branch-and-price-and-cut, Lagrangian relaxation, and model enhancements using the Reformulation-Linearization Technique in order to cope with the large-scale model formulations. The models and solutions procedures will be tested and validated through computational experiments on real-data provided by United Airlines and Tunis Air.If successful, the results of this research will positively impact the profitability and service quality of airline companies. The principal goal of this project is to demonstrate the benefits of simultaneous consideration of schedule planning, aircraft fleet assignment and routing, and crew scheduling. By recognizing the interplay among these operational planning problems and integrating them within consolidated models, airlines will be able to make more profitable decisions over the traditional sequential process that examines these interrelated problems separately. The solution methodologies developed for addressing the large-scale models will also contribute toward the repertoire of concepts and approaches for solving other related scheduling and discrete optimization problems.