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

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

0 引言

急造軍路是軍用工程機(jī)械遂行機(jī)動工程保障任務(wù)之一。根據(jù)急造軍路的任務(wù)性質(zhì)，通常可將其分為清除塌方、填塞彈坑和壕溝、修復(fù)崩塌路基等3種具體任務(wù)，且往往需要在不同地域同時開展。每個任務(wù)均涉及到推土機(jī)、挖掘機(jī)、裝載機(jī)等多種類型軍用工程機(jī)械協(xié)同作業(yè)。因此，軍用工程機(jī)械遂行急造軍路任務(wù)是一個多型裝備、多種任務(wù)、多點(diǎn)同時展開的機(jī)群作業(yè)問題。研究機(jī)群的優(yōu)化配置既有重要的現(xiàn)實意義，又有重要的理論研究價值，是該領(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)用線性規(guī)劃的方法建立了工程機(jī)械機(jī)群優(yōu)化配置的數(shù)學(xué)模型；曹豪榮［3］等人采用隨機(jī)過程排隊論方法得到基于快速施工的最優(yōu)機(jī)械配置方案；Faridaddin Vahdatikhaki［4］等人提出了一種多智能體系統(tǒng)，有效改善施工機(jī)群的協(xié)調(diào)問題；鄭雨茜［5］等人運(yùn)用極差最大化組合賦權(quán)法改進(jìn)了現(xiàn)有的機(jī)群配置模型。但上述研究僅限于單任務(wù)、單點(diǎn)展開作業(yè)的情況，對多型裝備、多任務(wù)、多點(diǎn)同時展開作業(yè)的機(jī)群配置問題考慮較少。本文針對軍用工程機(jī)械遂行急造軍路的機(jī)群配置的現(xiàn)實需求，以完成任務(wù)時間最短為優(yōu)化目標(biāo)，基于整數(shù)線性規(guī)劃理論建立了機(jī)群優(yōu)化配置模型，為軍用工程機(jī)械機(jī)群優(yōu)化配置提供了決策支持。

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

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

1.1 任務(wù)描述

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

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

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

挖掘機(jī)：

裝載機(jī)：

1.2 問題建模

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

需要滿足的約束條件有：

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

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

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

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

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

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

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

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

2 模型求解

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

2.1 算法流程

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

圖1 算法流程圖

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

對于機(jī)群優(yōu)化配置問題，每個粒子位置對應(yīng)一個配置方案，這樣就將每一種配置方案映射成一個粒子，粒子的飛行表示從一個配置方案到另一個配置方案的選擇。隨著算法的收斂，粒子逐漸逼近最優(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 臺的矩陣粒子編碼可表示為

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

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

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

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

均表示在任務(wù)1、任務(wù)2、任務(wù)3 分配推土機(jī)、挖掘機(jī)、裝載機(jī)各1 臺。所以在粒子位置矩陣按照式（9）迭代時，可對算法進(jìn)一步改進(jìn)。若子矩陣各行的和沒有改變，則不計算適應(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 臺，挖掘機(jī)7 臺，裝載機(jī)6 臺，各類機(jī)械在理想條件下（即機(jī)械技術(shù)狀況良好、中等土壤、白天、無雨雪等），對各任務(wù)的作業(yè)率如表2 所示。文獻(xiàn)［2］利用線性規(guī)劃方法得到的優(yōu)化配置方案完成總?cè)蝿?wù)時間為4.02 h。

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

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

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

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

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

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

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

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

4 結(jié)論

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