基于改進灰狼算法的通航運力匹配

杜貴和，汪 駿，凡麗明，周子林

(1. 國網通用航空有限公司，北京 102209；2. 中國民航大學電子信息與自動化學院，天津 300300)

1 引言

近年來社會用電量激增，國家電網系統(tǒng)面臨巨大運行壓力，客觀、合理的通航電力巡檢資源綜合匹配與調度能夠保障國家電網的安全、持續(xù)和平穩(wěn)的運行。因此急需建立一套通航電力運力匹配系統(tǒng)，科學合理地統(tǒng)籌通航公司運力生產資源。

受限于國內通航公司較小的機隊規(guī)模，目前國內通用航空領域在運力資源調度及分配方面研究成果較少。國外通航運力資源配置研究主要集中在帶時間窗的航空器飛行時間分配和航空器路徑維護以及機組排班管理等方面[1-3]。而在國內民航資源調度方面主要采用線性規(guī)劃及智能算法開展相應研究，文獻[4]建立了飛機排班問題的0-1整數模糊線性規(guī)劃數學模型，但該模型解決多目標多機型調度問題能力不足。文獻[5]針對多目標飛機排班問題，結合最優(yōu)化理論將多目標模糊線性規(guī)劃數學模型轉化為一般的線性規(guī)劃問題求解。非啟發(fā)式算法方面，文獻[6]提出了基于約束編程的動態(tài)列生成算法求解多機型排班模型，但樣本數據較大時計算效率較低。啟發(fā)式算法方面，文獻[7]建立飛機排班一體化優(yōu)化模型并采用具有自適應能力的單親遺傳算法求解，但容易陷入局部最優(yōu)解。但文獻中構建的模型與各類優(yōu)化算法多基于國內民航公司實際運行情況，并不完全適用于本文所研究的通航領域，需要進行一定的改進。此外，從模型求解方法來看，目前主要采用線性規(guī)劃法、動態(tài)列生成法及灰狼算法對所建模型進行求解，對于新型智能優(yōu)化算法的研究稍顯不足。而隨著各學科的發(fā)展，有必要探尋更多新型有效的算法以豐富該類問題的求解途徑。灰狼算法作為一種新型的群智能優(yōu)化算法由Mirjalili[8-10]等人于2014年提出，相比傳統(tǒng)智能算法需要調節(jié)的參數少，存在自適應調節(jié)的收斂因子[11-13]，能夠在全局最優(yōu)與局部最優(yōu)之間獲得較好平衡[14，15]。

相較于民用航空，通用航空產業(yè)起步較晚，信息化程度較低。由于機隊規(guī)模較小，一般只有1-2架航空器，因此機組資源安排也相對簡單。但是隨著公司業(yè)務規(guī)模的增長及機隊規(guī)模的增長，也將面臨如何降低運營成本，提高生產效益的問題[16]。本文根據國內某通用航空有限公司實際運行情況，分析通航運力匹配系統(tǒng)現狀的幾個問題，依據通航公司運力資源系統(tǒng)運行流程，構建運力匹配模型，采用結合通航電力巡檢特點的灰狼算法求解，最后收集實際運營數據進行仿真對比實驗。

2 通航運力匹配模型構建

2.1 運力匹配系統(tǒng)運行流程及特點

在通航公司的生產任務分配過程中，首先對航空器運行狀態(tài)、人員配置情況等運力信息進行運力評估，結合歷史天氣數據、周期性天氣狀況以及空管管制等外部制約因素，匹配年度巡檢需求，并分解為季度、月度計劃下達給各分區(qū)機組。各機組接到計劃性任務后，根據現有的航空器適航狀態(tài)、航檢設備工作狀態(tài)和人員倒休情況進行排班，分階段完成給定的任務。整體運力匹配系統(tǒng)運行流程圖如圖1所示。

圖1 運力匹配流程圖

2.2 運力匹配系統(tǒng)的現狀問題

通航公司目前通過人工排班，以機組與航空器相匹配的運力匹配方式來完成生產任務。在實際運營中，運力匹配系統(tǒng)會受到各種復雜的約束條件限制而產生效能低下的問題，總體上可以歸結于以下幾個方面：

1)生產任務飛行時長。

通航公司的各機型、同機型之間的單機日利用率參差不齊，單個生產任務所需飛行時間極差較大[17]。這說明公司航空器單機利用情況不均衡，同時也意味著航空器利用率有很大的提升空間。

2)巡線段任務重復度。

通航公司作業(yè)范圍點多面廣，由于受專業(yè)人員機型、作業(yè)天數、及航空器定檢、排故等因素限制，公司實際運行過程中會出現任務與運力資源匹配不當的情況，單機組頻繁往返基地執(zhí)行不同任務，嚴重降低了機組的產能效率。在優(yōu)化排班算法時需要考慮合理整合巡線段任務。

3)運力資源的快速響應能力。

隨著近年來通航公司機隊規(guī)模的擴大和專業(yè)保障人員、設備的激增，傳統(tǒng)模式下由人工進行資源的調配和評估的工作方法對人員的專業(yè)素質和能力提出極高的要求，容錯率極低，工作效率不高。

2.3 運力匹配系統(tǒng)建模

運力資源匹配數學模型的構建目標在于各區(qū)域分配到的機組數的確定，因此構建模型時需要綜合考慮運力匹配特點與流程等因素的影響。

2.3.1 目標函數的建立

構建運力匹配系統(tǒng)模型本質上是考慮如何在各種約束條件下求得最優(yōu)解的問題。該問題的求解目標在于使用最少運力資源完成給定任務量。目標函數如下

(1)

其中，As是系數矩陣，As的表達式為：

(2)

矩陣n維列向量分別代表機組n種作業(yè)類型任務人員配比，矩陣m維行向量分別代表機組m種工種人員配比。s代表不同區(qū)域，不同區(qū)域內運力資源分配方式不同，共有k個擬分配區(qū)域。

機組數自變量xs的表達式為：

(3)

向量中n個元素為區(qū)域s中n種作業(yè)類型的機組數。目標函數式(1)求和結果為各區(qū)域擬分配的運力資源結果總和，代表了使用最少運力完成生產任務的建模目標。

2.2.2 約束條件設定

求解目標函數主要有兩個約束條件：機組人員配置所代表的強約束和任務總量所代表的弱約束。

機組成員的相對固定性，決定了最終求得的目標函數結果必須小于等于總運行作業(yè)人員的數量，是優(yōu)先考慮的強約束，可列出強約束條件：

(4)

其中，Mi表示長度為m的列向量，代表通航公司m種職業(yè)人員總數。

強約束條件(4)不等式右端為通航公司各職業(yè)人員配置總數，不等式左端為擬分配的k個區(qū)域對應職業(yè)分配人數總和。

在滿足生產作業(yè)的條件下，需要考慮該人員配比組合能否完成擬分配任務量，可列出弱約束條件：

(5)

其中，Ns表示長度為k的列向量，代表k個不同區(qū)域年度擬分配任務量；Bs為任務量系數矩陣，Bs的表達式為：

(6)

矩陣m維列向量代表不同區(qū)域內同一種作業(yè)類型平均年可完成里程數；矩陣k維行向量代表同一區(qū)域內m種作業(yè)類型平均年可完成里程數。

系數矩陣Bs與機組數自變量xs相乘之后，可得到由xs決定的k個不同區(qū)域可分配任務量總數。

弱約束條件(5)代表不同區(qū)域可分配任務量總數，需大于等于不同區(qū)域年度擬分配任務量。在滿足強約束的條件下，弱約束條件求解過程中可能會出現無解或者解為負數的情況，即擬分配里程數總量大于可完成的年里程數，說明當前運力已無法滿足實際生產任務，需要任務外包。

3 基于改進灰狼算法的運力匹配模型求解

在公司運營過程中，運力匹配系統(tǒng)的基本目標是在減少總運營航空器數量的同時，提升單個生產任務巡線時長，同時合并優(yōu)化單個巡線段任務，減少任務重復度，達到提升單機日利用率和機組產能效率的目的。因此考慮到灰狼算法具有最優(yōu)化問題求解能力的特點，適合求解本文所討論的運力資源匹配性問題。但灰狼算法仍存在初始種群離散化程度高和后期收斂速度慢的問題。為改善這種現狀，本文結合通航電力巡檢特性，基于歷史數據對初始種群生成方式和狼群搜索機制進行改進，提出一種適合求解通航運力匹配模型的改進灰狼算法。

3.1 基本流程

灰狼算法是以狼群狩獵行為的追蹤、圍獵和狩獵三個環(huán)節(jié)構建的優(yōu)化算法。整個群體的適應度值自上而下分為首領狼(頭狼)α、副首領狼β、普通狼δ以及底層狼ω。首領狼α的適應度值最高，負責指定狼群移動方向；β狼和δ狼適應度值依次降低，負責向α狼提供參考方向；ω狼適應度值最低，服從于α、β、δ狼，并為狼群提供穩(wěn)定性。灰狼算法的基本思想是由α、β、δ狼定位獵物(最優(yōu)解)，引導ω狼包圍并進行狩獵(求解最優(yōu)解)。

狼群包圍獵物過程可表示為：

D=|C·Xp(t)-X(t)|

(7)

X(t+1)=Xp(t)-A·D

(8)

A=2a·r1-a

(9)

C=2r2

(10)

其中，D為灰狼個體與獵物的距離表達式；X(t+1)為灰狼位置更新表達式，t代表迭代次數，Xp(t)代表獵物(最優(yōu)解)位置向量，X(t)代表灰狼個體位置向量，C、A為系數向量；a隨著迭代次數由2線性減少至0，r1、r2為模在0至1間的隨機數。

在狼群包圍獵物后，通過計算適應度值最高的α、β、δ狼的位置來確定最優(yōu)解的位置：

(11)

(12)

最后由α、β、δ狼共同確定狼群的位置為：

(13)

3.2 系數向量C的生成改進

在灰狼算法的早期階段，如果出現系數向量C>1，則可能導致算法的勘測能力受到影響；而在算法的中后期，如果出現系數向量C<1，則可能導致算法出現過早收斂從而影響結果[20]。因此本文提出了一種新出的系數向量C的生成方式，使其能較大概率在算法早期保持小于1而在中后期保持大于1，以達到穩(wěn)定灰狼算法的勘測能力，防止過早收斂。設定系數向量C的生成方式為

(14)

其中，tm為總迭代數，r3為[0，0.5]之間的一個隨機數。

3.3 初始種群的生成改進

不同年份之間的生產任務差異較小，可以通過參考同期歷史情況確定當年機組分配數量，利用歷史數據改進灰狼算法初始種群，提升初始種群的整體適應度值，提升算法的收斂速度。

設定同區(qū)域歷史分配及組數向量為：

(15)

得到以下初始種群改進方式：

(16)

(17)

(18)

(19)

(20)

其中，p1、p2、p3為介于0到1的原初始種群權值變量；an是均為正整數的調整參數。式(16)表示當初始種群與同期歷史數據之間差的絕對值小于調整范圍向量時，本次的運力資源分配過程可以借鑒同期歷史數據，通過調整原初始種群優(yōu)先權值，得到更符合當前運力資源分配情況的決策建議；否則表示本次的運力資源分配過程與同期歷史數據相差較大，初始種群不作改進。

3.4 狼群搜索機制的改進

通航電力巡檢有同區(qū)域間人員結果變化較小的特性，本文結合這一特性，對狼群搜索機制進行改進，建立“觀察狼”參考機制，以解決灰狼算法后期收斂速度慢的問題：建立歷史數據向量作為觀察狼的坐標，狼群的狩獵方式改進為底層狼ω向α、β、δ狼與觀察狼協(xié)同位置靠近，在歷史數據的指導下增強算法收斂速度，式(11)、式(12)、和式(13)修改為：

(21)

(22)

(23)

所提出的改進灰狼算法將灰狼個體與獵物距離表達式擴列，引入以歷史數據種群為基準的觀察狼機制，狼群位置更新公式改進為由α、β、δ狼與觀察狼位置加權求和所得。為不影響狼群前中期種群多樣性并提高后期算法收斂速度，引入線性變化的加權因子控制四只頭狼對于種群的影響能力，狩獵前期仍主要由α、β、δ狼定位獵物位置，在狩獵中期及后期觀察狼引導狼群的比重逐漸上升，最終與α、β、δ狼共同定位目標，避免狼群前期受固定化的觀察狼位置支配喪失種群多樣性，也改善了灰狼算法后期狼群位置盲從頭狼而導致的收斂過慢問題。

3.5 改進灰狼算法求解步驟

采用改進后的灰狼算法求解運力匹配模型的步驟如下：

步驟1：確定總迭代數tm，計算優(yōu)先權值p1、p2、p3，調整范圍向量γ、種群規(guī)模等參數的選擇，同時引入歷史數據；

步驟2：根據式(2)與式(3)編碼規(guī)則由算法生成初始候選解群體，并根據式(14)對初始種群進行改進；

步驟3：根據目標函數式(1)以及約束條件式(4)、式(5)對當前種群中的個體適應度值進行計算，更新α、β、δ狼的個體位置，根據歷史數據生成觀察狼位置向量；

步驟4：根據式(21)、式(22)更新α、β、δ狼與觀察狼的位置向量，根據式(23)引導狼群更新位置，更新參數α、A、C、G1、G2；

步驟5：如果狼群適應度值滿足適應度值評價條件或達到最大迭代數，則算法達到預期目的并終止，轉步驟6，不滿足則轉步驟3；

步驟6：算法結束，輸出狼群群適應度值最高個體；

改進后的灰狼算法的整體求解模型流程圖如圖2所示。

圖2 灰狼算法求解流程圖

4 實例分析及評價

選取某通航公司歷史運行數據和實際運行數據如表1、表2、表3。

表1 某通航公司人員配置信息

表2 各區(qū)域不同任務平均年可完成里數

表3 各區(qū)域歷史人員配置

為驗證本文所提出的算法的有效性，在相同實驗環(huán)境條件下將改進灰狼算法與傳統(tǒng)灰狼算法求解運力匹配模型結果進行對比，所得結果如表4。

選取某通航公司運控中心人員手工排班結果如表6，完成總任務量的前提下，人工排班所需機組總數為27個，計算時間為30min。

表4 改進灰狼算法實驗最佳個體結果

表5 傳統(tǒng)灰狼算法實驗最佳個體結果

表6 人工資源調度結果

改進灰狼算法與傳統(tǒng)灰狼算法實驗結果以及人工排班數據對比結果如圖3、圖4、圖5所示。

圖3橫坐標為不同區(qū)域，縱坐標為作業(yè)總里程數，圖3將三種算法得到的作業(yè)總里程數作對比，可以看出三種運力資源的排班方式均可完成各區(qū)域給定總任務量。

圖3 不同算法下的作業(yè)總里程數對比圖

圖4橫坐標為不同算法結果，縱坐標為分配機組總數，圖中將三種算法得到的機組數量分配總數作對比，可以看出改進灰狼算法實驗結果相比傳統(tǒng)灰狼算法下降27.2%，相比人工排班下降40.7%，節(jié)約運力資源效果顯著。

圖4 不同算法下的分配機組總數對比圖

圖5橫坐標為不同區(qū)域，縱坐標為分配機組總數，將不同算法下，不同區(qū)域分配機組數量作對比，可以看出與傳統(tǒng)灰狼算法以及人工排班實驗結果相比，改進灰狼算法實驗結果中各區(qū)域所需機組數量均為最少，運力資源分配效果最優(yōu)。

圖5 不同算法下不同區(qū)域分配機組數對比圖

對不同算法計算時間作對比，可以看出采用灰狼算法相比人工排班能節(jié)約大量時間。采用改進灰狼算法相比傳統(tǒng)灰狼算法節(jié)約2.03s，節(jié)約了27.4%的時間，提升工作效果顯著。

結合實驗結果及對比試驗結果可以看出，改進灰狼算法求解模型的實驗結果在完成給定任務量的條件下能節(jié)約更多運力資源，提高工作效率，達到預期目標。

5 結論

當前的社會條件決定著采用算法構建通航電力作業(yè)運力匹配系統(tǒng)是我國通航領域未來的一個重要研究方向，其理論意義和實用價值都值得深入探討。本文基于實際生產情況以使用最少運力資源為目標構建了運力匹配系統(tǒng)模型，采用綜合改進系數向量、初始種群、狼群搜索機制后的灰狼算法求解模型，實驗結果表明使用改進后的灰狼算法求解通航運力資源匹配模型相比傳統(tǒng)灰狼算法及人工排班方式能夠節(jié)約較多運力資源和計算時間，具有一定實際應用價值。