航空公司飛行機組排班問題研究

航空公司飛行機組排班問題研究

呂建飛

(中國民航飛行學院 機場工程與運輸管理學院，四川 廣漢 618307)

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

關鍵詞：飛行機組排班；航空公司；圖著色；圖論算法

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

中圖分類號：V355文獻標識碼：A

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

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

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

1飛行機組分配問題的圖著色模型

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

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

1.2飛行機組分配的圖著色模型

基于圖著色的飛行機組分配結果轉化為二元式的圖模型：

G=(V,E)

2飛行機組分配問題的算法設計

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

2.1符號說明

首先對頂點著色算法中的一些符號進行說明：

2.2算法設計

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

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

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

3算例

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

圖1航班任務串

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

圖2　任務串時間沖突圖

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

表1　待分配飛行機組的任務串資料

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

表2　飛行機組資料

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

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

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

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

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

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

4結語

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

參考文獻

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

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

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

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

[5] Bondy J A,Murty U S R.圖論及其應用[M].北京吳望名,譯.北京：科學出版社,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] 中國民用航空局.《大型飛機公共航空運輸承運人運行合格審定規(guī)則》(CCAR-121部)[EB/OL]. [2010-01-04].http://www.caac.gov.cn/B1/B6/201003/t20100319_31073.html.

[責任編輯、校對：周千]

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