一种两类货到人订单拣选系统机械工程学报六十年庆

1、一种两类“货到人”订单拣选系统的适用性选择方法王艳艳1 周以齐2 沈长鹏1 吴耀华1(1山东大学控制科学与工程学院 山东 济南 250061； 2山东大学机械工程学院 山东 济南 250061)摘要：本文提出了一种在两类“货到人”订单拣选系统（即AS/RS系统和Carousel系统）之间，根据不同订单类型进行系统适用性选择的系统化方法。订单拣选系统最常用的两种作业策略分区策略和分批策略本质上都是对订单的聚类，因此订单可以被分为很多一维单元化网格；根据各系统的逻辑运动关系，可得到单元化网格的拣选时间表达式；利用作业时间模型和空间填充线，对单元化网格进行聚类，得到二维系统的总订单拣选时间，并采用遗

2、传算法、蚁群算法、粒子群算法三种常用智能算法分别计算各系统的最优值；通过比较各系统的时间选择更适用的系统，即选择总订单拣选时间更小的系统。本文通过对四类不同类型的订单进行实验研究，初步得出两类系统对四类订单的适用性分析和系统参数敏感性分析。关键词：订单拣选系统；货到人；订单网格化聚类；智能算法；适用性；选择中图分类号：F253.5An Applicability Selection Method of Two Parts-to-picker Order Picking SystemsWANG Yan-yan1 Zhou Yi-qi2 Shen chang-peng1 WU Yao-hua1 (

3、1 School of Control Science and Engineering, Shandong University, Jinan 250061, China；2 School of Mechanical Engineering, Shandong University, Jinan 250061, China )Abstract：A systemic method is presented to choose the suitable order picking system between AS/RS system and Carousel system for differe

4、nt types of customer orders. As both batching and zoning, the two frequently-used operational policies, are essentially order clustering, the customer order sheet can be divided into many unit grids. After the time formulation for each system in one-dimensional unit is defined according to the logic

5、al movements, we present a time sequence models for two-dimensional systems and use filling curves to link the one-dimensional unit grids. Three intelligence algorithms, which are genetic algorithm, ant colony optimization algorithm and particle swarm optimization algorithm, are adopted to search th

6、e optimal value for each system. In the experimental study, we not only get the suitability of each system for given orders with the hypothetic value of parameters by comparing the order picking time, but also discuss the effect of some key factors on suitability such as zone number and batch size.K

7、ey words：Order picking system; parts-to-picker; order cluster; intelligence algorithm; applicability; selection0 引言* 国家自然科学基金资助项目(50175064)。XXXXXXXX收到初稿，XXXXXXXX收到修改稿订单拣选消耗了配送中心内的主要劳力，决定着对下游客户的服务水平，是配送中心内部最重要的作业流程1。选择合适的订单拣选系统对于提高订单拣选效率、提高客户服务水平，有着至关重要的作用。文献2将实践中应用最多的采用人工的订单拣选系统分为人到货、推式、货到人三类系统。其中，货

8、到人拣选系统由于自动化程度较高、具有仓储和分拣一体化的特点，已逐渐得到越来越多的应用。常用的货到人拣选系统主要包括自动存储及取货系统（以下简称AS/RS系统）和旋转式货架系统（以下简称Carousel系统）。AS/RS多数系统采用巷道式提升机获取一个或多个存货单元，并运至巷道终端的拣选工位，由拣选员拣取所需数量的物品，剩余的将被送回至原存储位3。Carousel系统由旋转布置于双向闭环上的大量料架或厨柜组成4，需要拣选物品时所有存储位上的物品同时向拣选位运动。不同的拣选系统适应于不同的订单类型。但是，目前对AS/RS系统和Carousel系统的研究主要集中在各自独立的控制、调度、优化、设计等方

9、面，对于两者针对不同订单的适用性比较研究还很缺乏。本文根据订单拣选系统最常用的两种作业策略（分批策略和分区策略）对订单进行网格化聚类，并结合各系统的逻辑运动关系和作业时间模型，计算各系统的总订单拣选时间，通过比较时间选择更适用的系统（即时间更小的系统）；本文还通过对四类不同类型的订单进行实验研究，初步得出两类系统对四类订单的适用性分析和系统参数敏感性分析。1 订单网格化聚类1.1 作业策略订单拣选系统实际应用时可采用不同的作业策略，作业策略不同则所需的订单拣选时间也不同。因此订单拣选系统比选时，各系统均须在相同条件下选择各自最优的策略再进行比较。与订单拣选系统相关的作业策略包括分区、分批、仓储

10、、布局、路径、合单及分拣等5，其中布局、路径、合单及分拣与配送中心和订单拣选系统的具体尺寸密切相关，在系统选择阶段没有各类具体尺寸的前提下，重点应考虑的策略是分区、分批和仓储策略。1.2 基于订单网格化的分区和分批策略分区策略是指将拣选区划分为很多区，每个区指派一名拣选员负责本区的拣选工作。常用的分区策略包括串行分区和并行分区，“货到人”拣选系统适用并行分区，即各区的拣选员同时拣选一个或一批订单行，各自的拣选完成后再开始下一个或下一批订单行的拣选。分批策略是指将多个订单行合并为一个批次，在一个行走过程中完成本批所有订单行的拣选。分区策略和分批策略本质上都是对订单表的聚类，分区是将物品聚类到一个

11、区内，分批是将订单行聚类到一个批次内。应用分区和分批策略后，订单表可以被划分为M行N列的网格，如图1所示。图1 网格化聚类的订单本文用(m,n)表示第m行第n列的网格，即第m批订单行和第n个物品分区，其中1mM，1nN。同时，定义表示每个订单行的序号，表示每个物品的序号。1.3 基于COI的仓储策略本文用Heskett提出的单位订单行容积指标COI，来进行每个分区内的储位分配优化6。COI是某物品所需仓储空间和被订购频次的比值，如公式（1）所示；物品按照COI进行升序排列，并按非降序从开始端逐个进行储位分配。 (1)其中，是物品j所需的空间，是物品j被各订单行访问的总次数。可由Barthold

12、i提出的Fluid模型进行求解7。Fluid模型证明了为保证最少的从仓储区到拣选区的补货次数，物品j在分拣区所需空间的比例应为：(2)其中，为每个物品j的年销量。则本文定义物品j所需的空间为：(3)其中，为的平均值；为和比值后取整；若，则设。2 系统作业时间建模2.1 订单拣选作业时间构成根据某些调查，订单拣选时间可分解为行走、寻找、拣取、安装及其他等时间8，如表1所示。表1 订单拣选作业时间构成活动所占总时间比例行走50%寻找20%拣取15%安装10%其他5%对于“货到人”订单拣选系统，寻找、安装及其他活动可以忽略，行走和拣取是构成订单拣选作业时间的主要活动。2.2 一维单元化网格的作业时间

13、2.2.1 AS/RS系统的一维作业时间自动堆垛机可采用不同的作业模式：单命令循环、双命令循环和多命令循环。单命令循环是指一个存货单元从拣选位运至存储位或者从存储位运至拣选位。双命令循环是指一个存货单元从拣选位运至存储位，然后下一个存货单元从货架上获取。多命令循环是指自动堆垛机具有一个以上的叉伸位，可以在一个循环获取或存放多个存货单元9。本文选择实际应用最多的双命令循环模式作为AS/RS系统的应用策略。图2 AS/RS系统的运动逻辑AS/RS系统在一维网格(m,n)中的作业时间为：(4)其中，为网格(m,n)的拣选时间；为第n个区内物品的品种数；为堆垛机在第m批订单行、第k次行程取货时的行走时

14、间；为在仓储位取货的时间；为堆垛机从取货位到拣选位的行走时间；为拣取物品的时间；为堆垛机从拣选位返回取货位的行走时间；为物品被拣选的位置；为每物品仓储位的长度；为堆垛机行走速度；为每类物品的取货时间；为(m,n)内的物品品种数；为每个物品的拣取时间；为(m,n)内的物品个数。2.2.2 Carousel系统的一维作业时间在Carousel系统中，所有存储位上的物品同时向拣选位运动，所以从存储位到拣选位的距离总体上要小于AS/RS系统，尤其是所需物品的存储位相邻时更为明显。由于Carousel系统可双向旋转，可采用的旋转策略主要有两种：单向旋转SD策略和最近物品NI策略。SD策略是指Carous

15、el总是按照一个方向进行旋转，而这个方向是由第一次拣选时距离拣选位最近的需拣选物品的位置决定的； NI策略是指Carousel总是以拣选位为基准，向最近的需拣选的物品旋转。文献10证明了NI策略下的行走时间永远不大于SD策略下的行走时间，因此我们采用NI策略。图3 Carousel系统的运动逻辑Carousel系统在一维网格(m,n)中的作业时间为：(5)其中，为网格(m,n)的拣选时间；为第n个区内物品的品种数；为第m批订单行、第k次行程取货时所需物品从仓储位到拣选位的行走时间；为拣取物品的时间；为物品被拣选的位置；为每物品仓储位的长度；为旋转货架的旋转线速度；为每个物品的拣取时间；为(m,

16、n)内的物品个数。2.3 二维系统的总体作业时间2.3.1 基于空间填充线的二维系统利用空间填充线可将一维的单元化网格连接为二维或三维系统11。本文以二维系统为研究对象，“货到人”系统采用并行分区策略后的二维系统布局，如图4所示。图4 “货到人”系统的二维系统布局2.3.2 二维作业时间模型“货到人”系统采用并行分区策略，各分区可以有两种并行作业模式：一种是所有分区全部完成某批订单行的拣选后再开始下一批订单行的拣选，另一种是本分区完成某批订单行的拣选后就开始下一批订单行的拣选。本文选用前一种作业模式，具体模型如图5所示。图5 “货到人”系统的并行作业时间模型由模型知，每一批订单行的累积作业时间

17、为：(6)第一批订单行的累积作业时间为： (7)则，二维系统的总订单拣选时间为： (8)3 目标函数与遗传算法3.1 目标函数以效率为标准，显见应当选择耗时最少的系统作为优选方案。我们以两种系统同等条件下各自最优的总订单拣选时间的比值为判断标准。之所以选择最优的总订单拣选时间作为比较的因素，是因为在现实应用中，任何一种系统都会合理使用分区、分批等各种作业策略以使自身的总订单拣选时间趋于最优。 (9)其中，、分别为AS/RS、Carousel系统的最优的总订单拣选时间。当R>1时，选择Carousel系统；反之，选择AS/RS系统。R越大，则选择Carousel系统的趋势越大；反之，则更该

18、选择AS/RS系统。对于AS/RS、Carousel系统总订单拣选时间公式里的各参数，, , , 由订单拣选系统本身决定，而, , , 由订单聚类方式决定。对于给定的订单拣选系统，参数, , , 为常量，因此寻求订单拣选系统最优的总订单拣选时间的途径是寻找最合理的, , , ，即最优的订单聚类方式。3.2 智能算法最优的总订单拣选时间与最优的订单聚类方式之间存在何种逻辑关系很难直接数理推导，只能通过启发式算法去探求。本文采用遗传算法、蚁群优化算法、粒子群优化算法三种常用的启发式智能算法来获取最优的订单聚类方式，进而求得最优的总订单拣选时间。客户订单实质上可以看作是由若干行订单和若干列物品组成的

19、矩阵，该矩阵进行如图1所示的网格化聚类后，将得到如图6所示的“订单/物品”矩阵。图6 “订单/物品”矩阵其中，表示矩阵中的某个单元化网格，即第n个分区内的第m批订单；, 表示第i个订单行所在单元化网格的批次编号，其取值为，M表示订单批次的数量；, 表示第j个物品所在单元化网格的分区编号，其取值为，N表示物品分区的数量。为方便地表示“订单/物品”矩阵的变化，我们用I+J位的一维编码表示I行J列的二维矩阵，如下所示。当第i位或第j位编码的值发生变化时，表示订单行i所属的批次或物品j所属的分区发生变化，即矩阵的聚类发生变化；此时对应的目标函数值即订单拣选时间。通过搜索最优的一维编码值的组合，就可以寻

20、得最优的订单拣选时间。3.2.1 遗传算法遗传算法的优化机理与本问题的特性非常匹配，一维编码相当于遗传算法中的基因，订单拣选时间相当于适度函数。设和为基因，则可以组成具有I+J个基因的染色体。为寻找适度函数的近似最优解，可按如下步骤执行遗传算法。（1）初始化。随机产生一组个体作为初始种群，每个个体对应于一组一维编码，即一个订单聚类方式。（2）评价。计算种群中每个个体的适应函数值，即总订单拣选时间函数。（3）选择。运用轮盘赌规则选取拥有最低适应函数值的多个个体，并赋予作为下一代父辈的更高的概率。（4）交叉。按照一定的交叉概率，在“选择”操作后的种群中两两选取两个个体作为父辈，两个父辈均从和的交界

21、处切开，每个父辈的前半部分与另外一个父辈的后半部分组合。（5）变异。按照一定的变异概率，在“交叉”操作后的种群中选取用于变异的个体，并给所选取个体的某个基因赋予另外一个可行的值。（6）替换。在完成选择、交叉、变异后，如发现更低的适应函数值，则对最不适合的父辈用其子辈替换掉。（7）重复。从第2步开始重复，当迭代次数达到上限时遗传算法终止。3.2.2 蚁群优化算法蚁群优化算法同样可以用于求解最优的一维编码和最优的订单拣选时间；一维编码相当于蚂蚁寻找食物的路径，各位编码相当于蚂蚁每一步所经历的各个节点（可重复），最小的订单拣选时间是蚁群寻找的食物，订单拣选时间值为适度函数，本文设最小的订单拣选时间为

22、0并以迭代上限次数为终止条件。（1）初始化。给信息素矩阵赋一个相同的常数值，给禁忌表赋一个随机初始值。（2）路径选择。每个蚂蚁在第一步选择要经历的节点时，根据概率进行选择，概率与信息素有关，信息素越大，则被选择的概率越大；当所有的蚂蚁选择完编码以后，开始选择下一个编码，直到所有蚂蚁完成一次周游为止，即每只蚂蚁均有一个一维编码。每只蚂蚁的路径存于禁忌表中。（3）根据蚂蚁的路径（即一维编码），计算所有蚂蚁的适度函数值。寻找本次迭代的局部最优函数值和路径。（4）进行全局信息素更新：子代的信息素按照适度函数值的倒数增加，同时子代的信息素相对于父代的信息素按照固定的衰减比率进行衰减。（5）禁忌表清零。（

23、6）循环，直到迭代次数达到上限。3.2.3 粒子群优化算法粒子群优化算法根据粒子的速度来寻求最优解；一维编码相当于粒子寻找食物的方向，订单拣选时间值相当于粒子寻找食物的速度；在粒子群优化算法中，粒子具有记忆性，只有速度最大的粒子给出方向信息给其他的粒子，整个搜索更新过程是跟随当前最优解的过程。（1）初始化。给粒子群中的每个粒子赋一个随机初始方向即一维编码的值。（2）速度计算。计算出本代中每一个粒子寻找食物的速度，即一维编码所对应的订单拣选时间值距离最小订单拣选时间0的远近，订单拣选时间值越小表明粒子的速度越大。（3）粒子选择。比较本代速度最大粒子（即局部最优解）与全局速度最大粒子（即全局最优解

24、）的速度值，速度更大（即订单拣选时间更小）的粒子将作为新的全局速度最大的粒子。（4）信息传递。将全局速度最大粒子的方向作为下一代粒子群的主要方向，并允许一定的随机选择；本文以全局最大速度粒子的每一位一维编码值为均值，按照正态分布确定下一代各粒子的一维编码值。（5）记忆表更新。将全局速度最大的粒子的方向（即一维编码）和速度值（订单拣选时间值）存入记忆表中。（6）循环，直到迭代次数达到上限。4 实验研究4.1 输入分析4.1.1 试验订单为评价系统对于不同订单的适用性，本文根据订单密度（即订单中累计被订购品种数占累计总品种数的比例，亦即订单矩阵中非0的比例）和订购数量（即被订购品种所被订购的数量范

25、围）产生了四种典型订单。对每种订单，我们均假设有大客户、大品牌的存在，即假设订单行和物品均服从于正态分布，如图7所示。图7 各类订单的物品服从正态分布订单的主要参数如表2所示。表2 订单的主要参数因素值订单行数400物品种数400订单密度20%, 80%订购数量1, 1100.5m4.1.2 系统参数订单拣选系统的参数对订单拣选时间的影响很大。为保证公平的比较，我们设置多数参数具有相同的值，如表3所示。表3 拣选系统的主要参数参数单位AS/RS系统Carousel系统s22s10s11m0.50.5单批订单行数1,2,3,4,5物品分区数2,3,4,5,64.1.3 算法参数通过测试比较多组值

26、，我们设定了求解效果较优的遗传算法的参数值，如表4所示。表4 遗传算法的主要参数参数值种群10迭代次数100交叉概率0.8变异概率0.01表5 蚁群优化算法的主要参数参数值种群10迭代次数100信息素蒸发系数0.5表6 粒子群优化算法的主要参数参数值种群10迭代次数100精英原则正态分布4.2 输出分析4.2.1 系统适用性分析根据设置的参数值和实验订单，进行仿真后，得到两系统拣选时间的比值R，通过比较R与1的大小，就可以判断实验订单对于两种系统的适用性。对于本例中的所有实验订单，R均大于1，所以Carousel是更加适合的拣选系统，如图8所示。事实上，在实际应用中AR/RS系统更多的是作为仓

27、储系统使用，而不是作为拣选系统使用。AS/RS系统要作为拣选系统有更广泛的应用，需要做某些改进，如：某类国外医药企业较多采用的AS/RS系统，每层货架都有一个堆垛机，大大提高了分区策略的应用，总的订单拣选时间大大降低。此外，通过观察R值大小可见，订单密度越大、拣选数量越小的订单越适合选用Carousel系统。图8 各类订单的适用性和敏感性4.2.2 参数敏感性分析通过观察每条曲线的相对位置和自身斜率，我们可以发现：分区数量N越大，则R越小，则越适合采用AS/RS系统；分批数量M越大（即每批次所含的订单行越少），则R越大，则越适合采用Carousel系统。同时，对比R值的变化幅度，可以发现：分区

28、策略比分批策略对系统选择的影响更加显著。5 结论与研究展望通过实验研究，我们可以发现本方法不仅能够较好地应用于系统的选择，还可以用于主要参数的敏感性分析。粗略地讲，对于经典的AS/RS系统和Carousel系统，Carousel系统更适用于多数订单；而且，订单的订单密度越大、拣选数量越小，则越适合采用Carousel系统。此外，一些主要参数如分区数量、分批数量等对于系统的选择具有一定的影响，其中分区数量M的影响显著。本方法的不足是需要一定的时间开发系统和运行计算。如果通过测试大量的实验订单或实际订单能够发现某些定律或指标，那么我们就可以通过短时间内对订单的观察来决定系统的选取。潜在的定律可以用

29、订单行数、物品品种数、订单密度、订购数量、物品或周转箱尺寸、订单行和物品的分布函数等参数来进行描述。参考文献：1. BURINSKIENE A. Order picking process at warehousesJ. International Journal of Logistics Systems and Management, 2010, 6(2):162-782. DALLARI F, MARCHET G, MELACINI M. Design of order picking systemJ. International Journal of Advanced Manufactu

30、ring Technology, 2009, 42:1-123. MANZINI R, GAMBERI M, REGATTIERI A. Design and control of an AS/RSJ. International Journal of Advanced Manufacturing Technology,2006,28:766-7744. BATHOLDI J J, PLATZMAN L K. Retrieval strategies for a carousel conveyorJ. IIE Transaction, 1986, 18:166-1735. KOSTER R D, LE D T, ROODBERGEN K J. Design and control of warehouse order picking: A literature reviewJ. European Journal of Operational Research, 2007, 182