馬弘沈倪朱靖夏佳楠

(1.浙江大學 工程師學院,浙江 杭州 310015;2.浙江大學 管理學院,浙江 杭州 310058)

0 引言

航空運輸業(yè)在國民生產(chǎn)和生活中扮演著越來越重要的角色。與此同時,經(jīng)濟全球化和激烈的航空運輸市場競爭也對航空公司的運營與調(diào)度提出了更高的要求。航空運輸業(yè)具有服務(wù)密集型產(chǎn)業(yè)的特征,機組人員是航空公司最重要的航空資源之一,是其潛在競爭優(yōu)勢的來源[1],會對公司績效產(chǎn)生直接的影響[2]。近年來飛行事故調(diào)查結(jié)果顯示,人為錯誤因素誘發(fā)的飛行事故比例高達70%。其中機組成員的不良狀態(tài)如精神疲勞、協(xié)調(diào)缺失等是引起人為錯誤的重要因素[3]。由此,我們看到的確有必要在機組人員排班過程中充分考慮并協(xié)調(diào)各環(huán)節(jié)中能夠影響到機組人員身心健康的因素,如休息時間、環(huán)境變化等,并積極采取措施減少此類消極因素的影響。

在機組人員排班調(diào)度中,傳統(tǒng)機組排班是根據(jù)已確定的航段來生成固定周期內(nèi)從某一基地出發(fā)并且能夠返回基地的機組排班的集合,排班需要滿足民航局發(fā)布的民航運輸飛行人員飛行時間、值勤時間和休息時間的規(guī)定;同時確保這些機組排班能覆蓋所有計劃的航段,不應(yīng)使任何需要值勤的航段未分配給機組人員,即令排班計劃滿足合法性和可行性的約束。但值得注意的是,即便是滿足并符合上述兩個約束的排班計劃在航空公司的航班與飛行規(guī)劃實踐中仍存在較多可改進之處,這說明目前該領(lǐng)域仍尚未被充分研究。近期仍有不少學者通過在傳統(tǒng)的機組排班問題基礎(chǔ)上中添加有針對性的相關(guān)約束,以達到針對性地提升排班調(diào)度的質(zhì)量的目標。例如Quesnel等[4]將機組輪換問題(crew rostering problem)中的工作語言約束引入到機組配對問題中,研究表明在計算復雜度略微提升的前提下,能使違反語言約束的排班比率減少百分之九十。Quesnel等[5]的研究中亦加入了旨在將工作時間平均分配給全體員工的特殊約束。

在正常執(zhí)行任務(wù)狀態(tài)下,保障機組人員有充足的休息、維持其良好的工作狀態(tài)是保障航空運行安全和效率的重要方面。為加強排班計劃對機組人員良好工作狀態(tài)的保障,我們將車輛路徑規(guī)劃問題中的一致性標準引入到航空領(lǐng)域,提出了機組排班問題中新的一致性約束。包含一致性的車輛路徑規(guī)劃問題最早由Gro?r等[6]提出,是指固定線路上的顧客在固定時間區(qū)域內(nèi)被相同的司機服務(wù),從而獲得提升客戶滿意、提升公司收益等優(yōu)勢。經(jīng)過調(diào)研,我們發(fā)現(xiàn)在民用航空機組排班背景下的一致性,則強調(diào)機組人員的值勤期路徑應(yīng)呈現(xiàn)一定的規(guī)律性,以此來增強機組對新值勤期的適應(yīng)程度,提升人員調(diào)度計劃質(zhì)量,進而達到保障飛行安全和提高運營穩(wěn)定性的目的。

本文對該一致性標準的定義具體表現(xiàn)在人員的值勤班次一致性和過夜城市一致性兩方面。一方面,因為航空作業(yè)的特殊性,機組人員經(jīng)常需要倒班,如在夜間工作和日間工作班次之間轉(zhuǎn)換,這極易引起睡眠紊亂以致疲勞駕駛等問題[7]。而規(guī)律性的作息對于機組人員保持精力充沛非常重要,因此應(yīng)盡可能保證機組人員在值勤期內(nèi)工作時間的一致性,將其在一個周期內(nèi)的換班次數(shù)控制在一定區(qū)間內(nèi)[8]。這將更有助于保障機組人員身心健康,提升工作滿意度和促進航空公司運行的效率與安全性。另一個方面,過夜城市一致性要求將機組人員在一個周期內(nèi)除基地(居住地點)外的過夜城市數(shù)量限制在一定范圍內(nèi)。長時間的旅途奔波易使機組人員精神和體力疲勞,熟悉的環(huán)境有助于縮短機組人員的環(huán)境適應(yīng)過程以幫助其更好地休息,從而能夠促進其疲勞恢復,保證后續(xù)航空作業(yè)的安全性[9]。同時,對過夜城市數(shù)量的控制能幫助提升航空公司的管理效率,公司可與相對較少數(shù)量的相關(guān)酒店達成合作,以較為優(yōu)惠的價格預定客房和接送車輛,并更加集中地實施人員管理和調(diào)度,減少人員的不確定性。

本文在傳統(tǒng)機組排班模型中引入了考慮機組人員身心健康的一致性考量,在此基礎(chǔ)上分別構(gòu)建了考慮值勤班次一致性和過夜城市一致性的機組排班模型。根據(jù)新模型的特點,我們提出了求解該模型的啟發(fā)式列生成算法,采用了兩種形式分別構(gòu)建了相應(yīng)的子問題,并通過改進的動態(tài)規(guī)劃算法對子問題求解產(chǎn)生新列。我們通過對一航空公司的真實數(shù)據(jù)的求解分析,將結(jié)果和市面上先進的商業(yè)求解器的結(jié)果進行比較驗證了算法的效率和有效性,并深入分析比較兩種約束形式求解子問題的優(yōu)劣,以及探尋我們所提出的一致性約束在機組排班問題中的可行性和實用價值。

1 機組人員排班問題的相關(guān)研究回顧

1.1 值勤計劃問題相關(guān)研究

生成值勤計劃是航空公司機組人員排班研究的重要方面。值勤計劃問題是指將航空公司飛行計劃中的航段按照一定規(guī)則生成每個機組人員的工作計劃,并最終達到最小化運營成本或者最小化機組人員數(shù)量等優(yōu)化目標的問題[10]。由于生成值勤計劃問題具有需要滿足的規(guī)則繁多、可能的解集規(guī)模龐大、解決方案成本中薪資等部分與工作時長非線性相關(guān)等特點[2],該問題一直是熱門研究問題。

學者一般將集合劃分模型或集合覆蓋模型作為生成機組人員值勤計劃的基本數(shù)學模型[11-12]。集合劃分模型生成機組人員可行的排班計劃的集合,并使得每個飛行航段至少被覆蓋一次,并使總成本最小。集合覆蓋約束所允許的飛機航段被超過一次覆蓋則可解釋為有機組人員作為乘客搭乘了這些航段(deadhead)[12]。Arabeyre等[13]在其綜述文章中討論了可行的排班計劃集合的生成、縮減和優(yōu)化的各種方法。Kolner[14]、Fearnley[15]用子集減少方法縮減集合規(guī)模,并成功運用在了聯(lián)合航空公司和加拿大航空公司的調(diào)度系統(tǒng)中。Barnhart[10]、Desrosiers等[16]則為解決大規(guī)模的0-1整數(shù)規(guī)劃問題提供了相關(guān)的數(shù)學方法,為解決航空公司機組調(diào)度問題提供了借鑒。Desrosiers等[17]使用嵌入在分支定界算法中的列生成算法生成了值勤計劃的可行解,提高了求解的效率。此外,一些研究者也將啟發(fā)式算法與排班問題的求解過程相結(jié)合。Gershkoff[18]從啟發(fā)式解法產(chǎn)生的一組初始解開始,再利用整數(shù)規(guī)劃方式不斷改善初始解。Thomas 和Proksch[19]將模擬退火與特定問題的局部改進啟發(fā)式相結(jié)合,在提高解決方案的質(zhì)量的同時減少了算法運行時間。Bader等[20]利用遺傳算法來求解大規(guī)模的機組排班問題,并將分支定界法與遺傳算法相結(jié)合,有效提升了遺傳算法中尋找最優(yōu)解的收斂速度。Crawford等[21]分析了蟻群優(yōu)化算法對解決機組人員調(diào)度問題的性能,并將蟻群算法與列生成算法相結(jié)合,較好地解決了Beasley's OR-Library 中的測試實例。Saddoune等[22]打破了規(guī)劃過程的順序性限制,構(gòu)建了一個集成值勤期生成和機組人員排班問題的模型,并開發(fā)了組合的列生成與動態(tài)約束聚合方法求解的算法,實現(xiàn)了一體化排班。該模型使得北美一家主要航空公司的座艙機組總數(shù)減少約5.5%。

同時除了成本最小化目標外,也有研究關(guān)注到排班穩(wěn)定性與運營成本效益問題。Ehrgott 和Ryan[23]對延長機組人員值勤期之間空閑時間的成本效益進行了研究,在增強魯棒性的目標下使得調(diào)度計劃成本最小。Yen 和Bridge[24]通過減少機組人員在工作期間更換飛機的次數(shù),減少了因換機時間不足而導致的不確定性。趙正佳[25]制定了滿足機組休息時間約束并使機組在異地停留時間最短的調(diào)度計劃,該計劃能以較少的機組完成航段飛行任務(wù)。他們的實踐經(jīng)驗表明,人力成本的小幅增加可以帶來可觀的運營穩(wěn)定性收益。Tam等[26]考慮到了一個機組內(nèi)人員的延遲對排班問題的影響,他們發(fā)現(xiàn)由最低成本目標求出的排班結(jié)果對航段延遲幾乎沒有緩沖時間,所以機組人員在飛行延遲后進行的拆分會導致延遲在不同排班計劃上的傳播,影響排班計劃的魯棒性,因此,Tam等[26]在原有模型計算成本最小化目標的基礎(chǔ)上增加了最大化單位機組數(shù)量的目標。他們對新西蘭航空國內(nèi)航線的數(shù)值測試表明,增加此目標大大提高了單位機組的配備水平,而成本卻沒有大幅增加。

1.2 一致性標準相關(guān)研究

Gro?r等[6]首次在車輛路徑規(guī)劃問題中引入一致性標準,構(gòu)建了包含一致性標準的車輛路徑規(guī)劃問題(con-VRP),具體提出的路徑一致性標準規(guī)定了司機在固定的n條路線上工作;時間一致性標準規(guī)定了司機在大致相同的時間區(qū)間服務(wù)顧客;間隔一致性標準規(guī)定了客戶被服務(wù)的最大和最小間隔時間。Coelho等[27]認為在路徑規(guī)劃中加入一致性標準將有助于建立起一種使司機和顧客雙方都受益的紐帶。這些規(guī)定將使司機更加熟悉分配給他們的客戶和地點,從而更容易與客戶建立發(fā)展更加緊密良好的關(guān)系,培養(yǎng)與顧客之間的熟悉程度,進而獲得更多的配送需求,提高公司收益,這是在僅僅基于成本考慮車輛路徑規(guī)劃問題時所沒有的特點和優(yōu)勢。近年來有關(guān)車輛路徑規(guī)劃問題的一致性研究層出不窮。Coelho等[27]在庫存路徑規(guī)劃問題(IRP)解決方案中引入了反映通用服務(wù)質(zhì)量水平的六個一致性標準并建立了相關(guān)模型。Nowak等[28]在周期車輛路徑問題(PVRP)中加入顧客一致性標準(司機服務(wù)相同的一組顧客)并構(gòu)建了平衡人力成本和出行距離目標的模型,為管理決策提供了借鑒。Luo等[29]研究了帶有時間一致性標準和運輸容量一致性標準的多期車輛路徑選擇問題(MVRPTW-LVQ),分析了在不同需求波動水平下提升服務(wù)一致性水平對運營成本的影響。

綜合以上航班值勤計劃相關(guān)問題和一致性的車輛路徑規(guī)劃問題的文獻回顧可知,在目前航空公司運營調(diào)度問題研究中,研究者所增加的約束大多是以降低規(guī)劃成本以及增加運營穩(wěn)定性等為目標,而較少從機組人員的中長期身心健康與工作、休息狀態(tài)角度出發(fā)考慮。但機組排班計劃的主體是機組人員,他們的身心健康對航空公司的運營質(zhì)量和生產(chǎn)效率方面有著至關(guān)重要的影響,如乘務(wù)員在與客戶的互動中展現(xiàn)出的飽滿的精神狀態(tài)對于提高顧客滿意度有著積極影響[2];而身心疲勞則會使得飛行員注意力下降、反應(yīng)動作遲鈍、嚴重影響他們的判斷力和決策力,從而對飛行安全帶來隱患[30]。最后,機組人員的身心健康還會對其工作滿意度產(chǎn)生較大影響。由于不同的排班計劃涉及的飛行時間、區(qū)域、工作強度等都不同,機組人員對不同的排班計劃偏好也不同,如一些排班計劃內(nèi)的值勤期在日間飛行與夜間飛行之間不斷輪換,這對飛行員作息調(diào)整產(chǎn)生了極大的挑戰(zhàn),飛行員一般不愿意執(zhí)行該類任務(wù),而一些帶有國際航段的排班計劃則被認為是好差事,因為飛行員能夠有較長的帶薪休假以及高額飛行津貼[31]。一致性標準作為提升車輛路徑規(guī)劃相關(guān)問題求解質(zhì)量的有效手段,可以幫助提升配送服務(wù)水平、顧客滿意度、提升訂單成交概率和增加配送需求。因此,為使航空排班計劃更好地符合機組人員、航空公司、顧客三者的利益,我們嘗試在制定排班計劃的過程中,將一致性約束引入機組人員排班模型中,使得機組排班計劃不僅能夠關(guān)注成本與效率,而且在平衡機組人員技能素質(zhì)、身體狀況、身心負荷等條件下,減少影響機組人員身心健康的消極因素,進而給出更加均衡一致、科學合理的排班執(zhí)勤計劃。

2 機組人員排班問題介紹

2.1 值勤計劃相關(guān)概念

(1)航段:是指飛機從起飛到下一個著陸之間的飛行。

如上表1 所示,每一個航段包括①航段編號:該航段的序號,用來唯一確定這一航段。②飛機編號:該航段被指派的飛機的編號。③起飛機場和降落機場:說明該航段的出發(fā)地點和降落地點。④三字碼:國際航空運輸協(xié)會(IATA)所制定的代表不同機場的特定編碼。⑤日差:起飛時間和降落時間日期的差值,日差為0 時說明該航段在起飛當天就結(jié)束,反之則說明該航段一直延續(xù)到下一天。⑥起飛時間和落地時間:說明該航段的從機場起飛的時間和降落的時間,以北京時間計。

表1 航段示例Table 1 Example of legs

(2)飛行值勤期(tour of duty):是指在某一天中,機組成員從為完成該次任務(wù)到達指定地點報到時刻開始,到飛機在最后一次飛行后發(fā)動機關(guān)閉且機組成員沒有再次移動飛機的意向為止的時間段。

上表2 所示是某個編號為1 的值勤期中的具體航段。每個值勤期的第一個航段被稱為值勤期開始航段,最后一個航段被稱為值勤期結(jié)束航段。該值勤期的開始時間由報到時間決定,而每一個值勤期的報到時間根據(jù)規(guī)定為開始航段起飛前1.5 h,計算為7 月4 日10:35。該值勤期的結(jié)束時間由結(jié)束航段的結(jié)束時間決定,即7 月4 日21:05。值勤期的開始時間、結(jié)束時間、所包含的航段等要素構(gòu)成了值勤期的基本要素。

表2 飛行值勤期示例Table 2 Tour of duty

(3)值勤時間:是指機組成員按照要求執(zhí)行所分配的任務(wù)的時間,這些任務(wù)包括但不限于飛行值勤、置位航班和培訓等。值勤時間由值勤期的結(jié)束和開始時間的差值得到。表2 中的值勤時間是21:05 與10:35 的差值為9.5 小時。

(4)置位航班(deadhead):是指機組成員為完成指派的飛行任務(wù),作為乘客乘坐飛機或地面交通工具,但不包括其往返當?shù)氐淖∷迗鏊慕煌?。置位航班屬于值?該時間不能作為休息時間。

(5)飛行時間:是指機組成員在一個值勤期內(nèi)從飛機起飛到下一個著陸之間的飛行時間的累加。表2 中飛行時間是航段324,331,338 三段飛行時間的累加,其總和為5.17 小時。

(6)休息期:兩個值勤期之間的間隔,是指從機組成員到達過夜城市起,到為執(zhí)行下一次任務(wù)離開過夜城市的連續(xù)時間段。在該段時間內(nèi),航空公司不得為機組成員安排任何工作。

(7)過夜城市:是指機組人員在休息期所處的城市。在該地有可以控制溫度、降低噪音、條件良好的場所(如賓館等),該場所能夠控制光線亮度,使機組成員可以在床位上以平躺或接近平躺姿勢睡覺或休息。

(8)機組排班計劃(line of work):是指機組人員在較長時間跨度內(nèi)(一周或一個月等)的工作計劃。它是由多個值勤期和休息期構(gòu)成的連續(xù)的活動計劃。

2.2 值勤計劃相關(guān)規(guī)則

在實際值勤過程中,一個機組由飛行機組和乘務(wù)機組所構(gòu)成,不同類型的機組人員所適用的規(guī)則不同。由于飛行機組的責任更大,值勤計劃安排過程中對飛行機組成員的要求和約束也更多,在不失一般性的前提下,本文討論的值勤計劃以飛行機組成員的執(zhí)勤計劃為例,而在后續(xù)的應(yīng)用中可推廣至所有機組成員。飛行機組人員值勤計劃的規(guī)則由中國民航局《大型飛機公共航空運輸承運人運行合格審定規(guī)則》中的重要規(guī)則以及華東地區(qū)某民營航空公司的相關(guān)補充規(guī)則構(gòu)成[32]。

(1)每個飛行值勤期內(nèi)的值勤時間約束與飛行機組成員報到時間和航段任務(wù)數(shù)量有關(guān),詳見下表3。如某個飛行機組成員在0:00 至4:59 之間的時間報到,執(zhí)行小于4 個航段的航段任務(wù),則其最大的飛行值勤期不超過12 小時。

表3 飛行機組最大飛行值勤期限制Table 3 Maximum flight duty limitations for a flight crew

(2)每個飛行值勤期內(nèi)的飛行時間約束與飛行機組成員報到時間有關(guān),詳見下表4。如某個飛行機組成員在0:00 至4:59 之間的時間報到,則其最大的飛行時間不超過8 小時。

表4 飛行機組最大飛行時間限制Table 4 Maximum flight time limitations for a flight crew

(3)單個飛行值勤期后休息期不少于10 小時。

(4)若飛行機組成員執(zhí)飛值勤期的第一個航段,或飛行機組成員在值勤期內(nèi)從一架飛機換到另一架飛機,則飛行機組成員的報到時間是起飛前1.5 小時,若飛行機組成員的下一個飛行航段在值勤期內(nèi)的同一架飛機上,則不需要提前報到。

(5)排班計劃任意連續(xù)7 天飛行值勤內(nèi)有一個至少連續(xù)24 小時的休息期,且起飛基地和降落基地應(yīng)相等。

機組人員排班整體而言需要解決兩階段問題,生成值勤計劃和值勤計劃分配。生成值勤計劃是指航空公司根據(jù)已確定的航段來生成固定周期內(nèi)從某一基地出發(fā)并且能夠返回基地的排班計劃的集合,這些排班計劃要包含預設(shè)的所有航段;值勤計劃分配是指將生成的排班計劃具體地分配給每一個特定的機組人員的方法。常見的分配方法有資歷優(yōu)先競標法和公平任務(wù)分配法。本文研究機組排班問題中關(guān)鍵的第一階段的值勤計劃生成問題,因為該問題包含大量復雜約束,并且與一致性規(guī)范直接相關(guān)。而對于第二階段的值勤計劃分配問題,與本研究的主要貢獻點一致性規(guī)范并不密切相關(guān),故不做贅述,相關(guān)方法可直接參考 Ernst[33]、Butchers[34]等人的研究。

生成航空公司排班計劃是一個復雜的計劃制定過程,航空公司航線計劃和基地分布以及民航局的規(guī)定等都會直接影響模型的構(gòu)建。本文將在分析和總結(jié)現(xiàn)有機組人員排班模型的基礎(chǔ)上,構(gòu)建包含一致性標準的機組人員排班模型并設(shè)計相應(yīng)的求解算法,研究一致性標準的加入對排班計劃的影響,以改善現(xiàn)有機組排班相關(guān)研究中優(yōu)化目標不夠全面的弊端,保障機組人員規(guī)律作息和身心健康,同時促進航空公司的運營安全與人員工作效率。

3 問題模型

3.1 基本模型

機組排班問題可以被等價地建模為一個集合覆蓋模型,我們用J表示所有符合規(guī)則的排班計劃(列)的集合,對于每一條排班計劃j∈J,設(shè)aij為0-1 變量表示第j條排班計劃中是否包含i航段。使用二元變量xj表示是否選擇排班計劃j,假設(shè)總成本與每個排班計劃線性相關(guān),并令cj表示每個計劃的單位成本,則具體模型如下所示。

模型的目標函數(shù)是最小化排班計劃的成本,式(1b)為航段覆蓋約束,表示所有預設(shè)的航段都會被選中的排班計劃組合至少覆蓋一次;式(1c)表示xj為0-1 變量。

為了使問題清晰簡潔,在不影響對一致性約束探究的前提下,我們將模型中的排班計劃的成本cj設(shè)為1,即我們認為使用的飛行機組數(shù)越少,排班計劃的總成本越少。上述模型目標函數(shù)(1a)簡化為(1d)。

上述模型包含指數(shù)數(shù)量級的列,每列都描述了一個機組排班計劃。求解中遇到的困難主要在于求解所有排班計劃的集合,因為它是一個NP-Hard 問題,當求解所有滿足約束的排班計劃時,即使只有100 個航段的值勤計劃,也有可能生成上萬條可行的排班計劃,而對于有上千個航段的值勤計劃,排班計劃的數(shù)量可達數(shù)十億條[2]。由于存在太多的可行排班計劃(列),直接求解上述模型十分困難,與傳統(tǒng)研究類似,本文也將采用列生成方法(詳見4.1 節(jié))對模型進行求解。其主要思想是先構(gòu)造一個規(guī)模較小的主問題(僅包含少量初始列)和一個用于尋找新排班計劃的子問題。主問題為松弛的集合覆蓋問題,求解主問題的同時,為子問題提供對偶價值(dual price);子問題為主問題提供改進的排班任務(wù)。通過循環(huán)迭代,主問題增加新變量,逐漸逼近原問題的最優(yōu)解,當滿足一定收斂準則時即完成模型求解。

3.2 子問題

3.2.1 子問題基本模型

子問題基本模型的目的是生成滿足規(guī)范標準的排班計劃(列)。我們首先給出以下參數(shù)與變量:

參數(shù):

·i、j:代表航段,i,j∈I,I為所有航段的集合;

·t:代表值勤期的時間周期,t∈T,T為日期集合;

·πi:為來自受限主問題的對偶解;

·h(i):表示i航段的前導航段的集合;

·b(i):表示i航段的后繼航段的集合;

·fti:表示航段i的飛行時間;

·tdepi:表示航段i的起飛時刻;

·tarii:表示航段i的降落時刻;

·Fti:表示t日以航段i為起始航段的最大飛行時間;

·Dti:表示t日以航段i為起始航段的最長值勤時間;

·Scityi:表示航段i的出發(fā)城市的編號;

·Ecityi:表示航段i的降落城市的編號;

·M:表示一個極大的數(shù);

變量:

·xit:0-1 變量,表示t日i航段是否與j航段連接的決策變量;

·yijt:0-1 變量,表示t日i航班是否與t +1日j航班連接的決策變量;

·sit:0-1 變量,表示該排班計劃(列)是否由t日的i航段開始;

·eit:0-1 變量,表示該排班計劃(列)是否由t日的i航段結(jié)束;

·maxht:表示t日機組的最大飛行時間;

·maxdht:表示t日機組最長值勤時間;

·maxth: 表示飛機組一個排班計劃內(nèi)的最大值勤時間;

·nft:表示t日機組執(zhí)行的航段數(shù)量;

子問題表示為以下0～1 混合整數(shù)規(guī)劃模型:

子問題根據(jù)主問題求出的航段對偶價值,計算滿足約束且具有最小降低成本的排班計劃(列)。式(2a)對應(yīng)相應(yīng)列的差額降低成本(reduced cost)。式(2b)-(2d)是生成列的基礎(chǔ)約束。式(2b)表示該排班計劃(列)有且僅有一個出發(fā)航段,式(2c)表示該排班計劃(列)有且僅有一個結(jié)束航段。式(2d)是流量平衡約束,若航段為該列的出發(fā)航段,那么其必有一個后繼航段或其為結(jié)束航段;若航段為中間航段,那么其必有一個前導航段和一個后繼航段;若航段為該列的結(jié)束航段,那么其必有一個前導航段或其為出發(fā)航段。式(2e)表示該排班計劃(列)的出發(fā)城市和降落城市相同。最大飛行時間同當日飛行員報到時間(即第一個值勤航段出發(fā)前半小時)有關(guān),總飛行時間不得超過民航總局以及航空公司的要求限制,式(2f-1)識別出某日第一個值勤航段,并根據(jù)此航段的報到時間計算出最大飛行時間。式(2f-2)表示某日最大飛行時間(maxht) 的約束,即每一值勤期內(nèi)各航段的總飛行時間不得超過民航總局以及航空公司的要求限制。約束(2g-1)-(2g-3)給出了值勤時間相關(guān)約束。該約束與飛行員當日報到時間和該值勤期執(zhí)行的航段數(shù)量有關(guān),通常執(zhí)行越多航段,最長值勤時間越低。式(2g-1)識別出某日第一個值勤航段,并根據(jù)此航段的報到時間和執(zhí)行的航段數(shù)量(nft),計算了最長的值勤時間。由表三可知以4 個航段為界限,每增加一個航段值勤時間減少一個小時,故在計算時可由基礎(chǔ)值勤時間減去航段數(shù)量與4 的差值獲得此時的值勤時間,而式(2g-2)則給出了值勤期執(zhí)行的航段數(shù)量的計算。式(2g-3)表示某日最長值勤時間(maxdht) 的約束,當日值勤時間由當日執(zhí)飛的結(jié)束航段的降落時間減去起始航段的起飛時間得到。式(2h)表示結(jié)束時間和開始時間的差值不得超過一個排班計劃內(nèi)的最大值勤時間,使排班計劃滿足在7 個值勤期至少需要有連續(xù)24 小時的休息期約束。

3.2.2 納入一致性標準的模型

(1) 班次一致性約束

增加班次一致性是為了保證機組人員作息的規(guī)律性,為此需要將其在一個周期內(nèi)的班次交替次數(shù)限制在一定范圍內(nèi)。為更合理地劃分時間段,本文參考了中華人民共和國鐵道部有關(guān)發(fā)車時間的班次劃分規(guī)則,每六個小時劃分為一個班次,值勤班次區(qū)間分別為00:00 至05:59、06:00 至11:59、12:00 至17:59 以及18:00 至23:59,共計四班。

表5 值勤班次時間表Table 5 Schedule of duty

若相鄰兩天內(nèi)所屬的值勤班次不同時,我們就認為該機組人員進行了一次班次交替。但當相鄰的兩天中有一天為休息日時,由于機組人員的休息時間達到了24 小時,有足夠的時間來調(diào)整自己的作息規(guī)律,則不被認為進行了班次交替。為實現(xiàn)班次一致性,需要在求解子問題時加入新的約束。這里我們設(shè)計了兩組不同的約束形式,在后續(xù)的數(shù)值實驗中對分別帶有這兩組約束的模型進行求解檢驗并觀察其效果。

第一種約束形式如下所示:

參數(shù):

Lt:表示預設(shè)的最大班次交替次數(shù);

t:代表值勤期的時間周期,t∈T,T為日期集合;

sfi:表示航段i的出發(fā)時刻所屬的值勤班次;

變量:

at:0-1 變量,表示第t日與第t+1 日之間是否有班次交替;

bt:取值為[0,4]的整數(shù)變量,表示第t個值勤期的班次,休息日的值勤班次記為0;

ct:0-1 變量,表示第t+1 個值勤期的班次與第t個值勤期的值勤班次差值是否為0;

yt:取值為[0,4]的整數(shù)變量,表示第t+1 個值勤期的班次與第t個值勤期的班次差值的絕對值;

dt:0-1 變量,計算yt所用到的中間變量;

式(2i)表示一周之內(nèi)班次交替的數(shù)量不超過最大交替次數(shù)。式(2j)和(2k)表示某日與其后一日若有一日為休息日時,則當日與后一日沒有班次交替,即bt或bt+1等于0 時,at=0。式(2l)表示第t日與第t+1 日值勤班次的差值為0,即班次相同時,沒有進行班次交替。式(2m)計算了第t個值勤期的班次值,由當日的起始航段所屬的班次決定。式(2n)表示當兩天都不為休息日(當日存在執(zhí)飛航段)且班次差值不為0(班次值不同即ct=1) 時,第t日與第t +1 日之間有班次交替,此時at=1。式(2o)表示當yt=0(兩日班次的值相等) 時,ct=0,表示兩日班次值不存在差值;當yt≠0時,ct=1,表示存在差值。式(2p)～(2r)是將yt=| bt+1-bt|轉(zhuǎn)化為線性不等式的表示。

第二種約束形式如下所示:

變量:

ξi: 0-1 變量,是用來限制at取值的中間變量

β: 0-1 變量,是將絕對值約束轉(zhuǎn)換為線性表達式的中間變量

式(2i)表示一周之內(nèi)班次交替的數(shù)量不超過最大交替次數(shù)。第二種約束中的式(2i)-(2k)含義與第一種約束形式中的式(2i)-(2k)相同。式(2l)-(2m)表示將at≤轉(zhuǎn)化為線性表達式,其含義為第t日與第t +1 日值勤班次的差值為0 時,沒有進行班次交替。式(2n)表示第t個值勤期的班次的值的計算方式,由當日的起始航段所屬的班次決定。式(2o)-(2r)表示當bt和bt+1之間有差值且不存在休息日(即bt≠0且bt+1≠0) 時,at取值為0,否則存在班次交替,即at取值為1。

(2) 過夜城市一致性約束

過夜城市是機組人員在休息期時所處的地點,為了使機組人員休息時能盡量處于熟悉的環(huán)境中,需要將機組人員在一個周期內(nèi)除基地外的過夜城市的數(shù)量限制在一定區(qū)間內(nèi)。我們只統(tǒng)計值勤期內(nèi)不同的休息點的數(shù)量,且基地不作為過夜城市納入計算。為了實現(xiàn)過夜城市一致性,需要在求解子問題時加入以下約束:

參數(shù):

c:代表城市,c∈C,C為所有的城市的集合;

c(i):表示所有降落城市為c的航段的集合;

Lc:表示預設(shè)的最大過夜城市數(shù)量;

變量:

cityc:0-1 變量,表示城市c是否為過夜城市。

式(2s)表示總過夜城市數(shù)量不能超過預設(shè)的最大過夜城市數(shù)量限制;式(2t)～(2v)表示通過實際降落地點情況來計算出過夜城市數(shù)量。如果城市c是過夜城市,那么必須有在這個城市降落的航段和第二天在這個城市起飛的航段,并且城市c不能是基地。式(2t)表示對于城市c而言,如果降落地點為該城市的所有航段i,都不存在跨天的后續(xù)航段,則城市c不是過夜城市,即cityc=0。式(2u)表示對于城市c而言,如果降落地點為該城市的航段i中,有跨天的后續(xù)航段(航段i是當日的結(jié)束航段),且城市c不是基地,那么城市c是該排班計劃(列) 的一個過夜城市,即cityc=1。式(2v)表示當城市c為基地時,該城市也不能算作過夜城市。

4 模型求解算法

精確算法求解排班任務(wù)可采用經(jīng)典的列生成算法框架,求解非常耗時,即使使用流行的數(shù)學規(guī)劃商用求解器(如IBM ILOG CPLEX),針對大規(guī)模的應(yīng)用問題,也無法有效求解。本文在排班計劃中新添加了一致性規(guī)范約束,使得問題求解變得更為困難。為提高求解速度和效率,我們針對列生成算法框架中的子問題,設(shè)計了一個基于動態(tài)規(guī)劃的考慮一致性標準的尋找優(yōu)質(zhì)排班計劃的啟發(fā)式算法。雖然它不能像精確算法那樣保證最優(yōu),但通過對比驗證,該算法收斂精度高,并且能保證較好的求解質(zhì)量。

4.1 列生成算法

列生成算法是一種算法框架,適用于求解一類每個決策方案對應(yīng)整體規(guī)劃模型中約束矩陣的一列的組合優(yōu)化問題。接下來,本文簡要討論列生成算法(算法1)的總體框架。算法1 首先生成一些初始可行的排班計劃(列)來構(gòu)造受限主問題(restricted master problem),(第1 行)。然后在列生成過程中解決受限主問題(RMP)的線性規(guī)劃松弛問題(第3行)。求解受限主問題后,將主問題的對偶值傳遞給子問題修正路徑參數(shù)并進行求解(第4 行),子問題的目標是生成新的排班計劃環(huán),如果我們能找到降低成本為負的排班計劃(列)(第5 行),將迭代地把這些列添加到受限主問題(RMP)中(第7 行),這些排班計劃可能會改善當前受限主問題的解。如果滿足收斂條件(即列的降低成本非負),則求解過程停止,循環(huán)跳出(第9 行)。最后我們求解受限主問題(RMP),如果此時解均為整數(shù),則求解結(jié)束獲得最優(yōu)解(第11 行)。否則我們添加變量整數(shù)約束(第12 行)再次求解。

列生成算法的求解速度和質(zhì)量主要取決于子問題生成新排班計劃(列)的速度和質(zhì)量。如果在模型求解初期或在每次迭代能夠生成大量高質(zhì)量的排班計劃,這將提高原問題的求解速度和質(zhì)量。本文聚焦于迭代求解子問題時的排班計劃質(zhì)量,因此在獲得初始解時暫不考慮解的質(zhì)量,只保證解中包含的排班計劃滿足其生成規(guī)則并能覆蓋到所有預設(shè)航段即可。因此可多次調(diào)用3.2 節(jié)中求解子問題的模型,將目標函數(shù)設(shè)定為一個常數(shù),每次添加針對某一未覆蓋航段的約束以確保其被初始排班計劃覆蓋,多次求解后即可獲得一組覆蓋所有航段的排班計劃集合,也就是我們的初始解。初始解的求解過程如下圖1 所示。

圖1 初始解求解流程Figure 1 Finding the initial solution

為了減少子問題的求解次數(shù),提高候選排班計劃的數(shù)量,提高求解速度和收斂精度,我們允許主問題加入子問題新生成所有有效列,而不僅僅是最優(yōu)的列,同時在一定次數(shù)迭代次數(shù)后,對主問題的列進行一個篩選操作,以保證主問題模型的高效和精簡。

4.2 基于動態(tài)規(guī)劃的啟發(fā)式算法

由于航段數(shù)目過大且同時需要考慮一致性約束,使用分支定界的精確算法求解子問題這樣的MIP 問題求解時間過長,因此我們設(shè)計了針對子問題的基于動態(tài)規(guī)劃的啟發(fā)式算法求解,以兼顧生成列的速度和有效性。

我們可以把航班的前后依賴關(guān)系抽象作是一個有向無環(huán)圖(directed acyclic graph,DAG),那么所有的排班計劃都是該有向無環(huán)圖上的一條路徑。再將每趟航班所需的飛行與值勤時間看作資源,那么3.2 節(jié)中的子問題其實可以看作是在滿足時間資源約束條件下,尋找有向圖中的最長路徑問題[35]。因此,機組排班的子問題原則上可以用最長路徑算法求解,但是我們的排班問題附加有一致性約束條件。由于一致性標準的路徑依賴性,在最長路搜索過程中還要同時計算航班的班次交替次數(shù)和過夜城市數(shù)量,進一步增加了算法實現(xiàn)的復雜性。因此我們設(shè)計了一種新的基于動態(tài)規(guī)劃的啟發(fā)式算法來求解子問題獲取新的排班計劃,不但保證了一定的求解質(zhì)量且大大提高了求解速度和效率,使得整個排班問題可以在一定時間內(nèi)求解完成。具體來說就是在受限主問題求解后,將其對偶值傳遞給子問題,更新有向圖每個點的權(quán)值,再利用下述的動態(tài)規(guī)劃算法求得一條新的最長路徑,當無法生成一條權(quán)值為正的路徑時停止。

4.2.1 動態(tài)規(guī)劃基本步驟

我們首先介紹無一致性約束的子問題動態(tài)規(guī)劃算法如下,我們按照單個值勤期t劃分子問題的階段,將其轉(zhuǎn)化為多階段決策問題,在每個階段中我們需要決定多個航段如何順序排列組成這一值勤期的飛行任務(wù)。問題中的指標函數(shù)就是當前階段所包含的所有航段修正后的成本系數(shù)的加和,我們定義指標函數(shù)F(c,t,d,i) 為城市c出發(fā)的排班計劃在第t日的d時刻完成了航段i任務(wù)時的最長路徑長度,給出狀態(tài)轉(zhuǎn)移方程為:

動態(tài)規(guī)劃問題求解的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件,選取恰當?shù)臓顟B(tài)變量。對于本問題而言,如需要精確求解那么狀態(tài)中的時刻d需要包括單個值勤期的總耗費時間、該值勤期的飛行時間以及航段i的落地時間。因此如果直接使用上述狀態(tài)轉(zhuǎn)移方程求解將具有極大的時間復雜度和空間復雜度,無法在可接受時間范圍內(nèi)實現(xiàn)。因此我們再次考量到每段航班的耗時在1 至3 小時左右,單個值勤期執(zhí)飛的航班數(shù)目一般在3 至7 個左右的特點,由此引入了一個新的變量p來描述時刻狀態(tài),p表示該值勤期的執(zhí)飛任務(wù)次序,取值為[0,P]。這樣在確保解的一定的質(zhì)量同時大大降低了時間和空間復雜度,能夠快速高效地進行求解。此時新的指標函數(shù)F(c,t,p,i)為城市c出發(fā)的排班計劃在第t日的第p個任務(wù)為航段i時的最長路徑長度,新的狀態(tài)轉(zhuǎn)移方程為:

該動態(tài)規(guī)劃算法的步驟如下

4.2.2 納入一致性標準的模型

(1) 班次一致性

納入班次一致性的動態(tài)規(guī)劃算法在定義指標函數(shù)時需要多加入一維變量s,取值為[0,S],表示當前更換班次的次數(shù),則此時的指標函數(shù)F(c,t,p,s,i) 為城市c出發(fā)的排班計劃在第t日的第p個任務(wù)為航段i且當前換班次數(shù)為s時的最長路徑長度,狀態(tài)轉(zhuǎn)移方程為:

與上述基礎(chǔ)步驟相比,在每一階段更新指標函數(shù)時,如果航段i,j屬于同一個值勤期(t相同),那么此時航段i的換班次數(shù)與航段j相同,如果航段i,j不屬于同一個值勤期(t不同),此時需要比較航班i,j所屬值勤期的始發(fā)航段的班次是否相同,若相同則兩者的換班次數(shù)相同否則航班i的換班次數(shù)為航段j的換班次數(shù)加一,其余步驟和算法2.1 一致。

(2) 過夜城市一致性

納入過夜城市一致性的動態(tài)規(guī)劃算法在定義指標函數(shù)時需要多加入一維變量r表示當前過夜城市的數(shù)量,則此時的指標函數(shù)F(c,t,p,r,i) 為城市c出發(fā)的排班計劃在第t日的第p個任務(wù)為航段i且當前過夜城市數(shù)量為r時的最長路徑長度,狀態(tài)轉(zhuǎn)移方程為:

由于每個值勤期之間航段的起始城市與降落城市相同,所以仍舊可以在每一值勤期起始位置更新過夜城市的數(shù)量,但與換班次數(shù)相比,過夜城市一致性統(tǒng)計的是除基地外的不同城市種類而非每一值勤期之間的城市更換,此時我們將過夜城市數(shù)量的可行值r的取值范圍設(shè)為大于Lc(預設(shè)最大過夜城市數(shù)量)的值Lr(可取Lc至T之間的任一數(shù)值),然后在處理時分兩步走,首先在每一階段同4.2.2.1 更新指標函數(shù),如果航段i,j屬于同一個值勤期(t相同),那么此時航段i的過夜城市數(shù)量與航段j相同,如果航段i,j不屬于同一個值勤期(t不同),此時需要比較航班i,j所屬值勤期的始發(fā)航段的過夜城市是否相同,若相同則兩者的過夜城市數(shù)量相同否則航班i的過夜城市數(shù)量為航段j的加一。然后我們在找到的排班計劃中檢查實際過夜城市種類數(shù),如果小于預設(shè)值我們將其納入最后結(jié)果,如果不符合則舍去。同時我們參考了自適應(yīng)領(lǐng)域搜索中參數(shù)的更新方法在實驗中根據(jù)主問題的目標值不斷調(diào)整Lr的數(shù)值以獲得更快的收斂速度和更優(yōu)質(zhì)的解。

5 數(shù)值實驗

5.1 實驗環(huán)境

因為考慮了新的一致性約束,本文研究的問題與模型和過往研究中的機組排班問題存在著較大不同之處。因此本文提出的算法和結(jié)果不能通過計算實驗和現(xiàn)有文獻中的算法結(jié)果直接進行比較。于是,我們選擇與商業(yè)求解器(IBM ILOG CPLEX)的求解情況做詳細的對比。實驗包括了模型是否含有一致性約束的兩種不同情況。實驗數(shù)據(jù)來自華東地區(qū)某大型民營航空公司2019 年7 月國內(nèi)短途飛行航線數(shù)據(jù),其中共包含有39 架飛機的航線,每條航線代表了一架飛機在一周內(nèi)飛行的路線。39 條航線中共包含1420 個航段。本實驗將通過求解1420 個航段的排班計劃來檢驗模型和算法對實際問題的求解能力,并分別觀察加入一致性約束后機組人員數(shù)量的增長情況。數(shù)值實驗在配置了2.8 GHz 主頻的英特爾至強四核處理器、16 GB 內(nèi)存的CentOS Linux 7 的工作站上進行。我們采用Java 1.8 與IBM ILOG 提供的混合整數(shù)規(guī)劃商用求解器CPLEX 12.6.1進行編程實現(xiàn)。

5.2 實驗結(jié)果與分析

首先我們給出班次交替次數(shù)和過夜城市地點的排班計劃示例。如表6 所示的排班計劃,可以看到該機組人員此周的工作共有五個班次,分別屬于第2,2,1,2,4 班次,根據(jù)3.3.2.2 中的規(guī)則,第二班(周二)與第三班(周三)之間發(fā)生一次交替,第四班(周六)與第五班(周日)之間發(fā)生一次交替,而第三班(周三)與第四班(周六)之間雖隸屬班次不同但其中有一個兩天的休息期,因此不計入工作時間的交替,所以這條排班計劃一共有2 次班次交替。且這五個班次的過夜城市分別為杭州,西安,烏魯木齊,杭州和銀川,由于烏魯木齊為基地城市且杭州作為過夜城市重復出現(xiàn)了兩次,所以此排班計劃中的過夜城市數(shù)量記做3。

表6 增加班次與過夜城市列的排班計劃示例Table 6 Example of a work line

首先用不包含一致性約束的模型求解排班計劃,對比用CPLEX 和動態(tài)規(guī)劃啟發(fā)式算法求解得出的結(jié)果,可以看到CPLEX 求得至少需259 列排班計劃才能覆蓋所有航段,而啟發(fā)式算法求出只需要126 列排班計劃。統(tǒng)計啟發(fā)式排班計劃中班次交替與過夜城市數(shù)量如下表7 所示。

表7 基礎(chǔ)模型班次交替與過夜城市情況Table 7 Statistics of shift alternation and overnight city for the basic model

由上表7 可知84.13%的排班計劃交替次數(shù)不超過2次,這些機組人員在一周的工作時間內(nèi)只要調(diào)整兩次及以下的作息,但可以看到仍有大約15.87%的機組人員在一周內(nèi)要調(diào)整3 次到4 次作息時間,這對作息規(guī)律的影響是非常大的。所以本文決定將班次一致性的范圍限制在[0,2]的區(qū)間內(nèi)。同時僅有26.19%的排班計劃過夜城市個數(shù)不超過2個,有大量的機組人員在一周內(nèi)要在3 個及以上甚至5 個不同的城市度過休息期,這將非常不利于機組人員適應(yīng)環(huán)境以獲得更好的休息。所以本文將過夜城市數(shù)量限制在[0,2]的區(qū)間內(nèi)?；A(chǔ)模型的安排存在非常多不合理之處,所以有必要在班次特別是外出過夜城市中加入限制。

此時我們利用CPLEX 與啟發(fā)式算法分別求解問題。下表8,9,10 所示是兩者在分別求解基本模型、納入班次一致性約束模型和納入過夜城市一致性約束模型的結(jié)果。

從表8 可以看出我們的啟發(fā)式算法新生成的列的數(shù)量遠遠多于直接使用CPLEX 獲得的列的數(shù)量,啟發(fā)式算法在求解次數(shù)更多的情況下,所用的時間不到使用CPLEX 直接求解模型耗時的百分之一,同時最優(yōu)值也從CPLEX 求得的259 下降到了126,效果有顯著提升。可見啟發(fā)式算法在效率和可行性上都有保證,不僅能大大節(jié)約時間,而且能獲得高質(zhì)量的求解結(jié)果。

表8 基本模型求解情況Table 8 Results of the basic model

上表9 和10 分別展示了分別加入班次和過夜城市一致性約束的求解情況。表9 展示了納入班次一致性后兩種不同建模形式下的CPLEX 與啟發(fā)式的求解結(jié)果。在相近時間內(nèi)(約72 小時)第二種建模形式略優(yōu)于第一種,其最優(yōu)排班計劃數(shù)量分別為335 與354。相較于基礎(chǔ)模型求得的259 我們可以看出加入班次一致性后CPLEX 求解速度大大下降,這又進一步證明了CPLEX 在此等規(guī)模下求解是不合適的,而提出的啟發(fā)式算法在600 秒內(nèi)獲得最優(yōu)解為130,解的質(zhì)量有了顯著提升。通過表10 中我們可以看到CPLEX在求解過夜城市一致性時也表現(xiàn)不佳,在近72 小時內(nèi)求得最優(yōu)解為375,而啟發(fā)式求得的解為135,故而我們在下文對啟發(fā)式的結(jié)果進行進一步分析。

表9 納入班次一致性的模型求解情況Table 9 Results of the model with shift consistency

表10 納入過夜城市一致性的模型求解情況Table 10 Results of the model with overnight city consistency

從表11 中可明確看出加入班次與過夜城市一致性約束的兩種模型生成的最優(yōu)解中的總排班計劃數(shù)量與基礎(chǔ)模型相比并未有顯著增加,班次一致性加入后僅需增加4 條新排班計劃即可覆蓋預設(shè)航段,過夜城市一致性加入后僅需增加9 條新排班計劃,比之基礎(chǔ)模型分別增加了3.175%和7.143%。

表11 三組模型求解情況對比Table 11 Comparison of solutions for three models

增加班次一致性條件后,平均每個航班計劃飛行時間和值勤時間都沒有太大變化,我們對具體解分析后發(fā)現(xiàn)排班計劃數(shù)的增加是源于置位航班使用的增加。相對地,增加過夜城市一致性條件后,平均飛行時間和值勤時間都有3～4 個小時的減少,可以明顯看出由于要求過夜城市一致后,排班計劃路線發(fā)生了調(diào)整,排班計劃數(shù)量增加,致使平均飛行時間和值勤時間略有下降。

上述三個模型的求解結(jié)果不僅對模型中一致性約束設(shè)定的正確性進行了驗證,也展示了加入一致性約束前后所需排班方案的變化情況,從機組人員數(shù)量這一方面來看,增加一致性約束后機組人員數(shù)量均有所上升,在一定程度上說明增加排班計劃的一致性是以增加人力成本為代價的,但其所需付出的代價是在可接受范圍之內(nèi)的,同時雖然三個模型的日均飛行小時與值勤小時均不相同,有所起伏,但是變化幅度很小,結(jié)果較為穩(wěn)定,這說明了納入班次與過夜城市一致性后并未使得飛行時限和工作時間有較大的波動。此外我們統(tǒng)計了兩組一致性約束加入后班次與過夜城市情況(見表12,13)。

表12 增加班次一致性約束班次與過夜城市情況Table 12 Results of shift consistency and overnight cities consistency

由表12 統(tǒng)計我們可以看出納入班次一致性的模型求得的排班計劃很好地將班次交替數(shù)量限制在了[0,2]的區(qū)間內(nèi)。班次交替次數(shù)在0 次,1 次與2 次間的占比分別為8.462%,23.846%和67.692%,基本都在合理的區(qū)間范圍內(nèi)。與基本模型結(jié)果相比,過夜城市數(shù)量比例的分布沒有太大的變化,仍舊集中在2 至4 之間。從表13 可知模型在納入過夜城市一致性后所求得的排班計劃也很好地將過夜城市數(shù)量限制在了[0,2]的區(qū)間內(nèi),過夜城市數(shù)量在1 個和2 個的比例分別為22.963%和77.037%。而與基本模型結(jié)果相比,班次交替次數(shù)比例的分布也沒有太大的變化,集中在1 至3次之間。

表13 增加過夜城市一致性約束班次與過夜城市情況Table 13 Results of shift consistency and overnight cities consistency

另外,在敏感度分析方面,我們調(diào)整了允許班次交替數(shù)量的區(qū)間,將其上限控制在0 次、1 次和2 次分別進行試驗得到下表14 結(jié)果,從表中我們可以看出,當班次交替數(shù)量上限為0,也就是不允許機組人員有換班時,為執(zhí)行整個航段計劃我們共需要151 人,與基礎(chǔ)模型相比增加了19.84%。可見,嚴格的班次輪替要求會導致人力成本大大增加,同時因為人員的增加,平均飛行小時數(shù),值勤小時數(shù)和工作天數(shù)下降幅度較大,從而造成了人力資源的浪費。當班次交替數(shù)量上限為1 時,我們需要137 人,與基本模型相比增加了8.73%,而平均飛行小時數(shù),值勤小時數(shù)和工作天數(shù)則是略有下降。當班次交替數(shù)量上限為2 時,我們需要130 人,與基本模型相比所需人數(shù)增加了3.18%,平均飛行小時數(shù)下降了0.46 小時每人,值勤小時數(shù)增加了0.11 小時每人,工作天數(shù)則是略有下降,下降幅度為0.02 天每人。由此可見,雖然更嚴格的班次交替數(shù)量會提升機組人員的工作體驗和工作效率,但是過于嚴格的要求可能會導致排班本身的安排不夠緊湊,從而導致人力資源的浪費,管理者需要就具體情況對進行權(quán)衡。

表14 不同換班次數(shù)下模型求解情況對比Table 14 Comparison of solution with different shift times

同時我們也對班次區(qū)間調(diào)整后的班次與過夜城市情況進行統(tǒng)計,結(jié)果如下圖所示。我們可以看到當班次交替上限分別為0,1,2 時,班次交替次數(shù)均在約束區(qū)間內(nèi),三者過夜城市數(shù)量都較為集中在3 個,所占比例均達40%以上。我們關(guān)注到也有20%左右的排班計劃需要在多于4 個城市駐足,過夜數(shù)量多這一點需要在后期引起重視,我們也初步探求了將過夜城市限制在0 至1 個排班計劃數(shù)量的變化,結(jié)果顯示為減少過夜城市數(shù)量,排班計劃數(shù)量會大幅上漲,這極易導致高人力成本,所以上述兩點都啟示我們在安排值勤時需要更多地關(guān)注到過夜的具體地點和數(shù)量,比如我們建議可以和某些經(jīng)常出現(xiàn)的城市達成較為長期的合作以降低運營成本等。同時在后期的排班研究中我們可以更加關(guān)注過夜城市選擇對排班計劃的影響機理?？偨Y(jié)來說,從上述結(jié)果我們可以得到以下管理啟示,納入一致性標準的模型所求得的排班計劃與基礎(chǔ)模型解得的排班計劃在飛行與值勤時長的表現(xiàn)上相差不大,新模型在保留了原有計劃的效率與收益的同時,又滿足了我們提出的新的班次與過夜城市的約束,使得排班方案既合理有效,又能夠考慮到機組人員的精神狀態(tài)與身心健康,這啟示我們在實際的運用中,航空公司可以在可接受的人力成本的增幅下,將一致性更多的納入考量,提升機組人員的滿意度和工作效率,進一步提高綜合競爭能力。

表15 不同換班次數(shù)下模型求解情況對比Table 15 Results of overnight cities consistency with different shift times

6 結(jié)束語

6.1 研究總結(jié)

本文針對現(xiàn)有的機組人員排班問題研究中大多關(guān)注成本最小化和運營穩(wěn)定性目標、并沒有將機組人員身心健康的關(guān)注納入系統(tǒng)考慮范圍這一問題,將新的一致性規(guī)范約束引入機組排班問題這一領(lǐng)域。我們在排班計劃中增加班次一致性和過夜城市一致性標準,有利于保障機組人員身心健康與航空公司運營的穩(wěn)定性,為航空公司制定更加安全合理的排班計劃提供了理論參考。

本文構(gòu)建了基于真實排班計劃規(guī)則并包含一致性標準的模型,并基于列生成的求解算法,針對性的提出了一個啟發(fā)式的動態(tài)規(guī)劃求解生成列。在此基礎(chǔ)上使用真實航段數(shù)據(jù)驗證了模型的正確性以及算法的求解效率,并對比分析了設(shè)定兩個一致性約束前后所需機組人員數(shù)量的變化情況,證明了該模型和算法能夠有效求解真實情況下規(guī)模較大的機組人員排班問題,這將有助于航空公司結(jié)合實際情況,更好地將一致性約束運用到實際的排班計劃過程中,統(tǒng)籌考慮排班計劃的成本與質(zhì)量,提升管理和服務(wù)水平。但研究也存在一些局限性,有待進一步改進。本文模型中只考慮了使機組人員數(shù)量最小化的優(yōu)化目標,即使用最少的排班計劃數(shù)量來覆蓋所有的航段,而未考慮每條排班計劃的具體成本。在航空公司的實踐中,需要根據(jù)每一條排班計劃的航段數(shù)量、飛行地點、過夜地點數(shù)量等計算飛行津貼、任務(wù)津貼、旅館費用等的費用作為排班計劃的成本,因而加入一致性約束前后每條排班計劃的成本會發(fā)生不同的改變。因此,本文中求得的最小化目標與航空公司真實的成本最小化目標之間有一定的差距。此外,本研究在使用列生成算法求解排班問題的子問題時為了加快求解算法的速度設(shè)置了求解器的最大的求解時間以及最大求解次數(shù),因而最終選擇出的排班計劃會與理論上的最優(yōu)解選擇的排班計劃不同。本文雖然通過多次嘗試設(shè)定了這兩個參數(shù)的值,但是最大求解時間與最大求解次數(shù)的設(shè)置對最終結(jié)果的影響以及如何取得求解速度和求解性能之間的平衡點還有待進一步研究。

6.2 未來展望

機組排班問題是航空公司運營調(diào)度重要問題之一,影響機組人員排班計劃生成的因素有很多,如民航與航空公司的規(guī)定、人力成本、基地數(shù)量、飛機航線、上一周期排班計劃等,本研究只考慮了其中一部分因素。因此,在未來的研究中可以引入其他因素綜合考慮更全面的排班模型,以生成更完善的排班計劃。其次,本研究中只考慮了一致性規(guī)范中的班次和過夜城市對機組排班問題的影響,我們建議未來的研究中可以探討其他方面的一致性約束,例如機組與客機機型的一致性、機組內(nèi)成員的一致性(例如正副機長的一致優(yōu)先配對)等的加入對排班計劃的影響,從多方面提高排班計劃的質(zhì)量。最后,可將一致性與排班計劃研究的其他方向相結(jié)合,例如將一致性約束與機組排班計劃魯棒性的研究相結(jié)合,分析對比增加了一致性約束求解得到的排班計劃是否比原來的排班計劃在遇到延誤或其他突發(fā)事故時的運營更具有穩(wěn)定性等。