仓储中心拣选作业研究综述

拣选作业 (order picking, 又称拣货作业, 配货作业) , 是指根据客户订货单所规定的商品品名、数量和储存储位, 将商品从货垛或货架上取出, 并分放在指定货位, 完成用户的配货要求的过程。拣选过程一般包括订单的分批, 订单拣选顺序和货品拣选顺序合理安排等。拣选作业是整个仓储作业中劳动最密集、运营成本最高的环节。制造业正朝着单次批量小、批次数量多、响应时间短的方向发展。同时, 很多配送中心为了争取到更多的客户开始接受延迟订单 (late order) , 因此对发货速度的要求越来越高了。大量的规模较小的仓库正在被少数的规模较大的配送中心所取代, 为了赢得市场, 这些配送中心都在朝着日配送量大、配送时间短的方向发展。制造业和配送中心的发展趋势使拣选系统的设计和管理变得越来越重要, 同时也变得越来越复杂了。

拣选系统的追求目标是在一定资源条件下, 实现服务水平的最大化。而服务水平又与订单交货时间、订单完整性和订单准确性等多个因素相关。其中, 按订单迅速找到客户所需的货物并完成装运是提高配送企业服务水平的关键, 因此, 实现拣选时间的最小化是所有拣选系统共同追求的目标。拣货时间、行走时间和找货时间是构成拣选时间的三个主要因素, 其中行走时间又占到整个拣选时间的55%。因此, 行走时间或者说是行走距离是进行仓储设计和优化时考虑的首要问题。国内外围绕减少行走距离, 提高拣选效率的研究主要集中在以下几个方面:布局设计 (layout design) 、储位指派 (storage assignment) 、分区拣选 (zoning picking) 、批次配货 (Order Batching) 和配货路径规划 (routing) 。

2布局设计

拣选作业中的布局主要包括容纳拣选系统的设施布局 (facility layout) 和拣选系统内部的布局 (internal layout) 。设施布局考虑不同部门 (如接收、拣货、存储、排序和配送等) 间的布局, 通常根据不同部门间的活动关联进行规划, 其目的是实现控制成本的最小化。文献[1]描述了几种有效的设施布局的设计过程。

内部布局设计, 也称为巷道配置问题 (aisle configuration problem) , 考虑block的数目, 以及拣选区中每个block中的巷道的数量、长度和宽度。通常是寻找关于某一目标函数的“最好”的仓库布局, 且最常见的目标函数就是行走距离。

对人工拣选系统的内部布局设计的研究并不是很多。文献[2]使用分析和仿真的方法, 在仓储内部布局的基础上对存储策略进行了研究。文献[3]为确定巷道布局提出了非线性目标函数, 用于实现采用随机存储策略的仓储中心的行走距离的最小化。同样是平均行走距离的最小化为目标, Caron等人对基于COI (cube-per-order index) 的存储策略下布局设计进行了研究[4]。

相对于人工拣选系统, 对自动存取系统 (AS/RS, Automated storage and Retrieval system) 的内部布局设计问题的关注要多一些。Bozer和White的研究表明, 当采用随机存储策略时, 货架的高度与长度的比与拣选设备的垂直运动速度与水平运动速度的比应一致[5]。Larson等人1997年采用启发式方法实现布局设计, 并根据货品重量为货品指派存储位置, 以达到提高地面空间利用率和降低行走距离的目的[6]。

在根据客户订单对货物进行拣选之前, 货物必须要先保存在仓储中心内的具体储存位置。储存作业应考虑最大限度的利用空间, 最有效的利用劳动力和设备, 最安全经济的搬运货物, 最良好的保护和管理货物。存储指派方法可以定义为用于为产品指定存储位置的一组规则。好的储存策略可以减少出入库的移动距离, 缩短作业时间。下面对常采用的五种存储策略进行讨论, 它们分别是随机存储 (random storage) 、最近可用

存储 (closest open location storage) 、定位存储 (dedicated storage) 、全周转率存储 (full-turnover storage) 和分类存储 (class-based storage) 。

随机存储将入库的每一托盘或一定数量的货品, 按相同的概率指派到任意可使用的存储位置。每一个货品被指派的储存位置不是固定的, 而是随机且可以改变的, 也就是说, 任何品项可以被存放在任何可利用的位置。由于存储位置可以共用, 储区空间的利用效率较高, 但货物的出入库管理及盘点工作较难进行。同时, 因为周转率高的货品可能被储存在离出入口较远的位置, 增加了出入库的搬运距离;且具有相互影响特性的货品可能被存储在相邻位置, 可能造成货品间的相互伤害或发生危险。对随机储存系统与定位储存系统的模拟实验, 发现定位存储系统相对于随机存储系统可节省35%的移动储存时间, 但却增加了30%的储存空间。随机存储指派方法通常以增加行走距离为代价获得较高的空间利用率。随机存储策略一般只在计算机控制环境下采用。

如果允许存储作业人员自主选择他们所存储货物的存储位置, 那么得到的存储系统就是最近可用存储系统。也就是说, 货物会被指派到存储作业人员所遇到的第一个可用的存储位置。因此, 货物通常按其入库时间的先后顺序被储存于距离出入口 (depot) 由近至远的存储位置。如果仓储中心中存在空闲的存储位置, 在这种存储指派方法下将会出现如下现象:越接近出入口位置的货架越满, 越接近仓库后面的货架越空。Hausman等人认为在以托盘为单位进行作业时, 随机存储策略和最近可用存储策略具有相似的执行效率[7]。

如果采用定位储存策略, 那么每一项货物都有固定的储位, 货品不能互用储位。定位储存的一个优点是每种货品都有固定储存位置, 拣货人员对货物的位置比较熟悉。这种存储策略的一个缺点是即使货物不在储位, 其存储位置也要保留。此外, 这种指派方式要求每一种货物规划的储位容量不得小于其可能的最大库存量。因此是空间利用率最低的一种存储指派方式。

零售企业的仓库中产品与位置 (product-to-location) 的指派通常与商店的布局相一致, 因为产品按逻辑进行了分组, 可以减少店铺中的工作量。此外, 可按周转率大小或出货频率安排货物的存储储位, 从而缩短出入库时货物搬运的距离;还可根据货物的特性安排其存储位置, 从而降低货品之间的不良影响。最后, 如果产品重量不同, 固位存储策略也是有帮助的。将较重的货物放在货盘的底部, 较轻的货物放在货盘的顶部。通过将货物按重量进行排队并安排相应的工人拣货, 可以在不增加劳动的同时获得较好的堆垛顺序。

全周转率存储根据货物周转率确定它们在存储区域的位置。通常销售率最高的货物被摆放在最易取得的位置, 如靠近出入口的地方;搬动速度低的产品通常位于仓库后面的存储位置。早期的全周转率存储策略是Heskett的体积订单指数 (Cube-Per-Order Index, COI) 规则。一类货品的COI定义为一定时期内, 货品所需全部空间与订单数的比, 并将COI值最低的货物安排在距离出入口最近的位置。相关研究还有Kallina and Lynn的文献[8], Malmborg的文献[9]。

实际中, 全周转率存储和定位存储的结合较易实现。其缺点是由于用户需求经常变化会导致产品COI排序的频繁变化。采取基于COI或其他需求频率的定位指派方法, 与随机存储相比需要更多的信息, 因为必须对订单数据和存储数据进行加工以对货品排序和指派。

分类存储, 将所有的储存货物按照一定特性划分成不同类别, 每一类货品的存放位置固定, 并按照一定的原则为同一类的不同货物指派具体的存储位置。分类储存通常按产品相关性、流动性、尺寸、重量、特性等对货物进行划分, 是以上提到的方法的组合。

在进行库存控制时, 将货物划分为不同类别的经典方法是帕雷托 (Pareto) 分析法、又称为ABC分析法, 通常由COI或拣货体积等衡量货物需求频率实现货物的分类。习惯上将移动速度最快的货物称为A类, 次快的为B类, 并依次类推。尽管在某些情况下, 更多的分类能在行走时间方面带来附加的收获, 但分类的数目通常为三个。

根据仿真实验结果, Petersen等人发现在人工拣选系统中考虑行走距离时, 全周转率存储优于分类存储方法。两者之间的差别在于类划分策略 (如, 分类数、每类占存储体积的百分比等) 以及所采用的路径规划方法。对于AR/RS系统, Yang和Van den Berg等人发现分类数为6的分类存储方法是最好的选择。这种方法的优点是可以将搬运速度快的货品存储在靠近出入口位置的同时, 又能满足随机存储所具有的灵活性和低存储空间要求。Graves等人发现为了保证入货的货品能保存到正确的区域, 分类存储必须有空闲存储位置, 类的数量会增加存储空间的需求。因此, 分类存储比随机存储需要更多的存储空间。关于分类存储的研究多集中于AS/RS。

分类储存的优点是便于畅销品的存取, 具有定位存储的各项优点;各分类的储存区域可根据货品特性再做设计, 有助于货品的储存管理。分类储存的缺点是储位必须按各项货品最大载库量设计, 因此储区空间平均的使用效率低;分类储存比定位储存具有弹性, 但也有与定位储存同样的缺点。

分区拣选是将拣选区划分为多个分区, 每个拣选人员只负责拣选订单中属于其所处分区的货物。其优点是拣货人员只需在一个较小的区域进行作业, 不但可以减少交通拥挤, 还可以使拣选人员熟悉货品在分区中的位置。分区拣选的主要缺点是由于订单在拣货时进行了分割, 在发货给客户前还必须将其进行整合。

Speaker在文献[10]中对配送中心分区策略做了一般性的介绍与说明。De Koster在1994年构建了分区拣选和传送系统的Jackson队列网络模型, 能快速估算订单的拣选时间和平均在拣订单数。De Koster通过模拟实验对结果进行了比较, 其估算结果可用于确定分拣系统大小和分区的数量[11]。Brynzér和Johansson通过案例对批次拣选与分区拣选进行了分析, 认为在串行分区 (progressive zoning) 拣选系统中, 实现拣选人员间的工作负载平衡是很重要的[12]。Jane给出了几种启发式算法用于串行分区拣选系统中不同分区中拣货人员的工作负载的平衡和分区大小的调节[13]。Jane和Laih还针对并行分区 (synchronized zoning) 分拣系统中工作负载平衡问题, 提出了货物储位指派的启发式算法。算法将出现在同一订单中的货品存储在同一个分拣区中[14]。

动态分区拣选是相对于分区大小固定的静态分区而言的, 其特点是以动态的方式确定分区的大小, 并实现分区拣选作业人员的指派和管理。将生产运作领域中bucket-brigades理念应用于分区分拣作业就是动态分区拣选的一个例子。bucket-brigades可以协调生产线上工人的工作, 以实现生产的连续进行和效率的提高。在串行分区拣选系统中, 拣货作业人员拣选完属于其所属分区的货品后将已部分完成的订单递交给下一分区的拣货作业人员, 一直到拣货作业完成。其要点是确定订单在拣货作业人员之间传递的时间。Bartholdi等人在文献中对Bucket-Brigades在配送中心中的实现进行了报告, 该方法既能提高配货效率, 又能减少管理工作量[15], 其它相关成果可参阅文献[16]。

订单拣货 (single order picking) 以订单为单位进行货品的拣取, 适用于单张订单订购品项多, 且同一品项在不同订单重复率不高的情形。对于单张订单订购品项较少的情况, 如果在一次拣选作业中完成一组订单而非一个订单的拣选就能减少拣选作业人员的行走时间。订单批次配货的思路是, 先将某一数量的订单汇总成一批次订单, 再针对该批次订单进行总量拣取, 最后再以订单为单位对所拣取品项进行二次分类。分批拣选中订单的分批方式主要有两种, 一种是订单相似度 (Order Proximity) 分批, 另一种是时间窗口 (Time windows) 分批。

订单相似度分批方法根据订单中货物的存储位置与其它订单中货物的存储位置的相似度进行订单分批。Gademann等人在2001年对人工拣货系统中的订单相似分批问题进行了讨论, 在证明问题的NP复杂性后, 分别通过分支定界 (branch-and-bound) 算法和2-opt启发式算法解决小规模订单配货问题和大规模订单配货问题[17]。订单相似度分批的关键是订单之间相似度的衡量, 常采用的两种启发式算法是种子算

法 (seed algorithm) 和节约算法 (saving algorithm) 。

种子算法又可分为种子选取和订单成批两个阶段。种子选取阶段为每批订单选择一个种子订单;订单成批阶段则确定下一步该将那一个尚未分批的订单加到当前分批。通常根据订单与种子订单的“距离”决定是否加入该订单。常见的“距离”测算方法有:增加该订单到当前批订单后所增加的需访问的巷道数;批订单中的所有货物位置的“重心”与备选订单的所有货物位置“重心”的距离;备选订单中所有货品与种子订单中货品最近的距离的和;备选订单货品位置所覆盖的区域数量。节约算法源于Clarke和Wright1964年的车辆调度问题 (VRP:Vehicle Routing Problem) 算法, 其基本思想是将大量较短的行走 (tour) 组合成少数较大的行走, 从而达到降低行走距离的目的。

De Koster等人在多货架人至物 (picker-to-parts) 拣选系统中对种子算法和节约算法进行了比较研究, 从行走时间、分批数量和实际应用等方面对算法进行了评价。结论是最简单的分批方法也比先进先服务 (FCFS, First Come First Service) 的常规分批方法效率高。同时, 种子算法与S形路径算法和较大拣选设备结合使用效率最好, 而节约算法则与最大间隙路径算法和小容量拣选设备结合使用效率最好。

时间窗口分批方式, 将在同一时间段到达的一组订单合为一个分批, 时间段的长度可以是固定的, 也可以是变化的。根据是否允许分割订单, 订单分批后的货物分类方式也有所区别:如果订单可分割, 可采用边拣选边分类的策略 (sort-while-pick strategy) ;如果订单不可分割, 则应采取分拣后再分类的策略 (pick-and-sort strategy) 。文献[18]讨论了人工拣货系统中, 订单随机达到的情况下, 时间窗口可变的分批问题。

路径或顺序优化的目的是合理安排配货顺序, 以实现行走距离或行走时间的最小化。如果将所拣取货品的存储位置抽象为点, 存储位置之间的行走距离抽象为点之间的弧, 该类型问题就是一类特殊的旅行商问题 (TSP:Traveling Salesman problem) 。按照仓储中心的分拣系统配置的不同, 路径优化问题可分为四类:传统矩形分拣系统配货路径优化问题、单元荷载系统 (Unit-Load AS/RS) 配货路径优化问题、MOB AS/RS (Man-on-Board AS/RS) 配货路径优化问题、旋转货架 (Carousel) 系统配货路径优化问题。

Ratliff和Rosenthal的S形 (S-Shape) 路径是一种最简单的配货路径, 拣货人员从巷道一端进入巷道, 沿平行货架单向移动, 并只能在巷道的另一端改变巷道。另一种简单的启发式算法是返回法 (return method) , 拣货人员从巷道的一端进入走道拣取货品, 并且从进入巷道一端改变巷道。当每一巷道中待拣取的货品数较少时, 返回法的效果较S形算法好。相关的算法还有很多, 如Goetschalckx and Raliff的算法可以实现拣货人员能双向移动时的路径规划问题[19], Roodbergen和De Koster的算法用于解决具有三个cross巷道的分拣系统中的路径优化问题[20]。

单元载荷系统中作业人员以交叉的方式进行储存操作和拣取操作, 其解决方法可分为静态算法和动态算法两类。静态算法根据给定的一组储存与拣选需求对问题进行求解, 不考虑作业期间出现的新需求;动态算法则考虑作业期间出现的新需求。

进行储存作业时, 如果采用定位储存策略, 静态拣存路径优化问题就可转化为传统的物料调配运输问题和任务分配问题, 从而得到多项式精确算法。通常认为随机储存或分类储存的静态拣存路径优化问题是NP复杂问题, 其研究重点是高效的启发式算法。Han等人1987年提出的匹配算法, 可在储存与拣选任务之间存在物品位置对应关系的前提下, 实现分拣系统中拣货人员行走距离的最小化[21]。Lee和Schaefer通过任务分配问题模型解决中等规模问题, 可找到最优或近最优的解[22]。

动态拣存路径优化算法多由静态算法发展而来, 通常的做法是先寻求已到达的拣存任务顺序的解, 再在此基础上对新加入任务进行动态重排序。人工智能技术被用于动态路径优化问题的求解, 效果良好。某些情况下, 配货作业不但要考虑人员行走距离的最小化, 还要考虑客户订单及时性的需求。因此, 在进行配货路径优化时还必须考虑订单的交货期问题。

有学者对存在临时停靠点 (Dwell Point) 的单元荷载系统的优化问题进行了研究。拣货作业人员完成某一作业后不必返回集货点或停留点, 而可停靠在某一临时停靠点, 直接等待下一作业的开始。文献[23]将前面所提出的配货排序规则、临时停靠点选择规则和储存位置分配规则应用于具有不同产品的混合配货系统, 进行仿真研究。Kim等人对一特殊的自动拣存系统的路径优化问题进行了研究, 并给出了分族启发式算法。该系统中拣货操作和储存操作不是交叉进行的, 而是完全分开的, 且集货点完全分散[24]。

在MOB AS/RS分拣系统的拣货方式与传统矩形配货系统的拣货方式相似, 也是一次性把所需货品拣选至集货点, 但移动方式不同。矩形分拣系统中, 拣选人员或设备只能沿着巷道的方向前行或后退, 且只能在巷道的首尾两端改变巷道;在MOB AS/RS系统中存在三种模式移动:直线模式 (Rectilinear norm) , 柴比雪夫移动模式 (Chebyshev norm) 和欧式距离模式

(Euclidean norm) 。

Gudehus对柴比雪夫移动模式下的路径最优问题进行了研究, 提出了分段启发式算法 (Band heuristic) 。该方法沿垂直方向把货架划分为高度相等的两部分, 下面部分货架上的货品按水平坐标由大到小的顺序拣取, 上面部分的货品则按相反顺序拣选。如果一次拣选货物较多, 可将货架按高度划分为更多相等的部分[25]。Goetschalckx和Ratliff通过凸多边形算法对相同问题进行了求解。具体的做法是, 先将水平坐标或垂直坐标最大的货品 (存储位置) 连成一凸多边形, 然后将不在凸多边形上的待拣取的货品根据Chebyshev距离特性逐一加入凸多边形, 加入的过程中遵循增加路径最小的原则[26]。分段算法与凸壳算法各有优缺点, 分段算法计算速度快、易于实现, 但解有时不理想;凸壳算法通常能得到最优或较满意解, 但计算量大、不易实现。为克服以上算法的缺陷, Bozer等人提出了1/2分段插入启发式算法, 并建议采用中心席卷算法 (Center Sweep heuristic) 求解问题[27]。

为了保证拣货人员的安全, 某些MOB拣货系统对高位货架和低处货架采取不同的移动模式。文献[28]对采用混合移动模式的拣货系统的路径优化问题进行了研究, 通过混合凸多边形启发式算法进行问题的求解。该系统在低处采用柴比雪夫移动模式, 高处采用直线移动模式。文献[29]则通过仿真对解决传统旅行商问题的邻近域搜索算法、连续插入算法和局部搜索算法等进行了比较和评估。

旋转货架系统中, 拣货作业人员或设备位于集货点, 配货时拣货人员控制货品旋转到集货点进行拣取。根据具体配置又可分为水平旋转货架系统 (Horizontal Carousel) 、垂直旋转货架系统 (Vertical Carousel) 和双向旋转货架系统 (Rotary Carousel) 三类。合理解决旋转货架系统配货作业优化调度能显著提高旋转货架系统的作业效率。

文献[30]最先提出了此类系统的拣选作业优化调度问题, 将一次拣选多个订单任务的拣选作业优化调度问题转化为每个订单中货品的拣选顺序和订单的拣选顺序。其研究表明, 在订单到达率比订单拣取率小得多时, 订单内货品的拣选顺序是关键;当订单到达率对拣选作业有显著影响时, 就必须考虑订单需求与订单配货作业之间货架的无用旋转时间了。文献[31]给出了订单顺序固定的情况下, 拣选顺序的最优问题的动态规划算法。文献[32]在此基础上将订单顺序未确定的作业优化调度问题转化为传统的中国邮递员问题, 并提出最优算法。文献[33]对双操作作业在对单旋转货架和双旋转货架下的拣选效率进行了研究, 研究表明采用双旋转货架时效率较高。Litvak等人2001年对所拣货品在旋转货架中呈独立均匀分布时货架的最小旋转距离进行了讨论, 2004年对以上问题进行了进一步研究, 计算出最小旋转距离的上界和概率分布[34,35]。