货到人系统中分拣策略的设计与应用

郭 丽，杨腾飞，吴 双，王 祥，武明虎

（北自所（北京）科技发展有限公司，北京 100120）

0 引言

随着仓储物流自动化程度加深，越来越多的企业希望通过全自动化方式实现货物的分拣，提高企业的配送效率，从而产生更大的效益。

货到人系统主要由三个部分组成，分别是存储系统、配送系统以及分拣系统。存储系统的研究重点在于如何根据SKU使用的频率合理安排其存储区域，从而达到出库频次最高的SKU出库时间最短的目标。在配送系统中，从库端到达分拣站台的最短路径以及流量控制等问题一直是业界所关注的重点。而对于货到人分拣系统，针对分拣策略的研究相对较少。而对于整个系统效率而言，分拣策略的优劣，直接关系到系统整体的运行效率。

1 背景介绍

装箱问题是经典的NP问题，解决装箱问题是设计分拣系统中的一个重要环节。针对装箱问题的经典算法在研究过程中相继涌现。解决装箱问题的算法主要分为离线算法和在线算法。离线算法是指已知所有SKU的信息，提前计算出其分配序列，并根据此序列进行装箱。在线算法是指根据SKU到达的顺序，在保证固定数量箱子打开的情况下，对到达的物料进行装箱操作。从理论的角度看，在线装箱中所使用的算法在解决离线装箱问题均同样适用，但结合实际的业务生产过程，离线算法和在线算法各有优劣。

本文以某大型海外食品加工企业配送中心为研究案例，其客户分为大型超市以及个体零售商两种类型。这两种客户对于同一SKU需求的数量有着巨大差异。大型商超对同一SKU的需求数量大，一张订单所涉及的SKU数量较少。而对于零售个体，其订单需要SKU数量庞大，但每种SKU所需数量很小。在这种情况下，分拣策略的设计中使用离线装箱还是在线装箱，对分拣效率有着很大的影响。

对于货到人系统订单吞吐量以及设备利用率进行效率分析常用的方法是使用开环排队模型对其进行建模。通过对排队模型的分解可获得各个环节的指标，可以实现对系统效率的估算，发现系统瓶颈，并有针对性的对系统进行优化，从而达到系统效率最大化。因此使用开环排队网络分析货到人分拣系统是系统优化过程中重要的一个环节。

2 系统建模分析

2.1 建立系统模型

根据文献[3]所阐述的使用排队网络对自动化系统建模的方法对本案例的自动化货到人分拣系统进行建模。针对系统订单可以随时加入，每个子系统在繁忙状态下，新的任务均需要加入其队列进行等待的情况，本文使用开环排队网络对其业务场景进行建模，并基于该模型对系统整体效率进行分析。

建模基于如下若干条系统特征：

1）货物的存储方式为随机存储，仓储区域没有进行分区，货物使用某货位的概率为1/N（N为货位的总数量，由巷道数*层数*列数*排数计算得出）。

2）订单的所需SKU的货位地址为随机选择。

3）设备的服务规则为先到先服务，即：先到达的库存箱先对其进行相应的操作，后到达的库存箱将会在其服务队列中进行等待。

图1 系统模型图

4）堆垛机完成操作后的停止地点为上一条作业的目的地址。由于提升机为连续提升机，在一个隔板到达1层时，另一个隔板会自动到达2层，因此不需要考虑提升机系统的这一时间损耗。

5）堆垛机任务的到达时间满足以λ为参数的泊松分布。

6）各堆垛机的在同一时间段只进行一种作业类型。

基于以上约束，针对该系统建立的模型如图1所示，堆垛机任务的到达率服从以λ为参数的泊松分布。该模型包含三个子系统：双工位miniload堆垛机系统，连续提升机系统和2对4模式下分拣工作台系统。在堆垛机系统中，将到达该巷道的任务视为等待服务的顾客，miniload堆垛机作为服务者将完成将库存箱送至输送机的任务。在堆垛机子系统中，λis（i=1…7）标识第i个巷道的任务到达率，μiS（i=1…7）表示第i巷道堆垛机的服务率。基于货位地址随机分配的约束，任务由每台miniload堆垛机执行的概率均为1/7，因此λis（i=1…7）的值为λ/7。输送线将库存箱送至连续提升机，提升机作为服务者为库存箱提供服务。在模型中λT为连续提升机的任务到达率，其值应该为∑μiS（i=1…7），μT即为连续提升机系统的服务率。在分拣工位系统中，λjw（j=1…6）表示拣选工作台系统的任务到达率。由于分拣工位相对于连续提升机的位置从1号工位到6号工位由近到远的均匀排列，则各个工位的任务到达率与其距离成反比，由连续提升机只有一台，故其任务到达率即为μT/（6*k）（k=1…6）。μkw（k=1…6）即为分拣站台系统第k个工位的服务率。

2.2 系统模型分析

对于开环排队网络来说，求解的方式一般为将其拆分成若干M/M/1模型的子系统，并对子系统进行求解。通过式(1)可计算出每个子系统的队列的平均队列长度NQ。

其中ρ=λ/μ，λ表示各系统的任务到达率，μ表示各个系统的服务率。

由图2可知，完整的分拣系统由堆垛机系统、连续提升机系统以及分拣站台系统构成，因此完成对三个子系统求解，即可得到整个系统的解。根据上述对系统的划分，订单的等待时间为任务在各个系统中的等待时间以及执行时间的综合，如式(2)所示。

在式(1)中，tod为订单从到达到结束所需要的时间，tsw表示堆垛机系统的平均等待时间，tSE表示堆垛机系统任务的平均执行时间，tc1表示从miniload堆垛机到连续提升机的输送时间，该时间为常量；tTW表示任务在连续提升机中的等待时间，tTE表示连续提升机执行任务的时间，tc2是连续提升机配送到分拣站台的时间，该时间与分拣站台与连续提升机之间的距离成正比；tPSW表示任务在分拣站台的等待时间，tPSE表示任务在分拣站台的执行时间。根据利特尔公式(3)，将使用式(1)求得的各系统队列的平均长度以及其服务率和到达率代入式(3)中，即可求得个系统的平均等待时间。系统的平均执行时间由一定时间内的实际数据的平均值得出。

从以上模型可以看出，在堆垛机系统以及提升机系统达到最优效率的情况下，拣选工位的任务等待时间以及拣选任务的执行时间对系统效率有很大影响。而在实际的分拣业务场景下，拣选任务的拣选时间取决于工人的拣选速度，而等待时间取决于库存箱命中率。因此系统在进行拣选方案的设计时，从提高库存箱命中率出发，针对不同类型的物品，设计的装箱策略有所不同。

3 分拣策略设计

在通过第一节中对其业务场景的描述可以将分拣过程中的会出现的任务场景划分为两种。第一种场景是针对大型商超。其要求订单箱中均为同一种物料且不同订单的物料不能放入相同的订单箱。而且这种类型的客户，每张订单的需求数量较大，订单箱几乎没有空箱。第二种场景针对小型的零散客户。其订单模式通常支持混装，且需求的SKU中类型多单数量少，因此完成一个客户箱所需的库存箱数量较大。

从第二节中建立的订单完成时间模型中可以看出，在决定订单从到达到结束所需要的时间构成中，分拣工位的服务时间和任务等待时间起到很重要的因素。从上述两种任务场景分析，在第一种业务场景中，tPSE分拣任务的执行时间对整个分拣系统的效率影响较大，而tPSW对系统效率影响较小；在第二种业务场景中，tPSW分拣任务的等待时间对整个分拣系统的效率影响较大，而tPSE对系统效率影响较小。在优化tPSE方面，可以通过改善包装方式的方法进行。如针对采购的形式，将散装的单个物料以一定数量为单元进行二次打包，这样可以有效的缩短每次分拣的执行时间。在这种管理方式下，两种场景中tPSE值的差异性大大缩小。解决了tPSE的差异性之后，分拣策略设计的目标将集中在缩短tPSW，也就是分拣系统的任务等待时间上。

在本案例中，货到人分拣系统设备构成如图2所示，6个货到人拣选站台，分为上层库存箱输送系统与下层订单箱输送系统，属于二对四分拣方式。根据缩短tPSW的目标，针对上述两种情况分别设计了离线计算动态绑定策略和在线计算装箱策略。离线计算与在线计算为装箱算法的两种形式。在该项目案例中，某一SKU存放至相应客户箱的数量，由相关部门提供并导入到系统中。

3.1 场景一分拣策略设计

在场景一中，由于订单中对于某一物料的需求数量较大，通常情况下一个库存箱所包含的数量可以满足一至两个订单箱。因此采用离线计算的方式能够消除在线计算所需要的时间。离线计算的步骤如图3所示，系统根据订单中的客户信息找到相应的客户箱。通过系统维护的订单物料的基础数据计算所需的客户箱总数。根据客户对物料不同的存储日期的需要，筛选出满足条件的库存箱。根据订单数量对该物料需求的数量，为每一订单箱生成对应的唯一任务号，同时生成该订单箱的拣选任务，并与库存箱进行绑定。由于库存箱到达分拣站台的顺序不定，为了避免增加不必要的周转时间，当库存箱到达分拣站台后，再选择相对应的分拣任务执行分拣作业，而不是在订单箱到达之后就绑定其对应的分拣任务。这样的绑定模式可以避免由于库存箱到达顺序的不确定性而导致的tPSW的增加。在计算分拣任务的时候，可能会出现由于零箱所导致的交叉连锁效应，因此对于零头箱在生成分拣作业的前需要进行匹配和规整计算。

图3 场景一分拣策略流程图

3.2 场景二分拣策略设计

图4 场景二分拣策略流程图

在场景二中，由于一个订单箱的每个分拣任务通常需要最多高达10个左右的库存箱，多箱周转的情况势必会发生。因此降低单箱周转次数，保证每个库存箱到达后即可拣选可有效降低tPSW的值。因此，在线装箱算法更适合于该场景下的分拣任务。在线装箱算法的流程如图4所示。在这一阶段，场景一与场景二有很大不同，场景二的分拣策略在这一阶段不生成任何分拣任务，在完成匹配订单箱型以及查询存储期限后，不进行订单分解、生成分拣任务以及绑定库存箱的操作只生成出库任务。当库存箱到达之后，根据订单数量以及订单箱容量计算拣选数量，生成分拣任务，绑定库存箱，直到该订单箱装满或者订单分拣结束。在这种拣选模式下，可以达到使库存箱到位即可分拣的效果。有效避免了库存箱的无用周转，降低了tPSW的值，从而使得订单的开始时间和结束时间得以降低。

4 系统运行结果分析

针对以上业务场景，本文设计了两组对照试验，证明上述两种优化的方案对于缩短分拣过程中tPSW确实有效。场景一与场景二的试验中使用本案例中的某大型商超客户的6张订单，6张订单中所需的物料没有交叉，以排除由于物料交叉对料箱到达时间造成的影响。

场景一的订单结构如下表所示。由表中可以看出，这一组订单的特点为SKU需求的数目均在5～8种之间，需求量平均值反映了这一组订单对于每一种物料的需求数目相对较集中。这一组订单满足业务场景一所描述的特征与场景一相符合。对照组使用的分拣策略为客户箱到达即绑定分拣任务这样一种离线装箱策略。在本次分拣过程中，6个分拣工位分别绑定6张订单，分拣过程同时启动。

表1 场景一分拣效率对照表

通过对比数据可以看出，对照组的分拣时间明显大于实际的订单执行时间。结果说明，基于库存箱的动态绑定策略效果优于基于订单箱的绑定策略。

场景二选取得订单结构入下表。从表2可以看出，场景二的订单类的基本特征为SKU数量庞大且每一种SKU的数量很小，订单结构比较分散。对照组使用离线的分拣策略，即在订单开始分拣前即确定每一订单箱中所需分拣的物料及数量。本次分拣过程与场景一致，6个工位分别绑定6张订单，分拣过程同时启动。

表2 场景二分拣效率对照表

通过对比数据可以看出，对照组的分拣时间明显大于实际的订单执行时间。结果说明，针对场景二，在线装箱的分拣策略明显优于离线的分拣策略。

两种分拣策略通过在项目案例现场的实际应用，提高分拣效率在20%以上，缩短了订单的处理时间，提高了分拣订单量。

5 结语

本文运用了开环排队模型，对实际的项目方案进行建模。通过对模型进行分析，确定软件设计过程中系统的优化方向集中在缩短tPSw上。在确定业务场景后，本文提出了两种不同优化策略。从数据中可以看出，针对场景一，本文提出的离线计算动态绑定策略相比针对基于客户箱对订单进行绑定的策略能够有效缩短分拣任务的等待时间；针对场景二所使用的在线装箱策略同样达到了降低tPSw的效果。该项目实际投产使用超过一年的时间，分拣订单数量近4万，项目的实际运行情况也证明了以上两种策略切实有效的提高了分拣效率，缩短了订单的流转周期，为相同业务场景下的分拣策略设计提供了思路。