機(jī)組恢復(fù)問題的不確定規(guī)劃方法

李 寧，牟德一

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

機(jī)組恢復(fù)問題的不確定規(guī)劃方法

李 寧，牟德一

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

對航空公司來說應(yīng)急航班調(diào)度問題是最具挑戰(zhàn)性的活動之一.機(jī)組配對是規(guī)劃中十分重要的一環(huán).一個以延誤時間為不確定變量的機(jī)組恢復(fù)不確定規(guī)劃模型，在機(jī)組規(guī)劃被擾亂時，可以降低航空公司的成本.該模型的目標(biāo)為最小化旅客失望率，同時將估計延誤成本作為機(jī)會約束條件.運(yùn)用不確定理論，將該模型轉(zhuǎn)化為一個等價的確定性模型.并采用列生成算法解決該模型.該模型和算法有較強(qiáng)的實(shí)用性.

航空公司運(yùn)營；機(jī)組恢復(fù)；不確定規(guī)劃；列生成算法

航班計劃是一個實(shí)時優(yōu)化過程.當(dāng)航班出現(xiàn)延誤時，航空公司需重新制定新的航班計劃，以盡快恢復(fù)到正常的運(yùn)營狀態(tài)，同時保障公司利益損失最小.

機(jī)組恢復(fù)是航空公司運(yùn)營過程中的關(guān)鍵一環(huán)，許多學(xué)者從事機(jī)組調(diào)度問題的研究.Diana等[1]提出的策略是由三個優(yōu)化模型組成：整數(shù)規(guī)劃模型，集合劃分問題基礎(chǔ)上的模型和集合覆蓋問題基礎(chǔ)上的模型.Ranga等[2]討論并提出了一種獲得近似解的新方法.Joyce and John[3]描述了機(jī)組調(diào)度問題的隨機(jī)整數(shù)規(guī)劃模型，設(shè)計了一個改進(jìn)的分支定界算法，通過算例表明了算法的有效性.Ladislav[4]提供了一種新的機(jī)組恢復(fù)規(guī)劃方法.牟德一等[5]的機(jī)組恢復(fù)問題的隨機(jī)模型考慮到了概率的魯棒性.

這些學(xué)者主要應(yīng)用了確定性或隨機(jī)性的規(guī)劃方法.然而利用概率論的前提是該事件的實(shí)際頻率與所用概率分布基本一致.對于機(jī)組延誤問題我們難以得到充足數(shù)據(jù)，這時可以請專家給出相應(yīng)的信度.Liu[6](P113-132)提出的不確定理論可用來處理這種信度.本文應(yīng)用不確定規(guī)劃方法處理這些問題，優(yōu)化結(jié)果將更符合實(shí)際.

1 理論知識[6](P113-132)

定義1 若不確定變量ξ是不確定空間(Γ，L，M)到實(shí)數(shù)集上的一個可測函數(shù)，換而言之是對任何的Borel集B,集合

{ξ∈B}={γ∈Γ|ξ(γ)∈B}

是一個事件.

對一組不確定變量ξ1，ξ2，…，ξn和一個可測函數(shù)f，劉寶碇證明了ξ=f(ξ1，ξ2，…，ξn)

對ξ(γ)=f(ξ1(γ)，ξ2(γ)，…，ξn(γ))，?γ∈Γ.

定義2 不確定變量ξ的定義為

Φ(x)=M{ξ≤x},?x∈R

Peng和Iwamura證明了當(dāng)且僅當(dāng)除了Φ(x)≡0和Φ(x)≡1的單調(diào)遞增函數(shù)，函數(shù)Φ:R→[0,1]是一個不確定分布.

定理1 假設(shè)f(x,ξ1,ξ2,…,ξn)是對ξ1,ξ2,…,ξm嚴(yán)格單調(diào)增，對ξm+1,ξm+2,…,ξn嚴(yán)格單調(diào)減.并且gj(x,ξ1,ξ2,…,ξn)是對ξ1,ξ2,…,ξk嚴(yán)格單調(diào)增，對ξk+1,ξk+2,…,ξn嚴(yán)格單調(diào)減，j=1,2,…,p.如果ξ1,ξ2,…,ξn是獨(dú)立的不確定變量且分別具有不確定分布Φ1,Φ2,…,Φn，則不確定規(guī)劃模型

等于確定性規(guī)劃模型

2 模型描述

2.1 問題描述

當(dāng)不正常航班發(fā)生時，機(jī)組恢復(fù)的方式是類似于機(jī)組排班.首先要建設(shè)每一個機(jī)組是不可分割的，機(jī)組恢復(fù)問題的目的是降低損失成本.同時考慮到機(jī)組的飛行時間，可匹配的機(jī)型等.也可采用交換機(jī)組、備用機(jī)組和加機(jī)組來執(zhí)行任務(wù).

2.2 模型建立

在建立規(guī)劃模型時將考慮到航空公司和旅客兩方面.對于旅客而言，要最小化旅客失望率.對航空公司而言，要限制延誤損失成本.

表達(dá)式以及參數(shù)的符號表示如下：

uj：預(yù)定航班j的旅客失望率[7]，當(dāng)ti≥0時，uj=0.07ti/60+0.4；否則uj=0；

xij：二元變量，當(dāng)機(jī)組i執(zhí)行航班j時為1，否則為0；

yj：二元變量，當(dāng)航班j取消時為1，否則為0；

模型如下：

(1)

s.t.M(C(x,t)

(2)

(3)

(4)

(5)

xij∈{0,1},yi∈{0,1}

(6)

其中，式(1)為目標(biāo)函數(shù)，即最小化旅客失望率；式(2)是估計延誤成本約束；式(3)要求每個航班都對應(yīng)一個機(jī)組，否則航班取消；式(4)是機(jī)組的就緒時間要提前于航班的離港時間；式(5)是機(jī)組的值勤時間要晚于航班的進(jìn)港時間；式(6)為變量0-1約束.

應(yīng)用不確定規(guī)劃方法，上述模型等價于確定性模型如下：

s.t.

3 新的最短路徑算法

3.1 新的最短路徑算法

應(yīng)用新的最短路徑算法求解機(jī)組恢復(fù)模型時，將每個航班看成不同的地點(diǎn)，每個機(jī)組代表不同路徑，通過依次迭代尋找最小成本，并在確定一條路徑之后，產(chǎn)生新的路徑，代替已選擇路徑，再依次迭代，直到確定所有路徑，尋到最優(yōu)解.

3.2 解的步驟

(1)將延誤后的航班看作不同的城市，不同的機(jī)組看成不同的路徑；

(2)依次為航班選擇滿足機(jī)會約束的機(jī)組，并計算旅客失望率；

(3)將(2)中計算的旅客失望率進(jìn)行比較，選出最小失望率對應(yīng)的機(jī)組；

(4)更新(3)中所選機(jī)組信息，形成最新的可選擇路徑；

(5)轉(zhuǎn)下一航班重復(fù)步驟(2)(3)(4)，最終求出最優(yōu)解.

4 算例和計算結(jié)果

假設(shè)某航空公司的10個航班在三個機(jī)場之間執(zhí)行飛行任務(wù)，且有兩種機(jī)型.同時假設(shè)5個執(zhí)勤機(jī)組和1個備用機(jī)組都擁有兩種機(jī)型的執(zhí)照.記時刻0：00為0，時刻12：00為720.原計機(jī)組指派任務(wù)如表1所示：

表1 機(jī)組指派任務(wù)

假設(shè)機(jī)組4不能值勤，航班7和航班8或被取消或使用機(jī)組6來值勤.同時，機(jī)組2、3和5分別影響到航班3、4、5、6和10造成航班延誤.根據(jù)專家意見，假設(shè)機(jī)組造成的延誤時間分鐘數(shù)為線性不確定變量，分別服從分布：t1～L(640,680)，t2～L(950,990)，t3～L(730,770)，t4～L(910,950)，t5～L(980,1020).只對航班采取順延或使用備用機(jī)組時，新的機(jī)組指派如表2所示：

表2 受干擾的機(jī)組指派

從表2可以得出，使用順延的延誤機(jī)組和使用備用機(jī)組值勤時，所產(chǎn)生的延誤成本和旅客失望率.

假設(shè)預(yù)定的置信水平，用本文的模型和算法所得解如表3所示:

表3 重新配對后的機(jī)組指派

比較表2和表3，可以得出無論是延誤成本還是旅客失望率都大大減小，延誤成本僅有2700，旅客失望率僅為0.34.因此，本文所建模型和算法在機(jī)組重新調(diào)度問題的解決上是十分有效的.

5 結(jié)論

本文介紹了機(jī)組恢復(fù)問題的不確定規(guī)劃方法，并設(shè)計了基于最短路徑算法的新算法.在該模型中，以延誤時間為不確定變量，以延誤成本作為約束條件，把旅客失望率作為目標(biāo)函數(shù)，并使用改進(jìn)的最短路徑算法來求解.可以看出，本文方法所得解要優(yōu)于順延航班的機(jī)組指派，所以本文建立的不確定規(guī)劃模型和新的最短路徑算法是有效的.

[1] Diana C., Jose L., Miguel A., et al. A mathematical programming approach to airline crewpairing optimization[EB/OL]. [2012-01-01]. https://www.researchgate.net/publication/242396925.

[2] Ranga A., John J Forrest, William R Pulleyblank.Column generation and the airlies crew pairing problem[J]. Documenta Mathematica, 1998,(3):677-686.

[3] Joyce W Wen, John R Birge. A stochastic programming approach to the airline crew scheduling probelm[J]. TransportationScience, 2006,40(1):3-14.

[4] Ladislav L., Ellis L Johson, George L Nemhauser. Airlie crew recovey[J]. Transportion Science, 2000,34(4):337-348.

[5] 牟德一，王志新，夏群.基于機(jī)組延誤概率的魯棒性機(jī)組配對問題[J].系統(tǒng)管理學(xué)報，2011，28(6)：207-212.

[6] Liu B. Theory and Practice of Uncertain Programming(2nd ed.)[M].Berlin:Springer-Verlag,2016.

[7] 趙秀麗.航空公司不正常航班恢復(fù)模型及其研究[D].南京：南京航空航天大學(xué)，2010.

[責(zé)任編輯：劉秀敏]

Uncertainty Programming Method for Airline Crew Scheduling Recovery

LI Ning, MOU De-yi

(College of Sciences， Civil Aviation University of China, Tianjibrn 300300,China)

Airline schedule development continues to remain one of the most challenging planning activities for any airline. A critical component of the schedule development activities is the appointment of crew. That expenses account for a large proportion in the total cost for airline. In order to reduce cost of airlines when disruption of crew scheduling happens, an uncertain programming model of crew recovery is constructed under uncertain condition with the delay minutes considered as uncertain variables. In the model, the objective is to minimize the expectation of the total weighted disappointment rate; moreover, the estimated delay costs are considered as chance constraints. The uncertain programming model can be transformed to an equivalent deterministic programming with uncertainty theory. To solve the model, a column generation algorithm is adopted. Finally, a numerical example is carried out to illustrate the efficiency of the proposed model and algorithm.

Airline operations; Crew recovery; Uncertainty programming; Column generation algorithm

2017-01-12

中央高?；究蒲袠I(yè)務(wù)費(fèi)項(xiàng)目理學(xué)專項(xiàng)“應(yīng)急調(diào)度問題的不確定規(guī)劃方法”，編號：No.3122015L009.

李 寧(1992-)，女 ，河北黃驊人，中國民航大學(xué)理學(xué)院2014級在讀碩士研究生，研究方向：航班應(yīng)急調(diào)度的不確定規(guī)劃方法； 牟德一(1960-)，男，四川合江人，中國民航大學(xué)理學(xué)院教授，博士，研究方向：航空運(yùn)輸經(jīng)濟(jì)與管理、供應(yīng)量管理等.

O221

A

2095-2910(2017)02-0010-04