馬弘沈倪朱靖夏佳楠

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

0 引言

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

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

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

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

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

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

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

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

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

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

1.2 一致性標(biāo)準(zhǔn)相關(guān)研究

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

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

2 機(jī)組人員排班問(wèn)題介紹

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

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

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

表1 航段示例Table 1 Example of legs

(2)飛行值勤期(tour of duty):是指在某一天中,機(jī)組成員從為完成該次任務(wù)到達(dá)指定地點(diǎn)報(bào)到時(shí)刻開始,到飛機(jī)在最后一次飛行后發(fā)動(dòng)機(jī)關(guān)閉且機(jī)組成員沒有再次移動(dòng)飛機(jī)的意向?yàn)橹沟臅r(shí)間段。

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

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

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

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

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

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

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

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

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

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

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

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

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

表4 飛行機(jī)組最大飛行時(shí)間限制Table 4 Maximum flight time limitations for a flight crew

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

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

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

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

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

3 問(wèn)題模型

3.1 基本模型

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

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

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

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

3.2 子問(wèn)題

3.2.1 子問(wèn)題基本模型

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

參數(shù):

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

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

·πi:為來(lái)自受限主問(wèn)題的對(duì)偶解;

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

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

·fti:表示航段i的飛行時(shí)間;

·tdepi:表示航段i的起飛時(shí)刻;

·tarii:表示航段i的降落時(shí)刻;

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

·Dti:表示t日以航段i為起始航段的最長(zhǎng)值勤時(shí)間;

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

·Ecityi:表示航段i的降落城市的編號(hào);

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

變量:

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

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

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

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

·maxht:表示t日機(jī)組的最大飛行時(shí)間;

·maxdht:表示t日機(jī)組最長(zhǎng)值勤時(shí)間;

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

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

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

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

3.2.2 納入一致性標(biāo)準(zhǔn)的模型

(1) 班次一致性約束

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

表5 值勤班次時(shí)間表Table 5 Schedule of duty

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

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

參數(shù):

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

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

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

變量:

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

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

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

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

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

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

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

變量:

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

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

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

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

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

參數(shù):

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

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

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

變量:

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

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

4 模型求解算法

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

4.1 列生成算法

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

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

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

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

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

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

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

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

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

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

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

4.2.2 納入一致性標(biāo)準(zhǔn)的模型

(1) 班次一致性

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

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

(2) 過(guò)夜城市一致性

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

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

5 數(shù)值實(shí)驗(yàn)

5.1 實(shí)驗(yàn)環(huán)境

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

5.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

6.1 研究總結(jié)

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

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

6.2 未來(lái)展望

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