基于均衡条件的成本最小化航线调配问题研究

于 焯，樊 玮

(中国民航大学 计算机科学与技术学院，天津 300300)

基于均衡条件的成本最小化航线调配问题研究

于 焯，樊 玮

(中国民航大学 计算机科学与技术学院，天津 300300)

飞机航线调配是影响航空公司经营效益的关键因素之一。大多数提高航空公司经济效益的研究主要考虑的因素是飞机维护。随着航空公司和机场基地维修水平的快速提高，提高飞机航线调配的效益已经成为各大航空公司关注的重点。飞机使用成本及其均衡性则成为了影响航空公司经济效益的重要因素。为了提高航空公司的经济效益，在满足民用航空飞机检修维护条件、航班覆盖条件以及最小飞机数等约束条件的基础上，针对飞机运营成本最小化以及飞机使用均衡两个要素设计了目标函数，建立了一个多目标0-1整数线性规划模型，并使用国内某航空公司航班运行的真实数据对数学模型进行了实验验证。实验结果表明，所提出的模型既可满足飞机使用均衡的条件，也能保证飞机运营成本最小化，得到了经济合理的飞机航线调配方案。

航线调配；飞机排班；多目标；使用均衡；整数规划

0 引 言

飞机航线调配，也称飞机排班，是将机队中的每一架飞机指派到相应的航节上。飞机航线调配是影响航空公司运营成本、服务水平以及市场竞争力的重要因素，一直以来不论是在学术研究领域还是在行业应用中，都备受关注。

飞机航线调配属于组合优化问题，在国内外已涌现出了不少研究成果，主要的研究方法集中在运筹学算法和启发式算法。在国外，Feo和Bard较早地提出了一个大规模的混合整数规划模型，并对一周的飞机维修路线进行了优化[1]。后来Clarke等将飞机路线问题转换为带有边约束的旅行商问题，并利用Lagrangian松弛算法进行求解[2]。Gopalan等利用图论对飞机排班问题进行深入探讨,得到了4天以上飞机维护问题的存在可行解的条件，构造了一种“4-MET”(a Four-Day Maintenance Euler Tour)启发式算法[3]。在国内，孙宏等[4]提出将一个具体的飞机排班问题归结为基于飞机调度指令要求的飞机排班、基于最少飞机数的排班问题和基于飞机使用均衡要求的排班问题三种典型模型中的一种，构造了一系列启发式算法—基于飞机调度指令要求的飞机排班，提出了一种基于飞机阶段指派的启发式算法[5]；以所需飞机数最少为目标,提出了一种描述航班衔接问题的图论模型及优化算法[6]；基于均衡使用要求的飞机排班，提出了一种模拟退火算法[7]。肖东喜等[8]以飞机维修机会最大化为目标函数，采用列生成算法和Follow-on规则，动态构建满足“三天维修规则”的航班环；王锦彪等[9]将启发式智能优化算法引入到飞机排班问题中,有效降低了算法复杂度。

上述研究为飞机航线调配问题提出了非常有益的解决方案，大部分研究考虑的重点是方便飞机维护，但随着各机场及航空公司基地维修水平的快速提高，在实际应用中，飞机航线调配效益已成为航空公司关注的重点，飞机使用成本以及飞机使用均衡是影响效益的要素。为此，在满足维护条件的基础上，综合考虑上述两个要素，设计了一个多目标0-1整数线性规划模型，用于求解最经济的飞机航线调配问题。

1 飞机航线调配问题

航线网络可分为点对点的城市对结构和枢纽轮辐式(hub-and-spoke)结构两种主要模式。国内航线网络以自发形成的点对点模式为主，同时不少航空公司也把北京、上海、广州等机场作为枢纽机场建立基地，以基地为中心又形成小的轮辐式结构。采用小型枢纽轮辐式网络结构来展开研究，网络结构中只有一个基地机场，要求只在基地机场进行维护检修。

1.1 基本约束

在飞机航线调配过程中，需要满足以下基本约束：

(1)符合航班计划：分配给每个航班的飞机应该满足航班计划中规定的机型、航班起飞到达机场、航班起飞时刻。指派给同一架飞机的两个航班应满足过站时间要求航站衔接要求。

(2)航班覆盖：每个航班应当且仅能安排一架飞机执行。

(3)维护要求：航空公司一般只在各自的基地机场进行维护检修。保证维护要求就是要使飞机在航线网各点飞行时，能在正确的基地和正确的时间里得到需要的维护。

(4)最小飞机数：在运力紧张的情况下，飞机排班的基本目标就是要用最少的飞机承担尽可能多的航班任务。

1.2 航班节生成算法

在航空公司制订日常生产计划的过程中，常常将航班衔接起来，形成一连串航班，称为“航班节”[10-11]。通过引入航班节概念，将飞机对航班的分配问题转化为飞机对航班节的分配问题[12]。每个航班节均以枢纽机场为起点和终点，并在枢纽机场有固定的起飞和到达时刻，从而降低问题的规模和复杂度。生成的可行航班节需满足下述要求：

(1)维护要求：假设航空公司只在枢纽机场进行维护检修。每架飞机最多运营3天后，必须要有一个晚上在基地机场停场过夜，以便进行维护检查。

(2)周转时间要求：设地面过站时间大于45 min。

在地方财政困难的情况下，积极争取财政专项资金30万元用于省级宣传。2013年在中国水土保持生态建设网等部委网站上宣传100余次，在青海水利网和青海水土保持生态建设网上宣传近300次，在中国水利报、黄河报、青海日报宣传40余次，在青海电视台宣传15次。

(3)调配时间周期的要求：假设航线的有效调配封闭周期为3日。封闭周期是指飞机从一个机场出发，在3日期期末时回到这个机场，然后开始下一个周期。

通过计算机编程可以找出既能覆盖所有航班，又能满足维护、周转时间和调配周期等要求的可行航班节。生成可行航班节流程如图1所示。

图1 生成航班节流程图

1.3 数学模型

影响飞机使用成本的主要因素有飞机日利用率、航段耗油量及国际油料价格等。其中飞机日利用率是一项重要因素，而保证机队中每架飞机的使用均衡，既可有效保证每架飞机的日利用率，维持运力的稳定，也可保证每架飞机维护的均衡，提高飞机使用寿命和飞行安全。为此，在满足飞机维护要求的前提下，综合考虑成本最小化和飞机使用均衡条件，提出了式(1)和式(2)所示的目标函数，运用集合划分思想[13]和0-1整数线性规划[14-15]，建立了航线调配问题的数学模型：

(1)集合：F为航班集合；R为可行调配方案集合。

(2)下标变量：i(i∈F)为航班下标；j(j∈R)为航线下标变量。

(5)数学模型。

(1)

(2)

(3)

(4)

(5)

目标函数(1)表示成本最小化；目标函数(2)表示飞机使用均衡，采用每个可行的航班节的飞行时间与每架飞机平均飞行时间差的绝对值和来表示均衡与否；约束条件(3)表示航班覆盖的要求，保证每个航班仅能有一个航线调配方案；约束条件(4)表示机队规模要求，将选定的调配方案所需的飞机数限制在可用飞机数量之内;式(5)为决策变量的0-1整数性要求。

2 实验与分析

实验使用XM航空公司杭州基地组航班时刻表，共40个国内航班，分配给9架738机型，在此假定所有飞机都是一样的，不考虑现实中的一些限制因素(如飞机机龄等)。表1为部分航班时刻信息。

表1 航班时刻表

2.1 生成航班节

按照1.2节提出的算法，对于表1中的航班信息，生成可行的航班节。为满足维护要求，假设该航空公司只在枢纽机场，即HGH机场，设置维修设施。为满足周转时间要求，假设地面过站时间不小于45 min。为满足调配时间周期要求，假设封闭周期为3日，飞机从某一机场出发，在3日周期期末时回到这个机场。按照算法编写程序求解，共生成1 742 136个可行的航班节。表2列出了部分可行航班节信息。

表2 三日周期有效调配方案

2.2 模型验证

生成可行航班节后，按照1.3节提出的数学模型对1 742 136个可行航班节进行航线调配，使用Lingo15软件数学模型进行求解，最终得到9个优化解，可分配给9架飞机，如表3所示。

表3 基于使用均衡条件的成本最小化航线调配结果

2.3 结果分析

对表3进行分析，每个3日周期的可行航班节飞行小时分布在39～42之间，即在3日周期中，机队中飞机的日利用率分布在54.17%～58.33%之间。相同数据条件下，在只考虑成本最小化单一目标模型中，求得每个3日周期飞机日利用率分布在50%～59.03%之间，具体结果见表4；并且求得的最小成本与多目标模型求出的最小成本相差无几。可以看出，相比只考虑成本的单目标模型，多目标模型对飞机的使用更加均衡。相同数据条件下，在只考虑飞机均衡单一目标的模型中，每3日周期飞机日利用率分布在54.86%～58.33%之间，与多目标模型求得的结果相差无几，但是，多目标模型求得的成本对比使用均衡单目标模型更加节约了。可以看出，多目标模型在保证飞机使用均衡的条件下，更加节约成本。因此，所提出的多目标数学模型既可以满足飞机使用均衡条件，也可求得最小化成本，优于仅考虑成本或仅考虑飞机使用均衡的单目标数学模型。

表4 只考虑成本最小化的航线调配结果

文献[7]根据飞机的均衡使用要求构造了目标函数，设计了一种基于模拟退火算法的启发式算法，给出了算法复杂度，能够在较短时间内得出一个基本符合要求的较好的满意解，但是，并没有给出具体算例和实验结果。文献[10]在飞机排班的多目标模型中虽然考虑到飞机使用均衡的目标，其飞机日利用率分布在40%～54%之间。可以看出，相比已有算法，所提出的基于均衡条件下成本最小化多目标数学模型飞机的使用均衡度更好，同时也能够实现航空公司成本最小化，并且给出了较为满意的飞机航线调配优化方案。

3 结束语

针对小型枢纽轮辐式航线网络结构，在满足飞机维护要求、最小飞机数要求、航班覆盖和航班计划的前提下，建立了以飞机使用均衡条件和飞机运营成本最小化为目标的多目标0-1整数规划模型，用于解决飞机航线调配问题。以XM航空公司杭州基地真实航班及飞机数据进行实验验证，结果表明，该模型可以得出比较满意的航线调配方案，能够为航空公司实际工作提供支持。

[1] Feo T A,Bard J F.Flight scheduling and maintenance base planning[J].Management Science,1989,35(12):1415-1432.

[2] Clarke L,Johnson E,Nemhauser G,et al.The aircraft rotation problem[J].Annals of Operations Research,1997,69(1):33-46.

[3] Pauley G S,Ormerod R J,Woolsey R E D,et al.The four-day aircraft maintenance routing problem[J].Transportation Science,1998,32(1):43-53.

[4] 孙 宏.航空公司飞机排班问题：模型及算法研究[D].成都:西南交通大学,2003.

[5] 孙 宏,杜 文.航空公司飞机排班问题的排序模型及算法[J].系统工程理论方法应用,2002,11(3):244-247.

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

[7] 孙 宏,文 军,徐 杰.基于均衡使用要求的飞机排班算法[J].西南交通大学学报,2004,39(5):569-572.

[8] 肖东喜,朱金福.飞机排班中航班环的动态构建方法[J].系统工程,2007,25(11):19-25.

[9] 郑 芸,王锦彪,王元崑.蚂蚁算法在民航飞机排班问题中的应用[J].计算机工程,2005,31:7-9.

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

[11] Barnhart C,Boland N L,Clarke L W,et al.Flight string models for aircraft fleeting and routing[J].Transportation Science,1998,32(3):208-220.

[12] 李耀华,谭 娜,郝贵和.飞机排班航班串编制模型及算法研究[J].系统仿真学报,2008,20(3):612-615.

[13] Balas E,Padberg M W.Set partitioning:a survey[J].SIAM Review,1976,18(4):710-760.

[14] Meguerdichian S,Potkonjak M.Low power 0/1 coverage and scheduling techniques in sensor networks[R].[s.l.]:[s.n.],2003.

[15] Hane C A,Barnhart C,Johnson E J,et al.The fleet assignment problem:solving a large-scale integer program[J].Mathematical Programming,1995,70(1):211-232.

Research on Aircraft Routing Problem for Airlines Cost Minimization with Fleet Balance Application

YU Zhuo，FAN Wei

(College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

Aircraft routing problem is one of the key factors that affect the operation efficiency of airline companies.Most of the existing researches focus on the convenience of aircraft maintenance.With the rapid improvement of maintenance of the airlines and airport bases,improvement in efficiency of aircraft route deployment has become a major concern to most airlines.Airlines cost minimization and their fleet balance are two of the most important factors affecting economic benefit of Airline Company.In order to improve the economic benefit of airline company,on the basis of satisfying the constraint conditions of aircraft maintenance and minimum number of aircraft,a 0-1 integer programming model with the objective of fleet balance condition and cost minimization condition is proposed,which has been verified by the real data of a certain domestic airline company.The experimental results show that it has not only met the conditions of fleet balance,but also ensured minimum operation costs of airlines,by which economic and reasonable aircraft routing allocation plan can be provided.

aircraft routing;fleet assignment;multi-objective;fleet balance;integer programming

2016-09-21

2016-12-27 网络出版时间：2017-07-05

国家自然科学基金资助项目(U1333109);中央高校基本科研业务费(3122016B006)

于 焯(1989-)，女，硕士研究生，通讯作者，研究方向为航空公司收益管理理论及应用、大数据处理、计算机软件理论及应用、智能信息处理；樊 玮，教授，博士，CCF会员，研究方向为航空公司收益管理理论及应用、大数据处理、计算机软件理论及应用、智能信息处理。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1652.068.html

TP399

A

1673-629X(2017)08-0145-04

10.3969/j.issn.1673-629X.2017.08.030