不確定環境下機組調度問題的規劃模型及算法

【摘要】傳統航空公司機組調度模型大多是確定的，然而實際上航班通常會受各種不確定因素影響而產生延誤的影響。本文考慮隨機因素，將機組排班的配對尋優建成以成本最小和旅客滿意度最大為目標的多目標隨機機會約束規劃模型，并構造混合智能算法來尋找最優解。案例研究的結果顯示，模型和算法對于實際中機組配對的尋優是可行的。

【關鍵詞】機組配對不確定多目標機會約束規劃混合遺傳算法

【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 引言

由于民航業的特點和競爭的需要，航空公司的航班運行控制對運籌學的許多分支理論和方法，特別是最優化技術有著非常迫切的需求。航空公司計劃和控制系統是圍繞航班來運作的，運行控制部門通過使用輔助決策系統和利用各種現代優化技術建立符合實際問題的調度模型，采用有效的算法、軟件來實現調度方案的快速生成。

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

本文在考慮基本的機組配對基礎上，考慮實際運營情況，考慮一個不確定環境下的的隨機變量。在航班約束以及機會成本約束條件下，建成多目標機會約束模型，利用混合智能算法求解并結合案例加以實現。

2 隨機機會約束規劃

定義[8]：假設x是一個決策向量，ξ是一個隨機向量， 是目標函數， （j = 1，2，…，p）是沒有給出確定可行集的隨機約束函數。一個點x是可行的當且僅當事件 的概率測度不小于 ，即違反約束條件的概率小于 ，機會約束可以表示為如下的形式：

3 多目標規劃

作為單目標規劃的推廣，多目標規劃定義為在一組約束條件下，優化多個不同的目標函數，其一般形式為：

其中 是一個 維決策向量， 是目標函數， 是系統約束條件。

4 問題描述與基本方法

4.1 問題描述

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

機組調度問題分為兩個部分：機組配對和機組輪班。機組配對是尋找適合的機組，機組輪班是配對以后，將具體的機組人員分配到配對中。在實際航空公司運營中，為一個機組配備相關的人員很容易操作，而機組配對的過程很復雜，涉及到機場、城市、基地等等限制規則，所以本文重點研究機組配對。

4.2 機組配對的一般要求

（1） 公司排班人員根據計劃時刻表來對航班進行合理配對；

（2） 每個配對開始是從基地出發，結束則回到基地；

（3） 每個配對所安排的航班盡量能在一天內執行完畢以節省機組在外費用；

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

5 不確定環境下機組配對的機會約束多目標規劃模型與算法

本文將航班進港時間設隨機變量，將總成本和顧客滿意度作為一個隨機機會約束。

5.1 模型建立

5.1.1 符號約定

本文涉及的上、下標、參數、集合以及變量的實際意義，其中時間的計量單位是分鐘，成本的計量單位是元。

上標和下標變量：

j = 配對下標變量；

i = 航班下標變量。

集合：

F：航班集合；

P：可行配對集合；

K：機組常駐基地集合；

參數：

：配對j航班i，旅客可容忍的進港時間窗；

：機組配對j的成本；

：常駐地城市可k用最少機組數量；

：常駐地城市可k用最多機組數量；

：航班i由配對j負責則為1；否則為0；

：配對j的常駐地基地是城市k則為1；否則為0.

決策變量

：如果配對j是解的一部分則為1；否則為0。

5.1.2 目標函數和約束條件

目標函數：航班晚點延誤等的頻繁發生會引起旅客滿意度的下降。因此，綜合航空公司飛行成本和旅客的滿意度，本模型將航班總成本和顧客滿意度作為目標函數。

由此，模型的目標函數可以寫成下式：

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

約束一：航班到港時間在旅客可接受的時間范圍內。

航班計劃的固定性與隨機擾亂因素相互作用，導致了航班延誤。在每個航班對每個航班中，我們希望旅客以置信度水平 在其可容忍的時間窗口內進港，于是機會約束為：

約束二：航班覆蓋。

每個機組配對候選方案均覆蓋了一定的航班數量，我們必須保證每個航班僅被覆蓋一次。

例如，航班114在配對9、12、20和27中出現，因此要覆蓋這個航班則有：

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

5.1.3 不確定環境下機會約束規劃模型

根據上節的分析，得到如下模型：

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

本模型是在基于整數規劃中，加入了隨機機會約束。模型有兩個目標函數，模型混合智能算法的步驟如下：

步驟一：根據機組配對的規則和過濾條件得到所有的合法機組配對；

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

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

步驟四：利用混合智能算法來模擬輸入輸出數據，訓練神經元等來實現約束一。

本模型的步驟三和步驟四的求解均由Matlab編程實現。

6 案例分析

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

表1 B757-200機型的航線調配

航班號 始發地 起飛時間 目的地 到達時間

105 SFO 09：50 JFK 15：20

110 ATL 08：10 JFK 10：40

111 ATL 13：10 JFK 15：40

113 MIA 09：10 JFK 12：10

114 MIA 14：30 JFK 17：30

118 BOS 15：00 JFK 16：30

125 JFK 07：25 SFO 09：55

131 JFK 09：30 ATL 12：00

133 JFK 18：05 ATL 20：35

135 JFK 15：10 MIA 18：10

136 JFK 18：10 MIA 21：10

138 JFK 12：30 BOS 14：00

表2 B757-200機隊的28個合法機組配對

機組配對序號 第一天的航班 第二天的航班 飛行時間

1 125 105 11

2 131 110 5

3 131 111 5

4 131 110-138-118 8

5 133 110 5

6 133 111 5

7 133 110-138-118 8

8 135 113 6

9 135 114 6

10 135 113-138-118 9

11 136 113 6

12 136 114 6

13 136 113-138-118 9

14 138 118 3

15 131-111 5

16 131-111-133 110 10

17 131-111-133 111 10

18 131-111-133 110-138-118 13

19 131-111-136 113 11

20 131-111-136 114 11

21 131-111-136 113-138-118 14

22 138-118 3

23 138-118-133 110 8

24 138-118-133 111 8

25 138-118-133 110-138-118 11

26 138-118-136 113 9

27 138-118-136 114 9

28 138-118-136 113-138-118 12

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

表3 B757-200機型的航班旅客可接受的降落時間窗

航班號 始發地 目的地 時間窗

105 SFO JFK [14：50，15：50]

110 ATL JFK [10：10，11：10]

111 ATL JFK [15：10，16：10]

113 MIA JFK [12：40，11：40]

114 MIA JFK [17：00，18：00]

118 BOS JFK [16：00，17：00]

125 JFK SFO [09：25，10：25]

131 JFK ATL [11：30，12：00]

133 JFK ATL [20：05，21：05]

135 JFK MIA [17：40，18：40]

136 JFK MIA [20：40，21：40]

138 JFK BOS [13：30，14：30]

假設在旅客可接受的時間窗口內航班降落的置信水平為90%，即有機會約束：

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

我們在上述兩約束條件下極小化總成本，極大化顧客滿意度。利用混合智能算法求解最優值。

算法步驟：

步驟1用隨機模擬技術為機會約束不確定函數產生輸入輸出數據，

步驟2 根據產生的輸入輸出數據來訓練一個神經元網絡逼近不確定函數。

步驟3初始化pop_size個染色體，并利用訓練好的神經元網絡檢驗染色體的可行性。

步驟4通過交叉好變異操作更新染色體，并利用訓練好的神經元網絡計算所有染色體的目標值。

步驟5根據目標值計算每個染色體的適應度。

步驟6通過旋轉賭輪選擇染色體。

步驟7重復步驟4到步驟7直到完成給定的循環次數。

步驟8給出最好的染色體作為最優解。

首先利用隨機模擬為不確定函數 產生輸入輸出函數，根據訓練樣本，我們訓練一個神經元網絡來逼近不確定函數 。然后，我們把訓練好的神經元網絡嵌入遺傳算法產生混合智能算法。

通過運行混合智能算法，我們得到表4。

表4 B757-200機組配對的解

方案 配對序號 總成本 旅客滿意度

1 1 12 90.2%

10

12

16

2 1 12 95.1%

8

20

23

3 1 12 92.6%

5

9

21

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

表5 B757-200機組配對的最優解

航班號 第一天 第二天

配對1 航班125 航班105

城市對 JFK-SFO SFO-JFK

起降時間 07：25-09：55 09：50-18：20

配對8 航班135 航班113

城市對 JFK-MIA MIA-JFK

起降時間 15：10-18：10 09：10-12：10

配對20 航班131 航班111 航班136 航班114

城市對 JFK-ATL ATL-JFK JFK-MIA MIA-JFK

起降時間 09：30-12：00 13：10-15：40 18：10-21：10 14：30-17：30

配對23 航班138 航班118 航班133 航班110

城市對 JFK-BOS BOS-JFK JFK-ATL ATL-JFK

起降時間 12：30-14：00 15：00-16：30 18：05-20：35 08：10-10：40

7 結語

本文是在不確定環境下，將機組排班的尋優建成以成本最小和旅客滿意度最大為目標的多目標機會約束規劃模型，并采用混合智能算法來尋找最優解。在保證最小成本下，使旅客在可接受的時間窗內降落機場。在航班所有可行機組配對后，利用Matlab編程求解，得到最優解。案例表明，該模型和算法對于實際中機組配對的尋優是可行的。

參考文獻：

[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].中國安全科學學報，2012.

[4]牟德一，王志新，夏群.基于機組延誤概率的魯棒性機組配對問題[J].系統管理學報，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]劉寶碇，趙瑞清，王綱.不確定規劃及應用[M].北京：清華大學出版社，2003.

[9]彭錦，劉保碇，不確定規劃的研究現狀及其發展前景[J].運籌于管理，2002，11（2）：1-10.

[10]楊立興.不確定環境中的指派問題及其混合智能算法[D].保定：河北大學，2002.

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

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