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

于 焯，樊 瑋

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

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

于 焯，樊 瑋

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

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

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

0 引 言

飛機(jī)航線調(diào)配，也稱飛機(jī)排班，是將機(jī)隊(duì)中的每一架飛機(jī)指派到相應(yīng)的航節(jié)上。飛機(jī)航線調(diào)配是影響航空公司運(yùn)營(yíng)成本、服務(wù)水平以及市場(chǎng)競(jìng)爭(zhēng)力的重要因素，一直以來(lái)不論是在學(xué)術(shù)研究領(lǐng)域還是在行業(yè)應(yīng)用中，都備受關(guān)注。

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

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

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

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

1.1 基本約束

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

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

(2)航班覆蓋：每個(gè)航班應(yīng)當(dāng)且僅能安排一架飛機(jī)執(zhí)行。

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

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

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

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

(1)維護(hù)要求：假設(shè)航空公司只在樞紐機(jī)場(chǎng)進(jìn)行維護(hù)檢修。每架飛機(jī)最多運(yùn)營(yíng)3天后，必須要有一個(gè)晚上在基地機(jī)場(chǎng)停場(chǎng)過夜，以便進(jìn)行維護(hù)檢查。

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

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

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

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

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

1.3 數(shù)學(xué)模型

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

2 實(shí)驗(yàn)與分析

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

表1 航班時(shí)刻表

2.1 生成航班節(jié)

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

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

2.2 模型驗(yàn)證

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

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

2.3 結(jié)果分析

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

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

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

3 結(jié)束語(yǔ)

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

[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] 孫 宏.航空公司飛機(jī)排班問題：模型及算法研究[D].成都:西南交通大學(xué),2003.

[5] 孫 宏,杜 文.航空公司飛機(jī)排班問題的排序模型及算法[J].系統(tǒng)工程理論方法應(yīng)用,2002,11(3):244-247.

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

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

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

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

[10] 孫 宏.應(yīng)用網(wǎng)絡(luò)流模型解決航班銜接問題[J].西南交通大學(xué)學(xué)報(bào),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ī)排班航班串編制模型及算法研究[J].系統(tǒng)仿真學(xué)報(bào),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)絡(luò)出版時(shí)間：2017-07-05

國(guó)家自然科學(xué)基金資助項(xiàng)目(U1333109);中央高校基本科研業(yè)務(wù)費(fèi)(3122016B006)

于 焯(1989-)，女，碩士研究生，通訊作者，研究方向?yàn)楹娇展臼找婀芾砝碚摷皯?yīng)用、大數(shù)據(jù)處理、計(jì)算機(jī)軟件理論及應(yīng)用、智能信息處理；樊 瑋，教授，博士，CCF會(huì)員，研究方向?yàn)楹娇展臼找婀芾砝碚摷皯?yīng)用、大數(shù)據(jù)處理、計(jì)算機(jī)軟件理論及應(yīng)用、智能信息處理。

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