基于粒子群算法的工程機械機群動態調度問題的求解

李金鑫，何曉暉

（1.中國人民解放軍 32382部隊，河南 洛陽 471000；2.陸軍工程大學 野戰工程學院，南京 210007）

0 引言

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

1 模型構建

工程機械的調度需要依據任務類型、工程量及機械的作業能力確定，因此必須對調度問題進行建模分析，以制定最優的調度方案。

1.1 任務描述

道路搶修一般分為4種任務：新筑道路，清除塌方，填平彈坑、壕溝，修復崩塌道路。一般情況下，往往同時、不同地點展開，且都需要推土機、挖掘機、裝載機協同完成。由于不同任務的難易程度不同，故任務進展不同，現其中一點的任務已經完成，為使整體作業效率最大化，需將這一點的工程機械調度至其他任務點。將工程機械機群中的每一臺工程機械看做一個單位，單位集：

1.2 問題建模

合理調度工程機械，使總任務完成的時間最少。總任務完成的時間等于各任務完成時間的最大值。工程機群調度模型目標函數為

2）時間約束。

各任務必須在要求時間限制內完成：

2 模型求解

工程機械機群調度模型求解可以看做是一個尋找最優解的過程，即離散組合優化問題；解決此類問題的有效方法是啟發式算法，主要包括離散粒子群算法[1]、遺傳算法[2]、隱枚舉法[3]等算法。本文采用粒子群算法求解動態調度模型。該算法具有收斂速度快、全局優化性好的特點，其應用領域已從連續空間優化問題擴展到離散組合優化問題[4]，在解決機群動態調度問題上優勢尤為明顯。

2.1 算法流程

PSO算法中每一個潛在的解都被稱為一個“粒子”，粒子在解空間內“運行”，隨著算法運行，粒子不斷逼近函數的最值[5]。在每次進化過程中，粒子通過跟蹤2個“極值”來更新自己所在的位置。第一個極值為粒子自身找到的最優位置，相對應的適應值為pBest；另一個極值是整個種群當前找到的最優位置，相對于的適應值稱為全局極值為gBest[6]。其流程圖如圖1所示。在得知最優方案后，即可得調度方案。

圖1 算法流程圖

2.2 粒子編碼的設計

每個粒子位置對應一個新的分配方案，這樣就將每一種配置方案映射成一個粒子，粒子的飛行表示從一個調度方案到另一個調度方案的選擇。隨著算法的收斂，粒子逐漸逼近最優調度方案。機群的調度矩陣為

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

圖2 種群粒子位置

例如，任務1、任務2、任務3分配推土機、挖掘機、裝載機各1臺，其中任務2已完成，將任務2的各類工程機械任意調度到任務1、任務3，其矩陣粒子編碼可表示為

這樣的編碼方式的優點是直觀地將各任務的機群調度情況表示出來，將任務2的1臺推土機、挖掘機、裝載機調度給任務1，2臺挖掘機、裝載機調度給任務3。

2.3 粒子位置更新方式

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

3 案例分析

本文以文獻[3]中的構筑急造軍路任務為例。該急造軍路共有3條道路的構筑任務，各道路的偵查情況為：道路1大面積塌方，道路2有連續彈坑，道路3路基崩塌，據此將任務區分為：任務1清除塌方，任務2克服連續彈坑，任務3修復崩塌路基，各任務工程量如表1所示。因突發情況導致任務1和任務2的機械作業效率降為一半。現有推土機10臺、挖掘機7臺、裝載機6臺，各類機械在不調度的情況下，各任務的作業率如表2所示。文獻[3]完成總任務時間為7.86 h。

表1 各任務工程量

表2 各任務工程機械作業率 h

根據本文建立的數學模型，以最小化總任務完成時間為優化目標，用粒子群算法求解，用Matlab R2015b編程計算。模型求解的優化過程如圖3所示。

圖3 模型求解優化過程

可見，目標函數適應值在算法迭代75次左右達到收斂，總任務完成時間最小值為6.895 h，優于未調度工程機械的任務完成時間7.86 h。最優結果的機群調度矩陣為：

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

4 結論

本文對軍用工程機械遂行構筑急造軍路任務面臨的多型裝備、多種任務、多點同時作業的機群動態調度問題進行分析，提出了基于離散粒子群算法求解模型的機群動態調度方法。該方法能有效解決機群的動態調度問題，提高軍用工程機械的保障能力。