基于嵌套分区算法的立体仓库货位分配优化
发布时间：2014-10-04 17:30
摘要：根据小型立体化仓库运营特点，基于顺序单目标优化思想，提出一种新的仓库货位分配策略。将考虑存储能耗、货架稳定性、运行效率的多目标仓库货位优化问题，转化为单目标优化，建立了仓库货位优化数学模型。根据数学模型特点，采用嵌套分区算法进行优化求解。通过算例分析证明该分配策略与优化方法，可有效处理多目标仓库库位优化问题，优化效果显著。
关键词：货位优化；嵌套分区；货位分配；仓储能耗
1引言
随着我国经济的快速发展，自动化立体仓库在国内已得到了广泛的应用。它不仅是现代物流系统中重要的环节，也是现代制造业广泛采用与自动化生产线配套的的主要仓储形式。在节省占地面积、减轻劳动强度、提高物流效率、降低储运损耗、衔接生产需求、合理利用资源、进行科学存储与生产经营决策等方面起到重要的作用[1]。
为提升自动化立体仓库性能，国内外学者在自动化立体仓库货位分配优化方面开展了大量的研究工作。如：Thonemann和Brandeau[2]提出了应用周转率和分类进行货位分配优化的方法；严云中，孙小明[3]对仓库货位号与堆垛机运行效率之间的关系进行了详细的分析，并提出了相应的货位分配优化思想；Hsieh和Tsai[4]提出了基于BoM分类的货位分配优化方法；Moon和Kim[5]将分类存储策略和随机存储策略相结合，研究了货位的二次分类和三次分类方法；刘金平[6]在Hsieh和Tsai的基础之上，提出了基于分类的应用工艺BOM货位分配优化方法；文献[7]考虑了货物需求的相关性，对多巷道仓库货位分配优化问题进行了研究；文献[8]对货位优化算法进行了研究，基于改进粒子群算法对货位进行分配优化；段其昌等[9]采用仓库货位等效思想，提出了立体化仓库货位分配的螺旋排位法；张仰森等[10]考虑了重量均匀分布、就近货位选择、备件品种均匀分布、备件使用率、货位空置时间等因素，提出货位分配的综合优化算法。以上货位分配优化方法均只考虑了仓库运行效率和货架稳定性，而忽略了仓库运行成本。随着世界能源紧缺问题的日趋严重，能耗对存储成本的影响越来越受到更多学者的关注。如：银光球，何福英等[11]建立了货物存取能耗最小的货位分配优化数学模型，有效地降低仓库的运行成本。显然，高效率、低能耗、安全运行是未来仓储产业的发展方向，特别是对于与自动化生产线配套的小型自动化立体仓库而言。因此，考虑存取效率、货架稳定性、储存能耗等多目标货位分配优化必然是未来该领域的主要研究方向。
2货位分配原则
传统仓库货位分配中遵循的四项主要原则为：
（1）货架受力均匀和稳定性原则。避免质量大的货物过于集中造成货架受力不均和货架整体质心过高使货架不稳定，影响仓库安全性。
（2）效率原则。降低堆垛机存取货物作业的运行时间，提升自动化立体仓库系统的工作效率。
（3）分散存放原则。将同一种货物分散存储在不同巷道的货架上，避免由于某个巷道的阻塞或堆垛机故障，影响料单的执行或其他堆垛机的作业。
（4）“先入先出（FIFO）”原则。同一货物出库时，先入库的货物优先出库，加快货物周转，避免货物积压和货物因储存期过长造成品质下降。
在仓库货架设计初期，通过选材、适当的结构设计等手段可以充分保证货架对货物重量的承受能力和货架具有相当的稳定性。因此建立货位分配优化策略时，假设货物的摆放顺序不影响货架结构的安全，无需考虑货架受力的均匀；货架对装满货物后质心高度具有一定承受能力，质心高度可以作为货位优化的次要目标。
企业生产过程中，原材料的采购和储备是依据生产计划提前进行的，原材料的入库效率对整个生产过程来讲影响较小，且可通过采购储备计划的人为调整予以消除。而原材料的出库效率则会直接对生产线产生影响，较高的出库效率可提高生产线的生产速度，为企业带来更大的效益，出库效率过低会导致生产线停工待料，给企业造成巨大损失。因此，对于工业和制造业企业应用的小型立体化仓库而言，货物的出库效率是第一位的，是货位优化追求的最重要目标，货物的入库效率可不予考虑。
仓库货物存储的能耗与堆垛机的运行路径长度成正比，出库操作时为避免能耗限制影响出库效率进而影响到企业收益，不考虑能耗问题。而将入库操作的能耗最小作为小型立体化仓库货位分配优化的次要目标，降低仓库存储的成本。
小型自动化立体仓库存储货物种类、数量较少，且通常与生产线配套货物种类及特点是可提前预知的。因此，可通过人工干预的方法，在存储货物过程中对个别货物指定到特定货架内存放，以解决货物性质（危险）、货物体积与货架容积不符、相同货物分散存放、加快货物周转等问题。
综上所述，对企业的小型立体化仓库货位分配原则可归结为：
（1）出库效率最高；
（2）入库能耗较低；
（3）整体质心较低。
3货位分配策略
由力学原理得堆垛机纵向运送货物作功：
WH=mgh（1）式中，m表示货物质量；h是货物的垂直运输距离，近似取货架上货物质心高度；g是重力加速度。
堆垛机横向运送货物作功：
WL=μmgl（2）式中，μ表示摩擦系数；l是货物的水平运输距离。
考虑到无论是巷道式还是其他形式的堆垛机，堆垛机与地面摩擦系数非常低(μ<<1)。此外，当货物一定时，WL相对于WH是个较小值。因此，可忽略堆垛机横向运送货物作功WL。
设货物总数为k，货物摆放在货架上的总质心高度为：
hm=å(k)mihiå(k)mi（3）
i=1i=1
忽略堆垛机横向运送货物作功，入库操作时堆垛机总作功：
Wm=gå(k)mihi（4）
i=1
因为hmWm为大于零的常数，所以满足hm最小的hi(i=12k)必然满足Wm最小，反之亦然。因此，优化时对质心最低和能耗最小两个目标只需建立一个目标函数即可。
货物的出库效率，可由堆垛机执行出库任务运行时间的数学期望来描述：
S=å(Q)sipi（5）
i=1
式中，Q为出库任务单数量；si为执行第i出库任务的最小运行时间；pi是第i个出库任务的频率。
将式（4）与式（5）联立即可得货位多目标优化的数学模型，且该多目标优化问题只有在极特殊情况下才存在绝对最优解。目前，解决多目标优化问题常采用的方法有遗传算法、粒子群算法、模拟退火算法等，但这几类算法在应用中，存在参数难以确定、算法本身过于复杂不易掌握等缺陷。
由多目标优化理论可知，在多目标优化不存在绝对最优解时，获得有效解的前提是目标函数做出适当让步。结合小型立体化仓库货位分配问题的自身特点，基于顺序单目标规划思想，可采用如下策略对货位进行分配优化：
首先，按能耗最小原则对所有货物进行分层操作，确定货物所属层号。
式（4）中WH与h成正比。因此，若想能耗最小，质量越大的货物应摆放在层号越低的位置。一般而言，设货架有X列，Y层，共X´Y个货位，入库货物数量kX´Y，货位分层操作，可通过以下步骤实现：
（1）对k件货物按质量由大到小排序，若出现质量相等的货物，则将频率高的排在前面，得m1m2mk。
（2）将编号为j的货物归入货架的第q=éjXù(1qY)层，直至所有货物归层完毕，é•ù表示对•向上取整。
然后，以出库效率最高作为目标，货物分层作为约束条件，将原问题转化为有约束的单目标优化问题。不难证明该单目标优化问题的解是原多目标优化问题的有效解。
4优化模型
4.1建立数学模型
设堆垛机按货物存储货位由上到下顺序执行出库作业，则第i出库单的运行时间为：
ni-1
si=åmax(LVH)+
j=0
max(Lni0（6）
式中，ni表示第i出库单包含的货物量；j=(12ni)货物按重量从小到大排列后的序号；堆垛机的水平运行速度VL；垂直运行速度VH；L表示两作业货位间水平距离；H表示两作业货位间垂直距离。
令BH(j)表示j货物对应的货位编号，则：
式中，sH为垂直运行的单位时间（运行一个货位长度的时间）；sL为横向运行的单位时间；ë•û表示对•向下取整。
ini-1ææêêBH(j)-BH(j+1)úúöLs(BH)=åj=1maxçèçBH(j)-BH(j+1)-ëXûXø÷s
maxçBH(1)-X÷s货位优化数学模型为：
Q
minS=åsi(BH)pii=1
éêêjúúêêjúúX+Yúùj=(12k)
s.t.BH(j)ÎêX+1
ëëXûëXûû
m1m2mk（9）根据该优化模型的特点，可采用嵌套分区方法（NestedPartitionsMethod，NPM）[12]，对优化模型求解。该法是一种将全局优化和局部寻优很好结合起来的全局优化算法，通过分区，为问题本身引入特殊的结构，从而有效利用问题本身的信息，具有很高的计算效率和求解质量。
4.2分区
分区是嵌套分区方法中最重要的步骤，是合理、有效利用问题本身信息提高计算效率的关键。为便于叙述，下面以货架的某一层为例，根据约束条件假设可放入该层的货物编号为12n。
进行货位分配时，对该层而言优化问题可行域为
12n的全排列组合。具体操作时，首先将货物12n分别放入第1个货位，得到n个互不相交子域，每个子域包含n-1件未确定货位的货物，然后对各
域。详细分区过程见图1。
图1分区示意图
通常，第K次迭代时，将最可能域划分为MK个互不相交的子域区：
éiù
δ(i)=ê***xúi=(12MK)ëK-1k-Kû
[x1x2xMK]ÍéêêKúX+1êKúX+2êKúX+Yùú
ëëXûëXûëXûû
MK=æçêKú+1ö÷X-K（10）èëXûø
定义该优化问题的可行域Θ，除子域δ以外的区域
Θ\δ，称裙域（surroundingregion）。
4.3抽样
采用加权抽样法，给定常数pÎ[01]。
fori=K+1∶k
由U（0，1）随机产生u；
ifu<p
BH（i）=可选集合中最近货位；
else
BH（i）=在集合中由均匀分布随机产生一个货位；
end
采(end)用上述方法获得一个样本，嵌套分区算法中样本数量可以自由选取。为在保证精度的前提下尽可能提高计算效率，选取子域抽样数为当前尚未分配货物数（随着最可能域的缩小，抽样数递减）；全部计算过程中，裙域的抽样数取总货物数；对于中小型优化问题，选择
p=0.9可获得较好结果[13]。
4.4选区和回溯
（1）选区：对各子区域里抽到的每个样本按式（5）和式（8）求解堆垛机执行出库任务运行时间的数学期望。把数学期望最小的样本对应的子域δ(*)作为下次迭代的最可能域，同时将落选的子域归入裙域。
（2）回溯：如果数学期望最小的样本对应的δ(*)是当前裙域包含的子域，则需要进行回溯操作。由选区操作可知，裙域是由多个落选子域组成的，而出现最可能域属于裙域的情况，是由于抽样随机性导致的。因此，本文采用的回溯方法是选择裙域中包含最优解的落选子域，作为下次迭代的最可能域。
5计算实例
某公司给一条自动化生产线，配套建设一小型自动化立体仓库。立体仓库货架为6层9列形式，货位长0.7m，高0.3m。堆垛机水平运行平均速度0.4m/s，竖直提升平均速度0.3m/s，货架示意图及货位编号见图2。堆垛机执行单件货物存储时，货物按到达顺序编号
1~54，货物质量及出库频率见表1。
按常用的货物编号与货位号相对应的货位分配方
464748495051525354
373839404142434445
282930313233343536
192021222324252627
101112131415161718
123456789
图2货架示意图
表1货物质量及出库频率
货物质量出库频率货物质量出库频率货物质量出库频率货物质量出库频率式，货架重心高度为0.92m，出-入库总能耗为103.4kJ，出库效率的数学期望为124.24s。采用本文的方法优化后，货架存储货物的编号见图2。图中数字表示该货位存储的货物编号。
按常用的货物编号与货位号相对应的货位分配方式，货架重心高度为0.92m，出-入库总能耗为103.4kJ，出库效率的数学期望为124.24s。采用本文提出的方法优化后，货架存储货物的编号见图3。图中数字表示该货位存储的货物编号。
875443442382150
10469446133515
484547144953165232
171835111920331251
3740273412328241
312230242925393626
图3优化后货物储存位置
优化后货架重心高度0.57m，出-入库总能耗为63.8kJ，出库效率的数学期望为103.60s。优化后货架重心下降0.35m，显然，货架稳定性明显好于优化前；能耗降低38.3%，显著降低了仓储成本；出库效率提升16.6%，有效提高了出库效率。可见该优化方法可解决能耗、出库效率、货架稳定性等多目标货位优化问题，优化效果较好。
每次执行多件货物存储的分批次操作时，货物编号1~54，货物质量同表1。订单包含货物及订单操作频率见表2。
表2出入库订单
订单号频率货物编号
123456789
100.10
0.12
0.14
0.15
0.16
0.20
0.25
0.30
0.32
0.401、2、5、6、11、12、20、21、23、36、37、42、43、49
4、13、28、33、52
16、17、25、39、46
3、14、18、19、24、27、29、38、40、45、51、53
30、47、48、54
9、10、15、22、34、35、41、44、50
7
8、26
3231
优化结果见图4。优化前出库效率数学期望73.85s，优化后为43.75s，出库效率提升40.76%。按订单顺序依次执行全部订单的出入库操作，存储能耗及出库时间见表3。差值表示优化前减优化后，差值为正表示能耗降低（时间缩短），反之表示能耗升高（时间延长）。
784544243502138
10465694415313
324547494814531652
121751181119203533
1402723237344128
262425302939223631
图4优化后货物储存位置
在整个货物的存储过程中，优化后能耗比优化前减少12.1kJ，能耗降低19.77%。优化后执行完全部订单的出库任务，共可节约堆垛机运行时间达139.25s。除
频率最低的1号订单外，单独执行一个订单的出库时间
表3订单出入库操作能耗及效率
优化前优化后差值优化前优化后差值
能耗/kJ出库运行时间/s订单号
都有较大减少，最小减少9.75s，最大减少24.5s。
6结束语
针对小型立体化仓库运营特点，提出的货位优化策略，可将复杂多目标优化问题转化为相对简单的单目标优化问题，建立的优化数学模型可较好的描述原多目标优化问题，通过嵌套分区算法可方便对其求解。大幅度降低了多目标货位优化的难度，容易掌握，便于在企业小型立体化仓库中的应用。
通过算例证明该方法对小型自动化立体仓库货位分配优化效果显著，可解决仓储能耗、出库效率、货架稳定性等多目标货位优化问题，能有效减少仓储能耗，降低企业运营成本，提升货物出库效率。
参考文献：
参考文献：
[1]胡昌思.全新概念自动化立体仓库[J].制造业自动化，2002（7）：62-63
[2]ThonemannUW，BrandeauML.Optimalstorageassignmentpoliciesforautomatedstorageandretrievalsystemswithstochasticdemands[J].ManagementScience，1998，44（1）：142-148.
[3]严云中，孙小明，潘尔顺.立体仓库库位号与堆垛机运作效率关系的探讨[J].工业工程与管理，2000，5（6）：29-33.
[4]HsiehS，TsaiKC.ABOMorientedclass-basedstorageassignmentinanautomatedstorage/retrievalsystem[J].InternationalJournalofAdvancedManufacturingTechnology，2001，17：683-691.
[5]MoonG，KimGP.EffectsofrelocationtoAS/RSstoragelocationpolicywithproductionquantityvariation[J].Computer&IndustrialEngineering，2001（4）：1-13.
[6]刘金平，周炳海.在线自动化立体仓库货位分配方法及其实证研究[J].工业工程与管理，2005（1）：11-15.
[7]肖建，郑力.考虑需求相关性的多巷道仓库货位分配问题[J].计算机集成制造系统，2008，14（12）：2447-2451.
[8]陈月婷，何芳.基于改进粒子群算法的立体仓库货位分配优化[J].计算机工程与应用，2008，44（11）：229-231
[9]段其昌，王玮.自动化立体仓库库位螺旋优化方法[J].工业工程与管理，2009，14（2）：73-75.
[10]张仰森，刘安字.智能化立体仓库入库货位分配的综合优 化算法[J].计算机科学，2010，37（12）：175-177.
[11]银光球，何福英，盛冬发.自动化立体仓库中库位优化型研究[J].福建工程学院学报，2006，4（3）：347-358.
[12]OlafssonS，ShiLeyuan.Anintegratedframeworkfordeterministicandstochasticoptimization[C]//Proceedingsofthe1997WinterStimulationConference.USA：IEEE，1997：358-365.
[13]路晓伟，蒋馥.连续系统优化的嵌套分割算法实现[J].系统工程理论与实践，2004，24（1）：126-129.
注:本文由笔耕文化传播（www.bigengculture.com)整理，文章版权归原作者所有，转载请注明出处！
注:本文由笔耕文化传播（www.bigengculture.com)整理，文章版权归原作者所有，转载请注明出处！
本文编号：9472
本文链接：https://www.wllwen.com/guanlilunwen/wuliuguanlilunwen/9472.html
