范永俊，吳東華

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

基于分支定界法的飛機均衡排班計劃求解

范永俊1，吳東華2

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

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

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

0 引言

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

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

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

1 算法背景

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

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

1.1.1 分支

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

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

1.1.2 松弛

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

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

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

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

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

1.1.3 定界

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

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

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

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

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

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

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

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

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

2 飛機排班計劃求解

2．1 飛機排班計劃描述

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

飛機排班流程[5]見圖1所示。

圖1 飛機排班流程

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

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

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

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

M=維護基地集合

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

i=航班下標變量

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

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

Q=當天所有航班總飛行時間

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

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

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

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

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

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

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

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

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

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

3 算例分析

3．1 參數(shù)設定

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

表1 部分航班時刻表

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

3．2 實驗結(jié)果

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

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

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

表3 一周的實驗結(jié)果

4 結(jié)論

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

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

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

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

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

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

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

[6]朱星輝,朱金福,高強.基于動態(tài)列生成算法的飛機排班問題研究[J].數(shù)學的實踐與認識,2014,(19).

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

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

F224

A

1002-6487（2017）20-0060-04

國家自然科學基金資助項目（60672167）；國家軟科學研究計劃資助項目（2008GXQ6B141）

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

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

(責任編輯/易永生)