基于BP 方程算法的多機型機組恢復時空網(wǎng)絡模型

張 青 ，馬永秀 ，楊正全 ，陳增強 ，2

（1.中國民航大學理學院，天津 300300；2.南開大學計算機與控制工程學院，天津 300350）

基于BP 方程算法的多機型機組恢復時空網(wǎng)絡模型

張 青1，馬永秀1，楊正全1，陳增強1，2

（1.中國民航大學理學院，天津 300300；2.南開大學計算機與控制工程學院，天津 300350）

航空公司工作中的一個重要部分就是不正常機組排班恢復，為減少機組排班不正常對航班運行計劃的影響，以航空公司資源浪費最小為優(yōu)化目標，在分析不正常機組排班要滿足的客觀約束條件下，建立了多機型不正常機組排班恢復的時空網(wǎng)絡數(shù)學模型，并針對國內(nèi)某航空公司的實際運營數(shù)據(jù)運用該模型進行實例分析，利用最小頂點覆蓋（MDS）和BP方程法求解。結(jié)果表明：用MDS和BP方程法不僅加速了機組排班恢復的時間，更增加了機組排班恢復的魯棒性。該方法利用完全相關結(jié)構，當遇到某些突發(fā)情況時，機組排班能自動隨之調(diào)整，操作起來方法簡便，適用面廣，并且系統(tǒng)性強，便于普及和推廣。

BP方程；最小頂點覆蓋；機組排班恢復；能量函數(shù)；時空網(wǎng)絡模型

?

民航運輸作為現(xiàn)代運輸業(yè)之一，在國民經(jīng)濟中占有重要地位。長期以來，不正常機組排班恢復是航空公司運行控制的重要內(nèi)容之一，是航空公司的主要研究課題。合理的機組排班恢復不僅避免了航班的再次延誤，還能夠提高機隊的利用效率，有效地降低運營和閑置成本。機組排班恢復問題的優(yōu)化目標主要包括成本最小、航班盡早恢復等，約束條件要滿足航班覆蓋，每個飛行出勤不超過8 h，等待銜接時間在允許的上、下限之間，第2天第1個航班的起飛機場與前一天晚上最后一個航班的目的地相同等要求。

針對不正常機組恢復，主要有兩個研究方向：事后研究和事前研究，而我們主要針對后者。事前研究是指在機組排班計劃編制階段，設計機組排班計劃的魯棒性，提高機組排班計劃的抗干擾能力。雖然研究機組排班問題的文獻很多，但不正常機組排班恢復問題的研究卻非常少。Ellis L Johnson[1]討論了單個機組延誤無法正常連接后續(xù)航班任務的問題，給出了單機組恢復問題的數(shù)學模型和解決方案；Wei等[2]建立了機組恢復的多商品整數(shù)網(wǎng)絡模型，設計了基于分枝定界的啟發(fā)示算法；Stojkovic等[3]研究了以成本最小為目標函數(shù)，在給定航班計劃下恢復機組任務串的問題，將列生成算法植入分枝定界搜索樹進行求解；Lettovsky等[4]提出了一種最小化機組恢復成本的方法，通過定義恢復時間和受擾機組的最大數(shù)量，用列生成算法選擇最小的機組任務串集合；Medard等[5]從機組成員角度恢復機組，先構建一個整數(shù)規(guī)劃模型，求解機組配對，然后基于任務期的網(wǎng)絡上求K最短路問題；Rudiger Nissen和KnutHaase[6]針對歐洲航空公司的需要提出了一個基于執(zhí)勤期的機組恢復模型，采用分枝定價法和列生成法求解問題；北美洲和歐洲的機組薪酬制度不同。GUOYufeng等[7]針對地域的薪酬制度和航空公司的運作特點，對機組恢復問題進行了研究。其中，某些機組排班恢復的研究已取得了很好的成果，然而這些理論研究成果在實際應用中卻沒能發(fā)揮預期的作用，并且操作起來也比較困難，這是由于航空運輸系統(tǒng)是個復雜的系統(tǒng)，不正常機組排班涉及的各種資源之間是相互依賴和影響的。

目前對不正常機組恢復的研究，利用約束規(guī)劃方法，思路清晰，模型表達簡潔，一直是學術界研究的重點，也取得了很多成果。但其規(guī)劃方法比較固定單一，面對復雜的機組排班問題運行時間非常長，而且很難找到有效的求解方法，本文對不正常機組排班進行了研究，運用頂點覆蓋方法給出了機組可執(zhí)行的航班串，然后采用BP方程，將非線性的NP難多項式問題轉(zhuǎn)化成線性多項式求解問題。不僅降低了運算的復雜度，而且首次將物理方法運用到了求解數(shù)學模型上，成功解決了非線性式子編程復雜的缺點，并且為機組排班的進一步完善創(chuàng)建了很大的研究空間。

1 問題描述

航空公司不正常航班恢復通常包括以下4個問題：

1）對受擾航班時刻表通過延誤或取消航班來修復；

2）通過飛機交換、機型替換、調(diào)機等進行飛機恢復；

3）為受擾旅客重新安排其行程進行旅客恢復；

4）采用機組交換、加機組、備份機組等策略進行機組恢復。

前3個問題目前都有很多學者對其進行研究并取得一定的成果，并不納入本研究范圍。本文研究了一個飛行日內(nèi)不正常多機型機組恢復問題。多機型機組的恢復問題是一個從局部優(yōu)化達到全局優(yōu)化的問題，可被視為一個最小頂點覆蓋問題。但需動態(tài)地考慮其時空鏈接和空間銜接，并且不正常機組任務恢復最大的特點在于加機組策略的使用。即指一旦航班到位但沒有后續(xù)機組執(zhí)行時將機組像乘客一樣搭乘航班，去某機場執(zhí)行后續(xù)的航班任務。但無論是加機組航班還是機組實際執(zhí)行的航班，其航班銜接方式如圖1所示。故根據(jù)機組特點，設計以最小頂點覆蓋的方法利用信息傳遞來求解出最優(yōu)解。同時，為提高機組的工作效率，航空公司希望其有效飛行時間占總工作時間的比例越高越好，因此，模型中有關不正常機組恢復的部分不僅要考慮時間合法性的約束，并且為了降低成本還要盡量減少加機組、備用機組等策略的使用。

圖1 航班銜接方式Fig.1 Flight connection mode

2 時空網(wǎng)絡數(shù)學模型

本文在構造時空網(wǎng)絡圖中，用節(jié)點表示飛機可能停留的機場。用連接兩個節(jié)點的邊表示航班，每條邊的出發(fā)點都表示在該點有可利用的機組。因此，有的航班邊在網(wǎng)絡圖中會用推遲后的邊表示，產(chǎn)生使用加機組或使用備用機組成本。從而將不正常機組恢復成本問題利用時空網(wǎng)絡圖[8-9]轉(zhuǎn)換成數(shù)學模型。這樣便將不正常機組恢復問題轉(zhuǎn)換成了求解成本流最小問題。

2.1 符號定義

以下是對數(shù)學模型中使用到的上下標、集合、參數(shù)、變量的解釋：

上下標指示 z為正常機組指示；j為加機組指示；b為備份機組指示；s為機組基地指示；k為機型下標指示；r為配對下標變量指示；i為航班下標變量指示。

集合 F為航班集合；P為可行配對集合；S為機組基地集合；Z為正常機組集合；J為加機組集合；B為備份機組集合。

2.2 模型建立

數(shù)學模型為

模型中式（1）為目標函數(shù)，其表示使航空公司資源浪費最小，分別包括機組閑置成本、加機組成本和備用機組成本；式（2）為航班覆蓋的約束，即保證在一個航班上機組，加機組和備用機組至少有一個；式（3）為機組執(zhí)照約束，即對機組要執(zhí)行的航班，必須持有該航班對應飛機機型的執(zhí)照；式（4）為0，1整數(shù)約束。

3 模型算法

3.1 最小頂點覆蓋問題

頂點覆蓋問題用于工程應用領域許多實際的資源最優(yōu)配置問題，也是計算復雜性理論研究領域最基本的NP完備問題之一。Hartmann和Weigt[10]在專著中全面和詳盡地探討了頂點覆蓋問題的統(tǒng)計物理理論和算法。

考慮一個網(wǎng)絡 G，其由 N 個節(jié)點（i=1，2，…，N）和這些結(jié)點之間的M條邊構成，每一條邊連接兩個不同的節(jié)點。網(wǎng)絡G的覆蓋是由G中的一部分節(jié)點所構成的一個集合，其具有這樣的性質(zhì)，即G中每一條邊的兩個端點至少有一個端點是其元素?？蓪⒕W(wǎng)絡G想象為一個大型博物館，網(wǎng)絡G的每條邊對應于該博物館的一條走廊，網(wǎng)絡G的每個節(jié)點對應于這些走廊的終點以及兩條或多條走廊的交匯點。在博物館的一些走廊終點和走廊交匯點設置了安保崗，有保安在崗上監(jiān)視展品的安全，防止意外情況發(fā)生。為不留死角，每一條走廊必定有一頭設置了安保崗。每一種滿足這一約束的安保崗設置方式，顯然就對應于網(wǎng)絡G的一個覆蓋。網(wǎng)絡G的平庸覆蓋包含所有N個節(jié)點。顯然平庸覆蓋有冗余存在，是不經(jīng)濟的。例如：一個小網(wǎng)絡（包含N=6個節(jié)點和M=9條邊）的3種不同覆蓋方式，其能量分別為6（平庸覆蓋）、4和3（最小覆蓋）。該網(wǎng)絡只有1個最小覆蓋。

為了和自旋玻璃[11-12]聯(lián)系起來，定義N節(jié)點構型：c={c1，c2，…，cN}，其中，ci∈{0，1}是定義在節(jié)點 i上的微觀狀態(tài)，ci=1表示節(jié)點i包含于覆蓋集合，ci=0則表示i不屬于覆蓋集合。從而構型C需滿足的約束條件為

其中，ci∈{0，1}對于一條邊（i，j）成立，就稱為該邊被覆蓋，反之就稱該邊未被覆蓋。那么進一步定義構型C的能量為

該能量就是C所對應的覆蓋集合中的節(jié)點數(shù)目。把滿足上述約束條件且能量為全局最小的構型C稱為網(wǎng)絡G的最小覆蓋。如圖2所示，網(wǎng)絡G的最小覆蓋一定存在，但不一定是唯一的。

對于任意給定的網(wǎng)絡G，尋找頂點最小覆蓋的算法步驟為：

1）初始化子網(wǎng)絡g=G，即g包含原網(wǎng)絡的所有節(jié)點和邊。初始化集合L，使其包含網(wǎng)絡g中所有連通度為1的節(jié)點。

2）如果集合L為空，則停止；反之，從L中挑選一個節(jié)點j，并覆蓋j在子網(wǎng)絡g中的最近鄰節(jié)點i。

3）將節(jié)點i在子網(wǎng)絡g的所有邊都從g中刪去；更新集合L，使之包含化簡后的子網(wǎng)絡g中所有連通度為1的節(jié)點。

4）重復步驟 1）～2）直至程序停止。

也就是說，找出目前網(wǎng)絡中一個連通度為1的節(jié)點并將連到其最近鄰節(jié)點上的邊都從網(wǎng)絡上除去，直到網(wǎng)絡中不再存在連通度為1的節(jié)點。

對于找到的不止一個的最小頂點覆蓋，通過分析其實現(xiàn)概率來進行選擇。考慮一個N→∞且平均連通度為常數(shù)C的隨機網(wǎng)絡G。那么隨便挑選一個網(wǎng)絡中節(jié)點i，則i的連通度ki=k的概率服從泊松分布，即，故可分以下幾種情況：

1）i的連通度ki=0，因而i無需被覆蓋，這種情況對應的概率為e-c。

2）i的連通度ki=1，假設其鄰近節(jié)點為j。

a）如果邊（i，j）可以在保留 i的情況下除去，那么節(jié)點i等價于沒有任何最近鄰節(jié)點，其無需被覆蓋。這種情況對應的概率為c e-cρ0，其中ρ0是網(wǎng)絡G的一條邊在其一個端點被保留情況下的概率。

b）如果 j的除邊（i，j）以外的其它邊都可以在保留i的情況下除去，j等價于連通度為1的節(jié)點，那么覆蓋節(jié)點j和節(jié)點i在能量上是等效的。

c）如果節(jié)點j不屬于上述兩種情況，那么覆蓋j是比覆蓋i更經(jīng)濟的方案，節(jié)點i無需被覆蓋，這種情況對應的概率為c e-c（1-ρ0-ρ1）。

3）i的連通度 ki≥ 2。

a）如果i所連的所有邊都可以在保留i的情況下被除去，那么i等價于沒有任何最近鄰節(jié)點，其無需被覆蓋，這種情況對應的概率為

b）如果i的ki條邊中，有ki-1條可以在保留i的情況下除去，而剩下的節(jié)點可設為j，那么i和j都等價于連通度為1的節(jié)點，邊（i，j）對系統(tǒng)基態(tài)能量的貢獻為1，這種情況對應的概率為

c）如果i的ki條邊中，有ki-1條可以在保留i的情況下除去，而剩下的節(jié)點可設為j，不能被除去，那么i無需被覆蓋，這種情況對應的概率為

d）如果i的ki條邊中，至少有2條可以在保留i的情況下除去，那么i可以被除去，且覆蓋它是最經(jīng)濟的，這種情況對應的概率為

由上述分析可知，任意選取的節(jié)點i屬于不可除去的概率為

3.2 BP方程

BP（Bethe-Peierls）方程[13]在自旋玻璃統(tǒng)計物理和網(wǎng)絡科學中有廣泛的應用。要了解BP方程及其應用有以下幾個內(nèi)容。首先要知道能量函數(shù)[14-15]和因素網(wǎng)絡，為方便起見，假定每個粒子（i=1，2，…，N）的微觀狀態(tài)是分立的且只有兩個可能的態(tài)，用自旋σi=+1和σi=-1來表示。N個粒子自旋態(tài)的集合構成系統(tǒng)的一個微觀構型{σ1，σ2，…，σN}。故能量函數(shù)為

并且常常用因素網(wǎng)絡來直觀地描述一個多變量系統(tǒng)中的統(tǒng)計關聯(lián)[16-18]。其次是配分函數(shù)和基態(tài)構型。當系統(tǒng)達到平衡后，其宏觀性質(zhì)就不再隨時間而改變，而系統(tǒng)微觀構型σ的平衡概率分布為玻爾茲曼分布，即

其中：β為逆溫度，其與溫度呈反比關系，β≡（kBT）-1；Ψi≥0是變量節(jié)點i感受到的外場所貢獻的權重因子，而Ψα≥0是內(nèi)部相互作用α所貢獻的權重因子，其表達式分別為

Z是玻爾茲曼分布的歸一化系數(shù)，稱為配分函數(shù)，即

在溫度T趨向于0時，一個達到平衡的宏觀系統(tǒng)的平均能量將趨向于系統(tǒng)的基態(tài)能量，記為E0?；鶓B(tài)能量是系統(tǒng)所有微觀構型所對應的能量最小值，即

下面通過一個簡單模型系統(tǒng)來介紹這一方程。隨機規(guī)則網(wǎng)絡中包含N個變量節(jié)點，每個變量節(jié)點i都有K個最近鄰變量節(jié)點，因而其受到K個自旋耦合作用影響。該鐵磁系統(tǒng)的一個自旋微觀構型σ的能量為

其中：網(wǎng)絡中所有邊（i，j）上的自旋耦合常數(shù)都相同（=J）。

任意節(jié)點i的自旋邊緣概率分布的定義式為微觀構型能量E（σ）可分解成兩部分

其中：?i表示節(jié)點i的最近鄰變量節(jié)點組成的集合，而σ（cs）表示i之外的所有其它N-1個變量節(jié)點的自旋構型，即 σ（cs）= σ/σi={σ1，…，σi-1，σi+1，…，σN}。能量E（cs）是將變量節(jié)點i從網(wǎng)絡中刪除后剩下的能量，其與節(jié)點i的自旋σ1無關，是所有其它N-1個變量節(jié)點自旋的函數(shù)，即

其中：?ji表示變量節(jié)點j除節(jié)點i之外的所有其它最近鄰變量節(jié)點組成的集合，從而有

其中，qi（σ）即為要求的BP方程核心，在隨機網(wǎng)絡系統(tǒng)中，如果系統(tǒng)的特征關聯(lián)長度有限，那么BP近似對于這樣的隨機網(wǎng)絡在系統(tǒng)熱力學極限下就趨于精確。

3.3 基于BP方程求解多機型機組恢復問題

鑒于多機型機組恢復問題是NP難解的，那么在較短的時間內(nèi)得到精確解仍會存在很大的困難，大多數(shù)學者都是基于優(yōu)化不同的規(guī)劃算法對此問題進行優(yōu)化，存在的不足之處就是操作起來都很困難，不易實現(xiàn)，并且對航班的銜接也有要求，不能使多機型機組恢復問題簡便快捷的實現(xiàn)。而且大多數(shù)優(yōu)化算法大同小異，進步成效并不大。本文通過將機組看成節(jié)點，利用最小頂點覆蓋的方法得到現(xiàn)執(zhí)行機組與執(zhí)行后續(xù)航班機組之間的連接關系。將機組恢復需滿足的約束條件轉(zhuǎn)化成能量函數(shù)，考慮每個選擇的概率從而得出最優(yōu)選擇。將機組恢復轉(zhuǎn)化的因子如圖3所示。

圖3 頂點覆蓋因子圖Fig.3 Vertex cover factor diagram

故所求概率函數(shù)為

4 實例計算及結(jié)果分析

航空公司中不正常多機型機組排班恢復是在飛機路線恢復完成之后進行的，本文采用MatlabR2014a優(yōu)化軟件進行求解。給出案例如表1所示。

表1 機組排班表Tab.1 Crew schedule

本文在計算時基于以下假設：①機組閑置成本按照航班取消或航班推遲后機組閑置總時間乘以每分鐘的閑置成本，這里每分鐘閑置成本按120元計算。②機組換機型飛行時，若用大飛機換小飛機，由于飛機比原來容量大，因此產(chǎn)生換機成本，并將該成本加到加機組成本中合并計算；反之，用小飛機換大飛機則不產(chǎn)生換機成本。例如，若B737-800代替B757-200，那么飛機容量變大則要產(chǎn)生還擊成本，這里規(guī)定加機組成本為1 000元。③若使用備用機組，則按照每次10 000元計算，這個取值基于換機型時產(chǎn)生的設備及人工成本，以及對于機組成員的工資補償。

根據(jù)算例得到的因子如圖4所示。

圖4 機組恢復因子圖Fig.4 Crew recovery factor graph

那么，可求得配分函數(shù)Z和相應的概率函數(shù)為

所以最終花費為人民幣168 676元。

5 結(jié)語

本文針對發(fā)生突發(fā)事件不正常機組排班恢復的情況，根據(jù)算例數(shù)據(jù)，建立了多機型時空網(wǎng)絡數(shù)學模型，通過最小頂點覆蓋方法，利用BP方程求解，并用MatlabR2014a優(yōu)化軟件進行運算。實驗結(jié)果表明，通過優(yōu)化多機型時空網(wǎng)絡模型得出的成本較由于機組不到位航班再次取消的成本大幅度降低，并且維護了航空公司的信譽度，獲得了更多隱性利益。但本文尚存在一些不足之處，模型只考慮了一少部分機組恢復約束條件，把松弛時間均設為合理的，并沒有考慮到對于大型機場的使用，這些均為進一步的研究方向。

[1]ELLIS L JOHNSON.Final Report to North Airlines on the Crew Recovery Problem[D].The Lugistic Institute,Georgia Institute of Technology,1994.

[2]WEI G,YUG,SONG M.Optimization model and algorithm for crew management during airline irregular operations[J].Journal of Combinatorial Optimization,1997,1(3):305-321.

[3]STOJKOVICM,SOUMISF,DESROSIERSJ.The operational airline crew scheduling problem[J].Transportation Science,1998,32(3):232-245.

[4]LETTOVSKY L,JOHNSON E L,NEMHAUSER G L.Airline crew recovery[J].Transportation Science,2000,34(4):337-348.

[5]MEDARDCP,SAWHNEYN.Airlinecrew scheduling from planning to operations[J].European Journal of Operational Research,2007,183(3):1013-1027.

[6]NISSEN R,HAASE K.Duty-period-based network model for crew reseheduling in European airlines[J].Journalof Scheduling,2006,9(3):255-278.

[7]GUO Yufeng,SUHL L,THIELM P.Solving the airline crew recovery problem by a genetic algorithm with local improvement[J].Operational Research,2005,5(2):241.

[8]MESQUITAM,PAIASA.Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem[J].Computers&Operations Research,2008,35(5):1562-1575.

[9]LETTOVSKY L,JOHNSON E L,NEMHAUSER G L.Airline crew recovery[J].Transportation Science,2000,34(4):337-348.

[10]HARTMANN A K,WEIGT M.Phase Transitions in Combinatorial Optimization Problems:Basics,Algorithms and Statistical Mechanics[M].Hobken,New Jersey:John Wiley&Sons,2006.

[11]GARDNERE.Spin glasseswith p-spin interactions[J].Nuclear Physics B,1985,257:747-765.

[12]KIRKPATRICK T R,THIRUMALAID.p-spin-interaction spin-glass models:connections with the structural glass problem[J].Physical Review B,1987,36(10):5388.

[13]李臘梅,吳漢松,王樹人.基于BP算法的模糊關系方程解法及仿真[J].計算機仿真,2007,24(4):149-151.

[14]王春妮,王 亞,馬 軍.基于亥姆霍茲定理計算動力學系統(tǒng)的哈密頓能量函數(shù)[J].物理學報,2016,65(24):240501-240501.

[15]周雪梅,李 輝,潘 多.基于能量函數(shù)的故障診斷方法與實驗[J].計算機工程與設計,2015,36(5):1385-1389.

[16]FREY B J.Graphical Models for Machine Learning and Digital Communication[M].Cambridge,Mass:MIT press,1998.

[17]KSCHISCHANG FR,FREY B J,LOELIGER H A.Factor graphs and the sum-product algorithm[J].IEEE Transactions on information theory,2001,47(2):498-519.

[18]許 鋒,潘 琦,王一嵐,等.工業(yè)過程多變量系統(tǒng)常規(guī)控制結(jié)構的頻域設計[J].清華大學學報(自然科學版),2016,56(4):448-452.

Crew recovery time-space network model with various types of airplanes based on BP equation algorithm

ZHANG Qing1,MA Yongxiu1,YANG Zhengquan1,CHEN Zengqiang1,2
（1.College of Science,CAUC,Tianjin 300300,China;2.College of Computer and Control Engineering,Nankai University,Tianjin 300350,China）

Aircrew scheduling recovery is an important part of airlines work.To abate the effect on flight operation planning from abnormal aircrew scheduling,various types of airplane crew recovery time-space network model is built up.Before the establishment,the objective constraint according to abnormal aircrew scheduling is analyzed.Meanwhile,the minimum of airlines operation aircrew recovery of multi-types of airplanes based on time-space network model and heuristic binary search algorithm on costs is the optimization goal.These models are applied to the actual operational data of some domestic airline to carry on the instance analysis.Minimum vertex cover and BP（Bethe-Peierls） equation algorithm are used to solve it.Results showed that the usage of minimum vertex cover and BP equation algorithm accelerate the aircrew scheduling recovery and increase the robustness of aircrew scheduling recovery.They adjust automatically when some factor changes.Whole-related structure is employed to help aircrew scheduling automatically adjust to urgent change of factors.This model is simple to operate and with strong systematicness to be used widely.

BP equation algorithm;minimum vertex cover;aircrew scheduling recovery;energy function;time-space network model

張青（1965—），女，天津人，教授，碩士，研究方向為復雜系統(tǒng)建模與優(yōu)化、多智能體系統(tǒng)等.

TP272

A

1674－5590（2017）05－0030－06

2017-01-10；

2017-02-22

國家自然科學基金項目（6157399）；天津市自然科學基金項目（14JCYBJC18700）；中央高?；究蒲袠I(yè)務費專項（3122015C025）

?

楊媛媛）