基于混合蚁群遗传算法的多AGV任务分配*

□ 梅 前,董宝力

(浙江理工大学 机械与自动控制学院,浙江 杭州 310018)

消费者需求不断趋于多样化和个性化，订单结构呈现多品种、多批次、小批量的特点，因而对拣选作业的速度和准确性提出了更高的要求。在此背景下，拣选模式已由传统“人到货”逐渐向“货到人”模式转变，对拣选效率也提出了更高要求，而多AGV的任务调度是关系到拣选效率的核心问题。

目前，不同学者采用多种算法对任务分配问题进行研究。朱良恒等在考虑安全能量约束下，针对多AGV任务分配中存在的能量消耗不均衡问题，提出基于能量惩罚策略的遗传算法优化任务序列[1]。秦新立等在复杂约束环境下，引入局部优化算子和改进模拟退火算法求解多AGV任务分配问题[2]。李明等在基于Agent能力模型的基础上改进合同网的招标阶段和投标阶段，提出一种改进的合同网协议的多Agent动态任务分配方法[3]。张子迎等提出基于启发式深度Q学习多AGV任务分配算法解决环境复杂性增加时出现的维度灾难问题[4]。陈明智等采用Q-Learning算法求解综合时间代价、路径代价和协同度代价的多智能体分配算法[5]。Elango等提出利用拍卖机制和 K-means聚类算法求解双目标任务分配模型[6]。王晓军等采用改进交叉变异的方式的多种群遗传算法求解多作业模式下多AGV任务分配问题[7]。熊昕霞针对多AGV任务搬运问题，提出一种分布式协同任务分配策略，并采用k-means算法和改进遗传算法进行求解[8]。

本文在基于货架相似度的订单分批基础上,提出混合蚁群遗传算法求解任务分配问题，通过引入蚁群算法改进遗传算法寻优能力的不足并利用蚁群算法产生的最优解作为遗传算法的初始种群,以加快遗传算法的全局搜索能力和收敛速度。针对蚁群算法易陷入局部最优解这一问题，提出带惩罚机制的动态信息素更新策略，在遗传算法中采用实数编码,形象地表示搬运货架任务和AGV的对应关系，在选择方面采用轮盘赌和精英保留策略，对选择算子进行改进从而使最优个体能够直接遗传到下一代。仿真结果表明，在本文提出的混合蚁群遗传算法较使用遗传算法求解，能够更明显地发挥遗传算法全局搜索能力强的特点且算法性能稳定。

1 问题描述与模型建立

1.1 问题描述

本文研究某配送中心在“货到人”拣选模式下多AGV任务分配的问题。多AGV的任务分配问题可以描述为:当控制中心接受一个时间段订单，按照边播边拣的模式将订单合并同时基于货架相似度[9]进行分批处理，系统确认每个订单中货物所在货架的位置并调度系统中一定数量的AGV完成货架的搬运工作。当订单任务已经确定后，由于拣选人员所需拣选的订单品项是固定的，所有品项在货架的货位固定，即货架的位置是固定的。通过将多个货架搬运任务分配给多个AGV进行搬运，对AGV货架搬运任务顺序进行调整，可以减少AGV总行驶距离，提升系统的拣选效率。AGV任务分配问题属于NP-C问题，分配的目标是将订单任务合理均匀分配给不同的AGV并考虑任务之间的搬运顺序，加快整体的出库效率。

在AGV完成任务的过程中，AGV首先从初始位置移动到货架所在位置并将货架搬运至分拣站台，拣选人员根据订单的信息拣选货物并进行打包装箱工作，拣选完成后AGV将货架搬运到该货架的原来位置，在此位置进行下一次任务的分配[10]。边拣边播模式如图1所示。

在以上背景下，针对多AGV任务分配问题进行研究，建立最小化所有AGV任务距离最短的数学模型，通过引入蚁群算法改进了遗传算法，提高遗传算法局部搜索的能力，并对模型进行求解。

1.2 模型建立

本文选择栅格建模法对配送中心进行建模[11]，这种建模方法直观性强、适用性高且相对比较简单。配送中心环境如下：系统中有多个AGV、货架以及分拣站台，配送中心整体相当于一个二维平面。建立直角坐标系，以左下角为坐标原点O，横向建立X轴，纵向建立Y轴，将平面划分成一个个栅格，如图2所示。定义坐标原点O的坐标为(0,0)，每一个栅格都有确定的坐标(x,y)。

图2 配送中心建模

配送中心的整体布局采用I型布局，其中，货架区域由多排货架组成，每排货架之间留有AGV行走的通道，每个货架有多个货位，每个货位只有一种商品。AGV规定可以从通道内行驶，亦可从货架下方行驶。

本文对系统做出以下假设：

(a) 每个AGV从初始位置O出发；

(b) AGV在进行转弯作业时间设定为0；

(c) 所有货架和分拣站台的位置已知；

(d) 已分批订单所需拣选的品项存储在唯一货架上且位置固定；

(e)任务的数量远大于AGV的数量；

(f)不考虑AGV在货架等待和拥堵等情况；

(g)针对同一批次订单，每个货架只能被AGV 搬运一次。

参数如下：

①C为待拣选货架的数量，R为可调度AGV的数量，M为分拣站台的数量；O为AGV初始位置；

②i为第i个货架，i∈[1,C]；j为第j个分拣站台，j∈[1,M]；k为第k台AGV，k∈[1,R]；N为第k台AGV分配的搬运货架的任务数量，p∈[1,N]；

③(xi,yi)是货架i的坐标位置，(xj,yj)是分拣站台j的坐标位置，(xk,yk)表示第k台AGV在第i个货架坐标位置；

④Dkp0表示第k台AGV从初始位置到达任务p所在货架i所行驶的距离；Dkp1表示第k台AGV从货架i到分拣站台j行走的距离；Dkp2表示第k台AGV从分拣站台j回到货架i所行驶的距离；

⑤Sk(0,p)表示第k辆AGV执行p任务从初始位置出发将货架i搬运到分拣站台j并返回货架位置的距离；Sk(p,p+1)表示第k辆AGV将货架i搬运回原位置后，前往第p+1个任务搬运货架i+1并完成货架搬运任务的距离，Sk(p,N)表示第k辆AGV完成最后搬运任务后返回起始点的距离；

⑥Xkp为决策变量，表示第k台AGV是否执行第p个搬运货架任务。当Xkp=1，则由第k台AGV执行第p个货架搬运任务，当Xkp=0，则第k台AGV不执行p货架搬运任务。

基于AGV的任务分配目标函数表示为最小化所有AGV的总行驶距离，数学表达式如下:

(1)

(2)

Dkp1=|xki-xkj|+|yki-ykj|

(3)

Dkp2=|xki-xkj|+|yki-ykj|

(4)

式(1)表示最小化所有AGV完成搬运任务的总距离；式(2)表示第k台AGV执行q任务到达货架i的距离；式(3)表示AGV搬运货架前往分拣站台j的距离；式(4)表示AGV返回货架原位置的距离。

约束条件：

∑kxkp=1，p∈[1,N]

(5)

∑pxkpq=xkq，q∈[1,N]，k∈[1,R]

(6)

∑qxkpq=xkp，p∈[1,N]，k∈[1,R]

(7)

式(5)表示一个搬运货架任务只能由一个AGV执行；式(6)和(7)表示一个AGV一次只能执行一个任务。

2 混合蚁群遗传算法

遗传算法(Genetic Algorithm，GA)是一种随机化搜索方法，遗传算法实现简单，通用性强，但也存在过早收敛、局部搜索能力弱等问题。针对遗传算法的上述不足，本文在遗传算法的基础上，引入蚁群算法来改进遗传算法的局部搜索能力。

2.1 蚁群算法求解任务分配问题

本文求解的最小化所有AGV行驶总距离可转化为MTSP问题即将货架类比城市，AGV类比旅行商，通过改变AGV任务执行顺序使得总路径最短。

蚁群算法求解 MTSP 问题主要是将 MTSP 问题转化为TSP 问题，即在保持货架和AGV数目不变的情况下，通过建立(m-1)个虚拟坐标的单AGV问题。给每只蚂蚁随机分配一个初始任务,待初始任务完成将其加入禁忌表uk,然后从未完成的任务中选择一个任务。当第k辆AGV完成的任务数达到最大任务数时,蚂蚁选择下一个AGV执行其余任务,直到所有任务完成为止。

①设置蚁群算法的初始参数，其中最大迭代次数Nmax，蚂蚁的编号为k=1。

(8)

③当某一货架搬运任务被完成后，将其加入设置的禁忌表uk中，记录当前的最优解。

④判断蚂蚁是否完成对所有货架的访问任务，如果完成则对信息素浓度进行更新。蚁群算法在迭代产生最差的解会对后续蚂蚁选择路径的行为产生误导，因此，提出一种带惩罚机制的动态信息素更新策略，其更新方法如式(9)所示。

(9)

⑤判断算法是否达到最大迭代次数，即是否满足N>Nmax，是则输出蚁群算法的最优解，否则转入步骤②。

2.2 遗传算法阶段

①生成初始种群。首先本文在蚁群算法产生的最优解中选择路径最短的G/2个路径，再从随机产生的G/2个路径中确定初始种群的数量G，染色体长度为N，最大迭代次数为gmax，交叉概率为Pc和变异概率为Pm。

②编码。本文采用实数编码方式生成染色体，其中染色体的长度为一个批次中的总任务数；每个基因位代表一个货架搬运任务；基因位上对应的值表示该序号的AGV完成该位置的任务。

以图3染色体编码为例，AGV编码数字表示执行该任务的AGV编号，任务号数字表示一个批次的任务顺序。在种群初始化中，AGV编码按照均衡分配编码进行初始化。

图3 染色体编码方式

③适应度函数设计。取各染色体的目标函数值的倒数，即染色体中所有AGV完成全部任务行驶距离的倒数作为该染色体的适应度值，适应度函数如式10所示。

(10)

④采用精英策略和轮盘赌选择。先根据轮盘赌规则选择一定比例的个体，再通过精英策略选择最佳个体复制到下一代。

⑤交叉。交叉操作随机选择染色体中的父代染色体的两段基因片段，然后将两个基因片段进行交叉互换，生成两个子代染色体。

⑥变异。在任务总数范围内，随机选择一个基因位，并将该基因按照Pc进行变异，将发生变异的基因位的值与其他AGV编号进行替换。

⑦解码。设置最大迭代次数，当达到最大迭代时，终止迭代，输出最初结果。

图4 混合蚁群遗传算法流程

3 实例验证

假设仿真实验在50×50m配送中心中进行，用栅格法进行建模。配送中心中有3台AGV，从初始位置出发，速度v为1 m/s。参数设置为α=1,β=4,Pm=0.1，Pc=0.6，最大迭代次数=100。当一批订单需求到达后，按照货架相似度进行分批并确定货架的位置，分批后货架序号和货架位置见表1。

表1 订单分批后的货架序号及位置

通过上述参数对混合蚁群遗传算法和遗传算法的收敛速度和寻优能力进行仿真并进行算法操作，如图5所示。

图5 小任务量下两种算法的迭代图

由图5可知，两种算法的求解过程中最优值随迭代次数不断变化，与标准遗传算法相比，混合蚁群遗传算法迭代最小化目标函数值快速下降，证明了混合蚁群遗传算法具有更高的求解效率。由于混合蚁群遗传算法在迭代开始时就有较为优秀的种群,因而在迭代过程中可以快速跳出局部最优,收敛性比较强。

遗传算法求解3台AGV的任务分配结果见表2，仿真结果如图6所示；混合蚁群遗传算法的分配结果见表3，仿真结果如图7所示。

图6 遗传算法仿真结果

表3 混合蚁群遗传算法任务分配结果

图7 混合蚁群遗传算法仿真结果

由表2和表3可知， 在混合蚁群遗传算法下的所有AGV总行驶距离为1637m，在遗传算法下所有AGV总行驶距离为1756m。

由表4可知，相较于传统的遗传算法，本混合蚁群遗传的算法的减少行驶距离比例达到 6.7%，且在仿真范围内能更大程度缩短 AGV总行驶距离，得到更加理想的全局最优解。

表4 两种算法下任务分配效益表

通过改变 AGV 数目对混合算法寻优能力做进一步验证。本文设置任务数量为200，AGV数量分别为8、12、16、20、24、28，终止迭代次数为1000 次，使得各算法中个体充分迭代，迭代结果如图8所示。

图8 不同AGV任务完成总行驶距离

由图8可知，在不同AGV数量下，AGV 总行驶距离呈现波动状态，当AGV数量过少时，AGV分配任务较多且负载较大，总行驶距离增大，这是因为对任务执行顺序进行分配时可能会减少行驶距离，但会增加 AGV从初始位置前往货架的移动距离以及返回初始位置的距离。当AGV数量过多时,AGV在搬运过程中会造成不同程度的拥挤并且导致每个AGV分配的任务数过少,造成资源浪费。

4 总结

在“货到人”拣选系统中，配送中心的拣选效率是关键问题。本文在考虑订单分批前提下，从AGV任务分配角度进行优化，建立最小化AGV总行驶距离的数学模型，并设计了混合蚁群遗传算法优化AGV搬运货架的顺序。考虑到遗传算法局部搜索能力不足的问题，引入带惩罚机制的动态信息素更新的蚁群算法的最优解作为遗传算法的初始种群来提高算法性能。仿真实验表明，混合蚁群遗传算法能有效提升算法的寻优能力，不会陷入局部最优的快速下降陷阱，能更好地解决多AGV任务分配问题。