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

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

1 引言

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

受限于國(guó)內(nèi)通航公司較小的機(jī)隊(duì)規(guī)模，目前國(guó)內(nèi)通用航空領(lǐng)域在運(yùn)力資源調(diào)度及分配方面研究成果較少。國(guó)外通航運(yùn)力資源配置研究主要集中在帶時(shí)間窗的航空器飛行時(shí)間分配和航空器路徑維護(hù)以及機(jī)組排班管理等方面[1-3]。而在國(guó)內(nèi)民航資源調(diào)度方面主要采用線性規(guī)劃及智能算法開(kāi)展相應(yīng)研究，文獻(xiàn)[4]建立了飛機(jī)排班問(wèn)題的0-1整數(shù)模糊線性規(guī)劃數(shù)學(xué)模型，但該模型解決多目標(biāo)多機(jī)型調(diào)度問(wèn)題能力不足。文獻(xiàn)[5]針對(duì)多目標(biāo)飛機(jī)排班問(wèn)題，結(jié)合最優(yōu)化理論將多目標(biāo)模糊線性規(guī)劃數(shù)學(xué)模型轉(zhuǎn)化為一般的線性規(guī)劃問(wèn)題求解。非啟發(fā)式算法方面，文獻(xiàn)[6]提出了基于約束編程的動(dòng)態(tài)列生成算法求解多機(jī)型排班模型，但樣本數(shù)據(jù)較大時(shí)計(jì)算效率較低。啟發(fā)式算法方面，文獻(xiàn)[7]建立飛機(jī)排班一體化優(yōu)化模型并采用具有自適應(yīng)能力的單親遺傳算法求解，但容易陷入局部最優(yōu)解。但文獻(xiàn)中構(gòu)建的模型與各類(lèi)優(yōu)化算法多基于國(guó)內(nèi)民航公司實(shí)際運(yùn)行情況，并不完全適用于本文所研究的通航領(lǐng)域，需要進(jìn)行一定的改進(jìn)。此外，從模型求解方法來(lái)看，目前主要采用線性規(guī)劃法、動(dòng)態(tài)列生成法及灰狼算法對(duì)所建模型進(jìn)行求解，對(duì)于新型智能優(yōu)化算法的研究稍顯不足。而隨著各學(xué)科的發(fā)展，有必要探尋更多新型有效的算法以豐富該類(lèi)問(wèn)題的求解途徑。灰狼算法作為一種新型的群智能優(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ī)組資源安排也相對(duì)簡(jiǎn)單。但是隨著公司業(yè)務(wù)規(guī)模的增長(zhǎng)及機(jī)隊(duì)規(guī)模的增長(zhǎng)，也將面臨如何降低運(yùn)營(yíng)成本，提高生產(chǎn)效益的問(wèn)題[16]。本文根據(jù)國(guó)內(nèi)某通用航空有限公司實(shí)際運(yùn)行情況，分析通航運(yùn)力匹配系統(tǒng)現(xiàn)狀的幾個(gè)問(wèn)題，依據(jù)通航公司運(yùn)力資源系統(tǒng)運(yùn)行流程，構(gòu)建運(yùn)力匹配模型，采用結(jié)合通航電力巡檢特點(diǎn)的灰狼算法求解，最后收集實(shí)際運(yùn)營(yíng)數(shù)據(jù)進(jìn)行仿真對(duì)比實(shí)驗(yàn)。

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

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

在通航公司的生產(chǎn)任務(wù)分配過(guò)程中，首先對(duì)航空器運(yùn)行狀態(tài)、人員配置情況等運(yùn)力信息進(jìn)行運(yùn)力評(píng)估，結(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)狀問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

向量中n個(gè)元素為區(qū)域s中n種作業(yè)類(lèi)型的機(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ù)主要有兩個(gè)約束條件：機(jī)組人員配置所代表的強(qiáng)約束和任務(wù)總量所代表的弱約束。

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

(4)

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

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

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

(5)

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

(6)

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

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

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

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

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

3.1 基本流程

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

狼群包圍獵物過(guò)程可表示為：

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

(7)

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

(8)

A=2a·r1-a

(9)

C=2r2

(10)

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

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

(11)

(12)

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

(13)

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

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

(14)

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

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

不同年份之間的生產(chǎn)任務(wù)差異較小，可以通過(guò)參考同期歷史情況確定當(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ù)之間差的絕對(duì)值小于調(diào)整范圍向量時(shí)，本次的運(yùn)力資源分配過(guò)程可以借鑒同期歷史數(shù)據(jù)，通過(guò)調(diào)整原初始種群優(yōu)先權(quán)值，得到更符合當(dāng)前運(yùn)力資源分配情況的決策建議；否則表示本次的運(yùn)力資源分配過(guò)程與同期歷史數(shù)據(jù)相差較大，初始種群不作改進(jìn)。

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

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

(21)

(22)

(23)

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

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

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

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

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

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

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

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

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

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

圖2 灰狼算法求解流程圖

4 實(shí)例分析及評(píng)價(jià)

選取某通航公司歷史運(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)行對(duì)比，所得結(jié)果如表4。

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

當(dāng)前的社會(huì)條件決定著采用算法構(gòu)建通航電力作業(yè)運(yùn)力匹配系統(tǒng)是我國(guó)通航領(lǐng)域未來(lái)的一個(gè)重要研究方向，其理論意義和實(shí)用價(jià)值都值得深入探討。本文基于實(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í)間，具有一定實(shí)際應(yīng)用價(jià)值。