軍用工程機(jī)械急造軍路機(jī)群優(yōu)化配置研究

杜毛強(qiáng)，何曉暉，王 強(qiáng)，朱曉基，魏文海

（1.陸軍工程大學(xué)野戰(zhàn)工程學(xué)院，南京 210007；2.解放軍32228 部隊(duì)23 分隊(duì)，福建 廈門(mén) 361100）

0 引言

急造軍路是軍用工程機(jī)械遂行機(jī)動(dòng)工程保障任務(wù)之一。根據(jù)急造軍路的任務(wù)性質(zhì)，通?？蓪⑵浞譃榍宄?、填塞彈坑和壕溝、修復(fù)崩塌路基等3種具體任務(wù)，且往往需要在不同地域同時(shí)開(kāi)展。每個(gè)任務(wù)均涉及到推土機(jī)、挖掘機(jī)、裝載機(jī)等多種類(lèi)型軍用工程機(jī)械協(xié)同作業(yè)。因此，軍用工程機(jī)械遂行急造軍路任務(wù)是一個(gè)多型裝備、多種任務(wù)、多點(diǎn)同時(shí)展開(kāi)的機(jī)群作業(yè)問(wèn)題。研究機(jī)群的優(yōu)化配置既有重要的現(xiàn)實(shí)意義，又有重要的理論研究?jī)r(jià)值，是該領(lǐng)域的研究熱點(diǎn)。Manuel Parente［1］等人整合了啟發(fā)式算法和數(shù)據(jù)挖掘技術(shù)的優(yōu)點(diǎn)，以搜索工程機(jī)械的最佳配置；馮柯［2］等人以充分發(fā)揮現(xiàn)有工程機(jī)械作業(yè)效能為目標(biāo)，運(yùn)用線(xiàn)性規(guī)劃的方法建立了工程機(jī)械機(jī)群優(yōu)化配置的數(shù)學(xué)模型；曹豪榮［3］等人采用隨機(jī)過(guò)程排隊(duì)論方法得到基于快速施工的最優(yōu)機(jī)械配置方案；Faridaddin Vahdatikhaki［4］等人提出了一種多智能體系統(tǒng)，有效改善施工機(jī)群的協(xié)調(diào)問(wèn)題；鄭雨茜［5］等人運(yùn)用極差最大化組合賦權(quán)法改進(jìn)了現(xiàn)有的機(jī)群配置模型。但上述研究?jī)H限于單任務(wù)、單點(diǎn)展開(kāi)作業(yè)的情況，對(duì)多型裝備、多任務(wù)、多點(diǎn)同時(shí)展開(kāi)作業(yè)的機(jī)群配置問(wèn)題考慮較少。本文針對(duì)軍用工程機(jī)械遂行急造軍路的機(jī)群配置的現(xiàn)實(shí)需求，以完成任務(wù)時(shí)間最短為優(yōu)化目標(biāo)，基于整數(shù)線(xiàn)性規(guī)劃理論建立了機(jī)群優(yōu)化配置模型，為軍用工程機(jī)械機(jī)群優(yōu)化配置提供了決策支持。

1 優(yōu)化配置模型構(gòu)建

軍用工程機(jī)械機(jī)群的配置需要根據(jù)任務(wù)類(lèi)型、工程量以及機(jī)械的作業(yè)能力確定，因此，必須對(duì)機(jī)群配置問(wèn)題進(jìn)行建模分析，以制定最優(yōu)的機(jī)群配置方案。

1.1 任務(wù)描述

急造軍路可分為3 種具體任務(wù)：清除塌方、填塞彈坑和壕溝、修復(fù)崩塌路基。在遂行任務(wù)時(shí)，3 種任務(wù)往往同時(shí)開(kāi)展，且都需要推土機(jī)、挖掘機(jī)、裝載機(jī)協(xié)同完成。將軍用工程機(jī)械機(jī)群中的每一臺(tái)工程機(jī)械看作一個(gè)單位，單位集：

其中，T 表示推土機(jī)，W 表示挖掘機(jī)，Z 表示裝載機(jī)。各種機(jī)械數(shù)量分別表示為：推土機(jī)n1，挖掘機(jī)n2，裝載機(jī)n3。

假設(shè)共有推土機(jī)a 臺(tái)，挖掘機(jī)b 臺(tái)，裝載機(jī)c臺(tái)，任務(wù)數(shù)量為e。機(jī)群配置的任務(wù)—單位分配關(guān)系表示為：

挖掘機(jī)：

裝載機(jī)：

1.2 問(wèn)題建模

考慮每個(gè)任務(wù)如何配置機(jī)群，能夠使總?cè)蝿?wù)完成的時(shí)間最少。由于總?cè)蝿?wù)完成的時(shí)間等于各任務(wù)完成時(shí)間tj的最大值。軍用工程機(jī)械機(jī)群優(yōu)化配置模型的目標(biāo)函數(shù)為：

需要滿(mǎn)足的約束條件有：

1）機(jī)械數(shù)量約束。

各任務(wù)機(jī)械數(shù)量不得超過(guò)該類(lèi)機(jī)械現(xiàn)有數(shù)量：

2）任務(wù)完成時(shí)間約束。

各任務(wù)必須在要求時(shí)間限制內(nèi)完成：

其中，Ci為任務(wù)i 的工程量，Qj為單位j 的作業(yè)率。

3）各任務(wù)要盡可能地同時(shí)完工，避免出現(xiàn)某段任務(wù)完工過(guò)早或過(guò)晚的現(xiàn)象，以保證機(jī)群資源更加均衡合理分配使用。

4）每個(gè)任務(wù)必須都有3 種不同類(lèi)型的機(jī)械，且數(shù)量為整數(shù)。

通過(guò)對(duì)問(wèn)題的描述和約束條件分析，可建立如下數(shù)學(xué)模型：

2 模型求解

機(jī)群的配置模型求解是一個(gè)離散組合優(yōu)化問(wèn)題，而啟發(fā)式搜索算法是解決此類(lèi)問(wèn)題的有效方法。結(jié)合本研究問(wèn)題的特殊性，在對(duì)離散粒子群算法［6］、隱枚舉法［7］、遺傳算法［8］等方法進(jìn)行比較的基礎(chǔ)上，本文選用粒子群算法求解優(yōu)化配置模型。該算法具有收斂速度快、全局優(yōu)化性好的特點(diǎn)，其應(yīng)用領(lǐng)域已從連續(xù)空間優(yōu)化問(wèn)題擴(kuò)展到離散組合優(yōu)化問(wèn)題［9］，在解決機(jī)群優(yōu)化配置問(wèn)題上優(yōu)勢(shì)尤為明顯。

2.1 算法流程

離散粒子群優(yōu)化算法（BPSO）隨機(jī)初始化一群粒子，每個(gè)粒子代表多為空間中的一個(gè)點(diǎn)，它使待優(yōu)化函數(shù)最值的一個(gè)潛在解，隨著算法運(yùn)行，粒子不斷逼近函數(shù)的最值。在每次進(jìn)化過(guò)程中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己所在的位置。第1 個(gè)極值為粒子自身找到的最優(yōu)位置，相對(duì)應(yīng)的適應(yīng)值叫pBest；另一個(gè)極值是整個(gè)種群當(dāng)前找到的最優(yōu)位置，相對(duì)于的適應(yīng)值稱(chēng)為全局極值gBest。其流程圖如圖1 所示。

圖1 算法流程圖

2.2 粒子編碼的設(shè)計(jì)

對(duì)于機(jī)群優(yōu)化配置問(wèn)題，每個(gè)粒子位置對(duì)應(yīng)一個(gè)配置方案，這樣就將每一種配置方案映射成一個(gè)粒子，粒子的飛行表示從一個(gè)配置方案到另一個(gè)配置方案的選擇。隨著算法的收斂，粒子逐漸逼近最優(yōu)配置方案。遂行急造軍路任務(wù)的機(jī)群配置矩陣為：

式中，Tij，Wij，Zij∈｛0，1｝。可進(jìn)一步將其分解為子矩陣：分別表示推土機(jī)、挖掘機(jī)、裝載機(jī)在各任務(wù)的配置情況。

設(shè)種群中粒子位置的集合為：

式中，PO P 為種群大小。

種群中粒子位置如圖2 所示。

圖2 粒子種群位置

例如，任務(wù)1、任務(wù)2、任務(wù)3 分配推土機(jī)、挖掘機(jī)、裝載機(jī)各1 臺(tái)的矩陣粒子編碼可表示為

這樣的編碼方式可以直觀(guān)地將各任務(wù)的機(jī)群配置情況表示出來(lái)。

2.3 粒子速度與位置更新方式

由于每個(gè)單位只能被分到一個(gè)任務(wù)，每個(gè)任務(wù)至少分配一個(gè)單位，所以位置矩陣每列的和恒等于1，每行的和大于等于1。傳統(tǒng)的BPSO 在處理粒子位置的更新時(shí)，粒子中1 的個(gè)數(shù)可能發(fā)生改變，出現(xiàn)一列都為0 或一行都為0 的情況，故需對(duì)BPSO 進(jìn)行改進(jìn)。文獻(xiàn)［10］提出了一種速度位置更新公式：

按照本文的編碼方式，機(jī)群的配置方案由粒子位置矩陣各行1 的數(shù)量決定，所以各行0、1 的順序沒(méi)有實(shí)際意義。例如以下兩個(gè)矩陣：

均表示在任務(wù)1、任務(wù)2、任務(wù)3 分配推土機(jī)、挖掘機(jī)、裝載機(jī)各1 臺(tái)。所以在粒子位置矩陣按照式（9）迭代時(shí)，可對(duì)算法進(jìn)一步改進(jìn)。若子矩陣各行的和沒(méi)有改變，則不計(jì)算適應(yīng)值，返回重新迭代，這樣可以加快收斂速度。改進(jìn)的BPSO 速度與位置更新方式如圖3 所示。

3 案例分析

本文以文獻(xiàn)［2］中的構(gòu)筑急造軍路任務(wù)為例。該急造軍路共有3 條道路的構(gòu)筑任務(wù)，各道路的偵查情況為：道路1 大面積塌方，道路2 有連續(xù)彈坑，道路3 路基崩塌，據(jù)此將任務(wù)區(qū)分為：任務(wù)1 清除塌方，任務(wù)2 克服連續(xù)彈坑，任務(wù)3 修復(fù)崩塌路基，各任務(wù)工程量如表1 所示?，F(xiàn)有推土機(jī)10 臺(tái)，挖掘機(jī)7 臺(tái)，裝載機(jī)6 臺(tái)，各類(lèi)機(jī)械在理想條件下（即機(jī)械技術(shù)狀況良好、中等土壤、白天、無(wú)雨雪等），對(duì)各任務(wù)的作業(yè)率如表2 所示。文獻(xiàn)［2］利用線(xiàn)性規(guī)劃方法得到的優(yōu)化配置方案完成總?cè)蝿?wù)時(shí)間為4.02 h。

表1 各任務(wù)工程量（m 3）

表2 各任務(wù)工程機(jī)械作業(yè)率（m 3/h）

根據(jù)本文建立的數(shù)學(xué)模型，以最小化總?cè)蝿?wù)完成時(shí)間為優(yōu)化目標(biāo)，用改進(jìn)的BPSO 求解，并利用Matlab R2015b 進(jìn)行編程計(jì)算。模型求解的優(yōu)化過(guò)程如下頁(yè)圖4 所示。

可見(jiàn)，目標(biāo)函數(shù)適應(yīng)值在算法迭代40 次左右達(dá)到收斂，總?cè)蝿?wù)完成時(shí)間最小值為3.931 9 h，優(yōu)于文獻(xiàn)［2］利用線(xiàn)性規(guī)劃方法求得的任務(wù)完成時(shí)間4.02 h。算法在仿真20 次以后趨于穩(wěn)定，說(shuō)明算法在解決機(jī)群優(yōu)化配置問(wèn)題上具有快速的尋優(yōu)能力。最優(yōu)結(jié)果的機(jī)群配置矩陣為：

圖3 粒子速度與位置更新方式示意圖

圖4 模型求解優(yōu)化過(guò)程

得到軍用工程機(jī)械機(jī)群的最優(yōu)配置方案如表3所示。

表3 最優(yōu)機(jī)群配置方案

4 結(jié)論

本文對(duì)軍用工程機(jī)械遂行構(gòu)筑急造軍路任務(wù)面臨的多型裝備、多種任務(wù)、多點(diǎn)同時(shí)作業(yè)的機(jī)群優(yōu)化配置問(wèn)題進(jìn)行分析，提出了基于整數(shù)線(xiàn)性規(guī)劃理論建立機(jī)群優(yōu)化配置模型，并運(yùn)用改進(jìn)的離散粒子群算法求解模型的機(jī)群優(yōu)化配置方法。通過(guò)案例分析表明，該方法能有效解決機(jī)群的優(yōu)化配置問(wèn)題，提高軍用工程機(jī)械的保障能力。