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

于 焯，樊 瑋

(中國民航大學 計算機科學與技術學院，天津 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