張培（中國民航大學(xué)理學(xué)院，天津 300300）

不確定環(huán)境下機(jī)組調(diào)度問題的規(guī)劃模型及算法

張培
（中國民航大學(xué)理學(xué)院，天津 300300）

傳統(tǒng)航空公司機(jī)組調(diào)度模型大多是確定的，然而實(shí)際上航班通常會(huì)受各種不確定因素影響而產(chǎn)生延誤的影響。本文考慮隨機(jī)因素，將機(jī)組排班的配對(duì)尋優(yōu)建成以成本最小和旅客滿意度最大為目標(biāo)的多目標(biāo)隨機(jī)機(jī)會(huì)約束規(guī)劃模型，并構(gòu)造混合智能算法來尋找最優(yōu)解。案例研究的結(jié)果顯示，模型和算法對(duì)于實(shí)際中機(jī)組配對(duì)的尋優(yōu)是可行的。

機(jī)組配對(duì) 不確定 多目標(biāo) 機(jī)會(huì)約束規(guī)劃 混合遺傳算法

【Abstract】For the traditional airlines ，crew scheduling models are usually deterministic，in fact the flight is usually affected by many uncertain factors and cause delays. This paper take the uncertain factors into consideration to build a multi-objective stochastic chance constrained programming crew pairings model of minimum cost and maximum passenger satisfaction，and constructs a hybrid intelligent algorithm to find the optimal solution. the results of a case study show that the model and algorithm are feasible in practice for crew scheduling problems.

【Key words】crew pairings problems； uncertainty； multi-objective； chance constrained programming；hybrid intelligent algorithm

1　引言

由于民航業(yè)的特點(diǎn)和競(jìng)爭(zhēng)的需要，航空公司的航班運(yùn)行控制對(duì)運(yùn)籌學(xué)的許多分支理論和方法，特別是最優(yōu)化技術(shù)有著非常迫切的需求。航空公司計(jì)劃和控制系統(tǒng)是圍繞航班來運(yùn)作的，運(yùn)行控制部門通過使用輔助決策系統(tǒng)和利用各種現(xiàn)代優(yōu)化技術(shù)建立符合實(shí)際問題的調(diào)度模型，采用有效的算法、軟件來實(shí)現(xiàn)調(diào)度方案的快速生成。

在國內(nèi)外的文獻(xiàn)中，LOO［1］通過重新定義航班降落時(shí)間，建立一個(gè)用多目標(biāo)遺傳算法，（MOGA）來解決的多目標(biāo)優(yōu)化的模型。文獻(xiàn)［2］則引入一個(gè)懲罰函數(shù)，模擬實(shí)際運(yùn)營成本來進(jìn)行不確定環(huán)境下的機(jī)組調(diào)度問題研究。張英楠等人［3］引入機(jī)會(huì)約束構(gòu)建兼顧成本與航班運(yùn)行安全及旅客隨機(jī)需求的機(jī)型分配與機(jī)組排班模型。牟德一等人［4］提出機(jī)組延誤概率這一概念，給出機(jī)組延誤概率計(jì)算公式及方法，利用Matlab編程計(jì)算機(jī)組配對(duì)相關(guān)問題。Yen［5］一方面解決人員指派問題，另一方面加入懲罰函數(shù)來描述延誤。文獻(xiàn)［6］說明了確定性航班機(jī)組調(diào)度的綜合論述。

本文在考慮基本的機(jī)組配對(duì)基礎(chǔ)上，考慮實(shí)際運(yùn)營情況，考慮一個(gè)不確定環(huán)境下的的隨機(jī)變量。在航班約束以及機(jī)會(huì)成本約束條件下，建成多目標(biāo)機(jī)會(huì)約束模型，利用混合智能算法求解并結(jié)合案例加以實(shí)現(xiàn)。

2　隨機(jī)機(jī)會(huì)約束規(guī)劃

定義［8］：假設(shè)x是一個(gè)決策向量，ξ是一個(gè)隨機(jī)向量，是目標(biāo)函數(shù)，（j = 1，2，…，p）是沒有給出確定可行集的隨機(jī)約束函數(shù)。一個(gè)點(diǎn)x是可行的當(dāng)且僅當(dāng)事件｝的概率測(cè)度不小于 α，即違反約束條件的概率小于 （1-α），機(jī)會(huì)約束可以表示為如下的形式：

3　多目標(biāo)規(guī)劃

作為單目標(biāo)規(guī)劃的推廣，多目標(biāo)規(guī)劃定義為在一組約束條件下，優(yōu)化多個(gè)不同的目標(biāo)函數(shù)，其一般形式為：

其中 x=（x1，x2，…，xn）是一個(gè) n維決策向量，fi（x）（i=1，2，…，m）是目標(biāo)函數(shù)，gj（x）≤0（j=1，2，…，p）是系統(tǒng)約束條件。

4　問題描述與基本方法

4.1問題描述

機(jī)組調(diào)度的問題是航空公司制定航班計(jì)劃表的一個(gè)重要組成部分。在機(jī)型分配結(jié)束后，為每個(gè)機(jī)型的飛機(jī)配備相應(yīng)的機(jī)組人員來保證航班的飛行計(jì)劃。為每個(gè)機(jī)型尋找合適正確的機(jī)組不僅能提高飛行效率節(jié)約成本，在飛行安全方面也有一定的保障。

機(jī)組調(diào)度問題分為兩個(gè)部分：機(jī)組配對(duì)和機(jī)組輪班。機(jī)組配對(duì)是尋找適合的機(jī)組，機(jī)組輪班是配對(duì)以后，將具體的機(jī)組人員分配到配對(duì)中。在實(shí)際航空公司運(yùn)營中，為一個(gè)機(jī)組配備相關(guān)的人員很容易操作，而機(jī)組配對(duì)的過程很復(fù)雜，涉及到機(jī)場(chǎng)、城市、基地等等限制規(guī)則，所以本文重點(diǎn)研究機(jī)組配對(duì)。

4.2機(jī)組配對(duì)的一般要求

（1）公司排班人員根據(jù)計(jì)劃時(shí)刻表來對(duì)航班進(jìn)行合理配對(duì)；

（2）每個(gè)配對(duì)開始是從基地出發(fā)，結(jié)束則回到基地；

（3）每個(gè)配對(duì)所安排的航班盡量能在一天內(nèi)執(zhí)行完畢以節(jié)省機(jī)組在外費(fèi)用；

（4）為機(jī)組人員分配合理的航線。

5　不確定環(huán)境下機(jī)組配對(duì)的機(jī)會(huì)約束多目標(biāo)規(guī)劃模型與算法

表1　B757-200機(jī)型的航線調(diào)配

表2　B757-200機(jī)隊(duì)的28個(gè)合法機(jī)組配對(duì)

表3　B757-200機(jī)型的航班旅客可接受的降落時(shí)間窗

表4　B757-200機(jī)組配對(duì)的解

表5　B757-200機(jī)組配對(duì)的最優(yōu)解

本文將航班進(jìn)港時(shí)間設(shè)隨機(jī)變量，將總成本和顧客滿意度作為一個(gè)隨機(jī)機(jī)會(huì)約束。

5.1模型建立

5.1.1符號(hào)約定

本文涉及的上、下標(biāo)、參數(shù)、集合以及變量的實(shí)際意義，其中時(shí)間的計(jì)量單位是分鐘，成本的計(jì)量單位是元。

上標(biāo)和下標(biāo)變量：

j=配對(duì)下標(biāo)變量；

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

集合：

F：航班集合；

P：可行配對(duì)集合；

cj：機(jī)組配對(duì)j的成本；

blowerk：常駐地城市可k用最少機(jī)組數(shù)量；

bupperk：常駐地城市可k用最多機(jī)組數(shù)量；

ai，j：航班i由配對(duì)j負(fù)責(zé)則為1；否則為0；

hk，j：配對(duì)j的常駐地基地是城市k則為1；否則為0.

決策變量

xj：如果配對(duì)j是解的一部分則為1；否則為0。

5.1.2目標(biāo)函數(shù)和約束條件

目標(biāo)函數(shù)：航班晚點(diǎn)延誤等的頻繁發(fā)生會(huì)引起旅客滿意度的下降。因此，綜合航空公司飛行成本和旅客的滿意度，本模型將航班總成本和顧客滿意度作為目標(biāo)函數(shù)。

由此，模型的目標(biāo)函數(shù)可以寫成下式：

本模型共有2組約束條件：

約束一：航班到港時(shí)間在旅客可接受的時(shí)間范圍內(nèi)。

航班計(jì)劃的固定性與隨機(jī)擾亂因素相互作用，導(dǎo)致了航班延誤。在每個(gè)航班對(duì)每個(gè)航班中，我們希望旅客以置信度水平0β在其可容忍的時(shí)間窗口內(nèi)進(jìn)港，于是機(jī)會(huì)約束為：

約束二：航班覆蓋。

每個(gè)機(jī)組配對(duì)候選方案均覆蓋了一定的航班數(shù)量，我們必須保證每個(gè)航班僅被覆蓋一次。

例如，航班114在配對(duì)9、12、20和27中出現(xiàn)，因此要覆蓋這個(gè)航班則有： x9+x12+x20+x27=1

同理，所有航班i均可表達(dá)為上述形式。

5.1.3不確定環(huán)境下機(jī)會(huì)約束規(guī)劃模型

根據(jù)上節(jié)的分析，得到如下模型：

5.2模型分析與混合智能算法

本模型是在基于整數(shù)規(guī)劃中，加入了隨機(jī)機(jī)會(huì)約束。模型有兩個(gè)目標(biāo)函數(shù)，模型混合智能算法的步驟如下：

步驟一：根據(jù)機(jī)組配對(duì)的規(guī)則和過濾條件得到所有的合法機(jī)組配對(duì)；

步驟二：根據(jù)航班起飛降落時(shí)刻、機(jī)型、乘客等等，確定模型參數(shù)和集合的取值范圍；

步驟三：通過約束二確定航班的覆蓋范圍；

步驟四：利用混合智能算法來模擬輸入輸出數(shù)據(jù)，訓(xùn)練神經(jīng)元等來實(shí)現(xiàn)約束一。

本模型的步驟三和步驟四的求解均由Matlab編程實(shí)現(xiàn)。

6　案例分析

我們利用《航空公司運(yùn)營規(guī)劃與管理》書中B757-200機(jī)隊(duì)的機(jī)組配對(duì)來進(jìn)行案例分析。表1為該機(jī)型所有的航班調(diào)配。根據(jù)Ultimate Air公司對(duì)機(jī)組配對(duì)的要求（每個(gè)飛行出勤不能超過8小時(shí)；一個(gè)調(diào)配安排的最長時(shí)間為兩天；機(jī)組的常駐基地是JFK機(jī)場(chǎng)；等待銜接時(shí)間的上下限分別為10分鐘和3小時(shí)。），我們可以生成28合法機(jī)組配對(duì)，即表2。

航班延誤是指航班降落時(shí)間比計(jì)劃降落時(shí)間（航班時(shí)刻表上的時(shí)間）延遲30分鐘以上或航班取消的情況。所以我們定義顧客可接受的進(jìn)港時(shí)間窗為計(jì)劃降落時(shí)間前后三十分鐘，即表3。

假設(shè)在旅客可接受的時(shí)間窗口內(nèi)航班降落的置信水平為90%，即有機(jī)會(huì)約束：

同時(shí)，12航班全部覆蓋且僅被覆蓋一次，則有約束：

我們?cè)谏鲜鰞杉s束條件下極小化總成本，極大化顧客滿意度。利用混合智能算法求解最優(yōu)值。

算法步驟：

步驟1用隨機(jī)模擬技術(shù)為機(jī)會(huì)約束不確定函數(shù)產(chǎn)生輸入輸出數(shù)據(jù)，

步驟2 根據(jù)產(chǎn)生的輸入輸出數(shù)據(jù)來訓(xùn)練一個(gè)神經(jīng)元網(wǎng)絡(luò)逼近不確定函數(shù)。

步驟3初始化pop_size個(gè)染色體，并利用訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)檢驗(yàn)染色體的可行性。

步驟4通過交叉好變異操作更新染色體，并利用訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)計(jì)算所有染色體的目標(biāo)值。

步驟5根據(jù)目標(biāo)值計(jì)算每個(gè)染色體的適應(yīng)度。

步驟6通過旋轉(zhuǎn)賭輪選擇染色體。

步驟7重復(fù)步驟4到步驟7直到完成給定的循環(huán)次數(shù)。

步驟8給出最好的染色體作為最優(yōu)解。

首先利用隨機(jī)模擬為不確定函數(shù) U產(chǎn)生輸入輸出函數(shù)，根據(jù)訓(xùn)練樣本，我們訓(xùn)練一個(gè)神經(jīng)元網(wǎng)絡(luò)來逼近不確定函數(shù) U。然后，我們把訓(xùn)練好的神經(jīng)元網(wǎng)絡(luò)嵌入遺傳算法產(chǎn)生混合智能算法。

通過運(yùn)行混合智能算法，我們得到表4。

在總成本均為12的情況下，我們選擇旅客滿意度最高的方案2，即表5為最優(yōu)解：

7　結(jié)語

本文是在不確定環(huán)境下，將機(jī)組排班的尋優(yōu)建成以成本最小和旅客滿意度最大為目標(biāo)的多目標(biāo)機(jī)會(huì)約束規(guī)劃模型，并采用混合智能算法來尋找最優(yōu)解。在保證最小成本下，使旅客在可接受的時(shí)間窗內(nèi)降落機(jī)場(chǎng)。在航班所有可行機(jī)組配對(duì)后，利用Matlab編程求解，得到最優(yōu)解。案例表明，該模型和算法對(duì)于實(shí)際中機(jī)組配對(duì)的尋優(yōu)是可行的。

［1］Loo H.，Chul U.，A multi-objective genetic algorithm for robust flight scheduling using simulation ［M］，ScienceDirect，2007.

［2］Schaefer A J，Johnson E J，Kleywegt A J，et al.Airline crew scheduling under uncertainty ［J］.Transportation Science，2005，39（3）：210-223.

［3］張英楠，牟德一，李輝.基于機(jī)會(huì)約束規(guī)劃的航班應(yīng)急調(diào)度問題研究［J］.中國安全科學(xué)學(xué)報(bào)，2012.

［4］牟德一，王志新，夏群.基于機(jī)組延誤概率的魯棒性機(jī)組配對(duì)問題［J］.系統(tǒng)管理學(xué)報(bào)，2011，20（2）：207-212.

［5］Yen J，Birge J，A stochastic programing approach to the airline crew scheduling problem ［D］.University of Washington，2000.

［6］Barnhart，C.A.Cohn，E.L.Johnson，D.Klabjan，G.L.Nemhauser，P.H. Vance.Airline crew scheduling［M］.R.M.Hall，ed.Hand book in transportation Science，Kluwer Scientific Publishers，2002：517-560.

［7］Charnes A，Cooper W.Chance-constrained programming ［J］.Management Science，1959，6（1）：73-79.

［8］劉寶碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用［M］.北京：清華大學(xué)出版社，2003.

［9］彭錦，劉保碇，不確定規(guī)劃的研究現(xiàn)狀及其發(fā)展前景［J］.運(yùn)籌于管理，2002，11（2）：1-10.

［10］楊立興.不確定環(huán)境中的指派問題及其混合智能算法［D］.保定：河北大學(xué)，2002.

［11］馬蘇德-巴扎爾甘（美）.航空公司運(yùn)營規(guī)劃與管理［M］.邵龍，王美佳，譯.北京：中國民航出版社，2006：39-56，81-91.

張培（1994—），男，河南省商丘人，學(xué)歷：本科。工作單位：中國民航大學(xué)。