机队编排问题求解的基础——时空网络模型的介绍

摘要: 本文内容大部分来自航空业的经典巨著《全球航空业》,为了让广大读者更容易接受,航旅IT圈对原文做了编译。本文所使用书中内容已获得该书出版方上海交通大学出版社的授权,任何第三方不得转载和摘抄。

11-10 19:52 首页 航旅IT圈


前言

随着国内外航空市场上竞争日益激烈,国内航空公司逐步感受到压力,对精细化运营提出了越来越多的需求。由于国内航班时刻分配(Schedule or Slot Assignment)尚未市场化,航空公司在航班时刻计划上运作的空间不大,因此许多航空公司将目光移到了提升机队编排/排班、机组排班、飞机检修计划、不正常航班恢复过程的效果和效率上。本文介绍机队编排(即将机型分配给航班号)的基础模型——时空网络模型。

本文内容大部分来自航空业的经典巨著《全球航空业》,为了让广大读者更容易接受,IT微信公众号AirTIT对原文做了编译。本文所使用书中内容已获得该书出版方上海交通大学出版社的授权,任何第三方不得转载和摘抄


描述机队编排问题

当航班计划确定后,下一个步骤是机队编排,即将飞机机型安排给每个航班。机队编排的问题可通过以下简化的例子说明。假设某航空公司希望运营表1中列出的航班集合,或者图1所示的航线网络。每个航班航节都给出:航班号、起飞机场、到达机场、起飞时间、到达时间、平均票价以及希望搭乘此航班航节的旅客总数。注意表中所有时间都以当地时间形式给出,方便网络规划人员计算轮挡时间、全程时间(即从飞机推出起飞登机口直到抵达目的地登机口的时间)及到达与起飞间的地面停留时间。


图1:航线网络示意


表2中给出了该航空公司机队详情,包括可用飞机的机型、每种机型飞机的数量、每种机型的物理容量或可用座位数以及每种机型在各个航班航节上的运营成本。


    给定上述信息后,每日机队编排问题可描述成:为航空公司航线网络上每一个航班航节分配飞机类型,使利润最大化,同时应使用所有可用飞机,并确保每天各个机场上飞机类型平衡。用数学语言表述:将机型f分配给航班航节l的利润,可用平均票价与该飞机期望搭载乘客数量的乘积减去相应的运营成本的办法计算得到,即:

其中:


   此外,min(…)表示求括号内变量的最小值。表3穷举出将各类机型分配给不同航段的所有可能性,以及各种情况下产生的利润值。


“时空网络”模型

通常使用“贪婪”算法(穷举法),按照最大化利润的原则将机型分配给每个航班航节,则结果为:

1. 将机型A300安排给航班CL301、CL302、CL332、CL502和CL551;

2. 将机型B737安排给航班CL331、CL333、CL501和CL552;

3. 而将DC9安排给航班CL303。


但仔细观察图1所示的航线网络即可发现,这种方式明显不可行——未考虑机型在机场间的平衡,即在图1所示的静态航线网络中难以确定运营每日航班需要的各机型飞机架数。比如,考虑能达到平衡的往返程航班CL552和CL501,并指定B737机型。虽然一架飞机在一天内可以完成两个航班的飞行,但CL552的到达时间比CL501的起飞时间晚,因此需要两架B737飞机才能完成这两个航班的日常运营。


    为了有效分析该问题中的时间顺序,业界多采用“时空网络”模型对航线网络建模。时空航线网络是对静态航线网络的扩展,其每个节点既代表位置也表示某个时间点。时空网络中有两类弧线(连接节点的边):

1. 班弧线:表示一个航班航节,弧线的起点代表出发地和时间点,弧线终点代表到达地和到达时间加周转时间。最小周转时间是指一架飞机到达某机场后,直到下次从该机场起飞前所需要的最短时间。最小周转时间包含了加油、清洁及飞机检修时间,根据飞机类型、机场运营能力以及一天中的不同时段会有较大不同。本例中为了描述简单,设最小(及实际)周转时间为零,因而可忽略。

2. 地面弧线:表示在两个航班弧线的到达和起飞端点之间,飞机停留在地面上的时间长度。


    图2对时空网络如何与航空公司航班计划结合给出了直观的演示。


图2:时空网络中的时间线


寻找切实可行的机队编排方案等同于在时空网络上为每架飞机选择合适的路径。在本例中,B737和A300机型可选择的路径不超过2条,DC9机型则只有1条路径可用。由于只有一架DC9飞机,它的路径只能从同一机场开始和结束才能保证每日重复运营。但对B737和A300机型则不存在这个限制,对这两个机型只要求在网络中的每个机场上,路径开始和结束时飞机的数量保持一致。


最优解与次优解

机队编排问题通常采用基础FAM(Fleet Assignment Model)模型求解,本文因篇幅所限不做具体介绍,有兴趣的读者可自行搜索相关文献做深入了解。


图3给出的最优解是一组满足上述条件并且使总利润最大的路径。最优的机队编排方案使用了所有可用的飞机,并且用两架A300飞机来保证机场上飞机数量的平衡,即1架每天从BOS出发,到ORD后结束一天的飞行;另1架飞机每天从ORD出发,到BOS后结束一天的飞行。该最优化机队编排方案的总利润为280,500美元。


图3:最优化机队编排方案


此外图4给出了次优的解决方案,总利润为255,000美元,但该方案实现了每架飞机路径每天在同一机场开始和结束。



图4:次优的机队编排方案


机队编排优化的经济效益

机队编排问题的最优化方法在航空公司的日常运营实践中被广泛应用,并促使运营收入显著提高:

1. 美国航空(AA)的机队编排模型使其运营利润增长了1.4%(见Abara,1989)

2. 达美航空(DL)使用机队编排模型后每年能节省下1亿美元(见Wiper等,1994)

3. 某项对美国航空业的审计结果显示,由于使用机队编排优化算法每年可节省1500万美元(见Rushmeier与Kontogiorgis, 1997)。


尽管已经取得了一些令人印象深刻的成就,但在机队编排问题的建模以及优化方面仍有巨大的提升空间。特别是与机组编排、飞机检修计划综合的集成航班计划优化过程,目前在国外已经出现成功的应用案例,并产生了巨大的经济效益。

当然,某些航空公司、特别是低成本航空公司为了避免机队编排、机组排班问题以及节省成本而采用单一机型,如美国的西南航空和国内一些航空公司。不过,这些航空公司还是可以使用时空网络模型优化航班合并、取消、飞机检修计划以及不正常航班恢复等问题,同样能够产生巨大的经济效益。

时空网络模型除了用于机型指派优化之外,还可用于另一种机队编排优化过程:飞机尾号指派。不过飞机尾号指派过程中,需考虑的限制、约束条件较多,例如高原航线,飞机推力,机龄等要求,这增加了求解模型的难度;幸好目前计算机技术以及运筹学理论获得较大发展,求解此类问题也变得相对容易。此外,国内航空短期销售(起飞前14至7天开始上座)中变化较多、较快,因此航空公司短期调整相当频繁,这样飞机尾号指派在实际生产运行过程中更具有现实意义。(注:本段根据厦航专家意见添加,感谢李耀能老师的指导。)

(全文完)


郑重申明:本文拒绝任何形式转载。

●  ●  ●    

 ? 专业原创行业分析文章、行业热点评论、知识分享文章

 为国外IT厂商提供内容翻译和文章推广服务

 为IT公司提供软件产品宣传服务

 ? 为行业会议组织公司提供组织和宣传

 提供IT解决方案咨询服务,撰写RFP


首页 - 航旅IT圈 的更多文章: