航空公司飛行機(jī)組排班問題研究

呂建飛

(中國民航飛行學(xué)院 機(jī)場工程與運(yùn)輸管理學(xué)院，四川 廣漢 618307)

摘要：飛行機(jī)組排班是整個航空公司制定航班生產(chǎn)計劃中的一個重要環(huán)節(jié)，是提高航空公司運(yùn)營效率的關(guān)鍵。通過對飛行機(jī)組排班問題中飛行機(jī)組任務(wù)分配的分析，把飛行機(jī)組人員任務(wù)的分配轉(zhuǎn)化為圖著色，建立飛行機(jī)組排班問題的圖著色模型，設(shè)計頂點(diǎn)著色算法來求解模型，最后將此圖論算法模型應(yīng)用到具體航空公司飛行機(jī)組排班的實(shí)例中。

關(guān)鍵詞：飛行機(jī)組排班；航空公司；圖著色；圖論算法

作者簡介：呂建飛(1990-)，女，河南安陽人，碩士研究生，從事交通運(yùn)輸規(guī)劃與管理研究。

中圖分類號：V355文獻(xiàn)標(biāo)識碼：A

航空公司飛行機(jī)組排班問題不僅關(guān)系到飛行運(yùn)行的安全，而且直接影響到航班的運(yùn)行成本，對航空公司工作效率和經(jīng)濟(jì)效益有很大影響。機(jī)組排班問題在其他交通運(yùn)輸方式中也普遍存在，但在航空運(yùn)輸生產(chǎn)中其重要性更加突出。民航運(yùn)輸生產(chǎn)中的機(jī)組主要是由飛行機(jī)組組成。根據(jù)每個航班的機(jī)型屬性，為航班指派相應(yīng)的飛行駕駛?cè)藛T，以承擔(dān)該航班的飛行駕駛作業(yè)即為飛行機(jī)組排班。航空公司飛行機(jī)組排班問題包括兩個相對獨(dú)立的任務(wù)，首先是將所有待分配機(jī)組的航班根據(jù)機(jī)組成本最小的原則編成任務(wù)串即任務(wù)串編組問題，然后是為生成的任務(wù)串分配飛行機(jī)組人員即飛行機(jī)組分配問題。本文選取了其中復(fù)雜程度較高，對飛行機(jī)組影響最直接的飛行機(jī)組分配問題進(jìn)行研究。

多年來國內(nèi)航空公司使用的飛行機(jī)組資源管理系統(tǒng)中，一般都是采用簡單的規(guī)劃求解方法加上人工干預(yù)完成排班工作。但這種方法越來越難以適應(yīng)高速發(fā)展的航空業(yè)。目前國內(nèi)的一些大型航空公司已經(jīng)開始使用從國外引進(jìn)的自動排班系統(tǒng)，但是由于國內(nèi)外航空公司在運(yùn)營組織模式、法律法規(guī)對飛行機(jī)組使用限制等方面的差異，導(dǎo)致自動排班系統(tǒng)很難完全發(fā)揮作用。因此，建立符合我國航空公司實(shí)際情況的飛行機(jī)組任務(wù)指派模型并設(shè)計相應(yīng)算法是實(shí)現(xiàn)計算機(jī)輔助排班的重要內(nèi)容。對于飛行機(jī)組排班這個問題的研究，目前國內(nèi)學(xué)者常用的算法主要分為啟發(fā)式算法和最優(yōu)化算法，這些算法模型[1-3]有分枝定界法、遺傳算法、混合整數(shù)優(yōu)化法和模糊優(yōu)選動態(tài)規(guī)劃方法等。這些方法為航空公司飛行機(jī)組排班算法的進(jìn)一步研究提供了良好的理論依據(jù)，對實(shí)際應(yīng)用提供了較好的參考，但是這些算法均有不足，比如分枝定界法就是求解時間過長，過程繁瑣，而遺傳算法可能過早地陷入局部最優(yōu)解。

本文綜合考慮上述算法模型，在遵循國家民航法規(guī)和航空公司規(guī)章制度要求的基礎(chǔ)上，提出了飛行機(jī)組人員任務(wù)分配問題的圖著色模型[4-6]，確定生成的任務(wù)串之間的時間沖突集合，然后設(shè)計了一種求解模型的頂點(diǎn)著色算法。

1飛行機(jī)組分配問題的圖著色模型

1.1飛行機(jī)組分配的系統(tǒng)分析

飛行機(jī)組排班包括任務(wù)串生成和飛行機(jī)組分配這兩個相對獨(dú)立的任務(wù)，本文僅考慮在任務(wù)串問題解決之后，將任務(wù)串分配給飛行機(jī)組的問題。在滿足編制飛行機(jī)組排班計劃的基本規(guī)定和基本原則的條件下，為每個生成的任務(wù)串指派一個具體的飛行機(jī)組去執(zhí)行。對任務(wù)串進(jìn)行飛行機(jī)組指派時，本文假設(shè)飛行機(jī)組數(shù)量足夠，即可以為所有的任務(wù)串指派飛行機(jī)組去執(zhí)行，任務(wù)串能夠完全被執(zhí)行。具體分配飛行機(jī)組時，必須滿足以下約束條件：(1)每一個任務(wù)串都能且只能被分配給一個飛行機(jī)組。(2)在同一個時間段內(nèi)，一個飛行機(jī)組最多只能執(zhí)行一個任務(wù)串。(3)飛行機(jī)組開始執(zhí)行一個任務(wù)串到結(jié)束的時間總和不得超過法規(guī)規(guī)定的周期飛行小時數(shù)。根據(jù)中國民用航空規(guī)章第121部第三章第八條[7]對于飛行時間限制的規(guī)定，在任何連續(xù)24小時內(nèi)，單套機(jī)組最多飛行時間不得超過8小時，所飛航段不得多于4段；對于航段不多于2段的飛行，最多飛行時間不得超過9小時。此外，被分配給同一飛行機(jī)組執(zhí)行的兩個任務(wù)串前后之間的時間間隔應(yīng)滿足規(guī)定的過站時間，以保證下一任務(wù)串的順利執(zhí)行。

1.2飛行機(jī)組分配的圖著色模型

基于圖著色的飛行機(jī)組分配結(jié)果轉(zhuǎn)化為二元式的圖模型：

G=(V,E)

2飛行機(jī)組分配問題的算法設(shè)計

圖的著色問題在生產(chǎn)調(diào)度領(lǐng)域有著廣泛的應(yīng)用背景，已被應(yīng)用于資源分配、貨物儲存和課表編排等方面。本文以時間片劃分算法為基礎(chǔ)，應(yīng)用圖的著色模型，給出了求解飛行機(jī)組分配的頂點(diǎn)著色算法。

2.1符號說明

首先對頂點(diǎn)著色算法中的一些符號進(jìn)行說明：

2.2算法設(shè)計

考慮到飛行機(jī)組分配問題中的實(shí)際情況和約束條件，給出基于飛行機(jī)組分配的頂點(diǎn)序列著色算法，其步驟如下：

(1)首先確定指派飛行機(jī)組時存在時間沖突的任務(wù)串集合E。

(5)若全部的頂點(diǎn)都已著色，停止；否則，轉(zhuǎn)步驟(4)。

3算例

某航空公司現(xiàn)有13個待分配機(jī)組的航班任務(wù)串，具體情況如圖1所示：

圖1航班任務(wù)串

根據(jù)任務(wù)串之間指派飛行機(jī)組時存在的時間沖突情況，做出二元圖G=(V,E)，如圖2所示。

圖2　任務(wù)串時間沖突圖

然后按照各頂點(diǎn)的度數(shù)由大到小進(jìn)行排序，度數(shù)相同時按照頂點(diǎn)序號順序排列。結(jié)果見表1。

表1　待分配飛行機(jī)組的任務(wù)串資料

飛行機(jī)組資源中心現(xiàn)有12個可用飛行機(jī)組，將其按照作為顏色的集合C進(jìn)行編號，分別記為C1，C2，……，C12。根據(jù)航空公司向中國民用航空局申請，機(jī)型B737-800和B737-300可以通飛，A330-200和A330-300可以通飛。飛行機(jī)組資料見表2。

表2　飛行機(jī)組資料

根據(jù)前文所設(shè)計的頂點(diǎn)著色算法，首先對頂點(diǎn)2進(jìn)行著色，由于其執(zhí)飛機(jī)型為B737-800，除了顏色C1、C2、C3、C4和C5外，其他顏色都是禁止的，給它賦以顏色C1，即給任務(wù)串2分配飛行機(jī)組C1。

掃描剩余的頂點(diǎn)，由于頂點(diǎn)4、6、7、8、9、10、11、12與頂點(diǎn)1相鄰接，故其度數(shù)都減1，對剩余的頂點(diǎn)按度數(shù)從大到小排列，頂點(diǎn)12的度數(shù)最大，由于其執(zhí)飛機(jī)型為A330-200，因此給它賦以顏色C9。

掃描剩余的頂點(diǎn)，由于頂點(diǎn)7、8、9與頂點(diǎn)3相鄰接，故其度數(shù)都減1，對剩余的頂點(diǎn)按度數(shù)從大到小排列，頂點(diǎn)4的度數(shù)最大，由于其執(zhí)飛機(jī)型為A330-300，其與頂點(diǎn)12相鄰接，因此給它賦以顏色C10。

掃描剩余的頂點(diǎn)，由于頂點(diǎn)5、6、11與頂點(diǎn)4相鄰接，故其度數(shù)都減1，對剩余的頂點(diǎn)按度數(shù)從大到小排列，頂點(diǎn)9的度數(shù)最大，由于其執(zhí)飛機(jī)型為A320，且與頂點(diǎn)3和頂點(diǎn)12相鄰接，因此給它賦以顏色C8。

掃描剩余的頂點(diǎn)，由于頂點(diǎn)7、8與頂點(diǎn)9相鄰接，故其度數(shù)都減1，對剩余的頂點(diǎn)按度數(shù)從大到小排列，頂點(diǎn)6的度數(shù)最大，由于其執(zhí)飛機(jī)型為B737-800，且與頂點(diǎn)1和頂點(diǎn)2相鄰接，因此給它賦以顏色C3。

通過上述的圖著色過程，最后得到飛行機(jī)組分配的任務(wù)串結(jié)果為：C1:{2}、C2:{1}、C3:{6}、C4:{7、5}、C6:{10}、C7:{3}、C8:{9}、C9:{12、11}、C10:{4}、C11:{8}。本算法所得答案(僅需10個飛行機(jī)組)比原本所需12個飛行機(jī)組節(jié)約了兩個飛行機(jī)組的成本。因此在飛行機(jī)組排班過程中采用本算法有助于航空公司提高設(shè)備資源的利用效率, 同時節(jié)省人力資源，降低運(yùn)營成本，提高航空公司的經(jīng)濟(jì)性。

4結(jié)語

過去我國各航空公司普遍采用的傳統(tǒng)的依靠人工干預(yù)來完成飛行機(jī)組排班工作的方法已經(jīng)越來越難以適應(yīng)高速發(fā)展的航空業(yè)。從國外引進(jìn)的自動排班系統(tǒng)也難以適應(yīng)我國航空業(yè)的實(shí)情，其作用得不到完全發(fā)揮。本文通過構(gòu)造飛行機(jī)組分配的圖著色模型，設(shè)計了頂點(diǎn)著色算法，運(yùn)用到具體的航空公司飛行機(jī)組排班的計算分析中，這對優(yōu)化飛行機(jī)組排班，提高航空公司運(yùn)營效益具有實(shí)際意義。

參考文獻(xiàn)

[1] 李青.解決排班問題的多目標(biāo)優(yōu)化模型及算法研究[J].北京航空航天大學(xué)學(xué)報,2003,29(9):270-274.

[2] 李耀華,譚娜.飛機(jī)排班調(diào)度中飛行機(jī)組指派優(yōu)化模型及算法研究[J].計算機(jī)工程與應(yīng)用,2008,44(34):243-246.

[3] 趙正佳. 航空公司飛行機(jī)組排班計劃研究[J]. 運(yùn)籌與管理, 2011, 20(6):106-113.

[4] 王桂平,王衍,任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京:北京大學(xué)出版社,2011:438-451.

[5] Bondy J A,Murty U S R.圖論及其應(yīng)用[M].北京吳望名,譯.北京：科學(xué)出版社,1984：26-52.

[6] Daniel Brelaz.New method to color the vertices of a graph[J]. Communications of the ACM,1979,22(4):251-256.

[7] 中國民用航空局.《大型飛機(jī)公共航空運(yùn)輸承運(yùn)人運(yùn)行合格審定規(guī)則》(CCAR-121部)[EB/OL]. [2010-01-04].http://www.caac.gov.cn/B1/B6/201003/t20100319_31073.html.

[責(zé)任編輯、校對：周千]

Research on Flight Crew Scheduling in Airlines

LVJian-fei

(School of airport Engineering and Transportation Management Civil Aviation Flight University of China,

Guanghan 618307, China)

Abstract：The flight crew scheduling is an important part of the entire airline flight production plan, and also the key to improving the operational efficiency of airlines. A graph coloring model of flight crew scheduling is set up by analyzing the flight crew assignments and converting the assignment of flight crew tasks into graph coloring, and the vertex coloring algorithm is designed to solve the model, then this graph-theoretic algorithm is applied to specific instances of airline flight crew scheduling.

Key words：flight crew scheduling; airlines; graph coloring; graph-theoretic algorithm