内容发布更新时间 : 2024/5/21 23:16:43星期一 下面是文章的全部内容请认真阅读。

基于航班纯度的鲁棒性机型指派问题研究

摘 要：机型指派问题(FAP)是指根据飞机舱位能力、运营成本、潜在收益及飞机可用性，将具有不同舱位容量的飞机指派给各定期航班的问题。它是飞机、机组排班问题的基础，是整个航班计划中的最核心环节。然而，单独的机型指派最优对整个航班计划而言，可能是次优的，甚或是不可行的。本文针对国内航班计划特点，从航班的角度，定义了航班纯度概念，并建立基于航班纯度的机型指派模型。最后，以国内某航空公司干线网络为实例，表明该研究具有很大的理论意义和实践价值。 关键词： 航班计划；机型指派；航班纯度

The Research on Robust Fleet Assignment Problem Based on Flight Purity ZHU Xing-hui, ZHU Jin-fu, GAO Qiang

(College of Civil Aviation, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China) Abstract:The airline fleet assignment deals with assigning aircraft types to the scheduled flight legs based on aircraft capabilities, operational costs, potential revenues and aircraft availabilities. An airline’s fleet assignment decision is essential component of its overall scheduling process. However, an optimal solution for the fleet assignment is not necessarily optimal for the entire flight scheduling system, and can even yield an infeasible input to the subsequent processes, such as aircraft maintenance routing. This paper presents the notion of flight purity and builds fleet assignment model subjected to flight purity according to the characters of domestic airline network and flight scheduling. At last, the instance with 48 aircrafts and 1786 flight legs were testified, and the computational results reveal that theoretical value and practical significance of the research.

Key words:flight scheduling; fleet assignment; flight purity 1 引言

机型指派问题(Fleet Assignment Problem:FAP)是指根据不同机型具有不同的舱位数量，运行成本和潜在收益，指派不同的飞机类型给定期航班［1］。它是航空公司航班计划的核心内容之一，机型指派的优劣不仅影响到航空公司的成本和收益，也影响到航班之间的衔接、飞机维修路径、机组排班以及登机口、停机位指派等后续环节。

在国外，航空运输发达，机型指派研究资料很充分，但主要集中于枢纽航线网络和日航班计划。Hanif［1］等对机型指派问题的模型及求解算法进行了综述研究。机型指派基本模型有链接网络［2］(Connection Network)和时空网络［3］(Time-space Network)模型。为减少机型指派问题规模，Hane［4］对时空网络提出了节点缩减(Node Aggregation)和孤岛(Island)等预处理方法。Rexing［5］等将航班时刻综合考虑，建立了基于“时间窗”的机型指派模型。Barnhart［6］和Jonathan［7］分别从旅客行程结构和网络效应构建了机型指派模型。在国内，定量研究不多，孙宏［8,9］等对飞机排班问题进行了比较详细的研究，但其问题规模相对较小；朱星辉［10,11］等对竞争环境下航班频率和针对国内航线网络和航班计划特点的周机型指派模型进行了研究。在机型指派鲁棒性方面，国内尚未见公开发表的文献；国外Barry［12］等从机场纯度(Station Purity)的角度，建立了鲁棒性机型指派模型，即要求每种机型涉及的机场尽量集中。本文借鉴他的思路，从航班的角度，建立基于航班纯度的鲁棒性机型指派

模型。

国内航班计划均以周为单位周期进行编排，航班纯度的概念即要求对一个周期内具有相同航班号不同天的航班(每天航班的离港时间点往往相同)尽可能指派同一种机型。机型指派是飞机、机组排班的基础，航班纯度考虑不仅有利于不正常航班情况下飞机的调整、方便停机位安排，而且有利于维护飞行员飞行任务的稳定性等。因此，机型指派航班纯度的提高，能极大地改善机型指派的鲁 2 模型建立

与连接网络相比，时空网络更方便航班之间衔接，因此本文选择建立时空网络G(Nk,Ak)［10］，节点Nk表示机场与时间轴的二维时空点，弧Ak表示航班段。对于同一航班号上的不同天航班，本文定义一种

棒性。

主机型，例如某航班(航班号N257)一周飞行七班，即每天一班，其中有四班由机型A执行，两班由机型B执行，一班由机型C执行，则我们定义机型A为航班(号)N257的主机型，其它机型定义为辅助机型，即N257航班纯度为4/7(57.14%)，为提高航班纯度，为辅助机型设置罚函数。模型参数具体说明如下： (1)式为收益最大化目标函数；(2)式为覆盖约束，要求每个航班段指派一种且只有一种机型;(3)、(4)式为机型航班纯度约束，其中(3)为每一个航班号定义一种且只有一种主机型，(4)表示变量之间的逻辑关系，即当航班段i指派的机型k不是该航班号l(i)上的主机型，则航班段i上的机型必为辅助机型；(5)式为飞机守恒约束，要求周期结束时各机型在各机场飞机数分布与周期开始时一样；(6)式表示飞机可用性约束，即如果Xk

j=1，则保证在航班段j离港时至少有一架k机型飞机在机场待命；(7)式为机队规模约束，即飞

机架次限制，该约束与(6)式一起保证了各机场飞机守恒约束；(8)式为飞机利用率约束；(9)式为指派飞机的座位容量约束；(10)式表示经停航班约束，即要求一次经停航班的两个航班段指派相同机型。 3 实例计算

以国内某航空公司干线航班网络为例，进行验证分析。该公司有48架飞机干线飞机，根据飞机型号及座位数分为5种机型，执行54个机场，每周250个航班(号)，共1786个航班段，其中包括544个一次经停航班段。机型成本根据各机型实际总运行成本估算得出，见表1。

航班段的航班号，离港、到港时间和离港、到港机场由该公司航班时刻表读取，各航班段最大旅客溢出量均取i.spill=0.1，航班段旅客量由预测得出，平均票价为电子客票价格，再由德尔菲法考虑一定折扣最终确定。对辅助机型惩罚值γ很难界定，因此本文对不同惩罚值进行测试，结果见表2。

从表2可以看出当γ=0时，即没有考虑航班的机型纯度，最优目标函数值为84422052元，即为文献［10］的结论；随着γ增大，辅助机型减少，航班的机型纯度提高，而最优目标值在减少。但即使设置很大的惩罚值如γ=10000，目标值比实际收益还多出449963元，相对提高了0.54％(推算每年增加利润超过2千万)，辅助机型航班段数降到53个，航班纯度达到97.03％，而实际问题航班纯度仅为94.74％，提高了2.29％。因此，该模型不仅提高了航班纯度，改善了机型指派的鲁棒性，同时也提高了收益。进一步对γ=10000时单个航班纯度进行了分析，每个航班号最多指派了两种机型；航班纯度最低为50％，主要是存在两个航班号(占0.8%)每周只有两班（如某航班号班期为周二、周五），而指派了不同的机型；共有218(占87.20%)个航班号的航班纯度达到100％，优化效果十分理想。 4 结论

本文根据国内航线网络及以周为单位周期编制航班计划的特点，借鉴机场纯度的概念，提出了航班纯度的概念；同时，指出航班纯度的提高，能极大地改善机型指派的鲁棒性，有利于不正常航班情况下飞机的调整、方便停机位安排，而且有利于维护飞行员飞行任务的稳定性，因此本文建立基于航班纯度的鲁棒性机型指派模型。最后，以国内某航空公司干线航班网络进行实例分析。结果表明，不仅可以提高航班纯度，改善机型指派鲁棒性，还可以提升公司的收益水平，因此，该模型不仅可为航空公司机型指派决策提供参考，也为航班计划系统开发奠定理论基础，该研究具有很大理论价值和现实指导意义。 参 考 文 献：

［1］Hanif D S, Ebru K B, Zhu Xiaomei. Airline fleet assignment concepts, models, and algorithms［J］. European Journal of Operational Research, 2006, 172(1): 1-30. ［2］Abara J. Applying integer linear programming to the fleet assignment problem［J］. Interfaces, 1989, 19(4): 20-28.

［3］Berge M E, Hopperstad C A. Demand driven dispatch: a method for dynamic

aircraft capacity assignment, models and algorithms［J］. Operational Research, 1993, 41(8): 153-168.

［4］Hane C A, Barnhart C, Johnson E L, et al.. The fleet assignment problems: solving a large-scale integer program［J］. Mathematical Programming, 1995, 70(2): 211-232.

［5］Rexing B, Barnhart C, Kniker T. Airline fleet assignment with time windows［J］. Transportation Science, 2000, 34(1): 1-20.

［6］Barnhart C, Kniker T S, Lohatepanont M. Itinerary-based airline fleet assignment［J］. Transportation Science, 2002, 36(1): 199-217.

［7］Jonathan D, Fati A, Fran S. Improving the objective function of the fleet assignment problem［J］. Transportation Research Part B, 2009, 43(2): 466-475.

［8］孙宏,杜文.应用网络流模型解决航班衔接问题［J］.西南交通大学学报,2002,37(2):223-226.

［9］孙宏,杜文.航空公司飞机排班问题的分阶段指派算法［J］.系统工程学报,2003,18(2):168-172.

［10］朱星辉,朱金福,姜涛.我国航空公司机型指派模型及算法研究［J］.工业技术经济,2007,26(4):75-77.

［11］朱星辉,朱金福,姜涛.分阶段多航空公司竞争下航班频率研究［J］.预测,2007,26(5):71-74.

［12］Barry C S, Ellis L J. Robust airline fleet assignment: imposing station purity using station decomposition［J］. Transportation Science, 2006, 40(4): 497-516．