随机存储机制下基于引力模型的订单波次划分方法的研究

□ 卢烨彬 刘少轩

(上海交通大学 安泰经济与管理学院,上海 200030)

随机存储机制下基于引力模型的订单波次划分方法的研究

□ 卢烨彬 刘少轩

(上海交通大学 安泰经济与管理学院,上海 200030)

研究仓储中心随机存储机制下订单波次划分问题时,创新性地将引力模型应用到波次划分模型中,以波次内不同储位商品之间的引力大小衡量订单之间的相似度,从而进行订单的波次划分,然后运用遗传算法对该模型进行求解。并从实证的角度出发,将求解得出的方案与传统的基于订单聚类划分的方案进行对比,发现在都采用S型拣选策略的情形下,所提出的基于引力模型构建的波次划分方案的拣货路径更短,拣货效率更高。

随机存储;波次划分;订单相似度;引力模型;遗传算法

一、引 言

在2015年的”双十一”活动中,天猫一天的交易额达到912.17亿元,相比于2014年呈现爆发式增长,增速达59.7%,并且京东、苏宁等电商也实现巨量成交额。由此看出,网络购物在未来必定发展成为一种主流的购物形式,市场巨大。而在整个物流配送过程中,拣货是比较重要的一步,在整个订单配送过程中,订单分拣的劳动量占总劳动量的60%[1]。由此可见,提高仓储中心的拣货效率对整个供应链效率的提升至关重要。而各类电商在货物存储方式上各不同,1号店、京东等大部分电商采取的是分类存储方式,即按照A～Z拼音分类或者销量分类依次存储货物。而像美国亚马逊这样的大电商,它的许多仓储方法在世界均处于领先地位,其采取的则是随机存储方式,相比于分类存储,其在库存空间利用率上具有绝对的优势。随机存储是指对于每个商品而言,没有固定的存储位置,商品可以放到任何库存中空的货位,即“见缝插针”式存放。随机存储相比于分类存储,其空间节省约为30%。

本文以仓储中心的随机存储运作方式为背景,研究在随机存储机制下订单波次划分的问题。波次划分时需要考虑订单相似度,而同一个商品的不同位置的选择,直接关系到这个订单与波次内其他订单之间的相似度。在已有的学者研究文章中,一般通过订单之间的关联来构建订单之间的相似度,比如根据订单含有相同商品的个数作为划分依据,相同商品个数越多,应划分到同一个波次中[2]。然而这种划分方法并不适合于随机存储,因为随机存储机制下,即便是相同的商品,也有可能被存储在相距较远的储位上。因此,为了解决随机存储下波次划分问题,只能从存放商品的本身地理位置特征考虑相似度。

本文创新性地将引力模型应用到波次划分模型中,以波次内不同储位的商品之间的引力大小来衡量订单之间的相似度,从而进行订单的波次划分。

引力模型是根据牛顿的万有引力定律延伸而来,近几年不断地被运用到不同的领域,如城市群理论[3,4]。该模型能够很好的衡量不同位置对象之间的关联程度,而国内外学者曾经将该模型运用到衡量电子商务配送站点之间的关联强度[5]。

本文将引力模型引入,定义两个商品的引力大小为T=φ/r2(φ为引力常数,r为两商品之间的距离)。这样,就可以只从存放商品的本身地理位置特征构建订单相似度。通过对波次订单引力模型的构建,最大化该批订单的相似度。最终,运用遗传算法对该模型进行求解,并将求解得出的方案与传统的基于订单聚类划分的方案进行对比,发现在两种方案都采取S型拣选策略的情形下,基于引力模型构建的波次划分方案比传统的基于订单聚类划分方案拣货路径更短,拣货效率更高。

一般S型拣选策略指的是:对于每一个含有待拣选商品的货架通道,从通道一端进入另外一端出[6]。本文选取S型拣选作为拣选策略的原因,在于亚马逊当前在运用随机存储机制下,其实际仓储管理中运用的就是这种S型拣货策略,这样所进行的研究就与企业实际情况相符合。

二、文献综述

(一)仓储货位存储方法的研究

对于仓储货位的存储方法,国内外有许多这方面的研究。Haus man等[7]在1976年就研究得出,在仓储存储时,不同的存储方式——随机存储、固定存储、分类存储的选择,直接决定了拣货员拣货时的行走距离,从而影响了拣选效率,并研究了ABC周转率储存方式与其他存储方式,比如随机存储、固定存储、分类存储的组合的模式,最终发现了固定存储情况下的拣货路径要短于随机存储情况下的拣货路径。Br ynzer和Johansson[8]依据货物结构将货物分成不同类别,同一类别放在一起可以减少拣货时需要行走的路径。并且,提出了拣货效率不仅与拣货路径有关,也与拣货错误率有关,划分时需要兼顾两者。Petersen等[9]在2002年对比了分类存储和随机存储器拣选效率,分析了不同的存储策略和订单中货物数量对效率的影响,最终得出分类存储相比于随机存储拣货路径更短。董溪哲等[10]在研究中提出,以货物周转率为基础,以货架空间大小和稳定性为约束,最小化拣选距离构建模型。而朱子音[11]在研究中是从另外一个角度研究仓储货位分配问题,是以库房利用率为目标函数,从时间和空间两个角度考虑,将库房存储区域划分成动态和静态两个存储区域,不同类型,分别进行优化,最终得出最有的配置方案。

(二)波次拣货分拣策略的研究

对于同一个区域内的拣选,Acker man[12]在1990年首次提出订单分批拣选策略,并提出这种方法在一定程度上能够提高货物拣选效率。Gibson和Shar p[13]研究了订单分批拣选方法,并运用仿真将其与普通的拣选方法进行对比,最终得出分批拣选方法效率更高,在分批拣选时,需要考虑订单里面货物的相关性,以及仓储的分布等因素。Gade mann等[14]研究发现,订单划分批次问题是一个NP问题,作者采用的是分支定界法对其进行求解。

Choe和Shar p[15]在1991年研究提出,波次拣货划分有两个基准:相似度划分和时间窗。在相似度分拣的情况下,按照货物的存储位置来进行分批次,难点在于如何衡量各订单直接的相似度以及订单拣选的先后次序。这也是本文重点分析的问题。而Gade mann等[14]提出在波次拣货时,就近订单拣选能够将任意一个波次的拣货提前期最小化。对于订单之间的相似度研究,Chen和 Wu[16]从含有相同产品的数量考虑,构建模型使总关联程度最大,然后将其转化为0-1规划问题求解。而在时间窗分拣方面,主要是通过订单到达时间划分波次,同一个时间窗内到达的订单被划分到同一个波次。Tang和Che w[17]研究了在固定波次里订单量的情况下,动态调整时间窗的问题。通过测量服务时间来估算订单划分波次大小。李诗珍和王转[18]在2004年研究发现,通过建立最短拣选距离为目标函数的模型实现波次拣选,运用启发式算法聚类分析,提出了三个相关系数:巷道相似系数、包络距离、储位相似系数的概念。构建模型,最后用基于包络解码的混合遗传算法求解。在国内,马士华和文坚[19]在波次拣选中考虑到了订单延迟时间,通过调整时间窗改善拣选员闲忙分配不均的问题,使得整个供应链拣选效率得到有效地提高。波次拣货是属于NP问题,研究下来发现,有许多学者都是将原来问题转换为0-1分配问题,运用启发式算法、遗传算法求解问题。李云[20]在研究中对波次拣货算法进行了分类:种子启发式算法和节约启发式算法。种子启发式算法需要为每个波次定义种子的顺序,可以通过随机、数量、距离等方面考虑。而节约启发式算法是一种针对拣货路径上的优化算法。郑凌莺[21]对于物流仓储货物问题上的一般优化方法进行研究,并比较了各算法的优缺点,最终得出以多目标遗传算法为基础的算法效果最好。

参考已有研究,本文选取遗传算法对构建的波次划分模型和拣货任务指派模型进行求解。

三、模型构建

(一)模型相关假设

为了研究需要,参考已有的研究,本文做了以下合理假设:

1.每一个订单至少包含一个商品,最多包含N个商品(N为仓储中心内商品总数)。

2.忽略货架的高度,垂直方向的位移大小不计入拣选路径,显然,无论采用何种分配方法,垂直方向的位移大小均存在,因此,可以忽略这一部分。

3.拣选人员至少1个,这也是符合亚马逊的实际情况。

4.同一个订单只允许被划分的一个波次中,然后由一个拣货员完成拣选。

5.对同一个波次中的订单集合拣选时,拣选顺序不分先后,由系统给定拣选路径(按照亚马逊实际情况做出假设)。

6.由于是随机存储,同一个商品,在仓储中可能会存放在不同的位置。

7.仓储的过道、通道、货架的宽度、深度均为已知,在波次划分好之后,其拣货距离可以直接计算出来。

8.假设手推车有容量限制,因此同一个波次的商品总数不能超过M。

9.已知拣选单上的商品存储位置,拣选时按照S型路径行走,不存在缺货、补单等情况。

10.拣货员每次拣选完成一个波次后,需要将商品送到输入/输出点,即中转站,定义为I/O处,才可以开始下一个波次的拣选。

11.引力模型构建时,由于随机存储情形下从存放商品的本身地理位置特征构建订单相似度是最准确的,因此不同商品之间的引力大小只与商品的储位位置有关,其经济质量等因素可以归为统一常数φ,不会影响最终波次划分结果。

12.仓储中心为双区型仓储,这也是实际中运用最广泛的存储方式,平面图如图1。

图1 仿真时仓储平面图

(二)单个波次内引力模型构建

首先考虑波次内订单已经确定时,选择商品储位,以使得该波次引力最大的储位决策问题。在随机存储环境下,由于同一个商品可以存储在在仓库中多个位置,考虑每一个订单内商品取不同储位时,该波次中所有商品之间的引力值之和,使得这个引力和最大的储位决策即为在随机存储情形下该商品需要选取的储位。根据这个最大的引力和确定该波次中每一个商品的确定储位位置。

模型构建如下,对于任意一个波次z,其引力大小T z可以表示为:

其中:T z为第z个波次的总引力。(X zir,Y zir)为波次z中第i个商品的第r个存储位置的坐标;R i表示波次z中商品i一共有的储位个数,R j表示波次z中商品j一共有的储位个数。r i、r j为决策变量,表示商品i、j的第r i、r j个存储位置(r i=1,2,…,R i、r j=1,2,…,R j)。Q z为第z个波次中含有的商品总个数。i、j为下标(i=1,2,…,Q z、j=1,2,…,Q z),φ为引力模型参数。

上述问题可以用来在随机存储情形下给定波次的情况下,求解选取的对应商品的最优储位位置。

因为拣选时必须经过I/O点(i=0),因此构建模型时将I/O点当做一个商品,也考虑它与其他商品之间的引力。

(三)划分方案目标函数构建

从上分析,可以获得每一个波次订单内的总引力大小。接下来将运用0-1规划对波次进行划分。以总订单被分成不同波次后,所有波次订单的引力之和作为目标函数,使得该目标函数最小的分配方案即为最优的分配方案。

本问题中的各符号定义如下:

C i为订单i的商品个数,

M为每个波次的最大商品数,N为订单数,B为波次数目。因此,利用引力模型构建的随机存储情形下订单分批模型如下:

约束条件有以下:

T z由式(1)给出。

其中,第一个、第二个约束使得最终的解是0-1变量,第三个约束使得每一个订单只能被划分到一个波次中,第四个、第五个约束保证一共划分B个波次,第六个约束保证每个波次中最大商品数不超过M(由推车容量和商品体积所决定)。

四、实证分析

(一)问题说明

根据企业实际情况,随机生成算例求解模型。为了与企业实际情况对应,并保证具有一定的普遍性,构建算例时采用双区域型仓储货架,这种类型的区域货架会比单区域货架的情形更加复杂。整体的仓储中心布局如下:

为使得距离的计算更贴近实际情形,本文数值设置按照企业实际情形等比例对应。设置对应的d1、d2、d3、…、d6值,该值可以根据企业实际情况等比例缩小,这里取的是:d1=2,d2=2,d3=1,d4=4,d5=1,d6=4,并且区域类货架总数为40个,订单数为20个,波次数最大不超过订单数的一半,即10个,总商品类别数为30个,每个商品在该库存中最多有5个储位。

根据这些设置,通过visual st udio C++2010编写程序,随机生成一批订单,该每个订单都有相应的商品信息,每一个商品在该库存中都有相应的存储位置,依据随机生成的订单,最终构建模型,对该批随机生成订单进行求解,最终分析求解结果与普通波次划分方法的区别。并且,为了与随机存储情形对应,每一个商品都会随机生成多个储位。

(二)问题求解

1.波次的划分

为了对生成的随机订单进行波次划分,首先需要将模型在程序中实现,遗传算法运行结果如图2。

运用遗传算法求解随机存储情况下波次划分模型,遗传1 000代时,划分结果为:

波次1:5、8、12、17

波次2:9、15、18、20

波次3:1、2、3、6、7、10、13

波次4:4、11、14、16、19

图2 遗传算法求解模型目标值结果

2.波次订单拣货路径长度求解

由于在实际企业亚马逊拣选过程中,采用的是S型拣货规则,因此,波次划分完成后,需要求解该划分情形下采用S型拣货路径所需要行走的总拣货距离。显然,在求解拣货距离是相当于求解TSP旅行商问题,本研究直接通过构建遗传算法求解通过分不同的情况,能够将划分好的波次按照实际过程中的拣选原则(S型),最终估算出行走的路径长度,进而可以很好的衡量波次划分效果。

通过遗传算法实现TSP问题,最终求得各波次订单的最优拣货顺序,进而总共需要行走的S型拣货距离,整个划分方案的最终拣货路径长度为:

3.方案对比

将当前的最优波次划分和拣选路径求解方法与传统的只考虑商品类别、不考虑商品存储位置的聚类方法,比如层次聚类算法加以比较。这类方法通过构建数据之间的连接性,一层一层的聚合,不断的反复运行,使得最终展现出一种层级架构的方法。参照已有学者的研究,采用传统的聚合方法进行聚类分析。即首先每一个订单为一个单独的类,计算不同类之间的距离,即不同类中不重合商品的个数,合并距离最小的两个类,得到一个新类,类的个数减1,合并距离最小的两个类,得到一个新类,类的个数减1,依次类推。

同样,通过遗传算法实现TSP问题,最终求得各波次订单的最优拣货顺序,进而总共需要行走的S型拣货距离,划分结果为:

波次1:1、3、8、12、15、18、20

波次2:2、6、10、17、9、14、19

波次3:4、13、16

波次4:5、7、11

总共需行走的S型距离为:两种波次划分方法效果对比后,可以看到,随机存储情形下基于商品引力大小构建的波次划分模型,要比传统的基于订单聚类划分的方案更优,拣货行走距离减小12.7%。通过随机生成不同的订单、储位信息,多次构建模型求解,并与传统的波次划分方案对比,得出的结果如表1。

可以看到,本研究在随机存储情形下,采用的引入引力模型的方法得到的波次划分方案比传统的基于聚类的波次划分方案更优,多算例计算得出拣货行走距离平均减小了15.3%。

表1 多算例情形下两种不同的波次划分方法的对比

五、总结与讨论

本文从实证的角度研究在随机存储机制下订单波次划分的问题。对于仓储管理而言,构建考虑随机存储情形下,各种订单组合后取不同的储位形成的S型拣货路径的大小这一模型,并加以求解,是十分困难的,这是一个NP问题。而本文将引力模型引入,只从商品自身储位地理位置出发,以波次内不同储位的商品之间的引力大小,来衡量订单之间的相似度,从而进行订单的波次划分。最终,通过随机生成多组仿真算例,将本研究的模型和传统的波次划分模型进行对比,发现拣货行走距离有所缩短,归纳得出,基于引力模型构建的波次划分方案相比于传统的波次划分模型S型拣货路径更短,拣货效率更高,拣货行走距离平均减小了15.3%。

在此基础上,可以进一步讨论随机存储情形下波次任务分配问题,比如对于同一个波次,会考虑拣货员对该波次商品所在区域的熟悉程度,会优先将该波次分配给对这个波次更加熟悉的拣货员分拣,这种方法一定程度上可以缩短所有订单拣选完成所需要的时间。

[1]Dr ury J.Towar ds More Efficient Or der Picking[R].I MM Monograph No.1,The Institute of Materials Manage ments,Cranfield,U.K.,1988.

[2]Chen M C,Wu H P.An Association-based Cl ustering Appr oach to Order Batching Considering Custo mer Demand Patter ns[J].Omega,2005,33(4):333-343.

[3]石贤光.基于引力模型的中原城市群空间发展模式研究[D].南京:南京航空航天大学,2008.

[4]陈彦光,刘继生,基于引力模型的城市空间互相关和功率谱分析——引力模型的理论证明、函数推广及应用实例[J],地理研究,2002(6).

[5]李冠仕.B2C电子商务物流网络优化技术的研究与实现[D].上海:上海交通大学,2013.

[6]周丽,朱杰,郭键.分类存储返回型与S型拣选路径随机模型的比较研究[J].系统科学与数学,2011(8).

[7]Haus man W H,Sch warz L B,Graves S C.Opti mal Storage Assign ment in Auto matic Warehousing Systems[J].Manage ment Science,1976,22(6):629-638.

[8]Brynzér H,Johansson M I.Storage Location Assign ment:Using t he Product Str ucture to Reduce Or der Picking Ti mes[J].Inter national Jour nal of Production Econo mics,1996,40(46-47):595-603.

[9]Petersen C G,Aase G R,Heiser D R.I mproving Or der-picking Perfor mance Thr ough the Implementation of Class-based Storage[J].Inter national Jour nal of Physical Distribution&Logistics Manage ment,2004,34(7):534-544.

[10]董溪哲,李松龄,杨波.仓储货位选择优化问题的研究[J].科技资讯,2006(17).

[11]朱子音.提高库房利用率方法研究[D].长春:吉林大学,2008.

[12]Acker man K B.Practical Handbook of Warehousing[M].Springer Science&Business Media,2012.

[13]Gibson D R,Sharp G P.Order Batching Procedures[J].Eur opean Jour nal of Operational Research,1992,58(1):57-67.

[14]Gade mann A,Van Den Berg J P,Van Der Hoff H H.An Or der Batching Al gorit h m f or Wave Picking in A Parallel-aisle Warehouse[J].IIE Transactions,2001,33(5):385-398.

[15]Choe K,Shar p G.Small Parts Or der Picking:Design and Operation[R].Geor gia Tech Research Corporation,Atlanta,Georgia,1991.

[16]Chen M C,Wu H P.An Association-based Cl ustering Approach to Order Batching Considering Custo mer De mand Patter ns[J].Omega,2005,33(4):333-343.

[17]Tang L C,Chew E P.Or der Picking Syste ms:Batching and Storage Assign ment Strategies[J].Co mputers&Industrial Engineering,1997,33(3):817-820.

[18]李诗珍,王转.订单拣取路径优化研究[J].物流技术与应用,2002(5).

[19]马士华,文坚.基于时间延迟的订单分批策略研究[J].工业工程管理,2004(6).

[20]李云.基于波次分拣的图书配送中心分拣效率研究[D].武汉:华中科技大学,2013。

[21]郑凌莺.物流中心仓库货位优化算法的研究[J].商场现代化,2006(22).

F715.1

A

1003-1154(2016)04-0101-05

10.3969/j.issn.1003-1154.2016.04.028

国家自然科学基金青年基金(71202068);上海交通大学文理交叉基金重点项目(14JCY02)。