基于分支定界法的飛機(jī)均衡排班計(jì)劃求解

范永俊，吳東華

（1.南京農(nóng)業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，南京 210095；2.南京航空航天大學(xué) 繼續(xù)教育學(xué)院，南京 210016）

基于分支定界法的飛機(jī)均衡排班計(jì)劃求解

范永俊1，吳東華2

（1.南京農(nóng)業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，南京 210095；2.南京航空航天大學(xué) 繼續(xù)教育學(xué)院，南京 210016）

文章闡述的是航空經(jīng)濟(jì)優(yōu)化中，為實(shí)現(xiàn)現(xiàn)有飛機(jī)運(yùn)營(yíng)和維護(hù)成本的最小化，如何根據(jù)現(xiàn)有的航班時(shí)刻表以及機(jī)型分配結(jié)果，以每架飛機(jī)平均飛行時(shí)間均衡為優(yōu)化目標(biāo)的飛機(jī)排班問題的實(shí)現(xiàn)過程。提出了基于分支定界法解決飛機(jī)排班問題的方案。討論了分枝定界法求解具體優(yōu)化問題時(shí)所采取的算法策略。將以飛機(jī)使用均衡為目標(biāo)的飛機(jī)排班問題轉(zhuǎn)化為基于分支定界法的求解，并將此方法應(yīng)用于一個(gè)具體算例中，求得12架A320機(jī)型68個(gè)航班的滿意排班結(jié)果，總耗時(shí)小于0.3秒，實(shí)驗(yàn)結(jié)果表明，該方法可以有效解決飛機(jī)排班問題，并具有較高的實(shí)際應(yīng)用價(jià)值。

經(jīng)濟(jì)優(yōu)化；分支定界；飛機(jī)排班

0 引言

分枝定界算法(Branch-and-Bound Algorithm,簡(jiǎn)稱B&B)，是一種在枚舉法基礎(chǔ)上的改進(jìn)方法，能夠有效求解一些規(guī)模相對(duì)比較大的問題。這種算法靈活并且利于計(jì)算機(jī)求解，不僅可用于表達(dá)整數(shù)線性規(guī)劃(或者混合整數(shù)線性規(guī)劃)難題,也可用于多數(shù)組合最優(yōu)化問題[1]。分支定界算法目前能夠解決的問題，包括求解整數(shù)規(guī)劃、生產(chǎn)進(jìn)度表、貨郎擔(dān)、選址、背包以及可行解的數(shù)目為有限的其他問題等，而且被許多其他學(xué)科領(lǐng)域使用，如計(jì)算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)、管理科學(xué)等。對(duì)航空公司而言，飛機(jī)排班是生產(chǎn)計(jì)劃的基本內(nèi)容，本質(zhì)上是一個(gè)經(jīng)濟(jì)優(yōu)化過程,目前是民航界著名的NP難問題[2]。合理的航班計(jì)劃有助于保證航班的安全、正點(diǎn)，提高機(jī)隊(duì)的利用效率，降低運(yùn)營(yíng)和維護(hù)的經(jīng)濟(jì)成本[3]。

國(guó)內(nèi)最早進(jìn)行排班研究的孫宏等[4，5]應(yīng)用了模擬退火算法、二部圖最大匹配方法和固定工件排序模型和Hun-garian算法，鄭蕓等[2]使用了螞蟻算法等，但均不同程度的存在著算法參數(shù)設(shè)置復(fù)雜、收斂速度慢部分算法只能夠求局部最優(yōu)解等問題。2014年朱星輝等[6]提出了用約束編程快速求解航班連線（航班串）并計(jì)算航班串簡(jiǎn)約成本,動(dòng)態(tài)選擇列集并與限制主問題進(jìn)行迭代的基于約束編程的動(dòng)態(tài)列生成算法，近期賈寶惠等[7]應(yīng)用交叉粒子群算法，在迭代的過程中,粒子通過交叉得到新粒子;為避免粒子陷入局部最優(yōu),引入了粒子位置變異機(jī)制，但是這兩種算法在工作時(shí)間與指派成本上仍舊不能滿足實(shí)際排班工作需要。夏洪山等[8]針對(duì)影響航空公司運(yùn)營(yíng)成本的四個(gè)關(guān)鍵因素,在滿足航班銜接、航班覆蓋和機(jī)隊(duì)規(guī)模約束條件下,以最小化運(yùn)營(yíng)成本、最小地面等待時(shí)間、最小總飛行時(shí)間絕對(duì)偏差和最少起降次數(shù)為目標(biāo)函數(shù),建立了飛機(jī)排班問題的0-1整數(shù)模糊線性規(guī)劃數(shù)學(xué)模型，基于東方航空公司實(shí)際數(shù)據(jù),應(yīng)用模糊線性規(guī)劃理論對(duì)模型進(jìn)行驗(yàn)證,算法有效。

分支定界算法是求解整數(shù)線性規(guī)劃(ILP)問題的一種最常用的方法,如何劃分問題(分支)和按何種策略選擇子問題進(jìn)行擴(kuò)展是影響算法效率的兩個(gè)重要因素。本文提出了一種改進(jìn)的分支定界算法,應(yīng)用于國(guó)內(nèi)飛機(jī)排班，數(shù)值實(shí)驗(yàn)表明,改進(jìn)的算法能夠有效提高求解效率,與上述算法相比，當(dāng)問題規(guī)模較大時(shí),改進(jìn)效果尤其明顯。試驗(yàn)中，當(dāng)運(yùn)用于68個(gè)航班的指派工作時(shí)，總優(yōu)化時(shí)間少于0.3秒，具有非常好的實(shí)際應(yīng)用價(jià)值。

1 算法背景

1．1 分支定界法算法思想

對(duì)有約束條件的最優(yōu)化問題的所有可行解空間適當(dāng)進(jìn)行搜索。具體執(zhí)行時(shí),把全部可行解空間不斷分割為越來越小的子集(即分支),為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界(即定界)。即：分支、松弛和定界。

1.1.1 分支

對(duì)任何線性整數(shù)規(guī)劃問題（P），讓F（P）表示（P）的允許解集合。子問題（P1），…（Pq），若滿足條件：

則稱（P）可分解為（P1），…（Pq）之和。

1.1.2 松弛

凡是放棄（P）的某些約束條件后，所得到的問題（），都稱為（P）的松弛問題。對(duì)于(P)的任何松弛問題()，都具有如下明顯的性質(zhì)：

(1)若()沒有允許解，則(P)也沒有允許解。

(2)(P)的最優(yōu)解不優(yōu)于()的最優(yōu)解。

(3)若()的一個(gè)最優(yōu)解是(P)的允許解，則它也是(P)的一個(gè)最優(yōu)解。

最通常的松弛方式是放棄變量的整數(shù)性要求。

1.1.3 定界

假設(shè)按某種規(guī)劃，已將問題(P)分解為子問題（P1），…（Pq）之和，并且各(Pi)已有對(duì)應(yīng)的松弛問題()。

(1)若()沒有允許解，則探明了(Pi)沒有允許解。因此，可從(P)的分解表上把它刪去。

(2)假設(shè)當(dāng)時(shí)已掌握了(P)的一個(gè)允許解x*，它的目標(biāo)函數(shù)值為。若松弛問題()的最優(yōu)解不比更好，則探明了(Pi)中沒有比x*更好的允許解。因此，已無須再進(jìn)一步考慮(Pi)，可從分解表上把它刪去。

(3)若()的最優(yōu)解是(Pi)的允許解，則已求得了(Pi)的一個(gè)最優(yōu)解，因此，也無須再進(jìn)一步考慮(Pi)了，可從表上刪去。這時(shí)，若(Pi)的最優(yōu)解比x*好，那么，替換x*，同時(shí)也刷新的記錄。

(4)假如表上各個(gè)()的目標(biāo)函數(shù)最優(yōu)解都不比好，那么，當(dāng)時(shí)的記錄解x*，便是原問題(P)的一個(gè)最優(yōu)解。

分支定界算法就是在一個(gè)深度為n的樹上搜索,對(duì)樹上的每一個(gè)節(jié)點(diǎn)上求解線性規(guī)劃問題。在每次定界后,對(duì)搜索樹上目前所有葉子結(jié)點(diǎn)的下界進(jìn)行比較,找到下界最小結(jié)點(diǎn),把此結(jié)點(diǎn)作為下次分支的結(jié)點(diǎn)。最終分支肯定可以找到可行解,將目前已知最好的可行解及其值加以存儲(chǔ),假如待分支的結(jié)點(diǎn)的下界小于存放的值,就繼續(xù)分支,否則算法終止,存儲(chǔ)的解即為最佳解。算法中“分支和松弛”為最優(yōu)解的出現(xiàn)創(chuàng)造條件,通過“定界”來提高搜索效率。實(shí)際運(yùn)算結(jié)果表明：依據(jù)對(duì)實(shí)際問題的理解,選擇合理的“界限”,能夠充分提高算法搜索效率。

1．2 提高搜索效率的關(guān)鍵策略

首先，為了盡早搜索到最優(yōu)解，應(yīng)該在分支過程中盡快獲得整數(shù)可行解，為整數(shù)規(guī)劃問題的目標(biāo)函數(shù)值定出上界，以此為依據(jù)，放棄分支過程中，線性規(guī)劃問題目標(biāo)函數(shù)值超過此上界的分支，節(jié)省所有分支搜索時(shí)間。為達(dá)到求出最初整數(shù)可行解的目的，在分支過程中，不連續(xù)求解從同一點(diǎn)引出的分支，而是先將其中一個(gè)分支加以記錄，然后沿著另一個(gè)分支一直搜尋下去，直到分支被搜尋完成。如果無法出現(xiàn)可行整數(shù)解，則總是挑選下界最小的點(diǎn)進(jìn)行分支求解，并再沿該分支搜尋。重復(fù)上述步驟，不斷進(jìn)行分支，確保盡快得到一個(gè)整數(shù)可行解。

其次，在分支過程中，由于選擇分支變量的順序不同，整個(gè)求解過程所需搜尋的分支個(gè)數(shù)就會(huì)出現(xiàn)較大差別，從而使計(jì)算時(shí)間有長(zhǎng)有短。一個(gè)有效的辦法是首先選擇目標(biāo)函數(shù)中系數(shù)最大的整數(shù)變量進(jìn)行分支，就能較快地得到整數(shù)最優(yōu)解。

2 飛機(jī)排班計(jì)劃求解

2．1 飛機(jī)排班計(jì)劃描述

飛機(jī)排班是指排班人員依據(jù)航班計(jì)劃和機(jī)務(wù)部提供的飛機(jī)維護(hù)計(jì)劃和狀態(tài)信息，為每個(gè)航班指定飛機(jī)進(jìn)行執(zhí)飛。鑒于飛機(jī)長(zhǎng)時(shí)間空閑或者滿負(fù)荷工作都帶來航空公司運(yùn)營(yíng)成本和維護(hù)成本的增加，所以需要考慮在滿足航班覆蓋、維護(hù)要求、機(jī)隊(duì)均衡的前提下，保證每架飛機(jī)飛行時(shí)間的均衡。

飛機(jī)排班流程[5]見圖1所示。

圖1 飛機(jī)排班流程

2．2 飛機(jī)排班問題的數(shù)學(xué)模型

根據(jù)飛機(jī)排班問題要滿足的條件，充分考慮我國(guó)航空公司實(shí)際運(yùn)作特點(diǎn)，建立如下數(shù)學(xué)模型：

集合：F=所有航班的集合

R=可行航班環(huán)的集合

M=維護(hù)基地集合

下標(biāo)變量：j=可行航班環(huán)下標(biāo)變量

i=航班下標(biāo)變量

N=可執(zhí)飛飛機(jī)總數(shù)

Tj=可行航班環(huán)j的飛行時(shí)間

Q=當(dāng)天所有航班總飛行時(shí)間

2．3 數(shù)據(jù)準(zhǔn)備

基于分支定界法求解飛機(jī)排班問題的效率依賴于要進(jìn)行排班的航班數(shù)。分支定界法的思想源自于枚舉法，在最壞的情況下，分支定界法的計(jì)算復(fù)雜度仍為n!次。正是考慮到此因素，本文的做法是，為了減少算法的搜索空間，事先搜索所有航節(jié)，找出所有可行的航班環(huán)，使得分支定界法只在可能的范圍內(nèi)進(jìn)行搜索，從而提高了搜索效率。

為了得到可行航班環(huán)集合R，必須搜索所有航節(jié)。可行航班環(huán)是指航節(jié)間能滿足過站時(shí)間、當(dāng)天總飛行時(shí)間和基地維護(hù)要求的航班環(huán)。根據(jù)我國(guó)航空總局有關(guān)規(guī)定，基地維護(hù)要求是要保證所有飛機(jī)必須能夠在規(guī)定的時(shí)間飛抵正確的基地過夜以及進(jìn)行維護(hù)。過站時(shí)間指一架飛機(jī)從著陸到準(zhǔn)備好下一次飛行所需要的最少的時(shí)間?？梢圆捎脠D的深度優(yōu)先搜索算法得到集合R。在搜索時(shí)記錄下每個(gè)可行航班環(huán)的飛行時(shí)間Tj。

2．4 基于分支定界法的求解步驟

為快速求解到整數(shù)最優(yōu)解，算法中如果出現(xiàn)無可行解的情況，則按“最小下界優(yōu)先”的原則，從記錄表中取出此結(jié)點(diǎn)進(jìn)行分支求解。在分支過程中，本文選擇目標(biāo)函數(shù)中系數(shù)最大的決策變量進(jìn)行分支。具體步驟如下：

設(shè)(P)為上述問題，()表示放棄0～1整數(shù)性要求后的問題。

(1)求解 ()。記下()的最優(yōu)解及最小值0。這時(shí)若也滿足0～1整數(shù)性要求，則算法終止，說明已是(P)的最優(yōu)解。否則賦予(P)的目標(biāo)函數(shù)值下界為0。

(3)若π=?，則算法終止，x*便是(P)的最優(yōu)解。否則執(zhí)行(4)。

(4)從π中取出一個(gè)下界值最小的子問題，記作(CP)。將(CP)從π中移出。并求解其放棄各xj的0～1整數(shù)性要求后的松弛問題

(7)選取目標(biāo)函數(shù)中系數(shù)最大的整數(shù)變量xj進(jìn)行分支(如果xj不滿足0～1整數(shù)性要求的話)。分支采用“兩分法”，即按xj=0和xj=1分解成(CP1)和(CP2)兩個(gè)子問題。并賦予它們下界為0，將(CPl)和(CP2)記入π中。然后轉(zhuǎn)到(4)。

3 算例分析

3．1 參數(shù)設(shè)定

東方航空公司每周一由A320機(jī)型執(zhí)飛68個(gè)航班，構(gòu)成了航班集合F（i=1,…,68）。限于篇幅，表1（見下頁(yè)）中顯示部分航班集合。其中到發(fā)時(shí)間從當(dāng)天零點(diǎn)零分起。維護(hù)基地集合M有3個(gè)，分別是無錫、南京和浦東機(jī)場(chǎng)。有A320飛機(jī)12架，即N=12。根據(jù)我國(guó)民航總局規(guī)定，設(shè)置當(dāng)天每架飛機(jī)總飛行時(shí)間應(yīng)該不大于14小時(shí)，過站時(shí)間大于等于40分鐘。Q=航班時(shí)刻表中飛行時(shí)間列的求和。應(yīng)用圖的深度優(yōu)先算法搜索到233個(gè)可行航班環(huán)（j=1,…,233），構(gòu)成了可行航班環(huán)集合R，部分在表2中顯示。其中每一個(gè)航班環(huán)用航班時(shí)刻表中航班序號(hào)組成。在搜索時(shí)不難得到每個(gè)可行航班環(huán)的飛行時(shí)間Tj。設(shè)定目標(biāo)函數(shù)中共233個(gè)決策變量，除0～1整數(shù)約束之外，共69個(gè)約束條件，其中一個(gè)是對(duì)該機(jī)型機(jī)隊(duì)規(guī)模的約束。

表1 部分航班時(shí)刻表

表2 部分航班環(huán)

3．2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)的軟硬件配置為：3.0GHz cpu,10GB內(nèi)存，1000G硬盤，應(yīng)用軟件為matlab 7.0。用圖的深度優(yōu)先算法搜索可行航班集合R耗時(shí)0.133秒。在此基礎(chǔ)上，用分支定界法求解飛機(jī)排班問題共迭代58次，耗時(shí)0.097秒?？偤臅r(shí)應(yīng)為兩者之和，共耗時(shí)0.23秒。圖2中顯示的是12架飛機(jī)和68個(gè)航班序號(hào)的匹配結(jié)果。

圖2 飛機(jī)排班結(jié)果

表3中描述了將一周7天的航班進(jìn)行排班的耗時(shí)情況，每天的優(yōu)化均運(yùn)行10次以上，在用圖搜索法求每天可行航班環(huán)平均耗時(shí)大約0.152秒，用分支定界法求排班問題時(shí)平均耗時(shí)0.11秒，總平均耗時(shí)不到0.3秒?？梢?，在對(duì)每天80個(gè)以下航班數(shù)進(jìn)行排班時(shí)，采用這種方法具有較高的效率。并且，如果將每天分配結(jié)果以按周為單位進(jìn)行輪班，便可以得到一個(gè)月甚至一個(gè)季度的飛機(jī)排班表。

表3 一周的實(shí)驗(yàn)結(jié)果

4 結(jié)論

為了提高分支定界法的求解效率，本文給出了以下3個(gè)控制策略。首先在出現(xiàn)無可行解時(shí)，總是挑選下界最小的點(diǎn)進(jìn)行分支。其次，在有多個(gè)候選結(jié)點(diǎn)要分支時(shí)，選取目標(biāo)函數(shù)中系數(shù)最大的整數(shù)變量進(jìn)行分支。第三，在具體求解飛機(jī)排班問題時(shí)，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，讓分支定界法只在可能的范圍內(nèi)進(jìn)行搜索，從而使得計(jì)算量遠(yuǎn)遠(yuǎn)少于窮舉法。通過具體算例與遺傳算法進(jìn)行比較，證明該算法的可行性、有效性和實(shí)際應(yīng)用價(jià)值。

在實(shí)際求解過程中，若航班數(shù)為n，可行航班環(huán)數(shù)為m，從中發(fā)現(xiàn)，在最壞的情況下，分支定界法求解該問題的時(shí)間復(fù)雜度遠(yuǎn)小于原來的(O(n2)+m?。?。為了進(jìn)一步提高求解效率，可以考慮將分支定界法與現(xiàn)代啟發(fā)式算法相結(jié)合，開發(fā)出航班異常情況下的飛機(jī)排班以及實(shí)時(shí)航班調(diào)度算法。

[1]馬仲蕃.線性整數(shù)規(guī)劃的數(shù)學(xué)基礎(chǔ)[M].北京:科學(xué)出版社,1998.

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

[3]Bazargan M.Airline Operations and Scheduling[M].USA:Ashgate Publishing Limited,2006.

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

[5]孫宏,杜文.飛機(jī)排班數(shù)學(xué)規(guī)劃模型[J].交通運(yùn)輸過程學(xué)報(bào),2004,4(3).

[6]朱星輝,朱金福,高強(qiáng).基于動(dòng)態(tài)列生成算法的飛機(jī)排班問題研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2014,(19).

[7]賈寶惠,逯艷華,李耀華.基于交叉粒子群算法的飛機(jī)指派問題研究[J].中國(guó)民航大學(xué)學(xué)報(bào),2015,(14).

[8]吳東華,夏洪山.基于航空公司成本最小化的飛機(jī)排班問題模型與算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2014,(1).

F224

A

1002-6487（2017）20-0060-04

國(guó)家自然科學(xué)基金資助項(xiàng)目（60672167）；國(guó)家軟科學(xué)研究計(jì)劃資助項(xiàng)目（2008GXQ6B141）

范永?。?970—），男，江蘇南京人，博士，講師，研究方向：宏觀和制度經(jīng)濟(jì)學(xué)。

（通訊作者）吳東華（1973—），女，江蘇南京人，博士，講師，研究方向：宏觀和制度經(jīng)濟(jì)學(xué)。

(責(zé)任編輯/易永生)