基于MMAS算法的计量检定中心仓储堆垛机拣选路径优化

计量检定中心是自动化仓储物流技术与仪表自动检定系统有机结合的产物, 以实现仪表的集中采购、集中检定、集中仓储、集中配送等一系列作业的智能化、自动化.江苏、重庆、山东等地先后建立了省级计量检定中心.先进仓储管理技术与检定技术对于检定中心的检定质量与效率的提高起着至关重要的作用.

自动化立体仓库的优化问题主要有货位分配、存取路径优化与运输系统的调度问题.对于存取路径优化问题, 倪虹[1]等运用基于顺序的遗传基因编码方式编制程序, 对拣选路径进行优化;李诗珍[2]等采用S形启发式方法对订单拣取路径进行优化;田国会[3]等结合Hopfield网络模型, 采用改进的遗传算法研究自动化立体仓库中固定货架拣选作业路径优化问题;蒋丽林[4]等采用图论的相关算法对自动化立体仓库堆垛机拣选路径进行优化;王娴[5]等采用人工鱼群算法来优化路径;庞龙[6]等采用蚁群算法和遗传算法的混合算法对堆垛机拣选路径做出优化;宁春林[7]等采用MaxMin Ant System Algorithm来求解固定货架拣选路径优化问题.

许多研究表明, 在解决路径优化问题中, 蚁群算法相比于神经网络、启发式方法能更有效地找到最优解[7].在蚁群算法中, MMAS算法相比于基本蚁群算法, 避免了过早收敛而求得局部极值.文献[7]虽然也采用MMAS进行固定货架拣选路径优化, 但没有考虑堆垛机的容量限制.本文针对堆垛机的容量限制建立含装箱约束条件的单目标数学模型, 并分别采用基本AS和MMAS算法进行求解.仿真结果表明, MMAS算法明显提高自动化立体仓库拣选作业的运行效率.

检定中心主要包括自动化立体仓库、待检区和检定区.自动化立体仓库包括堆垛机和立体货架.立体货架为固定货架, 其上存放待检仪表, 待检仪表统一装在规格相同的箱中.位于巷道中的堆垛机接收调度中心命令从货架上取出若干个待检仪表箱, 将其运送至待检区的传输带上.传输带以一定速度运行, 将堆垛机卸下的仪表箱运至待检区的拆箱处, 由人工负责拆箱, 拆箱后的仪表送至检定区检定.工作原理如图1所示.

设有1个立体仓库, 共有8条巷道, 每巷道中设置有巷道堆垛机2台, 1台正常工作, 1台备用, 有6条检定流水线.根据检定需求, 各个巷道中的堆垛机从巷道口出发以拣选方式依次经过多个货位, 取出各个货位中的货物, 并将待检仪表箱转送至传输线, 完成1次拣选作业.单巷道堆垛机拣选示意图如图2所示.图2中, 货架上单个货位的宽度为b, 高度为h, 坐标 (x, y) 表示单巷道内堆垛机的取货点, 坐标 (0, 0) 表示巷道口.

本文的优化目标为堆垛机一次拣选作业路径最短.条件设定如下:

1) 堆垛机每次从传输带处出发, 最后返回到传输带处.

2) 堆垛机运输货物中启动和制动过程忽略不计, 可同时在水平与垂直方向运行, 速度恒定.

3) 忽略堆垛机的存取时间.

4) 仪表的存放状态已知.

5) 每个货位在1次拣选任务中只访问1次.

由以上模型可知堆垛机由货位点i运行至货位点j的距离为dij, 其表达式为

式中:xi, yi为货物点i的坐标;xj, yj为货物点j的坐标.

堆垛机的1次拣选数学模型为

式中:xij参数的定义为xij=0, i=j;xij=1, i≠j.

约束条件为

式中:n为待取货箱个数;nmax为堆垛机单次运行最大装箱数.

进出巷道的最小次数为m, 其表达式为

式中: 表示不小于括号内数值的最小整数.

蚁群算法 (ACO) 的基本原理是模拟真实蚁群觅食过程, 通过信息素的积累和更新来寻求最优解.蚂蚁在寻找食物源时, 在其走过的路上释放一种特殊的分泌物 (信息素) , 后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.当一定路径上通过的蚂蚁越来越多时, 其留下的信息素轨迹也越来越多, 后来的蚂蚁选择该路径的概率也越高, 从而更增加了该路径的信息素强度.而强度大的信息素会吸引更多的蚂蚁, 从而形成一种正反馈机制.通过这种正反馈机制, 蚂蚁最终可以发现最短路径.

蚁群算法在解决旅行商问题 (Traveling Salesman Problem) 中取得了较好的结果.假设有N个节点, 分别代表N个城市, d代表第i个城市与第j个城市的距离.TSP问题就是找到一个闭合的并且N个节点只能经历一遍的最短路径.

设m是蚁群中的蚂蚁数量, 有n个不同节点.第k只蚂蚁在节点i处选择节点j作为下一个节点的概率为[8]

式中:τij表示信息素痕迹浓度;ηij是启发式信息值, ηij=1/dij;Uik表示第k只蚂蚁在i处可直接到达下一节点的集合.通常α和β是2个参数来控制信息量和启发式的值, 通常α=1, β=2~5.该公式表明信息量越多的路径和距离越短的路径被选中的概率越大.

当m只蚂蚁都完成游历之后, 按照下式对所有边上的信息素痕迹进行更新:

式中:ρ是信息挥发率;1-ρ是信息残存率;Δτkij是第k只蚂蚁穿过边 (i, j) 时释放的信息素增量:

式中:Q为常数;Tk是第k只蚂蚁完成的游历, 总长为Lk.

最大最小蚁群算法对基本蚁群算法进行了较大的改进, 主要有以下4个方面.

1) 信息素的释放仅在具有迭代最优游历 (Le) 的蚂蚁上发生.

2) 当出现局部最优解或者停滞, 所有边上的信息素按照下式进行更新:

式中: , Le为迄今最优游历的长度.

3) 为防止停滞现象的出现, 将信息素的取值范围限制为τmin[, τmax];如果信息素在更新的时候超过了τmin[, τmax], 则进行如下限制:如果τij>τmax, 令τij=τmax;如果τij<τmin令,  式中a是一个参数.

4) 信息素初值τ0=τmax.

算法步骤:

1) 计算最大取货次数, 按每个货位横坐标由小到大的顺序分组, 每组货位数为nmax.

2) 初始化参数α、β、ρ、Q、a.

3) 循环次数NC+1.

4) 按照基本AS算法得到迭代最优解.

5) 根据本次迭代最优解计算出τmin、τmax.

6) 更新最优路径上的信息素.

7) 对信息素进行限制.

8) 判断迭代次数是否达到最大值, 若满足, 进行下一组货位求解;否则, 转步骤 (2) .

9) 判断是否完成每一组的求解, 如满足则算法结束;否则, 转步骤 (1) .

算法流程如图3所示.

以省级电网计量中心仓储为例, 自动化仓库每面货架有40列、15层, 共600个货位, 货架系统及巷道堆垛机各参数为:b=1 m, h=1 m, nmax=30, 仿真参数为α=1, β=5, ρ=0.5, Q=100, a=20, NCmax=200, 分别随机选取n=30个货物点和n=45个货位点, 采用基本蚁群算法和最大最小蚁群算法进行Matlab仿真实验.n=30时, 基本蚁群算法与最大最小蚁群算法仿真结果如图4、5所示, 实验的结果对比见表1;n=45时, 基本蚁群算法与最大最小蚁群算法仿真结果如图6、7所示, 实验的结果对比见表2.

从实验图表中可知, 在n=30和n=45的情况下, MMAS算法克服了基本AS算法过早收敛陷入局部极值的情况, 找到了全局最优解.n=30时, 采用MMAS算法后堆垛机的取货路径比采用基本AS算法情况下缩短了3.3%;n=45时, 采用MMAS算法的堆垛机的取货路径比采用基本AS算法情况下缩短了2.0%.

本文针对自动化立体仓库拣选路径优化问题, 建立了含装箱容量约束堆垛机拣选路径模型, 并通过蚁群算法对模型实现优化.利用最大最小蚁群算法的信息素初始化机制有效地克服了基本蚁群算法陷入停滞状态而过早出现局部极值, 对求解自动化立体仓库拣选路径优化问题具有很好的效果.仿真结果表明, 该方法具有较强的可行性, 能有效提高自动化仓库拣选作业的工作效率.