货到人系统拣选订单分批处理策略问题研究

2019-12-31范继东

物流技术 2019年12期

范继东

（南京医药股份有限公司，江苏南京 210000）

1 引言

随着拆零比例的持续上升，如何解决医药流通行业的拆零拣选问题成为主要问题。“货到人”系统由于能够降低劳动强度、提升人员作业效率，作为新型拣选方式正在日益为各家医药流通企业所重视，多层穿梭车系统作为其中典型的代表，由于其存储密度大、拣选效率高等特点，正为各家医药流通企业所采用。多层穿梭车系统在应对大量订单的情况下，巷道端头的料箱提升机成为影响整个系统效率的瓶颈点之一。本文针对多层穿梭车系统中“货到人”拣选系统中如何利用订单拣选分批策略，实现整体效率提升的问题，提出了基于k-means算法的细分批算法，以最小化货箱总出入库次数为目标，建立了考虑分批结果聚类程度的订单分批数学模型，实现可控聚类程度的订单分批，在同样的业务情况下，有效的降低了“货到人”拣选系统对提升机作业效率的要求。

2 问题分析

订单拣选是影响物流配送中心作业效率的重要因素。在“货到人”拣选系统中，货箱出入库频率是影响拣选效率的关键因素，当出入库较频繁时，对设备的性能要求较高，设备难以满足要求或成本较高。因此，降低货箱出入库频率是影响拣选效率的重要因素。

订单分批是把多张订单集合成一批，进行批次拣选作业。通过订单分批，可以把相似度高的订单合并在同一批次中，这样相当于把每批次订单中的同一商品品项汇总后，再分配到每一个顾客订单，可以有效的降低货箱的出入库次数，提高拣选效率。对于订单分批问题，常见的有三种分批方法：

（1）按时间窗分批：首先固定一个时间长度，从某个时间点开始，将该时间窗长度内到达的订单分到同一个批次。

（2）固定订单量分批：固定一个订单批量，将按照先后顺序到达的订单一次分到该批次，直到达到容量限制，开始下一个批次的分批。

（3）智能型分批：根据待分批订单的结构特点、使用特点的算法对订单拣选合理分批。

前两种方法属于先到先服务的方式，没法降低订单对提升机的作业要求，所以本文采用智能算法进行订单分批。当待分批订单的数量很大时，由于现有智能分批算法的计算复杂度较高，会导致求解订单分批结果的时间过长，增加拣选等待时间，有必要设计一种低复杂度的算法，用于大批量订单的分批，在计算速度较快的前提下实现大批量订单到小批量订单的转换。此外，拣选效率和订单的聚类程度不一定成正比。在医药拣选中，根据GSP的要求，必须对药品进行批号批次管理，在确定订单分批后，将货箱出库到拣选台进行拣选，由于同一批次中的订单相似度较高，同一批次中的某个药品原料箱有可能被多个订单需要，就会造成分拣时很多拣选台都在等待某个原料箱的情况，从而导致拣选等待时间过长。所以并非聚类程度越高，总拣选时间越短，还要考虑订单分批的聚类程度对后续拣选台拣选时间的影响。

WANGY[1]针对多层穿梭车仓储系统的任务调度问题，根据穿梭车和升降机的运动特性，建立了任务调度的时序数学模型，将穿梭车和升降机之间的任务调度问题转换为装配线并行作业问题，并用改进的遗传算法求解，可以减少总升降机空闲时间和总穿梭车等待时间。吴颖颖[2]为了解决拣选订单排序问题，定义订单耦合因子表示两个订单之间可放置于拣选缓存中的共用货箱数量，并以此作为模型参数，以降低货箱出入库频率为优化目标，建立订单排序优化模型，并提出改进的K-Means聚类算法求解模型。宁方华[3]研究了“货到人”作业模式下鱼骨型布局中的货位优化问题，按品项的订购频次和相关性划分品项簇，将相关性强且订购频次高的品项簇存储于一个货架，并以最小化拣选路程为目标建立数学模型；然后设计TS_SC算法求解货位优化模型，将相关性强的货架就近存放，从而减少货架搬运次数，缩短拣选路程，提高作业效率。马文凯[4]研究了跨巷道多层穿梭车仓储系统的最优配置问题，综合考虑客户对分拣系统的需求以及跨巷道多层穿梭车仓储系统自身的特点，通过分析系统的配置优化模型，提出启发式算法，求解使成本最小的系统最优配置，总结归纳出系统配置对系统性能的影响规律。

现有的研究在设计订单分批算法时，并没有针对医药批号批次管理的要求，考虑聚类程度的影响问题。本文在设计订单分批算法时，将提出聚类程度指数的概念来衡量订单分批的聚类程度，兼顾了药品批号批次管理要求对拣选作业的特殊要求，同时考虑控制聚类程度的订单分批。

3 模型建立

3.1 模型假设

为了建模的方便，对要研究的“货到人”拣选系统做了如下假设：

（1）所有订单的拣选信息在分批前已知；

（2）一个订单至少包含一个物品；

（3）一个订单只能被分在一个批次中，不允许分割；

（4）一个原料箱在同一个批次中只能出库一次；

（5）不考虑缺货和补货的情况。

3.2 符号说明

本模型所使用的符号具体含义如下：

N—订单总数；

On—第n个订单（n=1,2,...,N）；

K—仓库中所有品项的种类总数；

M—单个订单的订单行上限；

B—订单总共划分的批次数（b=1,2,...,B）；

C—每个批次的容量限制；

mn—第n个订单含有的品项数目（n=1,2,...,N）；

sij—订单Oi和Oj中相同品项的数量（i,j=1,2,...,N）；

T—货箱总出入库次数；

ρb—聚类程度指数；

λ—聚类程度阈值；

Ub—第b批订单中出现频率大于1次的所有品项的集合；

3.3 模型数学表达

根据上述问题分析，可以建立如下数学模型：目标函数：

约束条件：

上述模型中，式（1）为目标函数，表示所有货箱的总出入库次数最小，总出入库次数T为所有订单的品项次和订单分批所节省的出入库次数的差值；式（2）约束每个订单只能分到1个批次中；式（3）为容量约束，表示一个批次的订单总数不能超过批次的订单容量限制，式（4）为取值约束，表示决策变量的取值为布尔型，式（5）为聚类程度约束，表示聚类程度指数要满足设定的阈值条件，式（6）为聚类程度指数的定义，ρb表示第b批订单中所有品项的重复出现次数和第b批订单中出现的全部品项次的比值。

3.4 基于k-means的订单细分批算法

针对上述订单分批数学模型，设计了基于kmeans算法的改进算法，流程如图1所示。该算法实现了变聚类中心的订单分批，其大体思路是：基于订单之间的相似度进行订单的合批，每次加入一个订单后都要对聚类中心进行更新，重新计算相似度来选出其他订单；针对模型中的聚类程度限制，算法设计了反馈调整，会根据聚类程度限制来改变选择订单的优先级，从而改变分批结果的聚类程度。算法的具体步骤如下：

（1）计算所有订单两两之间相同品项的数目sij，构成初始的订单相似矩阵S0。

（2）将相似矩阵中未分批订单间的相似度取值按从大到小非重复降序排列。

（3）选择最大相似度值对应的两个订单组合作为聚类的初始订单批量。

（4）以这两个初始订单的组合订单为基准，比较合并订单与其他订单的相似度，得到新的订单相似矩阵，选择相似度取值最大的订单划入该批次。

（5）重复步骤（4），直到该批次的订单数达到容量限制，则已得到该批次的初步分批结果。

（6）计算该批次的聚类程度指数ρb，判断ρb＜λ是否成立，若满足条件则保留该批次分批结果，同时将该批次的订单从原始订单集中剔除，跳转到步骤（7）；否则重新对该批次进行分批：假设是第i次迭代，则回到步骤（3），选择排在第i个位置的相似度值，将其对应的两个订单组合作为聚类的初始订单批量，依次计算下去。

（7）得到更新后的未分批订单集，跳转到步骤（2），不断的重复整个过程，直到所有的订单都完成分批。