• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Affectation des types d'avions aux vols avec contraintes de maintenance.
【24h】

Affectation des types d'avions aux vols avec contraintes de maintenance.

机译：将飞机类型分配给具有维护约束的航班。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The interaction between the fleet assignment problem and the aircraft routing problem is studied in this thesis. Given a weekly schedule, the fleet assignment problem assigns an aircraft type - a fleet - to each flight. This assignment must not exceed the number of aircraft available, must respect the flow conservation constraints and aims to maximize the anticipated profits.;During tactical planning, realized six months to one year before the day of operations, the aircraft routing problem is solved to evaluate the feasibility of the fleet assignment. In addition, the aircraft routes are used to solve the crew scheduling problem. The weekly aircraft routing problem is, in general, considered as a cyclic problem in order to be able to reproduce the solution obtained each week of the considered season. For some aircraft type, it is difficult to build feasible aircraft routes because of the conflicting obligations to cover every flight assigned to the aircraft type and to visit a maintenance station at a prescribed frequency.;The work of this thesis aims at integrating maintenance planning in the fleet assignment problem. To achieve this goal, two parts are presented. The first part proposes a multicommodity model for solving the aircraft routing problem. This model is solved by the commercial solver Cplex and builds aircraft routes that respect the maintenance constraints. When it is impossible to do all the required maintenance checks, the model identifies aircraft routes that cover all flights and provides the number of delays on the maintenances.;The second part of this work is devoted to the integration of maintenance constraints in models for the fleet assignment problem. First, using a multicommodity model generally used for this problem, we propose the addition of maintenance constraints that provide a better maintenance management. The additional constraints are of two types. The first type of constraints are generated a priori. The addition of these constraints helps to make a better maintenance planning but they are not sufficient to avoid delays. The second type of constraints is generated as needed in a cutting plane method. The separation algorithm for these constraints uses a column generation algorithm applied to a problem separable by aircraft type.;Once the fleet assignment is known, the aircraft routing problem is solved for each aircraft type. An aircraft route is a sequence of flight legs, connections and waiting periods. Moreover, an aircraft route must contain a maintenance check at a prescribed frequency. In this thesis, the aircraft routing problem is studied on a weekly horizon. Typically, only the type A maintenances that must be performed, in general, each three or four days are considered when solving the aircraft routing problem. Each aircraft must visit a maintenance station at most at every three or four days and stay at the station enough time to perform the maintenance works.;In the literature, a set partitioning model is generally used for the combined problem of the fleet assignment and the aircraft routing problem. Presented by BARNHART ET AL. (1998a), this model is solved using a column generation algorithm included in a branch-and-bound method. This methodology has recently been accelerated by a dynamic constraint aggregation procedure in a different context. Therefore, we tried to apply this procedure for the combined problem. The results are not as good as we expected; the computational time has been reduced of 25% to 50% but the quality of the solutions has also been reduced (less than 0.1%). We provide some reasons that can explain these results.;Finally, recent works on the business process leading to the definition of the aircraft routing problem have brought us to think more about this problem. Until recently, the stochastic aspect of this problem was ignored even if it is obvious that the probability that a planned route will be performed as planned greatly reduces with the length of the route. Thus, some airlines have reviewed their business process in order to plan the aircraft routes differently. This is why we propose a classification of the literature according to three business processes driving the aircraft routing problem. We then compare these processes according to different aspects: solution costs, solution robustness, etc.;In summary, this thesis proposes a new model for the aircraft routing problem, two new solution approaches to solve the combined fleet assignment and the aircraft routing problem and, finally, a classification of the literature on the aircraft routing problem.
机译：本文研究了机队分配问题与飞机路径问题之间的相互作用。给定每周时间表，机队分配问题将为每个航班分配飞机类型-机队。此任务不得超过可用飞机的数量，必须遵守流量守恒约束，并旨在最大程度地提高预期收益。；在战术规划期间，在运营日前六个月至一年实现，解决了飞机路线问题以进行评估机队分配的可行性。另外，飞机路线用于解决机组调度问题。通常，每周飞机路线问题被认为是一个周期性问题，以便能够重现所考虑季节的每周中获得的解。对于某些型号的飞机，由于要承担分配给该型号飞机的每一次飞行并按规定的频率访问维修站的义务相互冲突，因此很难建立可行的飞机路线。机队分配问题。为了实现这个目标，提出了两个部分。第一部分提出了一种解决飞机路径问题的多商品模型。该模型由商用解算器Cplex解决，并建立了遵循维护约束的飞机路线。当不可能进行所有必需的维护检查时，该模型会确定涵盖所有航班的飞机航线，并提供维护延误的次数。该工作的第二部分致力于将维护约束整合到模型中车队分配问题。首先，使用通常用于此问题的多商品模型，我们建议添加维护约束，以提供更好的维护管理。附加约束有两种类型。第一种约束类型是先验生成的。这些约束的添加有助于制定更好的维护计划，但不足以避免延迟。在切割平面方法中根据需要生成第二种约束。针对这些约束的分离算法使用列生成算法，该列生成算法应用于按飞机类型可分离的问题。一旦机队分配已知，就可以针对每种飞机类型解决飞机路线问题。飞机路线是一系列航程，连接和等待时间的序列。此外，飞机路线必须包含规定频率的维护检查。本文以每周的时间为研究对象，研究了飞机路径问题。通常，在解决飞机路线问题时，仅考虑必须每三或四天执行一次的A型维护。每架飞机最多每三天或四天必须到一个维修站，并留在该站足够的时间来执行维修工作。”在文献中，通常将集合划分模型用于机队分配和飞行任务的组合问题。飞机路线问题。由BARNHART ET AL提出。 （1998a），使用分支定界方法中包含的列生成算法求解该模型。最近，通过在不同上下文中使用动态约束聚合过程来加速了该方法。因此，我们尝试将此过程用于合并的问题。结果不如我们预期的好；计算时间减少了25％至50％，但解决方案的质量也有所降低（小于0.1％）。我们提供了可以解释这些结果的一些原因。最后，最近关于业务流程的工作导致飞机路径问题的定义使我们对这个问题有了更多的思考。直到最近，这个问题的随机性都被忽略了，即使很明显，计划的路线将按计划执行的可能性会随着路线的长度而大大降低。因此，一些航空公司已经审查了其业务流程，以便以不同的方式计划飞机路线。这就是为什么我们根据驱动飞机航线问题的三个业务流程提出文献分类的原因。然后，我们根据解决方案成本，解决方案的鲁棒性等不同方面对这些过程进行比较；总而言之，本文提出了一种针对飞机路径问题的新模型，提出了两种解决组合机队分配和飞机路径问题的新解决方案，最后，对飞机路径问题进行了文献分类。

著录项

  • 作者

    Lacasse-Guay, Eve.;

  • 作者单位

    Ecole Polytechnique, Montreal (Canada).;

  • 授予单位 Ecole Polytechnique, Montreal (Canada).;
  • 学科 Engineering Industrial.;Operations Research.
  • 学位 Ph.D.
  • 年度 2009
  • 页码 214 p.
  • 总页数 214
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

  • 入库时间 2022-08-17 11:38:18

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号