基于粒子群算法的工程機(jī)械機(jī)群動(dòng)態(tài)調(diào)度問(wèn)題的求解

李金鑫，何曉暉

（1.中國(guó)人民解放軍 32382部隊(duì)，河南 洛陽(yáng) 471000；2.陸軍工程大學(xué) 野戰(zhàn)工程學(xué)院，南京 210007）

0 引言

道路搶修是工程機(jī)械機(jī)群工程保障任務(wù)之一。通常可將其分為清除塌方、填塞彈坑、壕溝、修復(fù)崩塌路基4種任務(wù)，往往需要在不同地域同時(shí)開(kāi)展。每種任務(wù)均涉及到推土機(jī)、挖掘機(jī)、裝載機(jī)等多種類(lèi)型軍用工程機(jī)械協(xié)同作業(yè)。當(dāng)前工程機(jī)械機(jī)群實(shí)際運(yùn)用過(guò)程中，機(jī)群往往是多點(diǎn)同時(shí)開(kāi)展工作，指揮員通常是根據(jù)主觀經(jīng)驗(yàn)來(lái)確定機(jī)群的動(dòng)態(tài)調(diào)度，工程機(jī)群開(kāi)始工作后各工作點(diǎn)之間基本沒(méi)有動(dòng)態(tài)調(diào)度。由于每個(gè)點(diǎn)的工作量不同，任務(wù)難度不同，故工程進(jìn)度也會(huì)不同。因此，合理地調(diào)度各個(gè)工作點(diǎn)的工程機(jī)械，才能保證任務(wù)順利完成，使工作效率達(dá)到最大化。如何利用有限資源在最短時(shí)間內(nèi)完成道路搶修任務(wù)成為檢驗(yàn)戰(zhàn)斗力的標(biāo)準(zhǔn)。因此，研究工程機(jī)械機(jī)群優(yōu)化調(diào)度方法，有助于合理、高效地使用工程機(jī)械，進(jìn)而為指揮員定下方案提供依據(jù)。

1 模型構(gòu)建

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

1.1 任務(wù)描述

道路搶修一般分為4種任務(wù)：新筑道路，清除塌方，填平彈坑、壕溝，修復(fù)崩塌道路。一般情況下，往往同時(shí)、不同地點(diǎn)展開(kāi)，且都需要推土機(jī)、挖掘機(jī)、裝載機(jī)協(xié)同完成。由于不同任務(wù)的難易程度不同，故任務(wù)進(jìn)展不同，現(xiàn)其中一點(diǎn)的任務(wù)已經(jīng)完成，為使整體作業(yè)效率最大化，需將這一點(diǎn)的工程機(jī)械調(diào)度至其他任務(wù)點(diǎn)。將工程機(jī)械機(jī)群中的每一臺(tái)工程機(jī)械看做一個(gè)單位，單位集：

1.2 問(wèn)題建模

合理調(diào)度工程機(jī)械，使總?cè)蝿?wù)完成的時(shí)間最少。總?cè)蝿?wù)完成的時(shí)間等于各任務(wù)完成時(shí)間的最大值。工程機(jī)群調(diào)度模型目標(biāo)函數(shù)為

2）時(shí)間約束。

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

2 模型求解

工程機(jī)械機(jī)群調(diào)度模型求解可以看做是一個(gè)尋找最優(yōu)解的過(guò)程，即離散組合優(yōu)化問(wèn)題；解決此類(lèi)問(wèn)題的有效方法是啟發(fā)式算法，主要包括離散粒子群算法[1]、遺傳算法[2]、隱枚舉法[3]等算法。本文采用粒子群算法求解動(dòng)態(tài)調(diào)度模型。該算法具有收斂速度快、全局優(yōu)化性好的特點(diǎn)，其應(yīng)用領(lǐng)域已從連續(xù)空間優(yōu)化問(wèn)題擴(kuò)展到離散組合優(yōu)化問(wèn)題[4]，在解決機(jī)群動(dòng)態(tài)調(diào)度問(wèn)題上優(yōu)勢(shì)尤為明顯。

2.1 算法流程

PSO算法中每一個(gè)潛在的解都被稱(chēng)為一個(gè)“粒子”，粒子在解空間內(nèi)“運(yùn)行”，隨著算法運(yùn)行，粒子不斷逼近函數(shù)的最值[5]。在每次進(jìn)化過(guò)程中，粒子通過(guò)跟蹤2個(gè)“極值”來(lái)更新自己所在的位置。第一個(gè)極值為粒子自身找到的最優(yōu)位置，相對(duì)應(yīng)的適應(yīng)值為pBest；另一個(gè)極值是整個(gè)種群當(dāng)前找到的最優(yōu)位置，相對(duì)于的適應(yīng)值稱(chēng)為全局極值為gBest[6]。其流程圖如圖1所示。在得知最優(yōu)方案后，即可得調(diào)度方案。

圖1 算法流程圖

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

每個(gè)粒子位置對(duì)應(yīng)一個(gè)新的分配方案，這樣就將每一種配置方案映射成一個(gè)粒子，粒子的飛行表示從一個(gè)調(diào)度方案到另一個(gè)調(diào)度方案的選擇。隨著算法的收斂，粒子逐漸逼近最優(yōu)調(diào)度方案。機(jī)群的調(diào)度矩陣為

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

圖2 種群粒子位置

例如，任務(wù)1、任務(wù)2、任務(wù)3分配推土機(jī)、挖掘機(jī)、裝載機(jī)各1臺(tái)，其中任務(wù)2已完成，將任務(wù)2的各類(lèi)工程機(jī)械任意調(diào)度到任務(wù)1、任務(wù)3，其矩陣粒子編碼可表示為

這樣的編碼方式的優(yōu)點(diǎn)是直觀地將各任務(wù)的機(jī)群調(diào)度情況表示出來(lái)，將任務(wù)2的1臺(tái)推土機(jī)、挖掘機(jī)、裝載機(jī)調(diào)度給任務(wù)1，2臺(tái)挖掘機(jī)、裝載機(jī)調(diào)度給任務(wù)3。

2.3 粒子位置更新方式

由于每個(gè)單位只能被分到1個(gè)任務(wù)，每個(gè)任務(wù)至少分配1個(gè)單位，所以位置矩陣每行的和大于1，每行每列任意互換。同時(shí)滿足以下束縛條件：

3 案例分析

本文以文獻(xiàn)[3]中的構(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ā)情況導(dǎo)致任務(wù)1和任務(wù)2的機(jī)械作業(yè)效率降為一半。現(xiàn)有推土機(jī)10臺(tái)、挖掘機(jī)7臺(tái)、裝載機(jī)6臺(tái)，各類(lèi)機(jī)械在不調(diào)度的情況下，各任務(wù)的作業(yè)率如表2所示。文獻(xiàn)[3]完成總?cè)蝿?wù)時(shí)間為7.86 h。

表1 各任務(wù)工程量

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

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

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

可見(jiàn)，目標(biāo)函數(shù)適應(yīng)值在算法迭代75次左右達(dá)到收斂，總?cè)蝿?wù)完成時(shí)間最小值為6.895 h，優(yōu)于未調(diào)度工程機(jī)械的任務(wù)完成時(shí)間7.86 h。最優(yōu)結(jié)果的機(jī)群調(diào)度矩陣為：

矩陣中“-1”代表調(diào)出一輛，“1”代表調(diào)入一輛。故方案為將任務(wù)2的4輛推土機(jī)和任務(wù)3的1輛推土機(jī)調(diào)到任務(wù)1，將任務(wù)1的3輛挖掘機(jī)和任務(wù)2的1輛挖掘機(jī)調(diào)到任務(wù)3，將任務(wù)1的1輛裝載機(jī)和任務(wù)3的1輛裝載機(jī)調(diào)至任務(wù)2。

4 結(jié)論

本文對(duì)軍用工程機(jī)械遂行構(gòu)筑急造軍路任務(wù)面臨的多型裝備、多種任務(wù)、多點(diǎn)同時(shí)作業(yè)的機(jī)群動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行分析，提出了基于離散粒子群算法求解模型的機(jī)群動(dòng)態(tài)調(diào)度方法。該方法能有效解決機(jī)群的動(dòng)態(tài)調(diào)度問(wèn)題，提高軍用工程機(jī)械的保障能力。