低层人至物拣货系统订单拣货路径问题研究1西南交通大学　2长江大学　李诗珍1,2　杜文宏1　彭其渊1 摘　要:归纳总结了影响拣货路径的各种因素,并以低层固定货架仓库为例,重点研究了各种订单拣货路径策略及路径长度确定方法,在对实际应用较多的启发式方法进行比较分析基础上,根据路径策略的理论研究与应用概况,提出了进一步的研究方向。

关键词:低层人至物拣化系统;订单拣货;路径;研究Abstract:The paper sums up the effect of various factors on picking routing and makes a study of routing policies for order -picking and how to determine routing distance by means of a case of low-level fixed-rack warehouse.On the basis of com2 paring and analyzing practical heuristic routing policies,it shows the direction of further study.K eyw ords:low-level picker-to-part picking system;order-picking;routing;study1　引言订单拣货(拣选、拣取)就是根据客户的订单,将物品从仓库的库存储位中取出,并进行出库作业。

为了提高仓库的效率,减少作业人员在仓库内的行程,需要精心设计拣货策略和路线。

拣货效率的提高取决于多方面的因素,如仓库的布局、相应的硬件设施、运作策略等。

其中订单拣取路径的缩短与优化作为一项提高拣货效率的运作策略,多年来一直受到企业家和学者的关注。

近年来随着消费需求从大批量少批次向多样少量的转变及电子商务的出现,配送时限要求越来越短,对配送中心的反应速度和拣货效率提出了更高的要求,有关拣货路径问题的研究也相继增多。

2　影响拣货路径长度的因素211　仓库的结构与布局在订单拣货中,布置设计主要涉及2个方面:包含拣货系统的设备布置及拣货系统内部的布局。

前者涉及不同功能区域的位置决策(收货、拣货、存储、分类、出货等),通常通过考虑各区域之间的关系来完成。

目标是搬运成本最小化,在很多情况下表现为行走距离的线性函数。

后者涉及区块数量的确定,每个拣货区中巷道数量、长度和宽度的确定。

目标就是在给定的约束条件和需求情况下对某个确定的目标函数,找到一个最好仓库布局。

最普遍的目标函数就是行走距离。

仓库中的拣货路径问题相当于一类特殊的旅行商问题,仓库的结构与布局如货格的宽度与深度、仓库出入口位置及横向通道的数量等都是影响拣货路径长短的重要因素。

212　存储策略存储策略是指如何给存货单元分配存储位置,主要分为随机存储、基于体积-订单指数存储和分类存储3类。

随机存储策略因其使用简单,可以节约存储空间而被广泛使用。

由于存储位置是随机的,被拣取品几乎分布在所有通道中,对拣货路径的减少没有帮助。

基于体积-订单指数的存储策略(C OI)是将储存货物所需的平均空间与该货物的日平均订单数量的比值小的放置在靠近出入口的位置。

在一个拣货通道内,这种存储策略能大大减少通道内拣货行走的时间,但和随机存储相比,其信息精确度要求高,不容易管理。

分类存储是将物品按拣货频率的高低分类,将流量大的品项存放在离出入口近的地方。

文献[1]的研究表明分类存储比随机存储节约12%～26%的拣货时间,节约的程度取决于拣货单上被拣品数量的多少,大的拣货单比小拣货单节约的时间少。

一般来说,如果不考虑拣货区的数量和拣货单的大小,采用基于体积指标的存储策略比随机存储策略的拣货路径短。

213　拣货策略拣货策略确定拣货单上应拣取哪些货物单元,再由拣货员从其储位上取出。

订单个别拣货是最普遍的策略,拣货员按一定的拣货路径从仓库中取出一个订单上所列物品。

这种拣货方式能保证订单的完整性且比较容易实现,因而应用较多。

另一种拣货策略就是将多个订单集合成一批进行批量拣取。

分批方式有固定订单量分批、总合计量分批、时窗分批和智能型分批等。

无论哪种分批方式,在减少拣货行走距离方面都优于先到先服务的订单个别拣货策略。

214　路径策略路径策略决定拣货员的行走路线,拣货员按路径策略指定的顺序依次拣取物品。

继文献[2]给出的一种在矩形仓库中的最优拣货路径算法之后,一些学者研究了多种启发式路径策略。

由于启发式方法简单易懂,又能形成比较接近最优的路径,在实际操作中,企业普遍愿意接受这种方法。

3　订单拣货路径策略研究在低层人至物拣货系统(拣货员沿着巷道行走到拣取位置拣取相应的物品)中,无论出入口位于仓库中间还是在仓库的一角,其拣货路径策略概括起来主要有基本路径策略、启发式路径策略和最优路径策略3类。

本文以多平行通道、出入口位于仓库一角的货架仓库为例,图1(图中阴影部分表示拣取位置)说明各种路径策略中拣货路线的确定方法。

311　基本路径策略(1)穿越策略如图1a所示,穿越策略是指一个拣货员从仓库的一端进入拣货通道,而从该通道的另一端退出进入下一个包含拣取位置的拣货通道。

拣货员从出入口出发,在返回出入口之前按这种方法遍历所有包含拣取位置的通道。

(2)返回策略如图1b所示,返回策略是指拣货员从拣货通道的同端进入和退出,拣货员只需要进入包含拣取位置的通道,不包含拣取位置的通道可以跳过。

图1　基本路径策略(a)穿越策略　(b)返回策略312　启发式路径策略启发式路径策略因其具有简单易懂、容易形成与实际一致的路径等优点,在实践中得到广泛的应用。

启发式路径都是在基本路径策略的基础上,对某些规则作一定的改进形成的,一般来说比基本策略更优一些。

(1)中点策略中点策略必须从拣货通道的中点处将仓库分为2部分,如图2a所示。

为便于描述,将图中与拣货通道垂直的水平通道分别称作南通道和北通道。

拣货员从拣货通道一端进入,到达一个拣货通道的最远处就是中点,拣取货物后,从该通道返回。

该通道中比中点远的拣取位置则从仓库的另一端进入并返回。

拣货员从出入口出发,按上述策略分别拣取南面1/2部分的货品,从最右边的通道穿越、从南通道进入北通道,再按相同的策略完成北面部分的拣取。

拣取作业完成后从北通道退出,穿越第1个拣货通道到达南端返回出入口。

(2)最大间隙策略最大间隙策略与中点策略相似,区别是到达通道最远处是最大间隙而不是中点,如图2b所示。

最大间隙是指同一拣货通道中任意2个相邻拣取位置之间的距离、第1个拣取位置与南通道的距离或者最后一个拣取位置与北通道的距离中的最大者。

如果最大间隙在2个拣取位置之间,拣货员采取从通道两端返回的策略;否则采用从南端返回或北端返回的策略。

因此一个通道的最大间隙就是拣货员未穿越的通道部分。

到达北通道从第1个拣货通道穿越或者最后一个拣货通道穿越。

(3)混合策略混合路径策略将返回策略与穿越策略相结合,其关键在于确定穿越与返回的时机,如图2c所示。

混合策略将2个相邻拣货通道中最远的拣取位置之间的距离最小化。

图中,从南通道进入第1通道中最远的拣取位置是第2个储位,第2通道中最远的拣取位置是第8个储位(由南向北的顺序)。

假设每个货格的尺寸为一个单位,以货格的中点为基准,忽略在货架两端行走的垂直距离及在垂直通道内行走的水平距离,则这2个位置之间的距离是11个单位,比穿越策略节约了1个单位。

从第2通道到第3通道则采用穿越策略,因为它比返回策略节约12个单位的距离。

(4)S 形启发式策略拣货员沿着拣取位置以呈S 形的路线行走,穿越任何包含拣取位置的通道,而跳过不包含拣取位置的通道。

在只有一个拣货区的仓库中,S 形启发式策略等同于穿越策略。

而在具有多个与拣货通道垂直的横向通道的仓库中,拣货区被分成多个区块,这时对每个区块分别采用穿越策略,而从每个区的最后一个拣货通道返回该区的南端,进入下一个拣货区,直到最后一个拣货区内的货品被全部拣出为止,如图2d 所示。

(5)通道接通道策略(Aisle -by -aisle )它是针对具有多个横向通道仓库的启发式方法[3]。

采用这种方法对每个拣取通道只访问1次,即首先拣取通道1内的所有品项,接着拣取通道2内的所有品项,依此类推。

采用动态规划方法确定从一个拣取通道向下一个拣取通道过渡的横向通道。

如图2e 所示。

图2　启发式路径策略(a )中点策略　(b )最大间隙策略　(c )混合策略(d )S 形启发式路径策略　(e )通道接通道路径策略313　最优策略仓库中的拣货路径问题相当于一类特殊的旅行商问题。

文献[2]提出了具有2个横向通道(1个区)的矩形仓库的最优路径算法,利用图论方法来解决问题。

文献[4]在文献[2]的基础上,将问题进行扩展,利用动态规划方法解决了具有3个横向通道的仓库最优拣货路径问题。

文献[5]利用分支定界法来确定具有多个横向通道仓库的最短拣货路径。

文献[3]采用动态规划方法开发了一个确定具有任意多个横向通道仓库的拣货路径模型。

4　路径策略比较分析文献[6]对5种启发式路径与文献[2]的最优路径作了比较,对于不同的仓库形状、仓库出入口的位置及拣货单的大小,混合策略和最大间隙策略的平均路径比最优路径长10%。

即使是5种方法中最好的,其拣货路径也比最优路径长5%。

文献[7]对3种路径策略进行了评价,仿真结果表明:对比较小的拣货单(如4个品项),返回策略效果较好;对非常大的拣货单(品项64～80),穿越策略较好。

一般来说,中点策略要优于穿越策略和返回策略。

文献[8]分析表明,如果拣取密度(一个巷道中被拣品的数量)的近似值小于318,最大间隙策略较好,当拣取密度大于318,则穿越策略优于最大间隙策略。

当拣货通道数大于拣取品项数时,中点策略和最大间隙策略接近最优策略,而当拣取品项数相对拣货通道数较大时,穿越策略比中点策略和最大间隙策略更受欢迎。

文献[9]对只有一个区、采用随机存储策略的几个具有代表性的仓库作了最优策略和穿越策略的比较,发现对于第1个仓库,穿越策略的路径比最优方法的路径平均长713%～1217%;对于第2个仓库,为1215%～2018%;对于第3个仓库则达到30%～3214%。

同时所采用的存储策略对路径策略的效率有很大的影响,穿越策略较适用于将需求频率最高的品项位于一个巷道中,次高的位于下一个巷道中。

文献[10]考虑了在一个具有2个区、出入口位于仓库中间的基于体积指标存储的仓库中采用S 形启发式策略和返回策略的情况。

结论是:返回策略仅仅只在每个巷道中的平均拣取数量较小(如<1)和基于体积指标的ABC 曲线偏斜时才优于S 形策略。

对一个区基于容积指标存储的仓库,文献[11]等比较了4种路径策略:混合策略、最大间隙策略、S 形策略和最优策略。