柔性制造车间多载具AGV 任务分组算法研究*

张博晖，武照云，程洋洋，代争争，高梦媛

（河南工业大学 机电工程学院，河南 郑州 450001）

引言

自动导引运输车（automated guided vehicle，AGV）是柔性制造车间中不可或缺的运输工具，但随着对柔性制造车间生产效率的要求不断提高，多载具AGV 在柔性制造车间中的应用也越来越多，即每辆AGV 上有多个可装载工位，如何对任务与多载具AGV 进行匹配是当前急需解决的问题，一种合理的任务调度策略可以有效提高多载具AGV 系统整体运行效率[1]。

本文提出一种基于取货点距离的多载具AGV 任务分组算法，即在已知多载具AGV 搬运能力和任务的情况下，对任务进行聚类分组，从而最大化的利用多载具AGV 的搬运效率，提高车间工作效率。

1 任务组合问题描述与建模

柔性制造车间多载具AGV 系统的任务序列中通常存在多个运输任务，由于每个任务的位置信息不同，所以要考虑多载具AGV 与多个任务如何匹配的问题，即每辆多载具AGV 选择哪些货物进行搬运的问题[2]。因此多载具AGV 任务调度要求AGV 控制系统对任务进行合理分配，协调所有任务有序执行，从而保证柔性制造车间能够高效运转。

1.1 车间环境建模

在制造车间环境中开展AGV 任务调度研究，首先要建立车间环境地图。关于车间环境表达存在许多方法，例如：可视图法、栅格地图法、拓扑地图法等，其中拓扑地图法是一种高效的电子地图建模方法，尤其适用于车辆路网确定的情形[3，4]。相应地，实际的AGV 可行行使路径可抽象为拓扑图中的线段或者是弧线，AGV 路径的交叉点、停车点、充电桩等特殊意义的位置可以抽象为节点，进而这些节点和连接线组合成为车间环境的拓扑结构图。

具体地，拓扑图 G=（V，E）中 V={v1，v2，…，vi，…，vz}是图G 中z 个顶点的集合，vi可代表路径交叉点和工作台等具有独特意义的位置，i∈[1，z]；E={e1，e2，…，ek，…，em}是图G 中数量为m 的边集合，ek代表车间运输道路，k∈[1，m]。

1.2 任务分组函数建模

柔性制造车间中多载具AGV 的任务调度问题首先要明确哪辆多载具AGV 搬运哪些工件，这是一种经典的NP-hard 问题。本文将多个任务与多个多载具AGV 的匹配问题转化为多个任务组与多个多载具AGV 的匹配问题，即将任务序列中的任务基于取货点聚类为多个任务组，再将这些任务组分配给每辆多载具AGV[5]。

为了描述模型，现定义以下变量和常量。

表1 模型参数和决策变量定义表

假设制造车间环境待执行任务信息已知，为建立基于取货点距离的任务分组模型，以模型构建的现实性和易处理性为原则且不失一般性，提出以下建模假设：

（1）所有多载具AGV 零时刻可用。

（2）不考虑工件的重量和体积。

（3）一道工序任务只能被分配到一个任务组中。

基于建模假设，多载具AGV 任务分组算法以组内取货点距离max（Czi-CGj）2为优化目标，具体可表示为：

约束条件为：

式（2）保证每个任务都被分配；式（3）保证同一个任务只能被分配到一个组中。

2 问题求解

柔性制造车间多载具AGV 调度系统检测到任务到来后，首先读取所有待执行任务的信息，然后根据所提任务分组算法对所有任务进行聚类分组，直至所有任务都被分组。基于取货点距离的任务分组算法流程如下：

步骤一：读取任务序列信息，提取各任务的取货点坐标，随机选择一个任务点作为一个初始组心；

步骤二：计算每个样本点与当前已有聚类中心之间的最短距离，用D（x）表示，然后计算每个样本点被选为下一个聚类中心的概率按轮盘法选出下一个聚类中心，D（x）越大被选为聚类中心的概率越大；

步骤三：重复步骤二，直至选出r 个组心；

步骤四：计算任务序列中其他各任务点到r 个组心之间的距离，并将其分配到距离最小的组心所对应的组中；

步骤五：重新计算r 个组的质心，并作为新的组心；

步骤六：重复步骤四、五直至组心不再变化；

步骤七：每个组心依次选择距离自身最近的任务点，直至所有任务都被分配到任务组中；

基于取货点距离的任务分组算法流程如图1 所示。

图1 基于取货点距离的任务分组算法流程图

3 实例验证

以某柔性制造车间为例，所建立的车间拓扑地图如图2 所示，共有38 个节点，61 条边，定义车间中1 点为坐标原点，车间中有多辆三工位的多载具AGV，即每辆AGV 可最多同时搬运三个工件，当前待执行任务序列Xn如表2 所示。

图2 车间拓扑地图

首先采用任务分组算法对任务进行聚类分组，然后使用Dijkstra 算法计算多载具AGV 完成所有任务所需的运输距离[6]。本实验以matlab2018 版为实验平台，通过所提算法求解可将任务序列分为6 组，算法结果图示意图如图3 所示，基于取货点距离的任务分组结果及组内各成员信息如表3 所示，经计算完成所有任务后，多载具AGV 总的运输距离为307.5m。

表2 柔性制造车间待执行任务序列

图3 任务分组算法结果示意图

表3 基于取货点距离的任务分组结果及组内各成员信息

然后，采用顺序分组的方法进行分组，基于顺序分组的结果如表4 所示，结合Dijkstra 算法求解，得出该方法下多载具AGV 完成所有任务的运输距离为463m。

表4 基于顺序分组的任务分组结果及组内各成员信息

通过对比两种方法下多负载AGV 执行任务所需的运输距离可知，在多载具AGV 任务已知的情况下，基于取货点距离的任务分组算法既能在充分利用多载具AGV 最大运输能力的情况下对任务进行分组，又可以有效减少AGV 执行任务所需的运输距离，共减少了155.5m 的运输路径，有效的提高了车间的运行效率。

4 结论

（1）根据柔性制造车间中现有的任务信息，设计提出了一种基于取货点距离的多载具AGV 任务分组算法。

（2）案例研究表明，在AGV 最大装载能力确定的情况下，所提算法既可有效的将任务进行分组，又能减少多载具AGV 完成任务所需的运输距离，进而证明了所提分组算法的可行性与有效性。