利用回旋时空网络求解飞机维护路径问题的新方法

In the last decade, airlines' profit margin has been continuously pressured by their growing exposure to a high-cost low-fare environment. The increasing cost in capital, labor, and fuel, and the elevated competition from budget carriers have tied the airlines' profitability to the current economic. How to efficiently utilize their expensive resources and generate the maximum profit is always a grand challenge in the airline planning operations. This challenge has motivated numerous research studies from both industry and academia. The majority of those studies, however, are focused largely on "daily schedule" problems, in which the schedule and the profitability of the flights are considered to be the same everyday in the week. For the U.S. domestic airlines, the schedules are normally the same during the weekdays and slightly different during the weekends due to the demand variation. For international airlines and airlines in China, on the other hand, the "daily schedule" assumption is no longer valid. For example, Lufthansa airlines only offer three flights per week from Frankfurt to Anchorage. Apparently, planning problems based on the "weekly schedule" are much more realistic and of interest to many international airlines and airlines in China. However, a very few studies in the airline schedule planning literature deal with the "weekly schedule" problems. One reason is due to the fact that the weekly problems are much harder, and their problem complexities increase drastically with the number of flights to be scheduled. Specifically, the models and solution methodologies for the daily schedule problems can be used to solve the weekly problems by extending the planning duration from a single day to an entire week; however, the models and computational complexities will increase exponentially, and cannot obtain the optimal solutions for large weekly problems in a reasonable time. In this project, we focus our research on the weekly aircraft maintenance routing problem (WAMRP). The aircraft maintenance routing problem (AMRP) is to determine the flight routes for every aircraft such that the maintenance requirements are satisfied. The sizes of the traditional models for the AMRP usually increase exponentially with the number of flights in the schedule, and these models are commonly solved iteratively using column generation approaches or row generation approaches. In this project, we propose a novel network-based model for the WAMRP. The advantage of the proposed model is two-fold. First, the size of the proposed mathematical model only increases linearly with the number of flights to be scheduled. Therefore, this compact and scalable model can be solved directly by most commercial mathematical programming packages. Second, we notice from our computational experience that the proposed time-space network flow based model provides very tight linear programming bounds, which can help to find good integer solutions efficiently.

飞机维护路径问题是唯一同时涉及利润和飞行安全的重要航空规划问题。目前国外以美国为主的飞机维护路径问题研究普遍假设"以天为单位"，即假定航班计划和盈利能力每天相同。此假设不适用于中国"以周为单位"的航班设计，故考虑以周为单位的飞机维护路径问题更加全面重要。然而，国内外以周为单位的研究在模型与算法上未取得令学术界和航空业界满意的结果。相比以天为单位的问题，以周为单位问题的解空间和算法复杂度都呈指数增长，导致求解非常困难。本项目拟提出一种基于回旋时空网络的新方法来解决以周为单位的飞机维护路径问题。初步研究经验表明，提出的模型有两个优点：1）模型规模随着航班数量的上升呈线性增长，对大规模实际问题无需分解算法，易于直接求解；2）模型有紧凑的线性规划松弛解，利于快速找到最优或近似最优解。在此基础上，本项目拟扩展提出的方法用于解决周机型指派与周飞机维护路径的整合问题，并设计高效优化算法求解整合问题。

飞机维护路径问题（Aircraft Maintenance Routing Problem）是航空运营中的重要问题，其目标是决定飞机的具体航班飞行路线及其维护计划。根据以往国内外调查分析，飞机维护的欠缺与疏忽是事故发生的主要原因之一。好的飞机维护路径计划能为飞机在飞行路径中安排充足的维护机会，以确保飞行安全。另一方面，飞机维护路径与航班延误密切相关。如果飞行航班路线设计合理，则航班的间隙可以有效吸收延误，降低延误在航班间的传播。由此可见，是唯一一个同时涉及安全、利润和航班延误的航空规划问题，具有重要的社会和经济价值。..目前，以美国为主导的航空运营管理，特别是飞机维护路径问题的研究中，一个基本假设是“以天为单位”，即假定航班计划每天相同，类似我国高铁。然而，我国航班一周中每天有较大差异，例如：某些小城市并非每天都有航班。欧洲航班与中国类似，“以天为单位”的假设也不适用。 “以周为单位”的航空规划可执行性更强，能更准确的反映飞机的飞行路线，对国内和国际航空业都具有重要意义。..本课题提出了一个“以周为单位”的回旋时空网络用于构建混合整数规划模型求解周飞机维护路径问题，此回旋时空网络以维护弧连接7个以天为单位的子时空网络。此模型延续了回旋时空网络的特性：即模型变量数量随航班数的增加呈线性增加，且此模型具有紧凑的线性松弛解，可在15分钟内对超过300架飞机、周航班数超过10000的大规模算例得到最优解。值得一提的是，此大规模算例与世界最大的机队规模相当（美国西南航空公司波音737-700机队），适用于我国所有的航空公司机队。“以周为单位”的回旋时空网络也对其它周期性的网络路由问题有一定借鉴意义。..本课题的相关研究结果共发表在6篇SCI论文上，其中3篇高水平论文分别发表在Transportation Science （2篇）和Transportation Research Part B上，项目负责人均为第一作者。其中发表在 Transportation Science 2013 和 Transportation Research Part B 2015 年的文章被美国、中国、新加坡、香港的多位学者引用并正面评价，显示本项目的工作具有一定的学术价值和科学意义。

内容获取失败，请点击重试