1.3 智慧拆零拣选系统研究现状

国内外对于拆零拣选系统的相关研究主要集中在人工拣选领域，De Koster等［14］对人工拣选系统的设计与控制进行了全面的研究。而在过去的十几年间，智慧拆零拣选系统的设计与优化问题已成为学术领域的研究热点，下面对现有智慧拆零拣选领域研究文献进行综述，既对已有研究成果进行系统总结，同时也作为本书研究问题的借鉴与参考。

1.3.1 人到货拆零拣选系统

如图1-3所示，对于不含输送线的人到货拆零拣选系统，仅是借助信息设备减少或消除订单处理时间和寻找货物时间的浪费，其他作业过程与人工拣选系统相同，作业人员仍须穿越仓库访问固定的货位进行货物拣选，该系统的设计与优化方法可以参考人工拣选领域的相关文献。因此，仅关注配合输送线的货到人拆零拣选系统的相关研究。

1．分区拣选流水线系统

分区拣选是在货到人拆零拣选系统中常见的一类拣选策略。分区拣选系统将整个分拣区划分为多个拣货区，由一个或一组固定的拣货人员负责拣选某个拣货区内的货品。为减少人工分区拣选系统中大量的订单箱搬运作业及分区间订单箱的交接传递环节，通过输送线将多个拣货区串联构成一条分拣线，称为分区拣选流水线系统(Pick and Pass System）。如图1-5所示，主输送线连接不同拣货区，每个拣货区内部通常包括一个拣选站台、一组流利货架和一个专门的拣货人员。拣选站台由一段输送线组成，接收从主输送线上自动转移的订单箱，避免主输送线上的订单箱因等待拣选而发生的堵塞；流利货架上存放待拣货物，货架后端为人工整箱补货面，货架前端为人工拣选面，通常在人工拣选面安装电子标签系统；拣货人员根据货架上的电子标签提示将拣货区内货物拣选至对应订单箱，订单箱在拣货区内的拣选任务完成后，被人工推至主输送线，然后传递给下一个拣货区。

（1）设计优化

De Koster ［15］将分区拣选流水线系统转化为Jackson排队网络，预计订单处理总时间。该模型假设每个拣选站台的服务时间遵循指数分布，客户订单到达遵循泊松过程。利用该网络分析拣货区数量与输送线速度变化对订单处理总时间的影响。

Yu等［16］将输送与拣货区视为服务员、将订单视为客户，将分区拣选流水线系统的拣选过程描述为G|G|m排队模型。他们假设一个订单箱对应一个拣货人员在一个拣货区内一次拣选任务，该任务含一个订单且每次拣选动作处理一个订单行，给出拣货区作业时间的均值和方差表达式。在此基础上，建立系统近似效率模型，并通过仿真和实际应用证明其有效性。该近似数学模型可以用来分析不同仓库策略（拣货区内货位分配、拣货区面积、拣货区内人员数量以及订单合并批次与订单拆分）对该拣选系统性能的影响。订单箱进入系统的频率对该系统性能影响很大，当订单箱集中到达系统时，会加重系统的作业负担，降低订单处理能力。将小订单合并为订单批次可以有效降低系统的订单箱进入量，减少系统订单处理时间；但是当订单箱进入系统频率低时，订单批次策略反而会增加系统订单处理时间。

Yu等［17］将经典的分区拣选流水线模型进行了变换，每个分区内的流利货架用一组垂直于主输送线的巷道货架代替。针对该系统，在已有研究成果的基础上，考虑订单分批策略对系统的影响，建立包含批次拣选与订单分类的系统效率模型。

Melacini等［18］研究了一类包含巷道货架和流利货架两类设备的分区拣选流水线，如图1-6所示。流利货架用来存放周转率高的货物，而巷道货架存储周转率低的货物。因为流利货架靠近输送线分布所以拣选效率高，而巷道货架相距输送线远，所以拣选效率低。拣选站台的位置选择在每个拣货区的中央，可以减少区内平均行走距离。针对该系统，提出一种以给定效率条件下作业时间成本最小为目标的设计框架，该设计框架中应用解析模型估计行走距离，利用网络排队理论分析平均订单效率，适用于订单拣选系统选择阶段应用。

（2）控制优化

Jane［19］在假设各拣货区内单订单行人工拣选效率相同的条件下，提出一种启发式品项分配算法来均衡各拣货区内人员的工作量，保证整条分区拣选流水线系统的连续运行。

Jewkes等［20］将单个作业人员在一个拣货区内的拣选过程描述为马尔科夫过程，预计每个拣货人员在各自拣货区内的拣选时间，在此基础上，以系统拣选效率最大为优化目标建立品项分配模型，提出了一种动态规划算法对问题进行求解。

Pan等［21］通过将每一个拣货人员的行走时间描述为马尔科夫过程来估计拣选线上人员行走距离期望值，建立分区拣选流水线的解析模型，在此基础上，针对单个拣选分区内、等分区拣选流水线、不等分区拣选流水线三种情况，分别提出了三种品项分配优化算法。

Pan等［22］研究以合并订单批次数量少且各分区拣选任务均衡为优化目标的订单批次生成策略，应用一种基于群体遗传算法的启发式算法对问题进行求解。

Pan等［23］认为导致分区拣选流水线上拣货人员等待的原因有两个：各分区拣选任务的不平衡和因补货不及时引起的缺货。一旦拣选线上某货物发生缺货现象，拣货人员必须等待，直至仓储区的货物补入流利货架，而拣货人员的等待会影响系统的拣选效率。另外，拣货人员之间的任务不平衡会影响系统的效率。与生产流水线相似，当多个人员同时在各分区工作时，不平衡会降低订单履行效率，因为拣货人员需要等待线上的上游拣货人员拣选完成并将装有货物的订单箱传递过来后才可以拣选。在一条流水线上的前后两个相邻拣货区之间的拣选时间不同时，将会导致主输送线上的堵塞现象产生。文章提出了一种启发式遗传算法求解分区拣选流水线上的品项分配方案，可实现每种品项分配合理的存储空间，避免缺货的同时可平衡各拣货区的工作任务，提高系统的拣选效率。

2．自动拆零分播系统

在人到货拆零拣选系统中，为了提高拣选效率，许多配送中心将多个订单合并为一个订单批次进行批次拣选。采用订单批次拣选需要增加分播作业，即将批次拣选的货物分播至相应客户订单的过程。Berg［24］对仓库系统的规划与控制中批次拣选策略进行了详细研究。

在电子商务配送中心内部，通常将大量小订单合并一个订单批次进行拣选，由于拣货人员可以在一次拣货行程中同时拣选多个订单，所以拣选效率大大提高，但是后续订单分播作业强度却大大增加。订单分播作业是将订单批次中的货物分离至独立订单。为降低分播作业强度，一类自动拆零分播系统已设计研发并成功应用［25］。如图1-7所示，在人工拣货区内，一组订单合并为一个订单批次被多个拣货人员同时拣选，每个拣货人员负责其中一部分货物的拣选任务。该订单批次拣选任务完成后，所有的货物被送至自动化拆零订单分播系统。通过设备或人工的方式在导入站台将批次拣选货物逐件放置在循环线上，一旦到达相应的订单箱，借助循环线上的动力机构，货物就会自动落入订单箱内。当订单完成后，包装人员对订单箱内货物复核，然后放置在输送线上运到相应的发货口。现有分播系统的相关研究主要关注用于发货理货区内自动化整箱分播系统，该系统通过环形输送线将拣选完成的整箱货物分播至对应的发货支线通道内，由工作人员将发货支线通道货物根据车辆送货顺序整理后装车。由于订单数量远大于发货支线通道，所以该系统经常发生输送线堵塞或货物再循环的问题。而对于自动拆零分播系统，通常订单数量小于或等于订单箱数量，因而不存在堵塞或货物再循环的问题。

Johnson等［26］认为导入过程是该系统的瓶颈问题，决定了整个系统的效率。他们通过伯努利过程描述导入过程，建立自动拆零分播系统解析模型，该模型中包含导入过程中的随机需求、产品结构和人机交互等影响因素。在此基础上，通过模型分析人工导入站和自动导入站设计中应注意的问题。

Russell等［25a］研究了在满足效率的前提下以成本最小化为目标的自动拆零分播系统类型的选择问题，提出在一定订单波次长度范围内的人工分播系统和自动化分播系统的理论效率曲线，并通过仿真分析表明，该理论效率曲线可以很好地测出系统实际效率。在此基础上，建立了包含需求率、劳动率、固定成本和可变成本、订单尺寸、波次尺寸和分拨能力等因素的系统描述性模型。通过该模型给出在不同系统配置下总成本最小的分播类型。通过试验仿真表明，在忽略随机影响的条件下，推荐的分播系统类型通常满足作业效率的要求。

1.3.2 货到人拆零拣选系统

在货到人拆零拣选系统中，装载货物的料箱通过自动化料箱存取仓库拣选出来并送至拣货人员面前，拣货人员根据电子标签或灯光提示进行拣选。该系统节省了人员行走、寻货和订单处理时间，在实现人员精益管理的同时大大提高了拆零拣选效率。

根据拣选站台与自动化料箱存取仓库连接方式的不同，可将货到人技术分为两类：近站台货到人拆零拣选系统和远站台货到人拆零拣选系统。在近站台货到人拆零拣选系统中，拣选站台与自动化料箱存取仓库直接相连，自动化料箱存取仓库将载货料箱直接运至拣选站台处拣选，拣选完成后，自动化料箱存取仓库将剩余的货物再送回至指定货位。如果系统中包含多组货架和多个拣选站台，则每个拣选站台固定对应一组或几组货架上的货物，因而存在同一张订单中货物通过不同拣选站台拣选的情况，此时需要增加后续订单合并作业环节。在远站台货到人拆零拣选系统中，自动化料箱存取仓库的一端与循环输送线相连，自动化料箱存取仓库首先将载货料箱运至循环输送线，通过循环输送线将料箱带至远离货架的拣选站台，拣选完成后再将料箱通过循环输送线送回货架。由于每个拣选站台拣选品项不受品项在各组货架分布情况的约束，因而每个拣选站台能独立完成一张完整客户订单的拣选。

1．近站台货到人拆零拣选系统

在近站台货到人拆零拣选系统中，根据自动化料箱存取仓库类型的不同，可以分为旋转货架拣选系统和轻载荷自动化仓库拣选系统。

（1）旋转货架拣选系统

在旋转货架拣选系统中，旋转货架内部货位可以沿顺时针和逆时针两个方向闭环旋转，拣选站台设置于旋转货架的一端，货位沿任意方向旋转都可以到达拣选站台，由专门的拣货人员进行订单拣选，如图1-8所示。旋转货架通常由多层料箱货格组成，既可以多层共用一台旋转动力设备，也可以每层都安装独立的旋转动力设备。如果货架层数过多，超过拣货人员有效拣货高度，还需要配备垂直提升机协助拣货人员拣货。对于旋转货架拣选系统的优化研究，根据拣货人员与旋转货架数量的对应关系，可分为单人单货架优化和单人多货架优化。

首先对单个拣货人员与单个旋转货架组成的单人单货架系统的优化问题进行文献综述，优化方法主要包括配置优化和作业优化。

单人单货架配置优化：有效的存储策略可以显著减少旋转货架的旋转距离。最简单的策略是将货架上的货物随机存储。Hwang等［27］［28］对随机存储策略应用效果进行了全面测试，得到在货架货物需求服从均匀分布时，系统的各种性能特征。Ha等［29］提出一种相比随机存储策略更能改善系统效率的存储策略，并将其称为“双分类存储策略”，该策略根据货物的需求频次将货物分为高周转率货物和低周转率货物两类。高周转率的货物随机分布在旋转货架的连续区域，低周转率的货物分布在其余区域，通过仿真表明，基于双分类存储策略在单指令周期（一个周期仅拣选一件货物或仅存储一件货物）和双指令周期（一个周期内包含拣选一件货物和存储一件货物）可以显著减少旋转时间期望。

Stern等［30］提出最大临近存储策略，即在订单内同时出现次数多的品项相临存储，通过建立马尔科夫链模型对该存储策略进行定量分析。Lim等［31］提出风琴管货位分配策略，并证明在各种设置下都是最佳的。在旋转货架拣选系统中，风琴管货位分配策略将需求频次最高的货物放置在一个任意料箱内，需求频次排第二位和第三位的货物在需求频次最高的货物料箱位两侧临近存储，按照这种方法重复以上过程将货物按照频次降序依次相邻排列。Park等［32］假设独立单品项订单按照泊松过程到达时，分析基于风琴管货位分配策略的系统效率，给出该策略相比随机分配策略的优化幅度，并且指出这些优化幅度随需求分布偏态程度的增加而增大。

Abdel-Malek等［33a］假设每个订单内包含一种货物，且订单拣选排序为马尔科夫链过程，研究对由N个料箱组成的旋转货架基于风琴管货位分配策略下的旋转时间。假设当前订单拣选料箱为p，下一个订单拣选料箱q的概率为Ppq，以最小平均旋转时间为目标求最优货位分配策略。大量数值实验表明，尽管在该条件下风琴管货位分配策略不是最优的，但是很多系统性能参数都接近于最优值，该问题的最优解可通过二次指派问题进行求解。Litvak［34］指出通过基于大型订单数据的实验结果表明，一般最优存储策略取决于订单尺寸，对于大尺寸订单风琴管货位分配策略没有优化效果。

旋转货架设备配比优化问题是研究如何通过对货架上的各种品项进行货位空间划分实现连续拣选订单数量最大，所谓连续拣选是指在拣选过程中不出现缺货现象。Jacobs［35］、Yeh ［36］、Kim ［37］和Li等［38］针对该问题进行了研究，提出启发式算法求解。Hassini ［39］在这一系列研究的基础上深化，求得最优空间配比，根据确定型与随机型需求下的精确最优解，提出了一种性能接近最优的启发式算法。

单人单货架作业优化：旋转货架系统订单处理总时间可以表示为货架系统旋转时间与系统静止等待拣选时间之和。系统静止等待拣选时间不受品项访问顺序的影响，但是系统旋转时间取决于品项访问顺序。针对单人单货架品项访问顺序问题，现有文献研究内容可以分为对单订单拣选模式下的品项访问排序问题和多订单拣选模式下的订单排序问题。

针对单订单拣选模式下的品项访问顺序问题，Bartholdi等［40］提出了一种多项式算法求解该问题的最优值，通过枚举所有可能路径保证一定能找到最快的订单内拣选顺序。但当拣选数量大时，一些简单的启发式算法计算更简单且运行效果好。这些启发式算法都基于简单的拣选原则，如最近品项算法，在任何时间拣货人员都选择最靠近的品项作为下一个拣选对象；最近旋转方向算法，系统总选择旋转距离最短的方向（顺时针或逆时针旋转）；偏执启发式算法，总按照向右或向左旋转的顺序拣选货物。Litvak等［41］在品项位置独立均匀分布的条件下，分析最近品项算法的系统旋转时间分布和渐进特性。

Litvak等［42］提出另外一种旋转策略，称为M阶策略，即在拣选不超过m种品项时通过改变旋转方向在继续拣选的2(m+1）个路径中选择最近的路线。并证明在品项位置服从独立均匀分布的条件下，当m=2时，该策略的平均旋转时间小于最近品项策略的平均旋转时间。

Ghosh等［43］利用连续的簇和空描述旋转货架，将旋转货架的路径视作一个圆，簇是圆上订单拣选必须访问的一串位置，而空是圆上簇之间的部分。他们提出了两种算法求最优拣选策略，特别的地方在于，为了避免全部枚举，他们规定每一次旋转不能覆盖1/3的旋转货架长度。

Stern ［30b］研究了在开环策略和闭环策略下最优拣选顺序的特性。开环策略是指系统完成当前订单的最后一品项拣选任务后保持静止等待下一个订单的发起，而闭环策略是指当前订单的最后一品项拣选任务完成后都回到规定的位置，等待下一个订单的发起。分析表明，在开环策略下采用最优订单拣选顺序，旋转系统最多改变一次旋转方向，而在闭环策略下旋转系统最多改变两次旋转方向。Litvak等［44］给出在闭环策略下，拣选品项随机分布的订单所需最小旋转时间的递归式分布表达式。

关于基于订单内品项位置相关性的系统旋转策略研究文献相对很少。Abdel -Malek等［33］假设连续品项位置构成一个马尔科夫链，研究风琴管存储策略的性能。Stern ［30a］通过考虑多种订单类型，建立同一个订单内品项间的相关性，将每种订单类型对应一组品项列表。Wan等［45］关注对于块状订单的最小拣选时间研究，块状订单是指该订单集中在旋转货架相对很小的部分，通过最近端点法求最优拣选顺序。在该情况下，品项位置不服从均匀分布，品项位置之间有很强的相关性。

张攀等［46］通过分析单拣选站台分层水平旋转货架系统的拣选路径特点，建立作业时间数学模型，并将其归结为城市间距离动态变化的旅行商问题。为求解该问题，首先提出基于层序邻域的快速局部搜索算法，在此基础上将局部搜索算法融入传统遗传算法，提出了一种新型混合遗传算法。仿真试验表明，该算法可高效、稳定地实现对中大规模的单拣选站台分层水平旋转货架系统拣选路径问题的求解。

在多订单拣选模式下，订单的拣选顺序任意，但是每个订单内的货物必须连续拣选，只有一个订单拣选完成后再拣选下一个订单。Bartholdi等［40a］定义最小跨越区间为一个订单内所有货物最短区间，假设拣货人员都是在该区间的任一端点开始或者结束订单拣选，在此基础上将订单排序构建最短订单链，提出了两种启发式算法。第一种是层次启发式算法，将恰好有重合区域端点的订单前后相连，其他订单则按照当前订单拣选结束后顺时针旋转至下一个未拣选订单端点的方式串联在一起。第二种是最近订单启发式算法，该算法是最近品项法的拓展。

Ghosh等［43a］假设订单按照先到先服务（First Come First Served，FCFS）的顺序进行拣选。因为订单按照先到先服务的模式进行拣选，所以该问题简化为通过单个订单内货物拣选顺序优化实现整体订单拣选时间的最小。他们通过动态规划提出了一种求多订单最优拣选顺序的算法，并且给出当新订单到达时如何动态更新当前订单内的拣选顺序。

Rouwenhorst等［47］将旋转货架系统描述为M/G/1排队系统，订单是寻求服务的客户，它们获取服务的顺序取决于系统采用的拣选策略。

Berg ［48］假设存在订单顺序给定和订单顺序任意两种情况，当订单顺序给定，他提出一种有效的动态规划算法求解在此特定订单顺序下的旋转最优路径；当订单顺序任意，他把问题简化为乡村邮递员问题，提出一类匹配树算法可在多项式时间内求最优解。

Lee等［49］将品项和订单优化排序问题描述为多旅行商问题，即多个旅行商从各自中心城市出发访问周边城市后回到出发城市，每一个城市至少被一个旅行商访问一次的最小路径。他们提出了一种有效的启发式算法求解包含多品项的订单组拣选顺序优化方案。

单人多货架优化：在实际应用中已出现单个拣货人员对应多旋转货架的拣选模式。如图1-9所示，一个拣选站台对应多个水平旋转货架。这种系统配置允许在拣货人员从其中的一个旋转货架中取出货物的同时，其他旋转货架将下一步要拣选的货物旋转至拣选站台位置。通常借助电子标签提示拣货人员拣选的位置与拣选货物的数量。当拣货人员将拣选货物放入相应订单箱后，行走至其他旋转货架继续拣选。

Emerson等［50］首次对平面多旋转货架系统的性能进行了研究。Emerson等对罗克韦尔柯林斯的电信产品仓库进行了仿真，系统包含22个旋转货架，每一对旋转货架包含一个独立的拣选站台，总共有11个拣选站台。他们关注的问题包括应该划分多大的订单批次以保证所有人员高效工作的同时满足系统性能，当减少一个旋转货架或一个拣选站台会发生什么，超负荷或不平衡应如何处理。针对这些不平衡情况，Emerson等研究了两条控制优化策略。第一条控制优化策略是研究了将七对旋转货架依次采用六种不同的存储方案。通过仿真模型研究存储规则对旋转货架系统的利用率影响。Emerson等发现在不同的存储策略下各组旋转货架间利用率的差别并不明显。第二条控制优化策略是让一个流动拣货人员根据特殊需要（例如根据特定站点的队列长度）移动至不同拣选站台工作，该解决方案有利于处理该系统的不平衡问题。

Hwang等［27a］研究了单货架系统和双货架系统的性能。基于随机货位分配策略，建立单指令和双指令的旋转时间模型。在此基础上，Hwang等［28a］定量分析了双载具提升机对单旋转系统和双旋转系统作业效率的影响。双载具提升机在垂直轴干两侧各有一个独立作业存取设备单元，该双载具提升机一个作业周期可以完成两次存货和两次取货作业。从测试结果来看，双载具提升机比单载具提升机效率提高明显，如果配合双旋转系统则效率提高效果更加好。由于考虑成本问题，Hwang等指出在实际应用之前，需要进行经济性评价来确定双旋转系统以及双载具提升机的附加成本。

Meller等［51］研究了由一组旋转货架配合一个拣货人员构成的拣选系统的作业效率。他们首先提出一个旋转货架配合一个拣货人员构成的拣选系统订单处理总时间，在此基础上将C个旋转货架作为一个排队系统来建模，其中每个旋转货架上有1/C个拣货人员，利用Gelenbe［52］的扩散近似方法求系统作业效率近似值。

Hassini等［53］针对双旋转货架配合单个拣货人员的拣选系统，研究了以系统长期旋转时间期望最小为目标的货位分配问题。他们忽略由于缺货引起的系统延迟，假设货物在任何时间都是充足的，并且系统仅处理单品项订单，即订单不能分批处理。该研究针对单品项订单采用先到先服务的原则处理，或者只有当目前品项被拣选后才确定拣选下一个品项的情况，通过设计简单的启发式算法实现求解。

Park等［54］假设待拣品项数量无限多且每个订单仅含一个品项的情况，对以上模型进行研究。Park等并没有研究存储策略问题，而是研究一个拣货人员在两个旋转系统中轮流作业的情况。该情况可能导致拣货人员必须在当前要操作的旋转系统等待很久，一直到货物送至他面前。Park等推导出在拣选数量固定的条件下拣货人员等待时间分布，由此建立系统效率与拣货人员利用率的数学表达式。Vlasiou等［55］通过取消与拣选次数或旋转次数相关的所有假设，对在参考文献［54］中提出的模型进行了扩展研究。

（2）轻载荷自动化仓库拣选系统

轻载荷自动化仓库是一种以料箱为存取对象的单元负载自动化仓库(Unit-load AS/RS），一次取货作业过程包含巷道内堆垛机将单个料箱货物从货架上取出，送至巷道端头的出入口位置；一次存货作业过程包含巷道内堆垛机将出入口处单个料箱货物输送至相应的货架位置。对于存货或取货作业完成后到在下一次任务开始之前堆垛机驻停位置的选择涉及驻停点策略问题。Roodbergen等［60］对单元负载自动化仓库控制策略进行了详细的研究综述，包括货位分配、订单分批、驻停点策略、存取任务排序及运行时间估计。

轻载荷自动化仓库拣选系统（图1-10）是一类由拣选站台和轻载荷自动化仓库构成的货到人拆零拣选系统，该系统的优化是对料箱存取过程和人工拣货过程的整体优化，本书仅对与轻载荷自动化仓库拣选系统相关的研究文献进行综述。