張 青 ，馬永秀 ，楊正全 ，陳增強(qiáng) ，2

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

基于BP 方程算法的多機(jī)型機(jī)組恢復(fù)時(shí)空網(wǎng)絡(luò)模型

張 青1，馬永秀1，楊正全1，陳增強(qiáng)1，2

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

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

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

?

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

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

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

1 問題描述

航空公司不正常航班恢復(fù)通常包括以下4個(gè)問題：

1）對受擾航班時(shí)刻表通過延誤或取消航班來修復(fù)；

2）通過飛機(jī)交換、機(jī)型替換、調(diào)機(jī)等進(jìn)行飛機(jī)恢復(fù)；

3）為受擾旅客重新安排其行程進(jìn)行旅客恢復(fù)；

4）采用機(jī)組交換、加機(jī)組、備份機(jī)組等策略進(jìn)行機(jī)組恢復(fù)。

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

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

2 時(shí)空網(wǎng)絡(luò)數(shù)學(xué)模型

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

2.1 符號定義

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

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

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

2.2 模型建立

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

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

3 模型算法

3.1 最小頂點(diǎn)覆蓋問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）i的連通度 ki≥ 2。

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

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

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

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

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

3.2 BP方程

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

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

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

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

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

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

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

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

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

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

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

3.3 基于BP方程求解多機(jī)型機(jī)組恢復(fù)問題

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

圖3 頂點(diǎn)覆蓋因子圖Fig.3 Vertex cover factor diagram

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

4 實(shí)例計(jì)算及結(jié)果分析

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

表1 機(jī)組排班表Tab.1 Crew schedule

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

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

圖4 機(jī)組恢復(fù)因子圖Fig.4 Crew recovery factor graph

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

所以最終花費(fèi)為人民幣168 676元。

5 結(jié)語

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

[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算法的模糊關(guān)系方程解法及仿真[J].計(jì)算機(jī)仿真,2007,24(4):149-151.

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

[15]周雪梅,李 輝,潘 多.基于能量函數(shù)的故障診斷方法與實(shí)驗(yàn)[J].計(jì)算機(jī)工程與設(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é)構(gòu)的頻域設(shè)計(jì)[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),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—），女，天津人，教授，碩士，研究方向?yàn)閺?fù)雜系統(tǒng)建模與優(yōu)化、多智能體系統(tǒng)等.

TP272

A

1674－5590（2017）05－0030－06

2017-01-10；

2017-02-22

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

?

楊媛媛）