铝型材立体仓库货位分配优化

吴 炳，瞿 畅

（南通大学机械工程学院，江苏 南通 226019）

1 引言

近年来，随着铝加工工业的飞速发展，铝加工材料特别是长直杆件铝挤压型材对现代物流管理提出了新要求。适用于存储长直杆件的悬臂梁式立体仓库的出现，彻底改变了铝型材企业仓储的落后面貌。

立体仓库的工作效率主要受货位分配的影响[1]，为了提高效率，文献[2]提出以减少堆垛机运行时间以及单位载荷为目标的分配规则。文献[3]为解决立体仓库的货位分配与交叉存取问题，提出停留持续时间的共享存储原则，以此来减少堆垛机等待时间，提高仓库运行效率。依照分配原则而进行的优化算法不仅可以充分利用存储空间提高存储效率，而且能使货架受到良好的受力承载，保证其安全性能[4-5]。文献[6]提出的并列选择单亲遗传算法，对优化后货位对应的拣选效率及货架稳定性有明显的提高。考虑仓库与货物的特殊性来制定分配规则及优化算法，是货位分配首要解决的问题。针对铝型材尺寸长、重量大的特点，提出了适用于悬臂梁式货架仓库的货位分配策略，从提高入库效率，降低货架重心、保持货架平衡以提高仓库安全性能为出发点，构建悬臂梁式立体仓库入库货位优化的数学模型。结合GA 算法与SA 算法的优点，设计了SAGA 算法来求解模型，寻找合理的分配货位。

2 仓库布局

自动化立体仓库的布局是影响仓储调度效率的重要因素[7]，仓库合理的布局不仅满足仓储需要，方便操作人员使用，而且也直接影响着货物的货位分配。根据某铝型材企业库房的实际情况。构建的悬臂梁式立体仓库平面示意图，如图1 所示。堆垛机从I/O 端口处出发，沿X 方向是仓库的排方向，沿Y 方向是仓库的列方向，沿Z 方向是仓库的层方向。堆垛机运行轨迹在图中已标出，在I/O 端口处取得货物，分别沿X 方向、Y 方向和Z 方向运行到货物对应的位置，完成作业后回到I/O 进行下一次任务循环。

图1 铝型材立体仓库示意图Fig.1 The Diagram of Aluminum Three-Dimensional Warehouse

3 多目标优化模型建立

根据铝型材立体仓库的特点，以提高货架安全性能为主要目标，依据入库效率和货架稳定性原则确立优化目标，建立合理的多目标货位优化数学模型。

3.1 模型假设

为了便于模型的建立，现对仓库边界提出以下假设：（1）假设仓库出入库端口为唯一端口，且堆垛机每次只取一次货物；（2）假设货架货格空间为长方体，货物与货格尺寸相匹配；（3）堆垛机匀速运行，且存取动作耗时不计；（4）存放有货物的货格不再存放其他货物。

3.2 模型建立

假设铝型材立体仓库沿X 方向共有a 排，沿Y 方向共有b列，沿Z 方向共有c 层，其中离地面最近的一层为第一层，离出入端口最近的为第一排、第一列，（i，j，k）为货物在仓库中的位置，即货物在仓库i 排j 列k 层。为方便问题的描述，对数学模型中的符

号作如下定义：

3.2.1 效率分析

悬臂梁式立体仓库的入库效率关系到仓库的仓储性能，在不改变现有堆垛机性能的基础上，提高仓库出入库效率的关键是减少堆垛机的行程。若货物存放于货位（i，j，k），则堆垛机在X 方向运行路程为在Y 方向运行路程为jb，在Z 方向运行路程为（k-1）h，由此可得到堆垛机摆放该货物的运行时间。累计所有货物的运行时间f1，建立效率数学模型如下：

3.2.2 稳定分析

悬臂梁式立体货架存储的多为尺寸长、重量大的货物，在此种类型仓库中进行货位分配需要考虑其稳定性。悬臂式仓库货架的稳定与否取决于货架重心高低。将较重的货物放入低层、较轻货物放入高层，使得货架的整体重心最低。参照效率分析，累计货物重心f2，建立货架稳定数学模型如下：

3.2.3 平衡分析

考虑到货物重载荷及悬臂梁式货架的结构特点，需着重考虑货架的平衡，以确保仓库有足够的安全系数。因此，在货位分配中，应最大限度地将质量相近的货物放入悬臂式货架的两侧，使得整个仓库工作货架的两侧悬臂有最小的质量差。累计货架两侧的质量差f3，建立货架平衡模型如下：

3.3 权重系数的分配

上述针对货位分配优化的数学模型属于多目标优化问题，求解较为复杂。为方便求解，采用加权法对三个优化目标函数分别赋以权重 α、β 和 γ，并使得 α+β+γ=1。

权重系数的选取受主观因素影响，为使仓库获得最大安全系数[8]，目标函数权重系数应满足α＜β＜γ，为使定性因素定量化，采用层次分析法（AHP）来确立权重系数，AHP 的使用流程与步骤，如图2 所示。应用AHP 方法时，规定uij表示ui对uj的相对重要性数值（ui和uj表示各权重），其中i，j∈｛1，2，…，N｝，uij的取值通常用（1～9）标度方法[9]，如表1 所示。

图2 AHP 的步骤流程图Fig.2 Step Flow Diagram of AHP

表1 判断矩阵标度及其定义Tab.1 Judgement Matrix Scale and Its Definition

根据上述定义及标度，构造权重系数α、β 以及γ 的取值判断矩阵P，如下所示：

应用方根法计算权重系数：

（1）计算判断矩阵P 的每一行元素的乘积M1，得到：M=［1/35 5/6 42］T

检验权重系数合理性：

（2）引入一致性指标CI=（λmax-N）/N-1。

（3）判断矩阵随机一致性比率CR=CI/RI，其中，RI—判断矩阵随机一致性指标，3 阶矩阵取值为0.58[10]。

这里CR=CI/RI=-1.25 根据参考文献[10]，当CR＜0.1 时，判断矩阵满足一致性要求，权重系数合理，因此，权重系数α、β 与γ 依次确立为0.07，0.2，0.73。同时，对目标函数进行归一化处理，以消除目标函数的量纲，可得优化函数：

4 SAGA 货位分配算法

SAGA 是结合传统遗传算法（GA）与模拟退火算法（SA）的一种混合算法，其能够很好的跳出局部最优解，在解空间中搜索到较好的解集。SAGA 算法实现流程，如图3 所示。

图3 SAGA 算法流程示意图Fig.3 The Algorithm Flow Chart of SAGA

SAGA 算法具体实现步骤如下：

（1）对需要入库的货位随机分配货位地址，形成初始种群P。对地址采用整数排列方式进行编码，一条染色体代表一个货物的分配地址，染色体中的三个整数分别代表三个基因，表示该货物在仓库位置中的排、列、层。

（2）适应度函数用来评价每个个体的优劣型，由于优化目标是越低越好，因此可以直接将优化函数作为评价函数，将货物的质量及对应货位坐标代入到式（6）中，计算数值即为适应度值。

（3）选择运算采用轮盘赌算子，计算每个货物的个体适应度值，比较个体在总体中适应度值的占比，占比越大其在下一代被选中的概率越大。

（4）交叉和变异是模拟退火遗传算法中产生新个体的核心步骤，交叉从群体中按较大值的概率选择两个货物个体，交换两个个体染色体中某个或某些基因，即交换货物的某些坐标数值以得到新的货位坐标值。变异是将某个体染色体编码串中不同基因位进行交换，即交换某个货物的三维坐标数值以变异得到新的货位。交叉变异后，保留较好的个体，得到新种群P1。

（5）为保证搜索能跳出局部空间，对得到的新种群进行“退火”处理。设置初始温度T0，温降与迭代次数相关为Ti=T0/1+i。在种群P1解空间周围随机生成新的种群P2，计算P2的增量d=F（P）2-F（P）1，若d＜0，则接受种群P2为当前解；否则按Metropolis原则接受种群，即计算P2的接受概率exp（d/T）i，随机生成（0，1）区间上的均匀分布随机数rand，若exp（d/T）i＆gt;rand，则接受种群P2为当前解，否则保留P1为当前解。

（6）判断是否满足终止条件，满足则接受当前解为最优解并解码，得到入库货物的分配货位；否则循环以上操作。

5 仿真实例分析

某铝型材企业的悬臂梁式立体仓库货架共12 排6 列10层，巷道宽L 为1.2m，仓库基本参数信息，如表2 所示。

表2 仓库基本参数Tab.2 The Basic Parameters of Warehouse

现有14 种质量不同的铝型材需要进行入库处理，货物的信息，如表3 所示。算法参数的选取会影响优化结果的优劣，因此在进行仿真时需要对参数进行测验，考虑到仿真结果的客观性，经过多次对比，选取算法种群规模NPop=40，迭代次数G=150，遗传交叉概率Pc=0.8，变异概率Pm=0.1，初始温度T0=500。运行SAGA算法进行货位分配，优化前后的目标函数值，如表4 所示。结果表明，相比于初始位置，经过SAGA 算法优化后，堆垛机运行效率提高11.98%，货架重心降低59.93%，仓库货架的平衡性能提高了72.57%。三维立体仿真效果，如图4 所示。

表3 入库货物质量表Tab.3 The Weight List of Goods

表4 优化运行结果Tab.4 The Results of Optimization

图4 货位优化前后对比图Fig.4 The Location Comparison Diagram Before and After Optimization

针对这里的多目标函数优化问题，SAGA 算法与传统的GA和SA 算法求解过程对比，如图5 所示。可以看出，SAGA 迭代至75 代已经趋向于收敛，而GA 需要迭代110 次才能达到相似收敛值，虽然SA 仅仅迭代50 次已能收敛，但其收敛值也大大高于其他两种算法。

图5 SAGA 与GA、SA 收敛对比曲线图Fig.5 Convergence Curves of SAGA、GA、SA

6 结论

旨在解决存储大尺寸、重载货物的悬臂梁式货架仓库的入库货位分配问题。以货物入库效率，货架稳定性和仓库安全性为优化目标建立数学模型，将定性分析转化为定量分析，并设计了SAGA算法来求解此问题。设计的SAGA 算法相较于传统GA 算法拥有更快的收敛速度，比传统SA 算法拥有更好的收敛性能。仿真实例表明，在尺寸长、重量大的铝型材存储行业，应用SAGA 算法来进行货位分配，不仅能够提高工作效率，更能保障仓库的安全性能。