基于遗传算法的自动化立体仓库储位优化研究

周杰

(研林自动化科技有限公司,上海 201822)

0 引言

自动化立体仓库是现代企业智能化物流的重要环节。该系统由现代物流技术、计算机应用技术、智能数据技术、电气自动化智能控制等技术相结合[1]。依据程序算法控制指令,实现货物的自动高效存取,已经成为重要研究方向,特别是自动化立体仓库中货物储位分配策略方面问题更需要深入研究。货物储位分配问题直接影响立体仓库系统的性能和运行效率。货物储位分配优化策略是依据货物、货架和客户存取需求,保证立体仓库内有限存储空间更合理分配,从而提高存储效率[2]。

结合立体仓库的构造模型,货物储位分配策略的优化主要包括:以优化仓库存储效率为目标建模,良好的货物储位分配策略可以提高货物周转率,方便库存盘点和移库。储位分配策略主要包括出入库效率、保证货架的稳定性和货物周转率。同时,通过遗传算法求解多目标数学模型,最终得到优化的货物分配方法。

1 自动化立体仓库

1.1 立体仓库的组成结构

自动化立体仓库主要包括立体货架、出入库托盘输送系统、有轨巷道堆垛机、钢结构平台、调节平台、货物扫码系统、电线电缆桥架配电柜、电气智能自动控制系统、工业通信系统和计算机智能信息管理系统等。典型的自动化立体仓库结构示意图如图1所示[3]。

图1 典型的自动化立体仓库结构图

1.2 立体仓库货物储位分配原则与策略

自动化立体仓库定义货架位置坐标为x排y列z层。即该立体仓库一共有a排b列c层。图2为实际货物位置与数学坐标对照示意图。虚线的交点对应着每一个货物位置的几何质心。

图2 实际货物位置与空间坐标对照示意图

自动化立体仓库货物储位分配考虑的主要因素是货物进出库的效率、货架的稳定性和货物周转率。在自动化仓储管理中,通常情况下,货物的分配应遵循以下几个原则[4-5]。

1)货物先进先出的原则。为避免长时间存放有实效性货物(如:食品、药品等),需要考虑仓库中的货物在出库操作中具有较高的优先级。2)货架稳定原则。货物轻上重下可使货架稳定。分散存放,使货架均匀受力,防止货架变形。其目的是提高访问效率和降低运营和维保成本,这可以通过提高生产率和减少不必要的移动性来实现。3)就近原则(提高周转率)。选择最近巷道减少堆垛机平均移动距离。搜寻最靠近储存巷道和最短存储货物位置的路径,从而缩短装载时间,提高堆垛效率。

2 自动化立体仓库储位优化模型建立

2.1 货物储位优化数学模型构建

在保证符合实际操作原理的基础上,为方便起见,将实际问题抽象成数学问题。需对数学模型的建立进行以下假设[6]:1)为便于实际操作和实例的分析转化,每条巷道内设置一架堆垛机;2)货物用货箱存放,货物箱与货箱外观尺寸成正比;3)每个货位只能存放一个货物,不允许货物混放。所以货物储位分配优化问题要从多方面考虑,既要权衡货物的周转率和关联性,又要使货物的摆放尽可能保证最低质心。这些因素是相互制约的,要想同时得到满足,就必须按多目标问题来解决。

2.2 仓库模型建立与求解

1)提高出入库效率目标函数

出入库效率的关键是减少货物出入库的时间,受堆垛机运行速度和货物运送行程的限制,不可能在短时间内提高堆垛机的移动速度。因此缩短出入库之间的距离是提高效率的关键。数学模型表示为

(1)

式中:xi,yi,zi是仓库中货物储位的空间坐标;sx是堆垛机横向速度;sy是纵向移动速度;sz是垂直移动速度;lc是货架单元的长度;ls是货架之间的距离间隔;Ti是存取i个货物的周转率。

2)货架稳定性目标函数

货架的稳定性取决于货物质心的高度,将重物放在底部,货架质心与地面之间的距离最近,可以提高货架的整体稳定性。所以,该数学模型表示为

(2)

式中:Wabci是第i种货物的质量;Mxyzi是货物i在储位的总数量;ls是货架之间的距离间隔。

3)“周转率靠近出入口存放原则”目标函数

要求堆垛机在出入库时有更高的搬运效率,货叉的移动距离对堆垛机搬运移动货物时有直接影响。所以,频繁进出的货物,应该将其货物位置布置在靠近巷道进口处。物品的周转率定义为某时间段货物出入库的数量与该货品总量的比值。数学模型表示为

(3)

式中:Ti是存取i种货物的周转率;Nabci是货物出入库的总数量;Txyzi是堆垛机从巷道进口处到货物储位所需要的运行时间。

3 基于遗传算法模型求解

遗传算法是一种通过实数编码、种群初始化、适应度函数评价、回放式随机选择、单点交叉、均匀变异等操作,有规则地实现随机搜索方法。像自然法则一样,该算法是一种仿生物进化过程的优化算法[7]。遗传算法鲁棒性强,收敛速度快。遗传算法工作流程如图3所示。

图3 遗传算法流程图

1)浮点数编码

设计遗传算法首先要进行种群编码。采用浮点数编码方式,该方法具有较高的精度和较好的局部搜索能力,有利于处理复杂的决策变量并且提高找到最优解的概率。与二进制编码不同,浮点数编码无需解码。例如:6(5,3,2)代表的意义就是6号货物存放在5排、3列、2层。

2)种群初始化

编码完成后,需要初始化种群,这也是求解前的准备工作。在种群初始化过程中,根据货物位置数量定义货物的类型。即使同一类货物放在不同的货物地点,也应视为不同的货物。然后确定种群规模和种群中的个体数即决策变量。种群规模的大小可以在100～200之间随机设置。种群越大可选择优化解越多。

3)适应度函数

初始种群确定后,需要计算个体适应度值。个体适应度值的大小可以通过目标函数来计算。将设定基本参数和优化前后的货物货位坐标引入到仿真软件中。

4)比例选择操作

比例选择操作是从当前群体中选择或复制比较优良的个体并遗传至下—代群体中。比例选择操作也是一种随机选择[8]。设群体大小为P,个体i的适应度为Fi,则个体i被选中的概率pis为

(4)

由式(4)可见,适应度越高个体被选中的概率也越大,反之亦然。

5)单点交叉操作

首先在0.4～0.99之间随机确定交叉概率。从比例中选出的优秀个体进行交叉配对。通过单点交叉选择配对,将种群即(染色体)通过单点交叉选择配对,再随机选择的位置点分割群体(染色体),并交换右侧部份,从而获得两条不同的染色体。与其他交叉口相比单点交叉的混合速度较慢。该方法增加了种群的交叉粒度,降低了种群被破坏的概率。

6)均匀变异操作

在0.000 1～0.1之间随机确定变异概率。均匀变异是指单个编码串中的每个基因位点是变异点。从一对基因值范围内取一个具有突变概率的基因值来替换原始基因值。均匀变异操作中搜索点在整个搜索空间中可以自由移动,增加了种群多样性。变异点新基因值由式(5)表示为

(5)

7)遗传算法终止条件

通过遗传操作次数,算法的终止数达到设定的迭代数,让最小和平均目标函数值逐渐接近或趋于稳定。

4 遗传算法货物位置分配仿真及分析

4.1 系统参数

自动化立体仓库系统由模拟立体仓库及储运设备组成。立体仓库共设6层×10行×10列立体货架,相关参数设置如表1所示。

4.2 遗传算法参数选取

遗传算法的参数设置会影响最终结果。因此,需要在仿真运算之前检查所有参数设置。初始化种群规模设置200,最高进化迭代设置3 000,交叉概率设置0.75,变异概率设置0.06。遗传算法使个体种群(染色体)多样化,剔除不适合的个体,保留具有更强的适应性个体。初始化迭代后,目标函数的值持续下降,这表明该算法能够持续有效地找到可行解空间。从2 000次迭代增加到2 500次迭代。随着迭代次数的增加,目标函数的收敛速度也加快。经过2 500次迭代后,多目标函数优化越来越稳定。利用MATLAB仿真实验优化基本仿真参数和货物储位坐标,加速出入库和保障货架稳定性。最优和平均适应度函数值迭代趋势图如图4所示。

图4 适应度函数迭代趋势图

遗传算法容易出现局部最优解,可以在短时间内获得比较满意的近似最优解,这大大提高了货物储位优化的计算效率,也提高了存储分配布局策略的有效性。

4.3 实验相关数据

为了使模型更理想化,设置堆垛机加减速时间和货叉伸缩量消耗的时间被忽略。货位编号如表2所示。

表2 货物信息及仿真结果

4.4 仿真优化结果分析

通过MATLAB三维仿真效果图显示优化前的自动化立体仓库货物位置分配布局比较凌乱,布局不合理,仓库储位分配策略综合性能较差。图5显示仓库中货物位置初始化分配布局。

优化后的储位布局如图6所示。在提高仓储效率的基础上,优化的仓储空间也使货架质心降低,提高货架的稳定性。通过优化后,货物位置分配集中在仓库出入库口,货物集中在仓库底部,总体布局合理,货物的摆放更加规范。

图6 货物位置优化后储位分配状态显示

从优化前后目标函数值对比(表3)可以看出,优化前后3个目标函数的变化分别下降了9.82%、16.53%和13.48%,整体下降率为11.89%,提高了出入库效率、货架稳定性和货物周转率。可以看出,在货物储位分配优化的具体应用中,由于自动化立体仓库规模较大,可能会有更多的货物需要处理。如果采用传统的求解方法求解该问题,会增加一系列的计算时间,无法应用于实际问题中。

表3 优化前后目标函数值对比

表4和表5显示堆垛机和货架利用率优化前后数据对比分析。可以看出通过遗传优化算法后,自动化立体仓库的工作效率得到很大提升。

表4 堆垛机利用率对比 单位:%

表5 货架利用率对比 单位:%

5 结语

通过货物储位分配的原则和策略,建立了合理的货物位置分配数学模型。在此基础上,设计3个目标函数,即货物的出入库效率、货架的稳定性、货物周转率。该数学模型验证货物储位分配优化,提高自动化立体仓库作业效率,方便管理,增强稳定性。基于遗传算法能够得到多目标函数的最优解,该算法清晰且易于实现,在短时间内可以得到一个全局最优解。通过此案例分析优化后的目标函数值比优化前有所降低,达到了预期效果。也证明遗传算法对解决提高自动化立体仓库堆垛效率和性能是切实可行的。