杜毛强，何晓晖，王 强，朱晓基，魏文海

（1.陆军工程大学野战工程学院，南京 210007；2.解放军32228 部队23 分队，福建 厦门 361100）

0 引言

急造军路是军用工程机械遂行机动工程保障任务之一。根据急造军路的任务性质，通常可将其分为清除塌方、填塞弹坑和壕沟、修复崩塌路基等3种具体任务，且往往需要在不同地域同时开展。每个任务均涉及到推土机、挖掘机、装载机等多种类型军用工程机械协同作业。因此，军用工程机械遂行急造军路任务是一个多型装备、多种任务、多点同时展开的机群作业问题。研究机群的优化配置既有重要的现实意义，又有重要的理论研究价值，是该领域的研究热点。Manuel Parente［1］等人整合了启发式算法和数据挖掘技术的优点，以搜索工程机械的最佳配置；冯柯［2］等人以充分发挥现有工程机械作业效能为目标，运用线性规划的方法建立了工程机械机群优化配置的数学模型；曹豪荣［3］等人采用随机过程排队论方法得到基于快速施工的最优机械配置方案；Faridaddin Vahdatikhaki［4］等人提出了一种多智能体系统，有效改善施工机群的协调问题；郑雨茜［5］等人运用极差最大化组合赋权法改进了现有的机群配置模型。但上述研究仅限于单任务、单点展开作业的情况，对多型装备、多任务、多点同时展开作业的机群配置问题考虑较少。本文针对军用工程机械遂行急造军路的机群配置的现实需求，以完成任务时间最短为优化目标，基于整数线性规划理论建立了机群优化配置模型，为军用工程机械机群优化配置提供了决策支持。

1 优化配置模型构建

军用工程机械机群的配置需要根据任务类型、工程量以及机械的作业能力确定，因此，必须对机群配置问题进行建模分析，以制定最优的机群配置方案。

1.1 任务描述

急造军路可分为3 种具体任务：清除塌方、填塞弹坑和壕沟、修复崩塌路基。在遂行任务时，3 种任务往往同时开展，且都需要推土机、挖掘机、装载机协同完成。将军用工程机械机群中的每一台工程机械看作一个单位，单位集：

其中，T 表示推土机，W 表示挖掘机，Z 表示装载机。各种机械数量分别表示为：推土机n1，挖掘机n2，装载机n3。

假设共有推土机a 台，挖掘机b 台，装载机c台，任务数量为e。机群配置的任务—单位分配关系表示为：

挖掘机：

装载机：

1.2 问题建模

考虑每个任务如何配置机群，能够使总任务完成的时间最少。由于总任务完成的时间等于各任务完成时间tj的最大值。军用工程机械机群优化配置模型的目标函数为：

需要满足的约束条件有：

1）机械数量约束。

各任务机械数量不得超过该类机械现有数量：

2）任务完成时间约束。

各任务必须在要求时间限制内完成：

其中，Ci为任务i 的工程量，Qj为单位j 的作业率。

3）各任务要尽可能地同时完工，避免出现某段任务完工过早或过晚的现象，以保证机群资源更加均衡合理分配使用。

4）每个任务必须都有3 种不同类型的机械，且数量为整数。

通过对问题的描述和约束条件分析，可建立如下数学模型：

2 模型求解

机群的配置模型求解是一个离散组合优化问题，而启发式搜索算法是解决此类问题的有效方法。结合本研究问题的特殊性，在对离散粒子群算法［6］、隐枚举法［7］、遗传算法［8］等方法进行比较的基础上，本文选用粒子群算法求解优化配置模型。该算法具有收敛速度快、全局优化性好的特点，其应用领域已从连续空间优化问题扩展到离散组合优化问题［9］，在解决机群优化配置问题上优势尤为明显。

2.1 算法流程

离散粒子群优化算法（BPSO）随机初始化一群粒子，每个粒子代表多为空间中的一个点，它使待优化函数最值的一个潜在解，随着算法运行，粒子不断逼近函数的最值。在每次进化过程中，粒子通过跟踪两个“极值”来更新自己所在的位置。第1 个极值为粒子自身找到的最优位置，相对应的适应值叫pBest；另一个极值是整个种群当前找到的最优位置，相对于的适应值称为全局极值gBest。其流程图如图1 所示。

图1 算法流程图

2.2 粒子编码的设计

对于机群优化配置问题，每个粒子位置对应一个配置方案，这样就将每一种配置方案映射成一个粒子，粒子的飞行表示从一个配置方案到另一个配置方案的选择。随着算法的收敛，粒子逐渐逼近最优配置方案。遂行急造军路任务的机群配置矩阵为：

式中，Tij，Wij，Zij∈｛0，1｝。可进一步将其分解为子矩阵：分别表示推土机、挖掘机、装载机在各任务的配置情况。

设种群中粒子位置的集合为：

式中，PO P 为种群大小。

种群中粒子位置如图2 所示。

图2 粒子种群位置

例如，任务1、任务2、任务3 分配推土机、挖掘机、装载机各1 台的矩阵粒子编码可表示为

这样的编码方式可以直观地将各任务的机群配置情况表示出来。

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

由于每个单位只能被分到一个任务，每个任务至少分配一个单位，所以位置矩阵每列的和恒等于1，每行的和大于等于1。传统的BPSO 在处理粒子位置的更新时，粒子中1 的个数可能发生改变，出现一列都为0 或一行都为0 的情况，故需对BPSO 进行改进。文献［10］提出了一种速度位置更新公式：

按照本文的编码方式，机群的配置方案由粒子位置矩阵各行1 的数量决定，所以各行0、1 的顺序没有实际意义。例如以下两个矩阵：

均表示在任务1、任务2、任务3 分配推土机、挖掘机、装载机各1 台。所以在粒子位置矩阵按照式（9）迭代时，可对算法进一步改进。若子矩阵各行的和没有改变，则不计算适应值，返回重新迭代，这样可以加快收敛速度。改进的BPSO 速度与位置更新方式如图3 所示。

3 案例分析

本文以文献［2］中的构筑急造军路任务为例。该急造军路共有3 条道路的构筑任务，各道路的侦查情况为：道路1 大面积塌方，道路2 有连续弹坑，道路3 路基崩塌，据此将任务区分为：任务1 清除塌方，任务2 克服连续弹坑，任务3 修复崩塌路基，各任务工程量如表1 所示。现有推土机10 台，挖掘机7 台，装载机6 台，各类机械在理想条件下（即机械技术状况良好、中等土壤、白天、无雨雪等），对各任务的作业率如表2 所示。文献［2］利用线性规划方法得到的优化配置方案完成总任务时间为4.02 h。

表1 各任务工程量（m 3）

表2 各任务工程机械作业率（m 3/h）

根据本文建立的数学模型，以最小化总任务完成时间为优化目标，用改进的BPSO 求解，并利用Matlab R2015b 进行编程计算。模型求解的优化过程如下页图4 所示。

可见，目标函数适应值在算法迭代40 次左右达到收敛，总任务完成时间最小值为3.931 9 h，优于文献［2］利用线性规划方法求得的任务完成时间4.02 h。算法在仿真20 次以后趋于稳定，说明算法在解决机群优化配置问题上具有快速的寻优能力。最优结果的机群配置矩阵为：

图3 粒子速度与位置更新方式示意图

图4 模型求解优化过程

得到军用工程机械机群的最优配置方案如表3所示。

表3 最优机群配置方案

4 结论

本文对军用工程机械遂行构筑急造军路任务面临的多型装备、多种任务、多点同时作业的机群优化配置问题进行分析，提出了基于整数线性规划理论建立机群优化配置模型，并运用改进的离散粒子群算法求解模型的机群优化配置方法。通过案例分析表明，该方法能有效解决机群的优化配置问题，提高军用工程机械的保障能力。