雷 斌,王菀莹,赵佳欣
1.兰州交通大学 机电技术研究所,兰州730070
2.甘肃省物流及运输装备信息化工程技术研究中心,兰州730070
3.甘肃省物流与运输装备行业技术中心,兰州730070
货位分配优化是指各企业根据本企业物料特征、需求物料以及变动因素,对企业库存的设置和货品摆放位置进行动态调整和再配置的过程。货位最优化要求不同设备、工具以及人工之间的相互协作,按照货架类型、货品特征和分类、货位的规划、人工因素等,共同实现最优的货位分配。货位最优化可为运营中的仓库提供更高的拣选效率,降低货物在装卸搬运,储存拣选过程中的损耗,有效的减少仓储中的作业成本。如今随着电子商务以及大数据时代的到来,消费者群体不再仅仅要求货物本身的质量,更多地追求商品配送服务水平的不断上升,那么就要求物流企业要做到最快送达的同时维持配送费用的稳定或者更低。企业在仓储环节的优化可以有效率减少成本,因此仓储货位的改进空间巨大。
目前,关于货位分配优化的研究文献已比较丰富,研究也比较深入,而相关的综述文献还比较欠缺。在货位分配优化中,优化目标和求解算法是最关键的两个问题。因此,为了梳理现有货位分配优化相关文献,分析其研究现状和趋势,本文从货位分配优化目标和模型求解算法两方面入手,进行归纳总结,以期对后续研究和实际应用提高一定的参考。
不同企业在面临仓储优化转型时需求是不同的,企业仓库应更加注重基于本企业的商品特性制定货位分配方案。例如零售行业的仓储特点是物品种类多,仓储货位密集摆放,零售行业订单多而杂,导致其出入库频率高。服装行业的仓储特点是流动性很强,根据季节或衣类属性流动性强,商品相关性高。而家电行业的仓储布局要求其空间利用率高且同时注重货架的稳定性等。大量的不确定因素使得企业仓库货位优化目标复杂多样。而货位分配不合理直接导致出入库时的大量作业消耗和不必要的人工消耗,致使货品配送前出库效率低下,最终导致货品送交消费者时间滞后。
因此,应当根据特定的仓储类型进行针对性分析,建立更加合理的优化模型,使得数学模型更加适用于实际案例。通过分析现有文献,将货位分配优化目标归纳如下。
整体出入库频率,也叫货品周转率。通常情况下,按照货物出入库频率由高到低按序存放,相近周转频率的货品摆放在同一档,并将出入库频率高的货品优先存放在距离出口近的位置。这样可以减少高频出库货物出入库距离,减少作业时间,提高作业效率,降低作业成本。
针对货物出入库频率的研究较早,Heskett[1]最早提出依据COI系数,即货物的储存空间与该货物的周转率的比值,应用于货物出入库频率的分档。COI越高的货物摆放越靠近出入口,相反COI越低则会摆放在距离较远的位置。Yang 等[2]通过考虑COI 分布来更好的区分产品出入库频率差异,提出运用聚类算法对产品进行分配来满足约束。杜沛霖[3]运用服装的季节性根据周转的变化情况建立目标COI函数,出入库频率高的热销产品容易拣选,提高了订单拣选效率。蔡安江等[4]也是依照不同类别货物的COI 值确定的货品出入库的频率大小。王贺[5]设置以商品出入库频率与出入库距离的乘积之和的最小值作为最终优化目标。郭万丹[6]通过对货品关系和出入库频率进行关联分析,以获取总体最短的拣货路程为目标对货位分配进行建模。Hausman等[7]通过对分配原则的对比分析,得出基于货物出入库频率而实行的分配策略能够减少堆垛机作业时间。Tu 等[8]将货物按照周转率分类,建立以堆垛机作业时间最短为目标的模型。结果表明可以减少拣选作业时间。
从实际出发,仓库将货物出入库的频率作为货位分配的目标,可以平均缩短货品出入库的作业时间,节省作业时间的同时提高了作业效率。但周转率根据各种因素是变化的,因此通常在实际中,每隔一个阶段都要重新规划一次货位。以出入库效率为主要优化目标的仓储企业大致为批发零售等一般出入库频率极高的销售企业。
根据货物的体积、质量、结构等不同因素,货架达到稳定一般要求两个方面:货架的垂直稳定和水平稳定。垂直稳定性要求货架的存放方式应按照质量较大的货品放下层,较轻质量货品放上层为原则。水平稳定性要求同一水平高度存放的货品间质量差距应当最小化,使得货架左右两端达到平衡来控制货架的整体稳定。
Wang 等[9]设计的以货架垂直稳定为优化的目标模型,在满足货架最大承载量和最高限度的同时使货物重心最低。并设计了层次遗传算法,计算结果降低了货架重心。韩彩云[10]以货架稳定性为目标建立模型,认为货架的稳定性可以理解为摆放货物重心最低,并通过算例得到理想结果。李小笠等[11]综合了以货架稳定以及运行效率的多目标货位优化问题建立模型,通过对产品摆放的总质心高度进行约束,质心高度越低则货架越稳定。张静溶[12]以货架重心最低,达到稳定为原则对货位的稳定性进行优化。杨玮等[13]以货架稳定性原则建立优化模型,按照货架重心最低进行上轻下重式摆放,且摆放货物总质量不超过货架最大承载力。
多数情况下讨论货架的垂直稳定性更多。仓库储存以货架稳定为目标的大多是一些存放大宗货物的、体积重量大的、易碎等又或者货品类别所要求的其稳定存放的。如此规划既可以做到货物的安全摆放,也可以有效利用空间。
按照各货品之间存在的相关性原则,即相关性高的货品有较大的可能同时存在于同一订单,同时出库入库,或者是因为产品性质结构相似而同一存放。为了方便拣选,将相关性高的货品混合存放,可有效减少拣选人员或设备取货的作业路径和时间。
Xiao 等[14]讨论了针对物料清单(BOM)信息,即表示出现在同一订单中的产品相关程度,提出订单拣选总路径最小、拣货速率最高的优化模型,并得出优化结果。Pang等[15]等通过分析客户订单中产品间的关联,建立优化目标是最小化存放和拣选订单操作的总路径。适用于物料关联性强的仓储管理。以此提高仓储作业效率。Jin等[16]利用关联规则分析订单内货品的需求相关程度,然后建立了以缩短总拣货距离为目标的库位分配的数学模型。数值实验证明该方法可以获得较高的拾取效率。Brynzer等[17]表明对货物信息进行相关化处理是很重要的,产品按照相关性原则摆放在订单拣选作业环节中可以大幅缩短作业时间。Zhou 等[18]通过建立仓储产品之间的关系,结合现行的分配策略建立优化模型,并通过软件进行仿真。李英德等[19]考虑相关性为原则尽可能的将货物集中摆放在临近的巷道,以拣选货物时间最短为目标,对货位分配进行优化,以此方法来提高拣货效率。李明等[20]提出关于以货品相关程度为原则的货位优化方法,建立订单拣选总时间减少的函数并设计算法求解。肖建等[21]等依照物料的相关与否,将关联货位就近摆放。设计算法求解得到证明,考虑货品的相关程度为原理的分配策略得到的结果更优。
将货品相关性原则应用到实践中,可以缩短拣选路径,同时也可以减少拣选时间,达到提高工作效率的目的。货物之间的相关性有多种表达方式,通常,首先计算物品两两间的存储距离,两货品间相关系数与距离乘积之和判断货品相关性储存合理与否的依据。这种算法被称作曼哈顿距离公式,这一原则一般适用于批发零售类等提供商品销售的企业仓储管理。
按照货物体积、质量等特性条件,合理分配其存储位置使得充分利用仓库空间,提高仓储空间利用率,提高仓储容纳量,减少货物储存占用过多空间带来的承租费用。此外一些配送中心的仓储内有多条巷道,可将同类物品就近摆放,临近的巷道内尽可能摆放同类相似类货品。多巷道存储可增加并行作业,减少出入库工作量,防止某种货物因出入库数量大而引起拥堵,保证配送中心内部正常的活动。
Lin等[22]主要用于组织仓库内物料的移动和存储空间,综合考虑先进先出的原则和空间利用程度来确定最优的货物位置,降低了货物搬运成本,提高了空间利用率。Yan等[23]的目的是根据不同产品的尺寸、数量、结构等属性与空间相联系合理分配货位,实现空间的充分利用,以减少企业的仓库成本。Quintaniua 等[24]研究了以仓储空间利用率最大为目标建立优化模型。求解得到这一方法不仅使仓库利用率大大提升还缩短了拣货时间。金树冬[25]按照空间利用率最大化为主要原则,最大化使用货位载重量进行拼箱操作为次要原则,解决零件仓储以货位空间利用率为优化目标的问题。
提高空间利用率这一优化目标一般适用于体积较大,不易堆放的货品仓储系统中,例如家具、大型家电,体积过小的零件类仓储可充分利用,都是以节省仓库承租费用为目标的优化。
基于上述关于货位分配目标的分析得出对比结论,如表1所示。
表1 货位分配目标对比分析
在计算目标多样、约束复杂的优化模型时,合理的计算方法会使计算过程更加快速,计算结果更加精确。因此如何选择高效的求解算法,也是货位优化问题中的研究重点。以下分别介绍广泛应用于货位分配优化中的遗传算法、改进遗传算法、模拟退火算法、蚁群算法、粒子群算法以及禁忌搜索法。了解各优化算法的应用及优缺点是合理选择的前提。
遗传算法是根据生物进化演变而来的。它模拟的是自然界“物竞天择,适者生存”的进化原则,将问题转换成类似生物进化中染色体的遗传、交叉、变异,最终达到最优解的过程。遗传算法相较于普通优化算法,表现出计算速度快,结果更加优化的特点。同时遗传算法普遍应用于各个领域,例如组合优化、信号处理、自适应控制和人工生命等。
Lin 等[22]利用遗传算法计算货位分配,建立考虑以检索时间和检索频次确定的多目标优化模型。结果表明,遗传算法在不同货物频繁出入的情况约束下搜索能力有很大提高。Seval等[26]设计出快速遗传算法以求得基于聚类的存储策略和拣选成本最小化为目标的货位分配问题,结果表明遗传算法可用于解决汽车行业的仓储布局问题。宋菊平[27]提出了通过遗传算法优化基于关联规则和货架稳定为目标的货位分配问题。运用MATLAB 仿真,结果显示该算法提高了结果的可行性和数据支持数量,同时在运行效率更快。徐伟华等[28]采用传统遗传算法进行计算对目标函数为入库的频次和堆垛机作业时间乘积之和最小化问题进行求解。实验结果表明:堆垛机运行次数明显减少,货物的托盘出入库效率大大提升。金树冬[25]采用遗传算法进行模型求解了航天零件的存储以保证货架稳定性建立的数学模型。运用Matlab仿真的结果表明:遗传算法能够很好地解决货位优化的NP问题。
遗传算法作为有效解决仓储货位分配问题的算法之一,已然得到许多研究人员的认可和应用。但传统的遗传算法仍存在缺点,例如收敛速度慢,局部搜索能力差,控制变量较多等问题。因此,研究人员应更加注重在此基础上的研究改进。
为保证运算效率和运算精度能够同时兼顾,研究人员在传统遗传算法的基础之上尝试融合一些手段对算法进行优化,弥补算法中收敛速度慢,局部搜索能力差,控制变量较多等的缺陷。改进后的算法求解精度更高,且应用领域更加广泛。
Wang 等[9]设计了一种层次遗传算法(Hierarchical GA,HGA),用来解决以货架重心最低和存取货物便利性为目标的自动化立体仓库货位分配优化问题。所得结果:降低了货架重心,降低了物流成本。同时表明HGA算法计算速度快、稳定性好。Li等[29]设计出一种新型帕累托遗传算法,并运用小生境术进行优化,用于解决多目标优化的货位分配问题,得出满意优化结果。Poulos等[30]提出一种改进的交叉算子的遗传算法,用来解决自动化仓储系统的补货问题。算法的改进增加了最优解的多样性。钟科艾[31]利用改良的遗传算法以出库用时短、关联性强、货架重心低三项约束为目标来求解得出货位分配的优化模型,由此得出的货位优化分布图更加直观,有效性明显。张鹏[32]采用了简单加权遗传算法,引入多种群遗传算法,对目标函数之间的单位进行统一,并成功避免了未成熟收敛问题在遗传算法中的出现。最终解决了多目标的货位优化模型。张富强等[33]设计了改进自适应遗传算法,根据案例结果得出了该算法对解决货位分配问题比较比较基本遗传算法更具优势的结论。刘德宝等[34]针对货位分配优化设计了小生境遗传算法。根据仿真实验结果得出,改进的小生境遗传算法对优化串并行混合拣选策略和品项货位分配的有效性和可行性。焦玉玲等[35]针对收敛过早的问题的出现,提出了多种群遗传算法,求解以货物出入库效率、货架稳定性,以及产品关联性为目标的模型,求得分配结果并验证算法有效性。刘万强等[36]设计了混合遗传算法,对棋盘格密集仓库出入库作业模式下的货位分配问题进行研究,优化结果使整体作业效率大幅提升,且研究发现货架规模越大则算法效率提升越明显的优势。杨朋等[37]设计了最近邻点策略(NN)的遗传算法。同时决策存货和取货的货位分配,并通过实验验证算法的有效性。王贺[5]运用改进的遗传算法,引入最优个体更新函数,并增加种群二次优化函数,提速收敛,最终得到结果有明显改善。
模拟退火算法是模拟固体物质的退火的过程。算法从较高的温度开始,随着温度参数的不断下降,自动在解空间中随机寻找全局最优的目标,结合概率突跳特性原则,跳出局部最优并逐渐趋于全局最优。因此,模拟退火算法在组合优化的应用中得到了广泛认可。
刘增辉[38]运用遗传模拟退火算法,求解了以出入库效率、货架稳定性、物料分类存放的多目标函数优化模型,使得模型与遗传模拟退火算法的有效性也得到了验证。左娴[39]用模拟退火算法,对不同权重系数下货品相关性货位优化模型进行求解。求解结果表明优化方案可以明显提高快消仓库拣选的作业效率,拣选的作业时间也明显缩短。Muppani等[40]运用模拟退火算法解决控制空间利用率和拣选成本的货位分配的线性优化模型,并通过实际数据案例证明模拟退火算法相比于动态编程算法得出的解更加准确。靳萌等[41]设计了多目标的模拟退火算法,运用于军用器材立体仓库的货位分配问题,经验证该算法应用具有良好的寻优性能,达到了高效储存目的。朱杰等[42]为了克服遗传算法(Genetic Algorithm,GA)易陷入局部最优的缺点,引入模拟退火算法(Simulated Annealing,SA)与GA 的结合(SAGA),用来解决储位优化模型。SAGA 算法的稳定性和收敛性都在最终得到了验证。张思建等[43]采用模拟退火算法对货箱进行货位分配建立以最小出入库能耗及最高存取效率为优化目标。实例验证了模拟退火算法明显优于随机货位分配方法。
蚁群算法是模拟蚁群在各类环境下为寻找食物而得到最短路径的过程。算法将蚁群可采取的所有路径看作该问题的可行解集,蚁群会在行走路径中留下一种信息素作为痕迹,信息素最密集的路径即最优可行路径。路径中释放的“信息素”形成一种正向的反馈机制,整个蚁群很快就会的根据这种反馈沿着最短路径找到食物。
宋宇博[44]制定了改进的蚁群算法,用来求解指令完工时间最短的自动化存取系统优化问题。仿真结果表明:改进的蚁群算法具有更好的全局搜索能力。颜廷鑫[45]利用遗传算法的初试解改变为蚁群算法的初始信息素分布等参数进行迭代,最终得到了以货架稳定、出入库效率为目标的货位分配方案。贺庆等[46]采用蚁群算法解决仓储堆垛机路径最短问题,调整路径中各节点上的信息素浓度,减少局部最优现象。仿真结果表明,改进的蚁群算法能较好解决该问题。
粒子群算法(PSO)是通过模拟鸟群觅食行为而演变而来的随机搜索算法。鸟类不知道食物的具体位置,但却知道自己距离食物有多远,那么鸟类会先找到距离食物最近的鸟,再围绕着这只鸟的周边进行搜索,这样可以很快找到食物。粒子群算法中,把鸟群比作粒子群,空间里的每一只鸟都是待优化的粒子,优化函数赋予每个粒子一个适应值,借此来决定每个粒子搜索的方向和距离。
陶勤勤[47]采用自学习粒子群算法对考虑货物周转率和货物相关性的货位分配数学模型进行求解,实现了货位动态最优分配。杨玮等[13]结合多色集合、粒子群算法和模拟退火算法,解决了以货架稳定性和出入库效率为目标所建立的货位分配模型。证明了与遗传算法相比,混合粒子群算法在求解该货位分配优化问题时的收敛速度快、稳定性高。闫军等[48]在考虑货架的稳定性的基础上。基于离子群算法和遗传算法的仿真对比,得出粒子群算法的优化程度更大。汤洪涛等[49]在K-Medoids聚类算法生成解的类簇的基础上,用粒子群算法进行对堆垛机总作业时间最短为目标的函数求解。K-Medoids聚类算法可以加快粒子的迭代,缩短求解时间。刘建胜等[50]采用自适应策略的遗传算法,以及粒子群算法对以货物出入库效率最高和货物存放重心最低为优化目标的模型进行求解。采用惯性权重线性递减的方法设计了粒子群算法,成功解决了收敛速度慢的问题。通过对比得到粒子群算法更适合解决此类问题。
禁忌搜索算法模拟的是人类的记忆。首先局部进行搜索,记忆并禁忌当前局部最优解。其次依照现有记忆给出下一步的搜索方向。全局搜索后比较记忆中所有局部最优解,得出全局最优解并释放它的禁忌状态。这种搜索办法可以有效避免局部最优和重复搜索。
Xie等[51]提出了一种多阶段随机搜索方法和禁忌搜索算法,针对带分组约束的存储位置分配问题的双层分组优化(BIGO)模型进行求解。实验验证了BIGO 模型的有效性和禁忌搜索方法存在优势。Yang 等[52]提出了一种求解整数规划模型的两阶段禁忌搜索算法,用来研究多穿梭机自动存储位置分配问题。结果表明两阶段禁忌搜索算法得到答案更加精确。Chen 等[53]提出了一种带时间窗的自动检索与储存的货位分配问题,为解决这一问题提出一种改进的禁忌搜索算法,结果证明这种算法求得的解质量更高。俞雷霖等[54]提出了一种混合禁忌搜索的算法,用来优化立体仓库货位分配并切实提高立体仓库的运作效率。郭万丹[6]将遗传算法与禁忌搜索结合起来,得到了全局搜索能力和局部搜索能力都很强的遗传禁忌搜索算法,计算了按照出入库频率和拣货路径最短而建立等人优化模型。陈显[55]将遗传算法和禁忌搜索法相融合进行计算,这种算法全局和局部的搜索能力都比较强,以此解决提升整体仓储运作效率为目的问题,同时求解结果也证明了混合算法的可行性以及优越性。
基于上述5种算法的介绍和分析,得出关于各算法之间的比较以及优缺点,如表2所示。
通过对国内外货位分配的优化模型以及优化算法的一系列研究,能够显著地认识到货位分配的联合优化对仓储高效运作的重要程度。随着社会经济的转型以及企业发展决策的迫切需要,优化目标与计算方法都一直在不断的更新和进步,逐渐成为近些年来企业仓储研究之中的热难点。
(1)货位分配目标的联合优化
货位分配优化是一个多目标联合优化的过程,实例证明企业运用单一目标并不能最大程度达到优化目的。由于仓储很难按照周期流通性货位优化、基于单位体积的优化、基于分拣效率的优化这三类目标精确地给出偏向,因此建立联合优化的模型显得较为困难。提出过仓储联合优化的Dekker等[56]研究以产品关联性和拣选路径最小化为联合优化目标,双重目标作用下使货位分配得到优化,拣选总路径减少了31%。邓爱民[57]研究医药仓储的货位分配,考虑以货物周转率、药品相关性以及拣选路径建立多目标优化模型,并赋以3个目标权重进行货位优化,得到了最优的货位分配方案。复杂的商品构成决定了货位优化目标的多样性,设计多目标联合优化进行货位分配的思想越来越被研究人员肯定与应用。企业为满足自身需求,将调整货位的各目标联合起来,使优化目标之间相互补充,相互制约,弥补单一优化目标约束求解误差大的问题,达到货位分配的最优改善效果。因此货位的联合优化成为进一步研究货位优化的必然方向。
(2)货位优化模型考虑动态因素变化
在优化模型中,视情况而需加入动态因素、不确定因素作为模型约束,实时动态地调整仓储摆放位置,适应需求的快速变换。Wang[58]应产品随时间产生的需求波动,及时更新仓库储存位置,开发出一种动态规划的模型并进行计算实验。徐翔斌等[59]设计的拣选路径可变情况下,在订单拣选的同时进行货位调整的模型,其实验结果表明这类思想可以为零售企业仓储提供科学的理论指导,优化效果可节约25%左右的拣货路径。项前等[60]在考虑实时的货架可分配状态以及托盘使用状态为动态约束,以货架重心和拣选路径为目标建立模型,并根据实时可分配的货位进行再分配,实现动态的约束调整。实验结果表明:总目标函数值优化近5%,单个作业路径平均优化时间3~4 s。
在货位优化的模型中加入动态条件约束,可以提高求解精度,缩小优化误差,对研究动态因素在货位分配中的影响十分重要。因此,在今后的货位分配优化的研究过程中,要不断总结影响货位分配的其他可变因素并加入到约束求解过程中,在提高优化水平和精准度的同时,也适应了实际案例中仓储作业需求的快速变化。
表2 各算法的比较
(3)货位优化智能算法的选择和改进
上述研究的计算方法中,不同计算方法各有优势,为适应建立起越来越复杂的货位优化模型,智能算法也提出了更高的要求。利用改进手段或者算法间的组合优化,提升算法优越性,为货位优化问题提供更加精准的解。在近年来开始研究的混合算法中:Bessenouci等[61]运用模拟退火和禁忌搜索算法的混合算法,来控制货位动态调整的过程以减少拣选的作业时间问题。实验结果表明混合式算法优于其他算法。苏永杰[62]解决货位分配和调度问题,建立以拣选订单时间最小为目标的模型。通过重新赋予粒子群算法中粒子的初位置和运行速度,结合模拟退火算法的优点,提出了二者的混合算法,并运用多组数据验证表明:混合的智能算法吸取模拟退火算法跳出局部最优以及避免早熟的现象,也做到了粒子群算法收敛快效率高等优点,使得最优函数值求解速度快且质量高。混合式的智能算法越来越受学者青睐,由于算法之间取长补短,使得算法实用性和准确度大大提升。因此,深入研究混合式算法的应用对货位分配优化问题的解决有很大帮助。
本文在研究现广泛应用的货位分配的原则基础上,对多种分配目标进行整理举例。并分析各目标不同的适用与特点。此外,本文对货位分配优化的算法介绍进行了整理和分析,在此基础上延伸出货位分配优化方法的研究和未来发展方向,以期待为相关企业在仓储货位分配管理方面的实践决策提供一定的借鉴。