自动化立体仓库 (Automated Storage and Retrieval System, AS/RS) 的效率高低主要受货位分配的影响, 采用合适的货位分配原则实现货物分配最优位置存储, 可以充分利用储存空间, 缩短出入库移动的距离和作业时间, 并能使得货架受力情况良好, 保证货架的稳定性, 加快货物周转, 提高工作效率以及货架可靠性[1,2,3]。

国内外学者在货位分配问题上做了深入研究。Lu Chen和Andre'Langevin等人[4]根据停留持续时间的共享存储原则, 解决了自动化立体仓库的货位分配与交叉存取问题;Guo Shin-Ming, Liu Tsai-Pei等人[5]分析了多通道立体仓库存储环境下, 双梭系统在基于不同产品类型存储问题下的优势, 以及不同存储分配问题对双梭系统性能的影响;赵雪峰[6]、鄂晓征[7]等人以出入库效率和空间利用率为目标, 分别提出两级遗传算法和混合遗传算法解决仓储货位优化问题;张晓兰、蒋丽娜等人[8]采用遗传算法对货位动态分配优化问题进行了研究, 通过权重系数变换法较好地解决了存取路径距离以及货架承重能力和稳定性多目标之间的相互冲突问题。

目前, 对立体仓库货位分配、存储问题常用的优化算法包括:枚举法、随机法和迭代算法等[9]。采用遗传算法进行优化求解时, 进行选择、交叉以及变异等遗传算子的操作会影响解的质量, 本文提出将模拟退火算法、粒子群算法相结合的混合粒子群算法解决货位分配问题, 在反复寻找最优货位分配的迭代过程中, 采用模拟退火算法来优化粒子群算法的速度更新公式, 从而避免结果陷入局部最优, 最后采用MAT-LAB软件实现所有算法的求解。

为提高自动化立体仓库效率, 加强货位管理, 自动化立体仓库货位分配应遵循以下原则[10,11,12]。

1) 上轻下重, 使货架的受力稳定。

2) 先进先出, 加快周转。

3) 根据货物的特性和出入库频率, 将存储区域划区分段存储。

4) 进行出入库操作时, 先确定该货物所在货位的分区, 再选择该分区内距离出入库台最近的货位作为出入库的货位。

本文在考虑上述原则的基础上, 从自动化立体仓库实际情况出发, 根据货物出入库频率和货物重量进行分类存储, 建立多色集合和混合粒子群算法相结合的决策模型, 以解决自动化立体仓库货位分配时货架稳定性和出入库效率问题。

多色集合是一种新兴的系统理论和信息处理工具, 其核心思想是对不同对象 (产品、设计过程、工艺过程和生产系统等) 使用相同形式的数学模型进行仿真。它应用数理逻辑、矩阵论和模糊数学等工具改进传统集合论, 清晰地描绘复杂机械系统中各种性质、属性、特征以及参数等技术指标的相互关系。多色集合的基本模型是布尔矩阵, 采用标准的数学模型, 有利于进行计算机编程[13]。

考虑货物出入库效率和货架受力情况, 采用多色集合理论进行货架分区。将货位编号作为多色集合的统一颜色 (代表所有货位的共同特征) , 将货位特征、货物出入库频率和货物重量作为多色集合的设计元素 (代表货物的个体特征) , 把两者相互联系建立立体仓库货位分区的数学模型, 组成围道布尔矩阵[B×F (B) ], 其中B为统一颜色集合, F (B) 为设计元素。

统一颜色集合B由不同货位编号组成, 其数学表达式为:B= (b1, b2, …, br, …, bR) , br表示第r个货位的物理编号。

设计元素F (B) 是指影响立体仓库出入库因素的集合, 包括货位特征、货物出入库频率和货物重量, 其数学表达式为:F (B) = (F1, F2, …, Fs, …, FS) , Fs表示第s个设计元素。

[B×F (B) ]从整体上表示约束立体仓库出入库的货位特征、货物出入库频率和货物重量与货位之间的关系。

本文以12层60列的立体仓库为例, 该仓库存储的货物按照所需货位个数、出入库频率和货物重量等分为5类, 货物特征表如表1所示。

表1 货物特征表  下载原图

组成围道布尔矩阵[B×F (B) ]如图1所示, (i, j) 为第i列第j层的货位坐标, 分别代表货架的列数和层数, 其中i=1, 2, …, 60;j=1, 2, …, 12。货位的物理编号为br, 其中r=60× (j-1) +i。

F1~F5为货物出入库频率特征, 分别表示频率在40%~50%之间、30%~40%之间、20%~30%之间、10%~20%之间和10%以下, 对应出入库频率的五个等级:高、较高、中等、较低以及低。

F6~F10为货物重量特征, 分别表示重量在800~1 000N之间、600~800N之间、400~600N之间、200~400N之间和200N以下, 对应货物重量的五个等级:重、较重、中等、较轻以及轻。

F11~F15为货物存放层数, 分别表示货物存放在1~5层、6~7层、8~9层、10层和11~12层, 对应货物存放层数的五个等级:低、较低、中等、较高以及高。

F16~F20为货物存放列数:分别表示货物存放在1~13列、14~33列、34~49列、50~59列和60列, 对应货物存放列数的五个等级:近、较近、中等、较远以及远。

F (br) 为集合B中元素br的个人着色 (个体特征) 。例如, 对于F (b14) = (F2, F6, F11, F17) , 用布尔矢量表示为F (b14) = (0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0) , 在图1中, 将布尔矢量表达式中的1和0分别用“●”和空格表示。

根据图1所示的货位编号———货位、货物特征的围道布尔矩阵, 利用MATLAB软件将货架分为5个区域, 分别用A、H、C、K、E表示各分区号, 货位分区图如图2所示。

分区A存放第1类货物, 分区H存放第2类货物, 分区C存放第3类货物, 分区K存放第4类货物, 分区E存放第5类货物。

图1 货位编号———货位、货物特征的围道布尔矩阵图[B×F (B) ]  下载原图

图2 货位分区图  下载原图

假设某自动化立体仓库固定货架共有I列J层, 处于第i列第j层的货位坐标记为 (i, j) (其中i=1, 2, …, I;j=1, 2, …, J) , 距离出入库台最近的列记为第1列, 最底层记为第1层。假设各个货位的长度、高度相同, 货箱重量相同, 每个货位重心位置位于该货位中心, 并且忽略堆垛机的启动、制动时间以及存取货物操作时间, 则固定货架的货位分配优化问题可以描述为[14]:

式中:i、j为第i列第j层的货位坐标;iG、jG为货架重心位置坐标;t为堆垛机存取货物的时间;Gij为第i列j层货位上物货重量;G0为整个货架最大承重能力;l、h为每个货位的长度和高度;vi、vj为堆垛机的水平运行速度和垂直运行速度;fij为第i列j层货位上货物存取频率;tij为忽略堆垛机启动和制动的条件下, 将第i列j层货位上的货物运送到巷道口所用的时间;S为进行出入库操作的货物总数量。

在固定货架的货位分配优化模型中, 式 (1) 表示在水平方向货架重心尽可能靠近出入库台;式 (2) 遵循上轻下重的原则, 保障货架稳定性, 使货架重心位置最低;式 (3) 根据最短路线原则, 满足对存取效率的要求, 使堆垛机存取货物的时间最短, 即离巷道口的出入库台的距离最短;式 (7) 表示货架存储货物的总重量不能超过货架的最大承重能力。由此可见, 该优化问题是一个关于货架稳定性和出入库效率的组合多目标优化问题。

粒子群算法 (Particle Swarm Optimization, PSO) 作为一种新兴的进化算法, 近年来发展迅速, 在多目标优化、模式识别以及信号处理等领域得到了广泛应用。相对于遗传算法 (Genetic Algorithm, GA) 而言, 二者都是基于群体的迭代搜索, PSO算法没有GA算法的“交叉”和“变异”操作, 是通过个体之间的协作来搜寻最优解, 以其具有的运算容易、精度高以及收敛快等优点引起了学术界重视, 在解决实际问题中展示了其优越性[15,16]。PSO算法的数学模型描述如下[17]。

设粒子 (即入库货物通过初始化分配的货位) 所在的搜索空间为D维 (货位分配问题的搜索空间为粒子的求解空间) , 总粒子数为popsize。Xn= (xn1, xn2, …, xnd, …, xn D) 为第n个粒子的位置 (即第n个粒子的空间解) ;Pn= (pn1, pn2, …, pnd, …, pn D) 为第n个粒子的当前最优位置, 即第n个粒子的局部最优解, Pg为所有粒子到目前找到的最优位置, 即全局最优解;Vn= (vn1, vn2, …, vnd, …, vn D) 为第n个粒子的速度, 代表位置变化量, 如vknd表示从k-1次迭代到k次迭代时, 粒子n位置在d维空间的变化值。粒子在寻优过程中通过式 (8) 、式 (9) 更新粒子的速度vnkd+1和位置xnkd+1为:

式中:d为搜索空间维数, d=1, 2, …, D;粒子n=1, 2, …, popsize;ω为粒子的惯性权重, 用以实现对粒子飞行速度的有效控制与调整;r1、r2为均匀分布在 (0, 1) 之间的随机数, 用来保持群体的多样性;k为到目前为止粒子反复寻优的迭代次数;c1、c2为学习因子, 可调节粒子向自己的历史最优点以及群体内最优点靠近。

第d (1≤d≤D) 维的位置变化范围为[Xmin, Xmax], 速度变化范围为[Vmin, Vmax], 迭代中若位置和速度超过边界范围则取边界值。

在应用PSO算法进行优化问题的求解时, 全局分散性搜索和局部趋化性搜索之间存在着一定的矛盾, 而模拟退火算法 (Simulated Annealing, SA) 能够有效缓解这种矛盾。SA算法赋予搜索过程一种概率突跳的能力, 可有效避免搜索过程陷入局部极小解。同时这种突跳概率受到温度参数的控制, 进化早期时温度较高, 使得算法侧重于全局分散性搜索, 随着温度下降, 算法将侧重于优良区域的局部搜索。显然, 温度控制策略能自动调节算法搜索行为, 提高算法性能。本文将PSO算法和SA算法相结合对货位分配进行优化。

结合SA算法的混合粒子群算法 (Hybrid Particle Swarm Optimization, HPSO) 流程图如图3所示。由于在货位分配前先进行了货架分区, 所以每类货物入库都在各自区域内进行。

图3 HPSO算法流程图  下载原图

以分区A为例来具体说明HPSO算法的初始化、解码、适应度计算和粒子的更新等过程。

1) 初始化位置和速度。利用MATLAB软件初始化PSO算法中粒子的位置和速度, 取粒子位置和速度的变化范围分别是:Xmin=0, Xmax=1, Vmin=-Vmax=0.5。

初始化位置XA:

初始化速度VA为:

式中:popsize为种群总粒子数;QA为分区A的货位数;NA0为分区A内的初始存货数量;unifrnd为MATLAB软件中的均匀分布随机函数。

2) 解码。将A分区的货位按照编号升序排列, 一个粒子的解码过程为:NA为A分区内需要入库的货物数量, 取出种群中的一个粒子, 令NA个确定入库货物的货位记为1, 其余的空货位数记为0, 已有存货货位对应的值记为2, 从而得到一个解码后的粒子。

3) 计算各粒子的适应度函数值 (即目标值) , 初始化Pn和Pg, 计算Pn和Pg的适应度函数值。

固定货架的货位分配优化问题是一个多目标的优化问题, 文中通过分配权重的方法来对多目标进行整合得到适应度函数U为[18]:

式中:t为堆垛机存取货物的时间;tmin和tmax分别为所有t中的最小值和最大值;G为货架的重心, Gmin和Gmax分别为G中的最小值和最大值, 通过加权将货架重心iG、jG整合为重心G;ω1为衡量堆垛机存取效率与货架重心重要性权重, 由于两者重要性等同, 这里取ω1=0.5。

4) 确定初始温度。算法流程中, 初始温度T0对算法的优化性能的影响采用经验式 (11) [15]:

式中:Upg为初始种群中最佳粒子的目标值。

5) 计算当前温度下各Pn的适配值。PSO算法的速度更新公式中采用了群体的最优位置Pg。为避免算法陷入局部极小解, 这里从诸多Pn中选取一个位置, 记作Pg1, 代替更新公式中的Pg。在SA算法的机制中认为, Pn是比Pg位置差的特殊解, 从而可根据式 (12) 计算温度T时Pn相对Pg的突跳概率。将此突跳概率值作为Pn的适配值, 按式 (13) 计算用Pn代替Pg的概率。根据此替代概率, 采用轮盘赌策略[17]确定哪个Pn成为Pg1, 来替换速度更新公式中的Pg。

温度T时Pn相对Pg的突跳概率为[15]:

Pn代替Pg的替代概率为[15]:

式中:Upn为局部最优位置Pn的适应度函数;Upg为群体最优位置Pg的适应度函数;N为种群总粒子数。

6) 更新粒子的速度和位置。取初始惯性权重ωmax=0.9, 结束时惯性权重ωmin=0.4, Mmax为最大进化代数, m为当前的进化代数值, 随着迭代次数的增加, 粒子速度更新过程的惯性权重ω按照式 (14) 进行递减[19]:

取学习因子c1=c2=2, 根据式 (8) 、式 (9) 来更新粒子的速度和位置。

7) 判断结束条件, 对满足结束条件的结果输出Pg及其目标值, 否则进行退温操作, 转步骤5) , 重新进行迭代求解。

迭代过程中, 取退火速率α=0.99, 则k到k+1次迭代时的退温操作Tk、Tk+1按照式 (15) 进行[20]:

本文2.3节的实例中, 自动化立体仓库货架参数为:货位长度l=1.2m, 货位高度h=0.8m。堆垛机的水平运行速度vi=3m/s, 垂直运行速度vj=1m/s。分区A、H、C、K、E内货物的入库数量分别是21、37、43、16、33。入库前分区A、H、C、K、E内货架中分别存有货物的数量为20、60、80、50、40。在MATLAB软件中, 先随机产生一组货位进行入库, 假设迭代次数分别为100、200、200, 种群数分别为50、50、100, 采用GA算法、PSO算法以及HPSO算法分别对优化后分配的货位进行入库操作, 并将文中提出的HPSO算法与GA算法、PSO算法求得的入库时间和重心位置进行比较, 最终优化结果如表2所示。表2中, 平均优化率= (随机结果-优化算法结果) /随机结果。

1) 与随机结果相比, GA算法、PSO算法和文中提出的HPSO算法各自取得的入库时间都更短, 货架重心得到优化, 水平坐标更靠近出入库台, 竖直坐标也有所降低。而且HPSO算法, 相较于GA算法和PSO算法所得的立体仓库货位优化效果更好。

2) HPSO算法随着迭代次数的增加和种群数的增加, 货物的入库时间和货架重心在水平方向的优化效率都得到提高, 但货架重心在垂直方向的优化效率有所下降。

由此可知, 增加迭代次数和种群数目虽然可以提高入库的效率, 但货架的稳定性会有所降低, 所以在货架的稳定性得以保证的前提下, 可以通过适当增加迭代次数和种群数目来得到更好的优化效果。

表2 随机结果与GA算法、PSO算法和HPSO算法优化结果比较  下载原图

图4所示为种群数为100, 迭代次数为200时, GA、PSO和HPSO三种优化算法的收敛效果图。比较发现, GA算法的优化结果出现了波动, 收敛速度最慢;PSO算法优化时, 迭代的前期收敛速度较快, 但达到稳态的速度较慢;本文提出的HPSO算法能快速收敛达到稳态, 且最终稳态时的优化效果也最好。

图5所示为货位分配结果图, 图5a所示为随机产生的入库货位的货位分配结果图, 图5b、图5c和图5d为种群数为100, 迭代次数为200时, 应用GA算法、PSO算法和HPSO算法三种优化算法进行货位分配优化所得到一组入库货位的货位分配结果图。

图4 三种算法收敛效果图  下载原图

图5 货位分配结果图  下载原图

图5中分别表示A、H、C、K、E分区入库货位, ·表示存有货物的货位。图5中各图直接地反映采用上述四种方法进行货位分配的情况, 对比这些图可知, GA算法、PSO算法和HPSO算法分配的货位与随机分配的货位相比较, 货物分布更有规律, 货架重心偏低, 存货位置集中, 且偏向于出入库台, 使存取货物时间更短, 提高了出入库效率, HPSO算法相对于GA算法、PSO算法效果更明显。

合理分配货位, 进行高效的货位管理, 是提高自动化立体仓库出入库效率的基础。本文在总结货位分配原则的基础上, 针对立体仓库货位分配时的货架稳定性和出入库效率问题, 提出多色集合与PSO算法、SA算法相结合的货位分配决策模型。HPSO算法结合了多色集合的方便描绘复杂系统能力、PSO算法的快速收敛性和SA算法的较强搜索能力等三种优势, 能够实现货位分配整体优化。

分析对比在同一实例中HPSO算法与GA算法、PSO算法的优化结果表明, HPSO算法的收敛速度快、稳定性高, 避免结果陷入局部最优, 且缩小了搜索空间, 提高了算法效率, 验证了HPSO算法在解决自动化仓库货位分配优化问题中的有效性和优越性。