密集仓储规划的实用算法研究

臧冀原，贠 超，张志强

（北京航空航天大学 机器人研究所，北京 100029）

0 引言

随着世界经济一体化和现代科技的迅猛发展,现代物流被认为是除降低资源消耗、提高劳动生产率以外的“第三方利润源泉”[1]。在这一大环境下,作为物流的重要组成部分的仓储,也越来越多的被人们关注。如何提高仓储管理效率和密度,成为一个热点研究问题。仓储是通过仓库对物资进行储存和保管。仓储作业是以保管活动为中心,从仓库接收物品入库开始,到按需要把物品全部完好地发送出去为止的全部过程[2,3]。现代物流配送中心规模日益增大，品种复杂和存储量大与存储空间紧张产生矛盾，如何解决在有限空间内存储尽可能多的货物成为一个值得研究的题目。提高仓储密度在缩短出入库周期，降低设备及其维护成本，减少占地开支等方面都有这积极的意义。

在不考虑货架和出库入库操作方式的情况下，该问题属于平面或者三维布局问题，布局问题属于组合优化问题，求解的难点在于迭代次数随布局对象数量呈阶乘增加。对于仓储对象复杂、货位数量多的仓储规划，如果采用经典布局求解算法，势必费力费时，甚至在规定的时间内得不到最优解。如果增加实际仓储过程中的机构和工艺等约束条件，单次迭代计算时间增加，求解更加缓慢，如何利用这些约束条件，简化求解过程，降低迭代计算次数是本文的主要目的。

1 问题分析

对于一个给定的仓储实体，比如物流配送中心、自动化立体仓库等，面临的问题是已知货物的包装尺寸和额定存储量，如果货位确定的情况下，需要求解占用最少货位并且冗余空间最少的布局；如果货位是可调节或者采用先设计规划后加工的方式，需要求解最优的货位布局，使得占据的存储空间最小。两种表述的数学本质是相同，就是求解满足额定存储量的最小存储空间。

实际的仓储实体多数采用纵横交错的金属框架结构，在三维尺寸方向均要求满足机械结构的约束，使得最小仓储空间的求解不同于下料问题（partition problem）[4,5]或者布局问题（placement problem）。如果采用模拟退火、蚁群算法等都将会导致巨大计算量，收敛缓慢，甚至得不出全局最优解[6,7]。

下面以实际的快速发药系统项目为例，对问题做更进一步的描述和求解。对于医院门诊药房，需要存储一定数量的药品以备一个补药周期内的药品发放，其中的盒装片剂的存储，通常采用金属货架摆放，造成空间的巨大浪费，取药路径长，药房工作人员劳动强度大，发药效率低下[8]。快速发药系统是针对解决医院门诊药房盒装药品的自动补给、密集仓储和自动发放整条流通渠道设计的一套自动立体仓库系统。密集仓储为快速发药系统的关键技术之一，其具体描述如下：

目标函数：求仓储额定药盒的最小货架高度

其中m为排布的层数。

整个货架的宽度不能超过立体仓库的总体宽度

货架的某列的宽度取为该列中最宽的货架宽度

考虑工艺和成本约束，货架每列的宽度满足系列约束

｛W'｝s为货架宽度系列值。

货架的某行的高度取为该行存放的最高药盒的高度

每种药盒的存储量不得低于额定存储量

每种药盒存放在相应的货位上。

f : (i, j)→r, i=0,...,m; j=0,...,n;r=0,..., p定义为第r种药盒放置在第i行第j列货位，满足Wij≥wr；Hij≥ hr。

(W)m×n为货位宽度在出货口截面上形成的矩阵。

(H)m×n为货位高度在出货口截面上形成的矩阵。

(w)p为药盒宽度列阵。

(h)p为药盒高度列阵；p为药品的品种数。

2 求解过程

2.1 数据采集

数据采集部分包括两个方面的内容：药盒最小包装尺寸的测量和药品一个周期的发药量统计，最终获得{li,wi',hi,ηi'}T,i=0,...p，其中

li为第i种药盒的实际长度尺寸；

wi'为第i种药盒的实际宽度尺寸；

hi为第i种药盒的实际高度尺寸；

ηi'为统计周期内第i种药盒的用量，以医院最小用药单位计量。

2.2 数据预处理

对于密集仓储规划求解来讲，数据预处理的目标之一是用转换系数解决医院药房最小用药单位和最小仓储单位不一致问题。转化系数定义为一个最小包装内包含的最小用药量的数量，是一个比值关系，比如药品A，医院使用时是以粒为单位的，而仓储时，是以盒为单位的，如果一盒包含N粒药片，那么转换系数为N。从而获得{li,wi',hi,ηi'}T,i=0,...p，其中 ηi'为药品额定存储量，以医院最小仓储单位计量。

数据预处理的另一个目标是在第一步的基础上， 把 {li,wi',hi,ηi'}T,i=0,...p， 转 化 为 {wi',hi,ηi'}T,i=0,...p，其中

wi' 为第种药盒占据货位的宽度；

ηi'为第种药盒额定存储占用的通道。存在如下关系：

wi=Wi，如果 Wi-1≤ wi'＜ Wi，则

ni=ηi/([L/li])+1)，其中L为一个货位存储的有效长度。

至此三维布局降为二维问题，问题转换为在平面内分行按列布局若干货位，使得所占矩形存储区域高度最小。

2.3 规划算法流程

为了节省迭代次数，提高求解效率，整个规划算法为两步：第一步，按行按列的排列规则，计算机模拟人工排布的方式，在整个宽度方向布局所有货位，获得占据全部宽度的一个较优解；第二步，采用平移货位的方法，将本层最高的药盒货位平移到较高一层的空白货位处，以此降低该层占据的层高，迭代寻优，获得各层的最小摆布层高，从而获得整个布局的高度。

对于仓储的整体布局而言，货位的调整不支持镜像、旋转和置换。货位绕本身轴线的镜像视为同一货位，若绕其它轴线的镜像会发生货位之间的干涉，违背约束条件。同时旋转是不能使得层高优化，也违背约束条件。如果两个货位置换可以带来层高的缩小，那么可以得出这两个货位的宽度必然一致，如果宽度不一样的货位交换，宽度较小的货位肯定放不下宽度较大的货位。而同一宽度的几列中，层高按升序的方式排列在各层中，故两个货位的调换只能导致层高增加（或保持不变）而不会减少。同一层之间货位的互换或者平移是不影响层高的，故优化层高只能通过不同层之间移动货位到空白货位处来实现。概率较大情况下，药盒宽度跟高度成比例关系，故宽度较大的货位通常高度也较大。为获得最优解，被平移的货位高度为该层中最高的，宽度必须最接近至空白货位宽度。

图1 预排布流程图

预排布的流程图如图1所示，预排布的目的是通过简单迭代获得一个满足约束条件的较优解，充分占满仓储的宽度方向，每种列宽的货位按其数量分成若干行若干列，依次按货位高度升序排布，作为优化迭代的初始值，减少了不必要的计算量。

层高规划流程图如图2所示，从最顶层到最底层搜索预排布后留下的空白货位，在空白货位层以下的层中逐个搜索比较高度在该层中最高宽度最适合空白货位的货位，并将该货位平移至空白货位处，修改其货位编码。

2.4 规划结果

在额定储药总量20000盒，各药盒的存储比例关系通过统计药房两周内的发药量获得，货位总数1354，货位宽度系列{38，48，58，68，78，88，98}，立体仓库存储宽度限制为3300，储存有效空间长度1650，药品品种数224的情况下，预处理总存储高度为926，迭代优化后的总存储高度为709，迭代优化前后各层层高分布如图3所示。

图2 优化迭代排布流程图

图 3 层高分布图

虚线为预排布层高值，实线为优化迭代后的层高值。

以上尺寸单位皆为mm。

3 结论

该仓储规划算法以快速发药系统药盒存储为实例，获得了迭代的最优存储高度，输出了获得最优存储高度的货位排布，解决了实际密集存储优化的最小存储空间问题。算法的数据预处理部分将额定仓储量转化为额定货位数量，是整个算法实现的基础。密集存储规划算法避开了经典布局问题求解算法带来的迭代次数过多的缺陷，把由于工艺和成本方面导致的仓储约束作为布局规则引入问题求解，算法在第一步采用模拟人工排布的试凑法，获得一个在可行域上的较优解。在算法第二步，平移高度较高的货位到层高更高的空白货位处，使得高度接近的货位尽可能的放置在一层中，从而使得每层的占据的存储高度尽可能下，达到整体存储高度最小，获得最优解。

[1] Dyckhoff H., A typology of cutting and packing problems[J].European Journal of Operational Research, 1990,44(1): 145～159.

[2] Dowsland K.A, Dowsland W.B., Packing problems [J].European Journal of Operational Research, 1992, 56(1): 2～14.

[3] Scheithauer G., Terno J.Modeling of packing problems [J].Optimization, 1993, 28: 63～84.

[5] Peter Bradley.The Post-Y2K Frontier.International Journal Of Physical Distribution & Logistics Management.1999, 5: 180

[6] Robert L.Lieb, Rbert A.millen.Third-party Logistics Services.A Compassion Of Experienced American And European Manufactures.International Journal Of Physical Distribution & Logistics Management.1997, (6): 12～13

[7] Robert C.lieb, Hugh L.Randall.1997 CEO Perspectives On The Current Status And Future Prospects Of The Third Party Logistics Industry In The United States.Transportation Journal.