A Global Approach to Crew-Pairing Optimization
A Global Approach to Crew-Pairing Optimization
复制标题
船员配对优化的全球方法
DOI：
10.1147/sj.311.0071
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Ellis L. Johnson
中科院分区：
文献类型：
--
作者：
R. Anbil;Rajan Tanga;Ellis L. Johnson
本文解决的问题是航空公司飞行计划中的船员配对优化：查找合法的职责之旅（配对），并以最少的成本覆盖每条飞行腿。配对的法律规则和成本由复杂的联邦航空机构和合同要求确定。此外，航空公司使用的集线器系统使问题更加困难，该系统将配对可以连接飞行腿的可能方式乘以。美国航空公司的最先进的船员配对旅行系统采用子问题优化，并且对于其他机组人员安排系统也是如此，即使存在更好的解决方案，也可能无法改善解决方案。我们报告了在IBM和美国航空公司决策技术联合研究中开发的方法，以结合旅行，通过采用全球方法来利用IBM优化子例程图书馆，以改善机组人员的解决方案。由此产生的改善是降低了5％至11％的超额船员成本。估计总储蓄为每年五百万美元。
The problem addressed in this paper is crew-pairing optimization in airline flight planning: finding tours of duty (pairings) that are legal and cover every flight leg at the least cost. The legal rules and cost of a pairing are determined by complex Federal Aviation Agency and contractual requirements. In addition, the problem is made more difficult by the hub-and-spoke system used by airlines that multiplies the possible ways a pairing can link flight legs. The state-of-the-art crew-pairing TRIP system of American Airlines uses subproblem optimization and, as is true for other crew-scheduling systems, may not be able to improve a solution even though a better one exists. We report on the methodology developed during a joint study by IBM and American Airlines Decision Technologies to use the IBM Optimization Subroutine Library in conjunction with TRIP to improve on crew-pairing solutions by taking a global approach. The resulting improvements have been a reduction of 5 to 11 percent in excess crew cost. Estimated total savings are five million dollars per year.