于 焯，樊 瑋

(中國民航大學 計算機科學與技術學院，天津 300300)

基于均衡條件的成本最小化航線調(diào)配問題研究

于 焯，樊 瑋

(中國民航大學 計算機科學與技術學院，天津 300300)

飛機航線調(diào)配是影響航空公司經(jīng)營效益的關鍵因素之一。大多數(shù)提高航空公司經(jīng)濟效益的研究主要考慮的因素是飛機維護。隨著航空公司和機場基地維修水平的快速提高，提高飛機航線調(diào)配的效益已經(jīng)成為各大航空公司關注的重點。飛機使用成本及其均衡性則成為了影響航空公司經(jīng)濟效益的重要因素。為了提高航空公司的經(jīng)濟效益，在滿足民用航空飛機檢修維護條件、航班覆蓋條件以及最小飛機數(shù)等約束條件的基礎上，針對飛機運營成本最小化以及飛機使用均衡兩個要素設計了目標函數(shù)，建立了一個多目標0-1整數(shù)線性規(guī)劃模型，并使用國內(nèi)某航空公司航班運行的真實數(shù)據(jù)對數(shù)學模型進行了實驗驗證。實驗結(jié)果表明，所提出的模型既可滿足飛機使用均衡的條件，也能保證飛機運營成本最小化，得到了經(jīng)濟合理的飛機航線調(diào)配方案。

航線調(diào)配；飛機排班；多目標；使用均衡；整數(shù)規(guī)劃

0 引 言

飛機航線調(diào)配，也稱飛機排班，是將機隊中的每一架飛機指派到相應的航節(jié)上。飛機航線調(diào)配是影響航空公司運營成本、服務水平以及市場競爭力的重要因素，一直以來不論是在學術研究領域還是在行業(yè)應用中，都備受關注。

飛機航線調(diào)配屬于組合優(yōu)化問題，在國內(nèi)外已涌現(xiàn)出了不少研究成果，主要的研究方法集中在運籌學算法和啟發(fā)式算法。在國外，F(xiàn)eo和Bard較早地提出了一個大規(guī)模的混合整數(shù)規(guī)劃模型，并對一周的飛機維修路線進行了優(yōu)化[1]。后來Clarke等將飛機路線問題轉(zhuǎn)換為帶有邊約束的旅行商問題，并利用Lagrangian松弛算法進行求解[2]。Gopalan等利用圖論對飛機排班問題進行深入探討,得到了4天以上飛機維護問題的存在可行解的條件，構造了一種“4-MET”(a Four-Day Maintenance Euler Tour)啟發(fā)式算法[3]。在國內(nèi)，孫宏等[4]提出將一個具體的飛機排班問題歸結(jié)為基于飛機調(diào)度指令要求的飛機排班、基于最少飛機數(shù)的排班問題和基于飛機使用均衡要求的排班問題三種典型模型中的一種，構造了一系列啟發(fā)式算法—基于飛機調(diào)度指令要求的飛機排班，提出了一種基于飛機階段指派的啟發(fā)式算法[5]；以所需飛機數(shù)最少為目標,提出了一種描述航班銜接問題的圖論模型及優(yōu)化算法[6]；基于均衡使用要求的飛機排班，提出了一種模擬退火算法[7]。肖東喜等[8]以飛機維修機會最大化為目標函數(shù)，采用列生成算法和Follow-on規(guī)則，動態(tài)構建滿足“三天維修規(guī)則”的航班環(huán)；王錦彪等[9]將啟發(fā)式智能優(yōu)化算法引入到飛機排班問題中,有效降低了算法復雜度。

上述研究為飛機航線調(diào)配問題提出了非常有益的解決方案，大部分研究考慮的重點是方便飛機維護，但隨著各機場及航空公司基地維修水平的快速提高，在實際應用中，飛機航線調(diào)配效益已成為航空公司關注的重點，飛機使用成本以及飛機使用均衡是影響效益的要素。為此，在滿足維護條件的基礎上，綜合考慮上述兩個要素，設計了一個多目標0-1整數(shù)線性規(guī)劃模型，用于求解最經(jīng)濟的飛機航線調(diào)配問題。

1 飛機航線調(diào)配問題

航線網(wǎng)絡可分為點對點的城市對結(jié)構和樞紐輪輻式(hub-and-spoke)結(jié)構兩種主要模式。國內(nèi)航線網(wǎng)絡以自發(fā)形成的點對點模式為主，同時不少航空公司也把北京、上海、廣州等機場作為樞紐機場建立基地，以基地為中心又形成小的輪輻式結(jié)構。采用小型樞紐輪輻式網(wǎng)絡結(jié)構來展開研究，網(wǎng)絡結(jié)構中只有一個基地機場，要求只在基地機場進行維護檢修。

1.1 基本約束

在飛機航線調(diào)配過程中，需要滿足以下基本約束：

(1)符合航班計劃：分配給每個航班的飛機應該滿足航班計劃中規(guī)定的機型、航班起飛到達機場、航班起飛時刻。指派給同一架飛機的兩個航班應滿足過站時間要求航站銜接要求。

(2)航班覆蓋：每個航班應當且僅能安排一架飛機執(zhí)行。

(3)維護要求：航空公司一般只在各自的基地機場進行維護檢修。保證維護要求就是要使飛機在航線網(wǎng)各點飛行時，能在正確的基地和正確的時間里得到需要的維護。

(4)最小飛機數(shù)：在運力緊張的情況下，飛機排班的基本目標就是要用最少的飛機承擔盡可能多的航班任務。

1.2 航班節(jié)生成算法

在航空公司制訂日常生產(chǎn)計劃的過程中，常常將航班銜接起來，形成一連串航班，稱為“航班節(jié)”[10-11]。通過引入航班節(jié)概念，將飛機對航班的分配問題轉(zhuǎn)化為飛機對航班節(jié)的分配問題[12]。每個航班節(jié)均以樞紐機場為起點和終點，并在樞紐機場有固定的起飛和到達時刻，從而降低問題的規(guī)模和復雜度。生成的可行航班節(jié)需滿足下述要求：

(1)維護要求：假設航空公司只在樞紐機場進行維護檢修。每架飛機最多運營3天后，必須要有一個晚上在基地機場停場過夜，以便進行維護檢查。

(2)周轉(zhuǎn)時間要求：設地面過站時間大于45 min。

在地方財政困難的情況下，積極爭取財政專項資金30萬元用于省級宣傳。2013年在中國水土保持生態(tài)建設網(wǎng)等部委網(wǎng)站上宣傳100余次，在青海水利網(wǎng)和青海水土保持生態(tài)建設網(wǎng)上宣傳近300次，在中國水利報、黃河報、青海日報宣傳40余次，在青海電視臺宣傳15次。

(3)調(diào)配時間周期的要求：假設航線的有效調(diào)配封閉周期為3日。封閉周期是指飛機從一個機場出發(fā)，在3日期期末時回到這個機場，然后開始下一個周期。

通過計算機編程可以找出既能覆蓋所有航班，又能滿足維護、周轉(zhuǎn)時間和調(diào)配周期等要求的可行航班節(jié)。生成可行航班節(jié)流程如圖1所示。

圖1 生成航班節(jié)流程圖

1.3 數(shù)學模型

影響飛機使用成本的主要因素有飛機日利用率、航段耗油量及國際油料價格等。其中飛機日利用率是一項重要因素，而保證機隊中每架飛機的使用均衡，既可有效保證每架飛機的日利用率，維持運力的穩(wěn)定，也可保證每架飛機維護的均衡，提高飛機使用壽命和飛行安全。為此，在滿足飛機維護要求的前提下，綜合考慮成本最小化和飛機使用均衡條件，提出了式(1)和式(2)所示的目標函數(shù)，運用集合劃分思想[13]和0-1整數(shù)線性規(guī)劃[14-15]，建立了航線調(diào)配問題的數(shù)學模型：

(1)集合：F為航班集合；R為可行調(diào)配方案集合。

(2)下標變量：i(i∈F)為航班下標；j(j∈R)為航線下標變量。

(5)數(shù)學模型。

(1)

(2)

(3)

(4)

(5)

目標函數(shù)(1)表示成本最小化；目標函數(shù)(2)表示飛機使用均衡，采用每個可行的航班節(jié)的飛行時間與每架飛機平均飛行時間差的絕對值和來表示均衡與否；約束條件(3)表示航班覆蓋的要求，保證每個航班僅能有一個航線調(diào)配方案；約束條件(4)表示機隊規(guī)模要求，將選定的調(diào)配方案所需的飛機數(shù)限制在可用飛機數(shù)量之內(nèi);式(5)為決策變量的0-1整數(shù)性要求。

2 實驗與分析

實驗使用XM航空公司杭州基地組航班時刻表，共40個國內(nèi)航班，分配給9架738機型，在此假定所有飛機都是一樣的，不考慮現(xiàn)實中的一些限制因素(如飛機機齡等)。表1為部分航班時刻信息。

表1 航班時刻表

2.1 生成航班節(jié)

按照1.2節(jié)提出的算法，對于表1中的航班信息，生成可行的航班節(jié)。為滿足維護要求，假設該航空公司只在樞紐機場，即HGH機場，設置維修設施。為滿足周轉(zhuǎn)時間要求，假設地面過站時間不小于45 min。為滿足調(diào)配時間周期要求，假設封閉周期為3日，飛機從某一機場出發(fā)，在3日周期期末時回到這個機場。按照算法編寫程序求解，共生成1 742 136個可行的航班節(jié)。表2列出了部分可行航班節(jié)信息。

表2 三日周期有效調(diào)配方案

2.2 模型驗證

生成可行航班節(jié)后，按照1.3節(jié)提出的數(shù)學模型對1 742 136個可行航班節(jié)進行航線調(diào)配，使用Lingo15軟件數(shù)學模型進行求解，最終得到9個優(yōu)化解，可分配給9架飛機，如表3所示。

表3 基于使用均衡條件的成本最小化航線調(diào)配結(jié)果

2.3 結(jié)果分析

對表3進行分析，每個3日周期的可行航班節(jié)飛行小時分布在39～42之間，即在3日周期中，機隊中飛機的日利用率分布在54.17%～58.33%之間。相同數(shù)據(jù)條件下，在只考慮成本最小化單一目標模型中，求得每個3日周期飛機日利用率分布在50%～59.03%之間，具體結(jié)果見表4；并且求得的最小成本與多目標模型求出的最小成本相差無幾?？梢钥闯觯啾戎豢紤]成本的單目標模型，多目標模型對飛機的使用更加均衡。相同數(shù)據(jù)條件下，在只考慮飛機均衡單一目標的模型中，每3日周期飛機日利用率分布在54.86%～58.33%之間，與多目標模型求得的結(jié)果相差無幾，但是，多目標模型求得的成本對比使用均衡單目標模型更加節(jié)約了?？梢钥闯?，多目標模型在保證飛機使用均衡的條件下，更加節(jié)約成本。因此，所提出的多目標數(shù)學模型既可以滿足飛機使用均衡條件，也可求得最小化成本，優(yōu)于僅考慮成本或僅考慮飛機使用均衡的單目標數(shù)學模型。

表4 只考慮成本最小化的航線調(diào)配結(jié)果

文獻[7]根據(jù)飛機的均衡使用要求構造了目標函數(shù)，設計了一種基于模擬退火算法的啟發(fā)式算法，給出了算法復雜度，能夠在較短時間內(nèi)得出一個基本符合要求的較好的滿意解，但是，并沒有給出具體算例和實驗結(jié)果。文獻[10]在飛機排班的多目標模型中雖然考慮到飛機使用均衡的目標，其飛機日利用率分布在40%～54%之間?？梢钥闯?，相比已有算法，所提出的基于均衡條件下成本最小化多目標數(shù)學模型飛機的使用均衡度更好，同時也能夠?qū)崿F(xiàn)航空公司成本最小化，并且給出了較為滿意的飛機航線調(diào)配優(yōu)化方案。

3 結(jié)束語

針對小型樞紐輪輻式航線網(wǎng)絡結(jié)構，在滿足飛機維護要求、最小飛機數(shù)要求、航班覆蓋和航班計劃的前提下，建立了以飛機使用均衡條件和飛機運營成本最小化為目標的多目標0-1整數(shù)規(guī)劃模型，用于解決飛機航線調(diào)配問題。以XM航空公司杭州基地真實航班及飛機數(shù)據(jù)進行實驗驗證，結(jié)果表明，該模型可以得出比較滿意的航線調(diào)配方案，能夠為航空公司實際工作提供支持。

[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].系統(tǒng)工程理論方法應用,2002,11(3):244-247.

[6] 孫 宏,杜 文.航空公司飛機排班問題的分階段指派算法[J].系統(tǒng)工程學報,2003,18(2):168-172.

[7] 孫 宏,文 軍,徐 杰.基于均衡使用要求的飛機排班算法[J].西南交通大學學報,2004,39(5):569-572.

[8] 肖東喜,朱金福.飛機排班中航班環(huán)的動態(tài)構建方法[J].系統(tǒng)工程,2007,25(11):19-25.

[9] 鄭 蕓,王錦彪,王元崑.螞蟻算法在民航飛機排班問題中的應用[J].計算機工程,2005,31:7-9.

[10] 孫 宏.應用網(wǎng)絡流模型解決航班銜接問題[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].系統(tǒng)仿真學報,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，F(xiàn)AN 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 網(wǎng)絡出版時間：2017-07-05

國家自然科學基金資助項目(U1333109);中央高校基本科研業(yè)務費(3122016B006)

于 焯(1989-)，女，碩士研究生，通訊作者，研究方向為航空公司收益管理理論及應用、大數(shù)據(jù)處理、計算機軟件理論及應用、智能信息處理；樊 瑋，教授，博士，CCF會員，研究方向為航空公司收益管理理論及應用、大數(shù)據(jù)處理、計算機軟件理論及應用、智能信息處理。

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