基于混合整數(shù)規(guī)劃的航班保障資源調(diào)度研究

康永, 汪福軍, 沈光越

(東部機場集團有限公司, 江蘇, 南京 211106)

0 引言

航班保障過程中需要大量的特種車輛和保障人員,以國內(nèi)某大型機場為例,高峰時段每天起降航班700多架次,航班保障車輛近500臺,保障人員超過1000人,機場的保障效率會直接影響航班的準點率。因此,如何高效合理地調(diào)度各種航班保障資源,成為每個大中型機場迫切需要解決的問題。

很多機場采用傳統(tǒng)資源調(diào)度模式,以紙筆記錄方式實現(xiàn)任務分配,由于不同航班所需要的保障資源不同,以及個人工作效率和記憶能力的限制,隨著航班量的增加,只能通過不斷增加調(diào)度人員和調(diào)度層級來解決。信息技術的不斷發(fā)展為改變傳統(tǒng)調(diào)度模式提供了機遇,由于需要根據(jù)不同的航空公司、航班類型、飛機型號、機位性質、車輛類型、人員資質等條件進行分配,因而要求航班保障任務分配方法能夠滿足多種限制條件。同時,也需要充分考慮機場不斷變化的航班起降時間以及航班保障車輛人員的動態(tài)位置和狀態(tài),避免出現(xiàn)航班保障任務遺漏的情況,因此需要分配方法能夠根據(jù)實時的運行數(shù)據(jù)對結果快速進行重新計算和分配。

國內(nèi)外學者從不同的角度對航班保障資源分配問題開展了大量的研究。馮明端等[1]通過遺傳算法研究了機場地面特種設備車輛構建帶有容量限制和時間窗的全種類車型車輛聯(lián)合調(diào)度的約束模型,并與先到先服務算法相比,明顯減少了車輛的使用數(shù)目和行駛距離。吳枕[2]根據(jù)機場保障車輛實際調(diào)度中的約束條件以及不同的需求建立了車輛動態(tài)協(xié)同調(diào)度模型,采用遺傳算法對昆明長水國際機場車輛的實際運營數(shù)據(jù)進行挖掘,實驗結果表明其算法在解決航班信息變化影響的問題時,能夠很好地滿足車輛動態(tài)調(diào)度的要求,降低車輛的運行成本。

混合整數(shù)規(guī)劃模型是指部分決策變量限制為整數(shù)的規(guī)劃問題,其經(jīng)常被用來處理復雜網(wǎng)絡選址、資源排班調(diào)度等可抽象為0和1選項的場景[3]。BAYLISS等[4]提出了一種混合整數(shù)規(guī)劃方法來安排航空公司的后備機組人員,其目標是找到在一組輸入情景中最小化總體中斷水平的后備人員時間表。張紅穎等[5]按照科學合理地權衡機場各種約束限制需求,提出了優(yōu)化停機位調(diào)度問題的混合整數(shù)規(guī)劃模型,目標是在確保航空器安全運行的前提下使得航班延誤的總時間最短。根據(jù)以上研究可知,混合整數(shù)規(guī)劃模型已應用在多種行業(yè)的資源調(diào)度上,但是在航班保障資源調(diào)度方面的應用少有研究。

1 模型建立

經(jīng)與機場航班保障地面服務管理人員深入研究和探討,梳理出機場航班保障資源管理中心整體流程,主要包括3個主要步驟:首先根據(jù)次日航班計劃編排保障資源計劃,并形成預排班表;其次根據(jù)航班運行情況,以特定規(guī)則進行最優(yōu)化資源調(diào)度;最后由實際保障人員及時反饋任務接收和執(zhí)行進度。具體流程如圖1所示。

圖1 機場資源管理中心業(yè)務流程

規(guī)劃排班和調(diào)度管理是最重要的兩個階段。在規(guī)劃排班階段,需要根據(jù)航班的次日計劃計算出次日需要的最少保障資源作為次日保障的最低人數(shù),并輸出次日排班表。調(diào)度管理階段由于航班量巨大且實時變化,以人工方式很難做到最優(yōu)調(diào)度,即使采用任務均衡規(guī)則也會因為特定航班特定服務而難以實現(xiàn),同時為防止航班延誤帶來的資源分配風險,有時候可能會在最低資源基礎上配置一定的冗余,由此需要根據(jù)實際資源重新分配保障任務,能夠實現(xiàn)根據(jù)航班運行情況動態(tài)生成保障任務,并結合當前航班保障資源分布情況進行最優(yōu)分配。綜上建立模型:模型一,根據(jù)航班次日計劃的起降時間,以獲取最小分配資源數(shù)量作為目標,具備預留好人工休息時間等約束條件;模型二目標為根據(jù)航班實際運行情況,結合現(xiàn)有可分配人員和已分配任務等約束條件,以分配后總體效益最大值作為目標。

1.1 模型一

模型一核心目標為按照航班次日計劃求解出所需最小航班保障資源數(shù)量以及相應的排班規(guī)則。根據(jù)航班計劃推導出所有保障任務清單情況,按照任務類型和資源工作時間范圍計算出所需最小資源數(shù)量和任務分配,其結果可作為次日排班計劃的參考。

(1) 變量定義

模型一的變量定義見表1,這些變量用來描述模型的目標函數(shù)和約束條件,為方便計算,可以將時間類數(shù)據(jù)轉化為整數(shù)類型,計算完成后再轉為時間類型。

表1 模型一變量定義

(2) 目標函數(shù)

目標函數(shù)是獲取所有空余時間最短,即用所有資源工作時間的總工時減去完成所有任務所需要的總工時,其函數(shù)如下:

(1)

其中,所有資源工作時間的總工時,用所有資源工作時間的和減去休息時間與已接收任務時間的和:

(2)

完成所有任務所需要的總工時的計算公式為

(3)

(3) 約束條件

約束條件如式(4)～式(9):

xrp∈{0,1}?r∈R,p∈P

(4)

(5)

PBp

?r∈R,p∈P,xrp≠0

(6)

?r∈R,p∈P,xrp≠0

(7)

?r∈R,p∈P,xrp≠0

(8)

?r∈R,r′∈R,p∈P,r≠r′,xrp≠0

(9)

式(4)表示保障任務被分配情況,為1時表示任務r被分配給資源p,否則為0。式(5)表示每個保障任務必須被分配,且只能分配1次。式(6)表示分配給同一資源的所有任務的開始時間和結束時間均要求在工作時間范圍內(nèi)。式(7)、式(8)表示所有待分配給同一資源的任務的開始時間和結束時間不能落在休息時間的區(qū)間內(nèi),休息時間的開始時間和結束時間也不可落在待分配任務的時間區(qū)間內(nèi),須確保各時間區(qū)間相互獨立,以此防止需要分配的任務和休息時間產(chǎn)生沖突[6]。式(9)表示所有待分配給同一資源的任務的開始時間和結束時間不能落在其他待分配任務區(qū)間,以防止待分配任務間的時間沖突。

1.2 模型二

由于不同航班所需保障要求不盡相同,比如某些特殊服務航班需要安排工作經(jīng)驗豐富的保障資源,因此不同航班對資源保障的期望值不同,模型二核心目標為按照航班當日執(zhí)行情況快速地解出資源分配方案。要求模型二能夠根據(jù)不斷變化的航班執(zhí)行情況實時推導出所有保障任務清單情況,按照任務類型、可用資源清單、資源空余工作時間、資源與任務匹配程度等條件快速計算出最優(yōu)化分配策略。

(1) 變量定義

模型二的變量定義見表2,這些變量用來描述模型的目標函數(shù)和約束條件。

表2 模型二變量定義

(2) 目標函數(shù)

目標函數(shù)為獲取所有任務分配后的最大權值總和,如式(10):

(10)

(3) 約束條件

約束條件如式(11)～式(17):

xrp∈{0,1}?r∈R,p∈P

(11)

(12)

PBp

?r∈R,p∈P,xrp≠0,Qrp>0

(13)

?r∈R,p∈P,i∈I,xrp≠0,Qrp>0

(14)

?r∈R,p∈P,i∈I,xrp≠0,Qrp>0

(15)

?r∈R,r′∈R,p∈P,

r≠r′,xrp≠0,Qrp>0

(16)

(17)

式(11)表示保障任務被分配情況,為1時表示任務r被分配給資源p,否則為0。式(12)表示每個保障任務必須被分配,且只能分配1次。式(13)表示分配給同一資源的所有任務滿足權值不為0,并且開始時間和結束時間均要求在資源的工作時間范圍內(nèi)。式(14)、式(15)表示所有待分配給同一資源的任務滿足權值不為0,并且開始時間和結束時間不能落在資源已接收任務或休息時間的區(qū)間內(nèi),已接收任務或休息時間也不可落在待分配任務的時間區(qū)間內(nèi),以此防止需要分配的任務和休息時間產(chǎn)生沖突。式(16)表示所有待分配給同一資源的任務滿足權值不為0,并且開始時間和結束時間不能落在其他待分配任務區(qū)間,以防止待分配任務的時間沖突。式(17)表示考慮任務分配盡可能均衡,即分配給某資源所有任務數(shù)量之和處于任務分配平均數(shù)±1范圍內(nèi)[7-8]。

2 算例仿真

為驗證模型一與模型二的合理性和可行性,本文選取某機場某日從10:00到13:00之間的航班保障任務分配作為研究對象。模型一所需數(shù)據(jù)如表3所示,可計算出最少所需資源數(shù)量,模型二所需任務清單重復利用表3,在崗資源清單可根據(jù)當日在崗資源情況獲取,由于航班保障任務與保障資源匹配權重矩陣決定了任務分配的方式,同時其權重矩陣的影響因素很多,本文定義了0～5作為權重值來加以說明,其中,0表示保障資源不具備保障該航班條件,其他數(shù)值越高表示越適合保障該航班。具體數(shù)據(jù)見表4。

表3 航班保障任務清單

表4 航班保障任務與保障資源匹配權重

在系統(tǒng)設計方面,從低耦合度以及業(yè)務無關性角度考慮,將航班保障資源調(diào)度算法服務獨立部署,數(shù)據(jù)以參數(shù)方式進行傳遞來減少對實際生產(chǎn)系統(tǒng)的影響。通過MATLAB的混合整數(shù)規(guī)劃模型根據(jù)業(yè)務需求進行封裝并編譯,形成獨立服務部署在Linux服務器上,通過HTTP協(xié)議以POST請求方式進行調(diào)用,請求參數(shù)采用Json格式。實際生產(chǎn)環(huán)境為企業(yè)私有云平臺,硬件配置為8核CPU、64 G內(nèi)存、1 T硬盤,運行于Red Hat Enterprise 7.6,JDK1.8環(huán)境下,各項任務按照每天1000個航班做壓力測試,其計算時間均小于5 s,完全滿足實際工作要求。根據(jù)本文測試驗證數(shù)據(jù),模型一算法模擬器核心目標為當前所有任務分配所需要最少資源,計算結果的保障任務分配情況如圖2所示。模型二計算結果如圖3所示,其核心目標為當前任務、資源和分配權值條件下,同時考慮任務分配均衡的約束,所能分配結果的權值總和最大,即為最優(yōu)化任務分配方式。

圖2 模型一任務分配計算結果

圖3 模型二任務分配計算結果

3 計算結果分析

由于模型一主要目標是為解決航班保障資源預排班問題,經(jīng)機場全量數(shù)據(jù)驗證,航班保障調(diào)度排班資源反饋其結果完全能夠滿足作為資源分配的參考依據(jù),特別是當航班量變化較大,比如航班換季期間,很好地解決了人員冗余和資源短缺的問題。

某機場原有任務分配方式為先空閑先排班(FFFS)原則,主要考慮的約束條件為工作量均衡,以表3中的數(shù)據(jù)為例,實際任務分配情況如圖4所示。依據(jù)模型二的約束條件,不僅解決了先空閑先排班的工作量均衡需求,還能夠結合航班保障與資源匹配權重矩陣,計算出最優(yōu)資源調(diào)度結果。根據(jù)測試數(shù)據(jù)按照先空閑先排班結果計算出的總計權重值合計為52,而根據(jù)混合整數(shù)規(guī)劃模型二計算出的最大權重值合計為81,由此可見所提出的模型算法較先空閑先排班規(guī)則具有明顯的優(yōu)化和提升效果。

圖4 先空閑先排班規(guī)則的任務分配情況

4 總結

本文通過詳細分析航班保障資源實際工作特點和環(huán)境,提出根據(jù)混合整數(shù)規(guī)劃算法建立2套模型。模型一根據(jù)某機場實際運行情況,計算結果能夠為地面服務資源的工作計劃安排提供較好的幫助,減少了盲目排班情況的發(fā)生。模型二與實際先空閑先排班規(guī)則不同,在排班資源的權重合計方面有明顯的提升效果。