以亚马逊Kiva机器人为代表的智能仓储拣货技术, 将传统的“人到货”模式革命性地升级为“货到人”模式, 极大适应了现代物流配送发货单位小型化的特点^[1]. 仓库规模扩大和订单数激增, 进一步要求提升拣货效率, 由此提出了面向智能仓储调度的群机器人任务分配问题^[2]. 其属于一类NP-Hard问题^[3], 通常采用启发式算法解决. Azadnia等^[4]借鉴旅行商问题的求解思路, 用遗传算法对订单任务进行排序, 使分拣人员走过的路程最短, 但其复杂性随任务量增加显著提高. 沈博文等^[5]将机器人状态设置为“忙”“闲”两种, 通过修正A*算法实现特殊道路条件约束下的仓储调度, 但该法仅适合小规模任务情形. 郭宇^[6]提出一种基于市场拍卖思想的多机器人任务分配方法, 通过性能差值的直观比较, 确定各机器人的竞标价格, 生成较优的任务分配方案. 该法虽回避了组合和整数规划中的复杂运算, 适合较大数量子系统之间的交互, 但对通信要求较高. 蒋家志等^[7]使用一种改进的微粒群算法(PSO)解决订单调度问题, 主要优化目标为同一订单中所有任务的完工时间与该订单总完工时间的相聚程度, 提高了智能仓储的运行效率, 但未考虑机器人的平均利用率, 可能导致部分机器人负担过重. 杨杰^[8]引入订单池概念, 以订单池中与分拣台上订单的适应度为标准, 使用离散PSO生成各分拣台上的任务执行顺序. 该法在处理大规模订单时, 容易产生早熟收敛现象, 且局部寻优能力较差, 无法找到最优分配规则. 李功捷^[9]引入虚拟任务概念和任务数分配思想, 通过智能优化算法求解智能仓储调度的机器人任务分配问题.

每种群体智能算法各有优缺点. 发挥各自优势,提高求解效率, 是不同算法融合的动机. 作为经典的启发式算法, 许多学者对蚁群算法和遗传算法的融合进行了大量研究, 以克服或抑制各自缺陷, 实现优势互补. 融合算法大体上分为两类: 一类是以蚁群算法为主体, 利用遗传算法产生的结果作为信息素进行寻优^[10]. 该法虽能够改善蚁群算法初期信息素匮乏的问题, 但在遗传算法阶段一旦陷入局部最优, 后续的蚁群算法将很难跳出, 且蚁群算法本身也很可能因收敛速度过快陷入局部最优. 为解决该问题, 在固定次数迭代后又引入遗传操作, 加大种群分布多样性, 但花费的时间代价高, 不适合实时应用场景^[11]. 另一类是以遗传算法为主体, 利用蚁群算法快速收敛的特性进行问题求解^[12], 提高了全局寻优能力, 但主要用于求解旅行商问题.

本文在前人研究的基础上, 根据智能仓储调度中多订单任务动态产生、任务由群机器人并发执行的特点, 将问题建模成群机器人协同调度的多目标优化问题. 利用蚁群算法产生的较为优秀的解集, 作为遗传算法的初始种群, 以加快遗传算法的收敛速度. 在遗传算法中采用多层编码, 以适应群机器人任务分配需求, 在轮盘赌算子后引入精英保留策略, 对选择算子进行改进, 并增加逆转算子, 在保证种群多样性的同时, 使最优个体能够直接遗传到下一代. 通过多种技术手段的综合运用, 设计了一种新的蚁群-遗传算法融合框架. 仿真结果表明, 在本文提出的融合框架中求解, 较分别使用蚁群算法或遗传算法求解, 能够明显发挥蚁群算法鲁棒性好和遗传算法全局搜索能力强的特点, 且算法性能稳定, 有效提高智能仓库的整体运行效率.

1 问题描述

如图1所示, 由货架、移动机器人、分拣台等组成智能仓储系统, 设置有出入口与外界相通, 机器人能将订单上商品对应的货架按照一定次序送至分拣台, 由等候的仓库工作人员按系统指示从货架上取出相应数量的商品, 放入订单对应的包装箱中打包配送. 现有一批订单, 包含货物的品类数为n, 要求由m个成员机器人组成的群机器人处理. 假设仓库为封闭的二维空间, 一个货架上只存放一种商品, 则可用货架位置表征特定品类商品对应的任务, 记任务集C = {1, 2, …, n}. 设i, j为货架(任务)编号, i, j∈C, 机器人从货架i运动到j的距离为D_ij, 仓库中空闲机器人的数量为r. 规定成员机器人执行的最少任务数为L. 对环境进行栅格化建模^[13]. 考虑机器人避碰, 货架间设置两条通道, 供机器人相向通行. 将各栅格设置的二维码视为路标, 用于机器人定位. 为简便起见, 追加如下假设:

(1) 每个机器人占据一个栅格, 以栅格为单位移动, 运动方向限定为上、下、左、右.

(2) 为避免机器人碰撞, 货架区域间由栅格组成的通道均为单行道.

(3) 机器人的感知、定位、交互、运算、运动, 以及托举重物的能力相同.

群机器人的任务分配流程为: 中央处理器接收到订单任务, 查表得到商品所在货架位置, 生成机器人的调度方案; 机器人运动到相应货架并将其托举至分拣台; 分拣台处等候的工作人员按订单要求取下货架上的商品; 机器人将货架送回原位置, 该次任务完成.

对于一个订单任务, 由于商品种类及货架位置均已确定, 故机器人在货架与分拣台间的行走距离也已确定. 这便意味着, 群机器人任务分配的优化目标, 为机器人完成相应于时序相连的两个任务(货架)的过程. 由于机器人只能沿栅格移动, 记栅格位置坐标(x, y), 故货架之间的距离用曼哈顿距离计算, 见式(1):

$ {D_{ij}} = |{x_i} - {x_j}| + |{y_i} - {y_j}| $

(1)

其中, x_i, y_i和x_j, y_j分别为第i, j个任务对应货架在栅格地图中的横坐标和纵坐标.

根据智能仓储系统的优化目标, 将任务分配评价指标定义为路径代价和时间代价的综合. 其中, 路径代价为机器人在目标任务间行走的距离. 构造如式(2)所示的适应度函数, 作为评价指标:

$ Fitness = A \times PAC + B \times TAC $

(2)

其中, PAC为路径代价, 即完成所有任务全部机器人走过的距离之和; TAC为时间代价, 即全部机器人完成所有任务花费的时间; A, B是路径代价和时间代价的权重. 由于完成任务花费的时间与机器人的行走距离有关, 故将完成任务时行走距离最大的机器人走过的距离值作为时间代价. 为避免误解, 同时作距离量纲到时间量纲的处理. 可见, 适应度函数值越小, 表明完成任务的代价越小, 即全部机器人完成任务走过的距离越短, 任务分配越合理.

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

用蚁群算法^[14]建模并求解任务分配问题. 蚂蚁之间通过觅食过程中释放的“信息素”进行间接通信, 选择较优路径, 形成正反馈, 经过多次迭代找到最优路径.

表示任务数和机器人数的符号意义保持不变. 将其转化为(n+m−1)个任务的单机器人问题. 由于机器人的能力相对有限, 故限定机器人执行的最大任务数为lr. 首先给每只蚂蚁随机分配一个初始任务, 待初始任务完成, 将其加入禁忌表, 然后从未完成的任务中选择一个. 当第r个机器人完成的任务数等于最大任务数lr时, 蚂蚁选择下一个机器人执行其余任务, 直到所有任务完成为止. t时刻蚂蚁k由任务i到j的状态转移概率 $P_{ij}^k\left( t \right)$ 见式(3):

$ {P^k_{ij}}\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}} \right]}^\beta }}}{{\displaystyle\sum\nolimits_{k \in \sigma } {{{\left[ {{\tau _{ik}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ik}}} \right]}^\beta }} }}, \; j \in \sigma } \\ {0, \;{\rm{else}}} \end{array}} \right. $

(3)

其中, ${\tau _{ij}}\left( t \right)$ 表示任务i和j之间的信息素强度, ${\eta _{ij}}$ 表示任务i和j间启发式因子的强度, $\alpha $ 、 $\;\beta $ 分别是信息素重要程度因子和启发函数重要程度因子, 用于调节 ${\tau _{ij}}\left( t \right)$ 和 ${\eta _{ij}}$ 之间的作用, $\sigma $ 表示机器人还未完成的任务, 即不在禁忌表中的任务. t+n时刻蚂蚁释放的信息素浓度, 按式(4)所示规律更新:

$ {\tau _{ij}}\left( {t + n} \right) = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + \Delta {\tau _{ij}} $

(4)

其中, $\rho $ 为信息素挥发因子, $\left( {1 - \rho } \right)$ 则为信息素残留因子, $\Delta {\tau _{ij}}$ 为本次循环任务i到j的信息素增量, 见式(5):

$ \Delta {\tau _{ij}} = \sum\nolimits_{k = 1}^m {\Delta \tau _{ij}^k} $

(5)

其中, $\Delta \tau _{ij}^k$ 为第k只蚂蚁在任务i到j路径上释放的信息素量. 当第k只蚂蚁从任务i到j移动时, 释放的信息素量如式(6)所示:

$ \Delta \tau _{ij}^k = Q/{L_k} $

(6)

其中, $Q$ 为信息素强度系数, ${L_k}$ 表示第k只蚂蚁本次循环所走过的路径长度. 群机器人任务分配求解的蚁群算法流程见算法1.

算法1. 蚁群算法解决任务分配

开始

　参数初始化

　随机产生m只蚂蚁的初始位置

　当不满足终止要求:

　　对于每一只蚂蚁k:

　　根据式(3)计算状态转移概率选择任务

　　更新禁忌表

　结束

　当m只蚂蚁搜索完毕:

　　记录本次迭代最佳路线

　　按式(4)–式(6)更新信息素

　　禁忌表清零

　结束

结束

3 遗传算法求解任务分配问题

用遗传算法^[15]求解群机器人任务分配问题. 为解决收敛速度慢和封闭竞争问题, 定义虚拟任务并加入列表. 为了使虚拟任务不影响代价计算, 规定虚拟任务间的关联代价为无穷, 虚拟任务与真实任务间的代价以及虚拟任务的自身代价为0. 群机器人任务分配的遗传算法求解流程见算法2.

算法2. 遗传算法解决任务分配

开始

　初始化参数

　初始化种群中m条染色体

　编码

　当不满足终止要求:

　　计算个体适应度值

　　遗传操作

　结束

　解码输出最优结果

结束

4 蚁群-遗传融合框架及其求解 4.1 基本思想

蚁群算法具有较强的鲁棒性, 对初始路线要求不高, 求解结果不依赖于初始路线选择, 但收敛速度慢, 易陷入局部最优, 且计算开销大. 遗传算法全局搜索能力强, 不会陷入局部最优解的快速下降陷阱, 但搜索速度较慢, 对初始种群依赖性强, 局部搜索能力差. 为发挥两种算法各自的优势, 提高收敛速度和执行效率, 提出一个蚁群-遗传算法融合框架. 基于该框架的群机器人任务分配算法流程见算法3.

算法3. 蚁群-遗传算法融合框架内的群机器人任务分配

开始

　初始化参数

　随机产生m只蚂蚁的初始位置

　对于每一个蚂蚁k:

　根据式(3)计算状态转移概率选择任务

　更新禁忌表

　结束

　当m只蚂蚁搜索完毕:

　将蚁群算法一次迭代所得解集作为遗传算法初始种群

　种群编码

　当不满足终止要求:

　　根据式(2)计算个体适应度值

　　do

　　{

　　　轮盘赌法从种群中选择一定比例父代

　　　精英保留策略选出最佳父代直接保存

　　　其余个体分别进行交叉、变异、逆转操作

　　}

　　结束

　　获得任务分配最优解

结束

不难看出, 融合框架的设计思路为, 利用蚁群算法, 经过一次迭代后产生一个较为优秀的解集, 将其作为遗传算法的初始种群, 以有效减少遗传算法的寻优次数, 快速找到最优解.

4.2 操作要点

(1) 种群初始化. 遗传算法的初始种群通常是随机生成的, 虽然保证了个体的多样性, 但随机生成的初始种群在迭代过程中收敛速度缓慢, 导致遗传算法寻优速度慢. 本文将蚁群算法经过一次迭代后产生的解集作为遗传算法的初始种群, 使遗传算法获得较为优秀的初始种群, 有效减少遗传算法的寻优次数.

(2) 编码. 遗传算法采用多层编码方式, 第1层编码为任务的执行顺序, 第2层编码为机器人之间执行任务中断点的位置.

(3) 选择算子. 采用轮盘赌法选择一定比例的父代, 再通过精英保留策略, 挑选出最佳父代, 直接保存在下一代中. 采用这种方法可以在保证个体多样性的同时, 还可以使最佳个体直接遗传到下一代中.

(4) 交叉算子. 采用部分映射交叉方式, 在染色体编码串中随机选择两个交叉点, 然后进行部分基因的交换, 得到新的个体.

(5) 变异算子. 采用互换变异的方式, 随机选择两个基因位置, 然后将这两个基因位置的编码交换, 获得一个新的个体. 染色体中基因互换过程见图2.

(6) 逆转操作. 为加速进化加入逆转操作, 这里的逆转操作具有单向性, 即加入逆转操作后产生的个体更优才会进行. 随机产生两个随机数n₁和n₂ (n₁, n₂∈n, n₁≠n₂), 将n₁与n₂间的基因反向排序, 得到新个体. 以n=8, n₁=3, n₂=6为例的逆转操作见图3.

5 仿真

仿真在Matlab 2018b的平台上进行. 将尺寸为100 m×102 m的实验环境建模为栅格地图, 单位长度为 1m. 货架的位置坐标设置后, 任务随机生成. 设置蚂蚁数=80, 信息素重要程度因子α=1, 启发函数重要程度因子β=5, 遗传算法种群数=80, 最大迭代次数=5000.

考虑到仓库存在空闲期和繁忙期, 分别用蚁群算法、遗传算法和本文所提的融合算法, 针对小任务量和中大任务量情形, 进行任务分配实验.

5.1 小任务量情形

设置空闲移动机器人数量=4, 随机生成任务数=20, 每个机器人执行5个任务, 分别使用蚁群算法、遗传算法和融合算法, 对群机器人任务分配进行控制, 收敛过程见图4.

图4显示, 融合算法在迭代300次左右时, 适应度函数值趋于稳定; 而蚁群算法和遗传算法分别在在迭代4000和2000次后, 适应度函数值逐渐稳定于200左右. 表明融合算法的收敛速度较蚁群算法和遗传算法快, 且结果也优于其他两种算法. 究其原因, 融合算法在迭代开始时就有较为优秀的种群, 在迭代过程中可以快速跳出局部最优, 收敛性强, 适应度函数值接近于最终稳定的结果. 因此, 对于小规模的任务分配, 本文所提融合算法能够快速寻求较优的任务分配结果, 进而提高智能仓库的整体运行效率.

5.2 中大规模任务量情形

(1) 固定任务数=100, 分别令机器人数=10, 20, 30, 40, 50, 每组实验重复执行30次, 统计结果见图5.

结果显示, 随着机器人数量增加, 群机器人完成任务花费的路径代价和时间代价逐渐降低. 通过折线图可以直观看出, 本文提出的融合算法无论是走过的路程还是花费的时间, 都明显优于单独采用蚁群算法和遗传算法时的任务分配效果, 体现出较高效率. 在执行固定数量的任务时, 采用融合算法进行任务分配, 机器人完成全部任务花费的时间比单独采用蚁群算法和遗传算法少50%以上, 融合算法具有明显优势, 大大提高了智能仓库的整体工作效率. 在机器人数=10, 20, 30, 40时, 融合算法的路径代价呈现线性下降的趋势; 当机器人数=50时, 下降趋势减缓. 其原因可能是, 随机器人数增多, 仓库中逐渐变得拥挤; 当执行任务的机器人过多时, 会导致每个机器人分配的任务数过少, 无法充分发挥机器人的价值, 造成资源浪费.

(2) 固定机器人数=10, 分别令任务数=50, 100, 150, 200, 每组实验重复执行30次, 统计结果见图6.

不难发现, 群机器人数不变时, 随着任务增加, 花费的路径代价和时间代价都随之增加.

使用融合算法和单独使用蚁群算法进行任务分配, 虽然在路径代价上没有明显差别, 但前者的时间代价远小于后者. 在任务数超过150后, 采用遗传算法进行任务分配花费的路径代价和时间代价增加速度变快, 完成任务机器人所走的路程以及花费的时间变大, 而融合算法则在任务数超过150后, 花费的路径代价和时间代价增加趋势减缓.

使用融合算法进行任务分配, 路径代价和时间代价均优于单独使用遗传算法.

本组实验结果表明, 本文提出的融合算法在中大规模智能仓储系统的任务分配效率更高.

通过两组实验可以发现, 蚁群算法收敛速度慢, 易陷入局部最优, 且计算开销大. 遗传算法搜索速度较慢, 对初始种群依赖性强, 局部搜索能力差. 采用融合算法进行任务分配, 相较单独使用蚁群算法或遗传算法, 时间代价明显为少. 随着任务数增加, 融合算法体现出更高的效率.

计算两种变量固定情形下的路径相对误差 ${\textit{S}_{P}}$ 和时间相对误差 ${\textit{S}_{T}}$ . 计算方法见式(7)和式(8):

$ {\textit{S}_{P}} = \sqrt {\sum {{{\left( {{R_{iP}} - \overline {AV{G_P}} } \right)}^2}/n} } $

(7)

$ {\textit{S}_{T}} = \sqrt {\sum {{{\left( {{R_{iT}} - \overline {AV{G_T}} } \right)}^2}/n} } $

(8)

其中, ${R_{iP}}$ , ${R_{iT}}$ 分别是第i次实验的路径代价和时间代价, $\overline {AV{G_P}} $ , $\overline {AV{G_T}} $ 分别是n次实验路径代价和时间代价的平均值, 结果见表1和表2中, ACO_GA_P, ACO_GA_T为融合算法分别对应的路径代价和时间代价, GA_P, GA_T为遗传算法分别对应的路径代价和时间代价, ACO_P, ACO_T为蚁群算法分别对应的路径代价和时间代价.

结果显示, 任务量确定时, 随着机器人数增加, 相对误差逐渐变小; 机器人数确定时, 随着执行的任务数增加, 相对误差逐渐变大. 可见, 作为启发式算法, 不同组合条件下都存在随机性. 但本文所提融合算法的代价, 其相对误差均较单独使用蚁群算法和遗传算法更小, 表明融合算法的性能较为稳定.

6 讨论

本文针对智能仓储调度中群机器人任务分配问题, 提出了一个适用于不同任务规模的蚁群-遗传算法融合框架, 通过仿真实验得到以下结论:

(1) 蚁群算法具有较强的鲁棒性, 采用蚁群算法解决群机器人任务分配问题时对初始路线要求不高, 求解结果不受初始路线的影响, 局部搜索能力强. 但蚁群算法收敛速度慢, 易陷入局部最优, 且计算开销大, 故采用蚁群算法解决群机器人任务分配问题效率较低.

(2) 单独使用遗传算法解决任务分配问题, 全局搜索能力强, 不会陷入局部最优的快速下降陷阱, 但搜索速度较慢, 对初始种群依赖性强, 局部搜索能力差, 故单独使用遗传算法解决该类问题执行效率较低.

(3) 蚁群-遗传算法融合框架下, 蚁群算法和遗传算法各自优点得到发挥, 全局搜索能力强, 不会陷入局部最优解, 收敛速度快, 完成任务的路程代价和时间代价较小, 寻优结果更好, 提高了智能仓储系统的运行效率.

(4) 本文提出的融合框架虽可有效提升智能仓储系统任务分配的效率, 但仍存在不足. 主要是, 成员机器人一次只能执行一个订单任务、未考虑动态订单分配等. 未来研究将围绕仓库动态订单分配进行, 以不断接近智能仓储系统的实际工作情形.