陶俊權(quán)，蘇析超，韓 維，李亞飛

(1.海軍航空大學(xué)， 山東 煙臺(tái) 264001； 2.海軍研究院， 北京 100072)

1 引言

艦載機(jī)作為航母這個(gè)現(xiàn)代戰(zhàn)爭(zhēng)中最重要作戰(zhàn)平臺(tái)的基本作戰(zhàn)力量，其出動(dòng)架次率是衡量航母作戰(zhàn)能力的關(guān)鍵指標(biāo)。而航空彈藥轉(zhuǎn)運(yùn)作業(yè)能力則是影響艦載機(jī)出動(dòng)架次率的重要因素。作為航空保障作業(yè)諸多作業(yè)之一，航空彈藥保障作業(yè)需要完成彈藥的貯存、轉(zhuǎn)運(yùn)、裝配、掛載，所需要的安全性高、作業(yè)流程復(fù)雜、花費(fèi)時(shí)間長(zhǎng)。彈藥從出庫(kù)到掛載，環(huán)節(jié)多，需要從彈藥庫(kù)取出，通過下層武器升降機(jī)運(yùn)送，依據(jù)武器類型判斷裝配地點(diǎn)，裝配好的彈藥再通過上層武器升降機(jī)或飛機(jī)升降機(jī)送達(dá)飛行甲板，最終在飛行甲板完成艦載機(jī)彈藥的掛載。因此優(yōu)化航母彈藥轉(zhuǎn)運(yùn)調(diào)度，對(duì)提高艦載機(jī)保障效率，增強(qiáng)航母作戰(zhàn)能力有重要意義。

航母航空彈藥轉(zhuǎn)運(yùn)作業(yè)問題復(fù)雜程度高，約束條件眾多，且求解難度隨單批次轉(zhuǎn)運(yùn)彈藥數(shù)量增加呈指數(shù)性增長(zhǎng)。對(duì)于此問題的求解，國(guó)內(nèi)學(xué)者已進(jìn)行了很多研究。首先是對(duì)美軍航母彈藥轉(zhuǎn)運(yùn)流程的分析，文獻(xiàn)[5-6]介紹了美尼米茲級(jí)航母的航空彈藥組成及彈藥轉(zhuǎn)運(yùn)基本流程，并通過分析美航母轉(zhuǎn)運(yùn)作業(yè)過程中遇到的問題并提出相應(yīng)的改進(jìn)建議，其次是對(duì)航母彈藥轉(zhuǎn)運(yùn)作業(yè)問題的智能算法求解。文獻(xiàn)[7-11]應(yīng)用遺傳算法及蟻群算法，對(duì)艦載機(jī)彈藥調(diào)度問題依據(jù)不同的假設(shè)條件進(jìn)行了優(yōu)化。除此之外，文獻(xiàn)[12]基于PERT網(wǎng)絡(luò)，對(duì)航空彈藥保障人員配置方案進(jìn)行分析，優(yōu)選出有限保障人員的配置方案。文獻(xiàn)[13]應(yīng)用基于T-S的模糊非線性優(yōu)化方法，實(shí)現(xiàn)了對(duì)彈藥組裝和轉(zhuǎn)運(yùn)速率的控制。文獻(xiàn)[14]考慮航空彈藥保障系統(tǒng)的動(dòng)態(tài)特征，借鑒Multi-Agent方法，建立了航空彈藥動(dòng)態(tài)調(diào)運(yùn)優(yōu)化模型。文獻(xiàn)[15]將航母彈藥轉(zhuǎn)運(yùn)問題抽象為2階段多目標(biāo)規(guī)劃問題，深入分析轉(zhuǎn)運(yùn)約束條件，采用彈藥轉(zhuǎn)運(yùn)優(yōu)先級(jí)的方法建立了轉(zhuǎn)運(yùn)模型。

本文在對(duì)航空彈藥轉(zhuǎn)運(yùn)流程及其約束條件進(jìn)行分析的基礎(chǔ)上，將問題抽象為資源受限項(xiàng)目調(diào)度問題，構(gòu)建了基于模塊化運(yùn)輸單元的彈藥轉(zhuǎn)運(yùn)優(yōu)化模型，并使用EDA算法進(jìn)行了求解。該模型通用性強(qiáng)，可適應(yīng)不同航母的不同彈藥轉(zhuǎn)運(yùn)流程，模型精細(xì)程度高，可實(shí)現(xiàn)對(duì)每一輛彈藥轉(zhuǎn)運(yùn)車的獨(dú)立調(diào)度，最后用實(shí)驗(yàn)表明，該算法及模型可有效求解航空彈藥轉(zhuǎn)運(yùn)問題，對(duì)作業(yè)效率進(jìn)行優(yōu)化。

2 彈藥調(diào)度問題模型描述

彈藥轉(zhuǎn)運(yùn)作業(yè)時(shí)間長(zhǎng)、工作量大，涉及包括各類武器彈藥、彈藥轉(zhuǎn)運(yùn)車、武器升降機(jī)、彈藥裝配區(qū)等在內(nèi)的眾多因素，其保障效率是制約艦載機(jī)出動(dòng)架次率主要因素之一，本節(jié)對(duì)彈藥保障轉(zhuǎn)運(yùn)過程中的運(yùn)輸流程及約束進(jìn)行具體分析，構(gòu)建彈藥調(diào)度問題的總體框架。

2.1 彈藥轉(zhuǎn)運(yùn)處理流程分析

參照美“福特”級(jí)航母的航空彈藥轉(zhuǎn)運(yùn)作業(yè)流程，艦載機(jī)彈藥轉(zhuǎn)運(yùn)基本環(huán)節(jié)如圖1所示。彈藥管理人員依據(jù)該出動(dòng)批次飛機(jī)所需彈藥，確定彈藥總需求量、種類，并將運(yùn)彈任務(wù)分配至各彈庫(kù)。運(yùn)彈人員則因彈藥儲(chǔ)存方式不同采取不同手段取出彈藥并考慮是否進(jìn)行簡(jiǎn)單裝配。完成上述步驟的彈藥將等待下層升降機(jī)空閑，若空閑則將下層升降機(jī)調(diào)至該彈庫(kù)實(shí)施升降機(jī)轉(zhuǎn)運(yùn)。若彈藥需要裝配臺(tái)進(jìn)行裝配，將彈藥轉(zhuǎn)運(yùn)至彈藥裝配區(qū)進(jìn)行裝配作業(yè)，否則轉(zhuǎn)運(yùn)至機(jī)庫(kù)甲板。待上層升降機(jī)或多用途升降機(jī)空閑后，彈藥繼續(xù)轉(zhuǎn)運(yùn)至飛行甲板及各停機(jī)位處進(jìn)行掛載作業(yè)。最后彈藥轉(zhuǎn)運(yùn)車及運(yùn)彈人員待升降機(jī)空閑后原路返回，彈藥轉(zhuǎn)運(yùn)結(jié)束。

圖1 彈藥轉(zhuǎn)運(yùn)流程框圖

2.2 彈藥運(yùn)輸約束分析

一個(gè)批次的彈藥轉(zhuǎn)運(yùn)任務(wù)需要許多彈藥轉(zhuǎn)運(yùn)車，當(dāng)最后一輛彈藥轉(zhuǎn)運(yùn)車在停機(jī)位完成彈藥裝載作業(yè)并成功返回原位后，該批次的彈藥轉(zhuǎn)運(yùn)任務(wù)成功完成。視一輛彈藥轉(zhuǎn)運(yùn)車為一個(gè)獨(dú)立運(yùn)輸單元，其完成轉(zhuǎn)運(yùn)任務(wù)并回到原位的時(shí)間花費(fèi)設(shè)為，時(shí)間從該批次彈藥開始轉(zhuǎn)運(yùn)任務(wù)起計(jì)算。若有個(gè)運(yùn)輸單元，則其時(shí)間花費(fèi)分別為,,…,，因該問題存在多個(gè)可行解，為完成整個(gè)轉(zhuǎn)運(yùn)任務(wù)時(shí)間花費(fèi)最小的任務(wù)目標(biāo)，目標(biāo)函數(shù)可設(shè)為最后完成任務(wù)的運(yùn)輸單元所處時(shí)刻距任務(wù)開始時(shí)間最短。即：

=min{}

=max{,,…,}

(1)

彈藥轉(zhuǎn)運(yùn)最優(yōu)任務(wù)目標(biāo)的完成仍需滿足以下約束條件。

1) 從某一彈庫(kù)獲得某種彈數(shù)量不超過該彈庫(kù)儲(chǔ)存的該種類彈數(shù)量上限。

(2)

式(2)中，代表第個(gè)運(yùn)輸單元從第個(gè)彈庫(kù)所取的第種彈的數(shù)量。共有個(gè)彈庫(kù)，種彈藥。

2) 每個(gè)運(yùn)輸單元只從一個(gè)彈庫(kù)取彈。

(3)

式(3)中，為狀態(tài)變量。若第個(gè)運(yùn)輸單元從任務(wù)規(guī)定的第個(gè)彈庫(kù)取彈，則值為1，否則為0。

3) 每個(gè)運(yùn)輸單元只取一種類型的彈藥。

(4)

式(4)中，為狀態(tài)變量。若第個(gè)運(yùn)輸單元取任務(wù)規(guī)定的第種彈藥，則值為1，否則為0。

4) 每個(gè)運(yùn)輸單元彈藥量不超過該運(yùn)輸單元容納彈藥上限。

(5)

式(5)中，代表第個(gè)運(yùn)輸單元承載彈藥數(shù)上限。

5) 升降機(jī)承載的運(yùn)輸單元數(shù)量不能超過最大載運(yùn)量。

(6)

式(6)中：為狀態(tài)變量，代表所處的升降機(jī)，共有個(gè)升降機(jī)；代表第個(gè)升降機(jī)能承載的彈藥轉(zhuǎn)運(yùn)車數(shù)量。

6) 單個(gè)彈庫(kù)內(nèi)轉(zhuǎn)運(yùn)設(shè)備同時(shí)轉(zhuǎn)運(yùn)彈藥數(shù)量不超過設(shè)計(jì)上限。

(7)

式(7)中：代表第個(gè)彈庫(kù)內(nèi)正在轉(zhuǎn)運(yùn)的第種彈藥數(shù)量；代表第個(gè)彈庫(kù)可同時(shí)轉(zhuǎn)運(yùn)彈藥數(shù)量上限。

7) 彈藥裝配區(qū)同時(shí)進(jìn)行裝配數(shù)量不超過容納上限。

(8)

式(8)中，代表彈藥裝配區(qū)裝配臺(tái)的數(shù)量。

8) 一個(gè)運(yùn)輸單元只能前往一個(gè)停機(jī)位。

(9)

3 改進(jìn)分布估計(jì)算法設(shè)計(jì)及其實(shí)現(xiàn)

3.1 分布估計(jì)算法的基本原理

分布估計(jì)算法(estimation distribution algorithm,EDA)是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的群體進(jìn)化算法,通過建立起概率模型來描述候選解在搜索空間的分布信息并以此解決問題，利用統(tǒng)計(jì)分析的工具，EDA從群體宏觀角度建立一個(gè)描述解分布的概率模型，估計(jì)精英個(gè)體所在編碼變量的潛在概率分布。在生成初始種群和初始化概率矩陣后，采用迭代方法估計(jì)最優(yōu)解的分布。EDA總體流程如圖2所示。

圖2 EDA算法總體流程框圖

3.2 調(diào)度模型的改進(jìn)分布估計(jì)算法實(shí)現(xiàn)

本節(jié)中，航母的彈藥調(diào)度問題，將通過建立針對(duì)彈藥調(diào)度問題的特殊概率模型、基于EDA搜索機(jī)制的概率更新機(jī)制以及進(jìn)行深度優(yōu)化的局部搜索機(jī)制來進(jìn)行求解。

3.2.1 編碼方案

參考多模式資源受限項(xiàng)目調(diào)度問題，采用調(diào)度順序+雙重模式的編碼方式。一個(gè)批次彈藥所對(duì)應(yīng)的所有運(yùn)輸單元按先后順序進(jìn)行調(diào)度，起始彈庫(kù)及停機(jī)位作為每個(gè)運(yùn)輸單元所對(duì)應(yīng)的雙重模式，如圖3所示。

圖3 編碼方案示意圖

第1行代表各個(gè)運(yùn)輸單元的調(diào)度順序，數(shù)字代表運(yùn)輸單元編號(hào)。第2行則代表按運(yùn)輸單元編號(hào)排列的各運(yùn)輸單元所屬?gòu)棊?kù)。第3行代表按運(yùn)輸單元編號(hào)排列的各運(yùn)輸單元將要運(yùn)輸?shù)竭_(dá)的停機(jī)位。

各個(gè)運(yùn)輸單元序號(hào)及其所包含的彈種與彈藥數(shù)量由各停機(jī)位所需彈藥的運(yùn)輸任務(wù)分配情況決定。如圖4所示，一輛轉(zhuǎn)運(yùn)車可轉(zhuǎn)運(yùn)彈藥a數(shù)量為2，則轉(zhuǎn)運(yùn)5枚彈藥a的任務(wù)被分配給了3個(gè)彈藥車運(yùn)輸單元，所有運(yùn)輸單元編號(hào)順序按停機(jī)位及彈藥需求任務(wù)依次排列，而每輛彈藥所需運(yùn)載彈藥也由此確定。

圖4 停機(jī)位彈藥分配過程框圖

3.2.2 多彈庫(kù)多通道并行調(diào)度時(shí)序生成方案

航母彈藥轉(zhuǎn)運(yùn)，彈藥從不同的彈庫(kù)出發(fā)，經(jīng)由固定的轉(zhuǎn)運(yùn)通道轉(zhuǎn)運(yùn)至飛行甲板及停機(jī)位。由于各轉(zhuǎn)運(yùn)通道的運(yùn)輸路徑之間可能存在交叉，全艦的單批次彈藥轉(zhuǎn)運(yùn)任務(wù)無法轉(zhuǎn)化為各通道的單獨(dú)彈藥運(yùn)輸子任務(wù)，因此需要建立多彈庫(kù)多通道聯(lián)合調(diào)度方案。具體流程如圖5所示。

3.2.3 概率模型及概率生成機(jī)制

相較于其他智能算法(如遺傳算法等)采用交叉及變異方式產(chǎn)生新的解來求解彈藥調(diào)度問題，分布估計(jì)算法采用更簡(jiǎn)便的概率模型來解決這一問題，如何產(chǎn)生概率模型是設(shè)計(jì)一個(gè)EDA算法的關(guān)鍵問題。

本文所建立的概率模型包含2個(gè)概率矩陣，一個(gè)是×的調(diào)度順序概率矩陣()，為運(yùn)輸單元總數(shù)。另一個(gè)是×的彈庫(kù)選擇概率矩陣()，為彈庫(kù)總數(shù)。

1)()：該概率矩陣被用來預(yù)測(cè)每個(gè)運(yùn)輸單元在總調(diào)度過程中的順序。

(10)

式(10)中，象征編號(hào)為的運(yùn)輸單元位于第個(gè)被調(diào)度位置上的概率，其大小表示運(yùn)輸單元在位置上的優(yōu)劣性。初始概率如式(11)所示，以此保證概率估計(jì)及采樣的公正性。

(11)

圖5 多彈庫(kù)多通道轉(zhuǎn)運(yùn)任務(wù)求解流程框圖

2)()：該概率矩陣被用來預(yù)測(cè)每個(gè)運(yùn)輸單元選擇不同彈庫(kù)的概率，即：

(12)

式(12)中，象征運(yùn)輸單元選擇彈庫(kù)的概率，其大小表示運(yùn)輸單元從彈庫(kù)出發(fā)的優(yōu)劣性。同調(diào)度概率矩陣一樣，該矩陣也用保證公平的初始矩陣來確定平等選擇各彈庫(kù)。表達(dá)式為：

(13)

另外，由于不同彈庫(kù)所儲(chǔ)存的彈藥種類有所不同，彈庫(kù)選擇概率初始矩陣，應(yīng)根據(jù)不同運(yùn)輸單元所搭載的彈藥種類將相應(yīng)位置的概率歸零并重新分配每行的概率。

由于各運(yùn)輸單元之間不存在前后序約束，因此各運(yùn)輸單元可以按照編號(hào)順序依次經(jīng)過調(diào)度順序概率矩陣，并最終生成一個(gè)完整的調(diào)度順序。運(yùn)輸單元選擇位置的概率為：、

(14)

若位置已被選取，則對(duì)應(yīng)的列概率全部歸零，即該位置不可再被選取，以保證位置的唯一性。

選取完各單元位置后，還需對(duì)各單元所屬?gòu)棊?kù)進(jìn)行選擇，運(yùn)輸單元選擇彈庫(kù)的概率為：

(15)

由于運(yùn)輸單元所屬停機(jī)位在分配運(yùn)輸單元彈藥時(shí)已經(jīng)固定，故無需進(jìn)行選取。最終，經(jīng)過調(diào)度順序概率矩陣及彈庫(kù)選擇概率矩陣的選取，可以確定一個(gè)完整的調(diào)度順序集。由于存在同一彈庫(kù)取彈量不得超過存彈量等約束條件，確定運(yùn)輸單元所屬?gòu)棊?kù)后，需進(jìn)行檢驗(yàn)，若不滿足約束，需重新進(jìn)行選取。

將確定調(diào)度順序集的操作重復(fù)次，由此得到了一個(gè)擁有個(gè)個(gè)體的種群，為之后的操作做準(zhǔn)備。

3.2.4 局部搜索

3.2.5 概率矩陣更新機(jī)制

為了更好地進(jìn)行迭代，加速獲得更加優(yōu)秀的解，需要依據(jù)計(jì)算所得的個(gè)優(yōu)勝解對(duì)概率矩陣()及()進(jìn)行更新，其更新規(guī)則為：

(16)

(17)

圖6 局部搜索流程框圖

3.3 EDA算法總結(jié)

經(jīng)過上述設(shè)計(jì)，基于EDA算法的航母彈藥調(diào)度問題可以有總結(jié)表述如下：首先，初始化概率矩陣，以保證選擇公平性。其次，使用多彈庫(kù)多通道并行時(shí)序生成方案，生成個(gè)解，挑選其中個(gè)優(yōu)異解并進(jìn)行局部搜索以優(yōu)化解的質(zhì)量。最后，依據(jù)優(yōu)化后的優(yōu)異解對(duì)概率矩陣進(jìn)行修改，并進(jìn)行迭代運(yùn)算，以求得最終的最優(yōu)解。

4 仿真實(shí)驗(yàn)

本節(jié)中，算法的實(shí)用性會(huì)通過一個(gè)具體實(shí)例來證明。由圖1可知，航母的彈藥轉(zhuǎn)運(yùn)流程可根據(jù)彈藥種類及特點(diǎn)的不同分為2種：一種彈藥經(jīng)彈藥裝配區(qū)裝配后轉(zhuǎn)移至飛行甲板停機(jī)位，另一種在彈庫(kù)簡(jiǎn)單裝配后經(jīng)機(jī)庫(kù)甲板到達(dá)飛行甲板停機(jī)位，具體轉(zhuǎn)運(yùn)流程及編號(hào)如圖7所示。

圖7 2種彈藥轉(zhuǎn)運(yùn)流程框圖

設(shè)某型航母共有11個(gè)彈庫(kù)，分為1-3號(hào)、4-7號(hào)、8-11號(hào)3個(gè)彈庫(kù)群。相對(duì)應(yīng)的有10臺(tái)升降機(jī)，其中6臺(tái)下層升降機(jī)(3臺(tái)對(duì)應(yīng)3個(gè)彈庫(kù)群執(zhí)行任務(wù)類別1，另外3臺(tái)對(duì)應(yīng)3個(gè)彈庫(kù)群執(zhí)行任務(wù)類別2)；4臺(tái)上層升降機(jī)(3臺(tái)對(duì)應(yīng)各個(gè)彈庫(kù)群執(zhí)行任務(wù)類別1，另外1臺(tái)對(duì)應(yīng)所有彈庫(kù)執(zhí)行任務(wù)類別2)。

在彈藥轉(zhuǎn)運(yùn)任務(wù)設(shè)置上，設(shè)該批次航母彈藥轉(zhuǎn)運(yùn)涉及5個(gè)停機(jī)位，上層升降機(jī)位于飛行甲板上的4個(gè)出口與各停機(jī)位之間存在獨(dú)立的轉(zhuǎn)運(yùn)時(shí)間。共需運(yùn)輸3種類型彈藥，A型彈1車1枚，彈庫(kù)內(nèi)3枚聯(lián)裝，經(jīng)任務(wù)類別1進(jìn)行運(yùn)輸。B型彈一車2枚，彈庫(kù)內(nèi)獨(dú)立包裝，經(jīng)任務(wù)類別2進(jìn)行運(yùn)輸。C型彈1車1枚，彈庫(kù)內(nèi)獨(dú)立包裝，經(jīng)任務(wù)類別1進(jìn)行運(yùn)輸。共需運(yùn)輸5枚A型彈、10枚B型彈、5枚C型彈且各停機(jī)位彈藥分配平均，均為1枚A型、2枚B型、1枚C型。共需調(diào)度15輛彈藥轉(zhuǎn)運(yùn)車，即15個(gè)運(yùn)輸單元。

EDA算法參數(shù)設(shè)置上，種群大小設(shè)定為200，局部搜索概率為0.05，學(xué)習(xí)速率為0.3，共迭代運(yùn)行4 000次，對(duì)比未采用局部搜索的EDA算法及采用局部搜索的改進(jìn)EDA算法，運(yùn)行結(jié)果如圖8所示。

由圖8可以看出，采用局部搜索的改進(jìn)EDA算法所獲得的最優(yōu)解優(yōu)于標(biāo)準(zhǔn)EDA算法，收斂速度也有所超出，這是對(duì)解空間進(jìn)行深度搜索的結(jié)果。

各彈藥轉(zhuǎn)運(yùn)車執(zhí)行各個(gè)調(diào)度工序的甘特圖如圖9，橫軸為時(shí)間，縱軸代表各個(gè)運(yùn)輸單元的編號(hào)，各甘特塊長(zhǎng)度代表所耗工時(shí)，其內(nèi)編號(hào)為工序編號(hào)。所得到的最優(yōu)調(diào)度方案盡可能利用各升降機(jī)，以保證總調(diào)度時(shí)間最小，實(shí)現(xiàn)資源的有效利用。通過該甘特圖驗(yàn)證模型滿足式(2)至式(9)中的各項(xiàng)約束，證明了模型的合理性。

圖8 2種EDA算法運(yùn)行結(jié)果曲線

圖9 彈藥運(yùn)輸單元工序甘特圖

5 結(jié)論

改進(jìn)的EDA算法引入了雙概率矩陣的形式，對(duì)初始種群的生成進(jìn)行了改進(jìn)。并結(jié)合了局部搜索，相較于標(biāo)準(zhǔn)EDA算法，對(duì)于解空間的深度搜索效果有了很大的提高。充分結(jié)合了EDA算法種群正反饋機(jī)制下的全局搜索能力以及對(duì)精英個(gè)體深度搜索后的快速收斂能力。采用彈藥轉(zhuǎn)運(yùn)車運(yùn)輸單元為基本單位進(jìn)行計(jì)算，優(yōu)化了解的精細(xì)程度。通過實(shí)例仿真，驗(yàn)證了其在航母彈藥調(diào)度方案設(shè)計(jì)中的實(shí)用價(jià)值。