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

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

1 引言

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

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

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

2 通航運(yùn)力匹配模型構(gòu)建

2.1 運(yùn)力匹配系統(tǒng)運(yùn)行流程及特點(diǎn)

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

圖1 運(yùn)力匹配流程圖

2.2 運(yùn)力匹配系統(tǒng)的現(xiàn)狀問題

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

1)生產(chǎn)任務(wù)飛行時長。

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

2)巡線段任務(wù)重復(fù)度。

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

3)運(yùn)力資源的快速響應(yīng)能力。

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

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

運(yùn)力資源匹配數(shù)學(xué)模型的構(gòu)建目標(biāo)在于各區(qū)域分配到的機(jī)組數(shù)的確定，因此構(gòu)建模型時需要綜合考慮運(yùn)力匹配特點(diǎn)與流程等因素的影響。

2.3.1 目標(biāo)函數(shù)的建立

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

(1)

其中，As是系數(shù)矩陣，As的表達(dá)式為：

(2)

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

機(jī)組數(shù)自變量xs的表達(dá)式為：

(3)

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

2.2.2 約束條件設(shè)定

求解目標(biāo)函數(shù)主要有兩個約束條件：機(jī)組人員配置所代表的強(qiáng)約束和任務(wù)總量所代表的弱約束。

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

(4)

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

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

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

(5)

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

(6)

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

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

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

3 基于改進(jìn)灰狼算法的運(yùn)力匹配模型求解

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

3.1 基本流程

灰狼算法是以狼群狩獵行為的追蹤、圍獵和狩獵三個環(huán)節(jié)構(gòu)建的優(yōu)化算法。整個群體的適應(yīng)度值自上而下分為首領(lǐng)狼(頭狼)α、副首領(lǐng)狼β、普通狼δ以及底層狼ω。首領(lǐng)狼α的適應(yīng)度值最高，負(fù)責(zé)指定狼群移動方向；β狼和δ狼適應(yīng)度值依次降低，負(fù)責(zé)向α狼提供參考方向；ω狼適應(yīng)度值最低，服從于α、β、δ狼，并為狼群提供穩(wěn)定性?；依撬惴ǖ幕舅枷胧怯搔?、β、δ狼定位獵物(最優(yōu)解)，引導(dǎo)ω狼包圍并進(jìn)行狩獵(求解最優(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為灰狼個體與獵物的距離表達(dá)式；X(t+1)為灰狼位置更新表達(dá)式，t代表迭代次數(shù)，Xp(t)代表獵物(最優(yōu)解)位置向量，X(t)代表灰狼個體位置向量，C、A為系數(shù)向量；a隨著迭代次數(shù)由2線性減少至0，r1、r2為模在0至1間的隨機(jī)數(shù)。

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

(11)

(12)

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

(13)

3.2 系數(shù)向量C的生成改進(jìn)

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

(14)

其中，tm為總迭代數(shù)，r3為[0，0.5]之間的一個隨機(jī)數(shù)。

3.3 初始種群的生成改進(jìn)

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

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

(15)

得到以下初始種群改進(jìn)方式：

(16)

(17)

(18)

(19)

(20)

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

3.4 狼群搜索機(jī)制的改進(jìn)

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

(21)

(22)

(23)

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

3.5 改進(jìn)灰狼算法求解步驟

采用改進(jìn)后的灰狼算法求解運(yùn)力匹配模型的步驟如下：

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

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

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

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

步驟5：如果狼群適應(yīng)度值滿足適應(yīng)度值評價條件或達(dá)到最大迭代數(shù)，則算法達(dá)到預(yù)期目的并終止，轉(zhuǎn)步驟6，不滿足則轉(zhuǎn)步驟3；

步驟6：算法結(jié)束，輸出狼群群適應(yīng)度值最高個體；

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

圖2 灰狼算法求解流程圖

4 實(shí)例分析及評價

選取某通航公司歷史運(yùn)行數(shù)據(jù)和實(shí)際運(yùn)行數(shù)據(jù)如表1、表2、表3。

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

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

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

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

選取某通航公司運(yùn)控中心人員手工排班結(jié)果如表6，完成總?cè)蝿?wù)量的前提下，人工排班所需機(jī)組總數(shù)為27個，計(jì)算時間為30min。

表4 改進(jìn)灰狼算法實(shí)驗(yàn)最佳個體結(jié)果

表5 傳統(tǒng)灰狼算法實(shí)驗(yàn)最佳個體結(jié)果

表6 人工資源調(diào)度結(jié)果

改進(jìn)灰狼算法與傳統(tǒng)灰狼算法實(shí)驗(yàn)結(jié)果以及人工排班數(shù)據(jù)對比結(jié)果如圖3、圖4、圖5所示。

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

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

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

圖4 不同算法下的分配機(jī)組總數(shù)對比圖

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

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

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

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

5 結(jié)論

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