刘　权，杨鹏辉，刘润茜，杨悦月

(1.安徽财经大学统计与应用数学学院,安徽 蚌埠 233000；2.安徽财经大学金融学院；安徽 蚌埠 233000)



基于遗传算法的仓库布局优化模型及最优角度的确定

刘权1，杨鹏辉1，刘润茜1，杨悦月2

(1.安徽财经大学统计与应用数学学院,安徽 蚌埠 233000；2.安徽财经大学金融学院；安徽 蚌埠 233000)

摘要：目的优化物流仓库布局和调整最优的布局角度来提高货品的运输效率、空间利用率并对比分析优化前后的布局效果。方法选择传统的Fishbone布局方法，根据仓库布局的两大原则，得到优化目标1：所有货物组合运货时间之和最小；优化目标2：所有货品质量和所处层数的乘积之和最小。确定约束条件，建立多目标优化模型。采用遗传算法对模型进行求解，选择权重w1=0.6、w2=0.4，将多目标问题改造为单目标问题，并将目标函数和约束条件进行编码处理，进行矩阵式编码，使用MATLAB对模型进行求解，得到优化后的布局分布。之后确定Fishbone布局的最佳角度，假设最优角度α，得到运输过程中横向、纵向和斜方向的运输总路程，再对α为参数的方程进行偏微分求解，得到最优角度α。结果与优化前的布局相比，优化后的布局在运输总路程上从65 670降低为55 643，总的空间利用率由89%提升至92%。求解微分方程得到最优角度，相比角度调整前的布局，调整后的布局总移动距离由65 670降低到57 843，仓库运作效率由67%提升至81%。结论优化后的仓库布局和角度的调整提高了空间利用率，并缩短了工作时间，提高了工作效率，经过优化后的仓库布局其物流效率有了很大提高,说明了改进后的Fishbone布局在仓库布局设计中具有极高的可行性和实用性。

关键词：遗传算法；多目标优化；MATLAB；角度建模

近年来国内仓储业发展迅猛，随着网络购物、网上支付、移动电子商户的数量急剧增加，越来越多的企业开始大举进军仓储业。现在的仓储开始向货品存取作业小批量、多数量、多种类、高时效性等方向发展，需要进行存取作业的货品种类、数量不断增加，货品的流动频率也在迅速提高。而自动化立体仓库作为物流产业的主要环节之一，日益成为仓储企业优先发展的对象，仓储企业追求利益最大化的需要使得货位分布布局的研究成为热点。

仓库布局是指在一定区域或库区内，对仓库的数量、规模、地理位置和仓库设施道路等各要素进行科学规划和整体设计。本文通过仓库布局优化模型和最佳角度的确定对仓库整体布局及货物分配这一问题进行研究，并考虑模型的复杂性给出模拟遗传算法，对问题进行求解。

1问题分析和基础假设

目前的仓库布局方法主要有以下3种：普通布局方法、Flying-V布局方法和Fishbone布局方法。根据美国的学者Gue和Meller对Fishbone布局的研究，这种仓库布局的进货口和出货口合并一个出入库口，是一种拥有两条主拣货通道和无数条局部拣货巷道的货架布局形式。相对于传统的仓库布局，这种仓库布局可有效地缩短拣货距离，减少仓库的作业时间。同时，与普通的仓库布局相比，Fishbone布局的仓库作业移动距离可减少约20%，见图1。

图1　Fishbone布局图

本文基于Fishbone仓库布局对仓库货位分配优化及货物分配问题进行了一般情况下的研究。为了方便说明问题，对模型进行如下假设：①仓库规模适合实行四分货区，采用单端出入库的方式；②入库货品的数量不超过仓库的最大存放量，且其质量、存取频率及所占货位个数信息已知；③仓库中相邻两排货架之间巷道的宽度等于单排货架的宽度；④货品的体积肯定不超过货格的体积，并且同一种类的货品可以存放于不同的货格，但是同一货格内不能存放不同种类的货品；⑤在运行过程中自动小车的速度保持不变，不受所载的货品重量的影响，不考虑小车的制动和起动过程；⑥搬运过程中自动小车一次只搬运一个货格所能存放的货物量；⑦货位的选择对商品质量不会造成影响；⑧各种商品具有不同的包装形态、包装质地和体积重量，但每个货位的货区装卸设备条件与仓储商品的操作方法都相适应；⑨自动小车的行驶时间就是其存取货物的作业时间。

2仓库布局优化模型

2.1模型的准备

仓库布局优化问题原则[1]：

1)方便吞吐发运的原则

货位的选择，应符合方便吞吐的原则，要方便商品的进出库，尽可能缩短收发货作业时间。货物吞吐快慢，仓储商品的流转快慢不一，有着不同的活动规律。对于存取频率高的商品，要选择有利于车辆进出库方便的货位；存取频率低的商品，货位不应靠近库门。

2)保持货架稳定性的原则

货位的选择，还要保持货架稳定性的原则，尽量降低一个货架所承载货物的重心。在货位负荷量和高度基本固定情况下，对于质量小的商品，应安排在位置高的货位；对于质量大的商品，应安排在位置低的货位。

2.2模型参数

某仓储企业有一立体仓库，仓库内部货架的布局方式如图1所示。整个仓库共有16排货架224个货位，平均分为4个货区(即k=4).每个货区有4排货架(即n=4)。货架的具体参数为：货架的层数p=4；货架的列数q=6；货架上货格的长度(即宽度)l=1 m；货架上货格的高度h=0.8 m；自动小车在水平方向上的速度v1=2 m·s-1；自动小车在垂直方向上的速度v2=1 m·s-1。

2.3模型的建立

一个仓库共有4 n排货架，从左下角顺时针平均分别为1区、2区、3区、4区。每个区有n排货架，货架在第几区用k(1,2,3,4)表示，货架的排数用x(x=1,2,3…)，货架的层数用y(1,2,3…)表示,货架的列数用z(z=1,2,…b)表示。则一个货位的位置可以表示为k、x、y、z的函数，即由确定下来。设f(k,x,y,z)表示货品的存取频率，m(k,x,y,z)表示货品的质量。自动小车在水平方向的移动速度为v1,在垂直方向的移动速度是v2。

基于Fishbone仓库布局的货架排数和列数布局情况如下：

第1排：共16列第2排：共14列第3排：共13列

第4排：共11列第5排：共10列第6排：共8列

第7排：共7列第8排：共5列第9排：共4列

第10排：共2列第11排：共1列

可以看出货架的排数和列数有如下规律：

式中：bx——不同排数的货架列数；

b——当x=1时的货架列数；

x——货架的排数。

根据仓库布局优化原则，建立模型：根据原则1，存取频率高的货物放在离仓库口近的地方，运货所需时间越短；存取频率低的货物放在离仓库口远的地方，运货所需时间越长。目标函数为所有货物组合运货时间之和最小[2]。

T(k,x,y,z)=t1+t2+t3

L1为自动小车从仓库口到货品所在货架的移动距离；L2为自动小车货架到货品所在货列的移动距离，L3为货列到货品所在货层的移动距离。

根据原则2，质量大的货品放在货架层数低的位置，质量大的货品放在货架层数高的位置，降低整个货架的重心。目标函数是所有货品质量和所处层数的乘积之和最小。

针对在Fishbone仓库布局中，根据原则1和原则2，减少总路程并增加空间利用率，将货品的安排进行优化调整，从而建立针对Fishbone仓库布局的优化模型。

2.4模型的求解

2.4.1遗传算法的设计

本文的货位优化问题属于多目标优化问题，所建立的货位优化模型需要同时满足2个约束条件，优化的过程既要考虑货架的稳定性同时又要使得立体库的出入库效率最高，所以货位优化是一个多目标优化问题，需要采用多目标决策来解决。

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

选择权重和法将多目标转化为1个目标函数，选择W1与W2为所赋权重。则目标函数为[5]：

H(k,x,y,z)=w1f1(k,x,y,z)+w2f2(k,x,y,z)

综上所述，得到目标函数：

将多目标改造为单目标优化问题，再通过遗传算法进行优化求解[6]。

首先，将目标函数和约束条件进行编码处理，根据所建立的数学模型，采用矩阵式编码。

Step1:控制参数

N为个体数目，Pc为交叉概率，Pm变异概率，g为当前进化代数，MAXGEN最大遗传代数。

Step2：生成初始种群，并对初始种群进行选择、交叉、变异操作。

Step3：对进行相互交叉后形成的子个体与父个体通过适应度比较，得到适应度Zi和Zi，若子代适应度大于父代适应度，则无条件将子代进入下一代，若子代适应度小于父代适应度，求出概率Pij，判断概率是否符合条件，符合条件进入下一步，不符合条件将对整个群体进行循环前两步操作，直至产生符合条件的下一代族群。

Step4：停止命令，若g=MAXGEN，则停止算法，反之，令g=g+1,Tt=Ttr，若g以10倍增加时，调整变异概率，Pm循环第三步。

2.4.2货位优化模型的求解与结果分析[7]

将表1所给的数据导入后，进行处理。所给的货区k取值为1、2、3、4；

表1　入库货品的参数

编号质量频率(%)货位(个)编号质量频率(%)货位(个)21225331219322187532153423258333197524365434101252514613520642634443624832723953718442835623821114291745392375302662402993

输入质量序列mkxyz;

输入货品的存取频率序列fkxyz;

排数n=16；层数a=4；l列数b=6；根据权重表选择权重w1=0.6，w2=0.4。一般情况下，选择N为200，Pc交叉概率=0.4，Pm变异概率=0.1。

根据所建立的遗传算法，通过MATLAB软件进行编程求出最优解。得到结果。

货位优化前的布局不合理，仓库综合性能较差。其仓库布局如下：

图2　初始仓库布局

MATLAB结果输出见图3。

图3　初始数据结果输出

经过货位优化后，仓库布局得到改善，其布局情况如下：

图4　优化后仓库布局

MATLAB结果输出见图5。

图5　优化后结果输出

在对输出结果进行统计分析后，可以得到结果见表2。

表2　两种布局结果比较

可以得到优化后的货位在满足了方便吞吐发运的原则和保持货架稳定性的原则，经过遗传算法，得到的结果符合题目中的要求。以选取的15个点为样本，估计整个总体的优化效果，虽然无法达到最优解，但由于收敛速度快，可以得到符合条件的近似解，所以，遗传算法对货位优化求解具有较大的应用价值。

3最优角度模型

3.1研究思路

假设仓库只有一个库门，每次存取货后都必须回到库门处等待下一次仓库作业，因此库门就是仓库的存取点，简称O点。底部的横向主通道固定不变，另外两条主通道以O点位圆心在左右两半仓库中旋转。将仓库分为A、B、C和D 4个区域[2]。如图所示:

图6　区域分布图

根据图1和图6所示，A、B、C和D 4个区域的路径如下：存取A区和D区货物时，需要从O点出发经过α角度的拣货通道到达货物所在排，然后经过横向通道到达货物所在具体位置。我们可知存取B区和C区的货物时，需要从O点出发，经过α角度的拣货通道，然后经过纵向通道到达拣货点作业。由于仓库是左右对称的，所以只需要考虑一半。

3.2模型的建立[3]

假设总路程为S，需要总路程最小。对于任意一点N(k,x,y,z),假设N(k,x,y,z)在A区域和B区域对应的移动距离为DA(k,x,y,z)和DB(k,x,y,z),则计算步骤如下：

若N(k,x,y,z)在A区域，到N进行存取货物，必须经过α角度斜线通道，再经过横向通道。所以运行的总路程可以得到：

同样，当N(k,x,y,z)在B区域，到N进行存取货物，必须经过α角度通道，再经过纵向通道。在α角度的斜线通道上经过，所以总路程为：

同理，C区域和D区域与A区域、B区域相同。

3.3模型的求解[4]

可令:

所有货位存取货物总路程：

需要求出最佳的α使得所有货位存取货物总路程Y最小，对∂进行求导，极值对应的导数为0，进行化简后，可以得到：

从而可以解得：

sinα=0.746

3.4结果分析

当α=arcsin(0.746)时，路程最短，其为最佳角度。这个角度可以使得存取所有货物的路程总和最小，使得仓库的运作效率最高。

4结论

本文在仓库的布局、路径的选择、货物的安排分配等方面对提高仓库工作效率和空间利用率进行了优化研究。基于仓库布局的基本原则，针对2个优化目标，一是保障货架稳定性，同时使得立体库中货品的配送时间最短，二是实现快速出入库，提高出入库效率；根据优化目标和约束建立了立体仓库货位优化的数学模型。建立了运输距离最短、空间利用率最高的多目标函数的数学优化模型和确定仓库布局最佳角度模型，利用遗传算法并使用了MATLAB对模型进行求解。结果表明，优化后的仓库布局提高了空间利用率、缩短了工作时间、提高了工作效率。经过优化后的仓库布局其物流效率有了很大提高，说明改进后的Fishbone布局在仓库布局设计中具有极高的可行性和实用性。

参考文献：

[1]刘清雪.遗传模拟退火算法在系统发育树构建中的应用研究[D].长春：东北师范大学，2007.

[2]刘艳秋,张义华,焦妮.基于Fishbone的仓储货位分配优化[J].物流科技，2014，(12):66-70.

[3]蒋美仙,冯定忠,赵晏林,等.基于改进Fishbone的物流仓库布局优化[J].系统工程理论与实践，2013，(11):2920-2929.

[4]王健.基于遗传算法的仓储货位优化研究[D].西安：西安建筑科技大学，2009.

[5]卫三军.基于遗传退火算法的AS/RS货位分配问题求解[J].制造业自动化，2011(03):36-37.

[6]刘启.基于遗传模拟退火算法的配电网重构研究[D].西安:西安理工大学，2011.

[7]韩彩云.基于遗传算法的自动化立体仓库的货位优化研究[D].山西:太原科技大学，2009.

[责任编辑：刘守义英文编辑：刘彦哲]

Optimization Model of Warehouse Layout and Determination of Optimal Angle Based on Genetic Algorithm

LIU Quan1，YANG Peng-hui1,LIU Run-qian1,YANG Yue-yue2

(1.School of Statistics and Appl.Math，Anhui University of Finance and Economics，Bengbu 233000，China;2.School of Finance,Anhui University of Finance and Economics Bengbu 233030,China))

Abstract:ObjectiveTo optimize logistic warehouse layout and adjust the optimal layout angle to improve transport efficiency and space utilization rate of goods;and to comparatively analyze the layout effects before and after optimization.MethodsAccording to the two principles of warehouse layout,the traditional Fishbone layout method was chosen,obtaining optimization objectives:1)the minimum sum of delivery time of all the goods;2)the minimum sum of the product of goods quality and the number of layers.Constraint conditions were determined to build multiple target optimized model.The genetic algorithm was applied to solve the model.After choosing the weights ω1=0.6 and ω2=0.4,the multi-objective function was transformed into a single objective function.Then,genetic algorithm was used to solve the model,encoding processing of objective function and constraint conditions.MATLAB was used to solve the model,obtaining optimized layout distribution.Then,the best angel of the Fishbone layout was determined.By setting hypothesis optimal angle α,the total transportation distance of the horizontal,vertical and oblique direction in the transportation process was obtained,and the solution to the equation for partial differential with the parameters α,was found,getting the best angle α.ResultsCompared with layout before optimization,the optimized layout decreased from 65,670 to 55,643 in the total transportation,the overall space utilization increased from 89% to 92%.Differential equations were solved,getting the best angle α=0.746.Compared with the layout before the adjustment of angle,the adjusted mobile distance of the overall layout decreased from 65,670 to 57,843,and the efficiency of the warehouse operation increased from 67% to 81%.ConclusionOptimized warehouse layout and angle adjustment improved the space utilization and work efficiency,and shortened the working time.Optimized warehouse layout greatly improved the logistics efficiency.The results show that the improved Fishbone layout has high feasibility and practicability in the warehouse layout design.

Key words:genetic algorithm;multi-objective optimization;MATLAB;modeling

基金项目：国家自然科学项目(11301001)；国家级大学生创新项目(201510378050)

作者简介：刘权(1994-)，男，安徽安庆人，安徽财经大学统计与应用数学学院在读学生，研究方向：经济数学。通讯作者：杨鹏辉(1981-)，女，安徽淮南人，安徽财经大学统计与应用数学学院讲师，硕士，研究方向：图论与网络分析建模。

中图分类号：TP 278

文献标识码：A

DOI：10.3969/j.issn.1673-1492.2016.03.006

来稿日期：2015-12-24