在线订单分批及拣选路径规划模型及算法

闫 军，常 乐，封丽华

1.兰州交通大学 甘肃省物流与信息技术研究院，兰州730070

2.兰州交通大学 机电技术研究所，兰州730070

订单拣选是从仓库中的存储位置取回物品以满足客户需求的过程。在人到货订单拣选系统中，客户指定的订单在运送给客户之前，需要经过仓库中的几个物理过程，包括接收订单、下架、拣选、检查和包装。仓配企业的进货方式一般是从生产厂商方大批量接收货物并进行存储，而具有配送需求的客户通常是订购小批量产品，因此出现了拣货这一生产活动。过长的处理和交付时间以及高昂的人工和交付成本，将导致不满意的客户服务，可能会降低仓库的竞争力[1]。

订单分拣系统可以分为两类：货到人订单分拣系统和人到货订单分拣系统。在第一种类型的订单拣选系统中，自动存储和穿梭车将所需物品运送到固定拣选机，而在第二种类型的订单拣选系统中，拣选员步行或乘车穿越仓库并收集订单所涉及的物品[2]。因为人工成本高的因素，订单分批系统的好坏会对人到货订单拣选系统产生巨大影响，所以本文主要研究第二种类型的订单拣选系统，考虑减少此类企业的生产成本。人到货订单分拣系统在运营过程中会出现三个不同的计划问题：将物料分配到存储地点（仓库货位优化），将客户订单分配到不同的分拣批次（订单分批）和拾取货物时穿梭仓库的行走路径（拣选路径规划）。本文主要关注第二个问题。在这个问题中，通过优化不同的客户订单之间的拣配订单组合，可以大大提高仓库运营效率。

针对来自客户订单中的可用信息，可以区分两种不同类型的订单批处理问题：离线（静态）订单分批处理问题，该活动在计划期开始时就知道所有客户订单；在线（动态）订单分批处理问题（online order batching problem，OOBP），提前不知道客户订单，并且随着时间的推移会产生新的订单[3]。本文考虑了具有多个拣选员的在线订单批处理问题，其中需要解决三个主要决策问题：（1）哪些客户订单应分组在同一批中；（2）应如何将已构造的批次分配给空闲的拣选人员；（3）何时开始每批的拣选过程。目的是最小化所有批次的最大完成时间。由于离线订单批处理问题是NP 难题，本文提出了一种基于规则的启发式方法来解决上述决策问题。该算法将在线订单批处理问题分解为与定义的决策点类型有关的一些离线问题，并基于由分批处理规则、分批处理选择规则和拣选员分配规则组成的决策规则来解决每个离线订单批处理问题。

对于处理离线订单分批处理问题的算法，精确算法方面，Gademann和Velde[4]提出了一种分支定价算法，以在合理的计算时间内解决离线订单批处理问题的小实例。Bozer和Kile[5]提出了一种混合整数规划方法，以获得离线订单分批处理问题的最佳解决方案，但该方法仅适用于订单数量少（最多25个）的实例。而启发式算法方面，国内外文献中主要有四种类型：基于优先级规则的算法、种子算法、保存算法和元启发式算法。第一类算法是按照订单的到达顺序或重要程度等优先级规则进行分批处理；第二类种子算法一般依据某种规则选择种子订单，然后依据订单一致性原则进行分批处理；第三类保存算法是寻找订单间的相似性，以获得拣选路径最大节省值为目标进行订单的合并；最后一类元启发式算法是构建订单分批的初始解结构，通过在可行域内的随机搜索得到相对最优的结果。如Hsu等[6]提出了一种遗传算法来解决离线订单分批问题，但是他们的方法仅限于S形路由策略。Tsai等[7]提出了一种具有提前和拖延惩罚的多重遗传算法，以解决集成的订单分批和分拣机路由问题，并获得最佳的分拣计划。Henn[8]也提出了一种算法，该算法是迭代局部搜索和蚁群算法的组合。Henn 和Schmid[9]展示了如何使用元启发式算法来最大程度地减少给定预定日期的给定客户订单集的总拖延时间。

有些文献将对OOBP 的部分研究抽象为经典生产运输联合调度的变体，王旭坪等[10]以订单的总服务时间最小为目标，设计三阶段启发式算法处理在线订单分批问题；曾庆成等[11]考虑提前下单和实时下单共同参与的实际情况，设计基于插入算法和2-opt 邻域搜索的混合启发式算法进行求解。除此之外，马氏华等采用等待机制设计延时动态时间窗分批策略；陈方宇等[12]对实时订单进行仿真实验，通过重复使用算法优化结果得出订单分批和拣选路径规划方案。近年来OOBP 在建模时经常考虑时间窗口对分批处理的影响，Chew 和Tang[13]考虑S型拣货路径策略，将可变时间窗口应用于OOBP模型。作者运用理论分析，将订单拣选系统建模为具有两个队列的排队网络：第一个队列进行分批处理过程，在该过程中，根据优先级规则对客户订单进行排序，并当队列中积累一定量的订单时对客户订单进行分批合并。第二个队列进行拣选过程，将已分批处理的订单移至第二队列进行拣选。Le-Duc和de Koster[14]提出了一种排队模型，该模型考虑了固定时间窗和可变时间窗批次，计算双区型仓库中客户订单的平均周转时间。综上所述，文献中对订单分批的研究为OOBP的数学建模和解决算法提供了丰富的可借鉴方法，但OOBP的研究大多是进行先到先分批的策略或累计到一定数量的订单进行离线订单分批处理，有关在线订单分批和拣选路径优化进行联合调度的研究较少。

本文构建限制订单过早或延迟处理的在线订单拣选分批优化模型，并考虑存在多个拣货员的情况，求解出所有批次平均最小服务时间；根据订单的时间窗规则构建在线订单分批求解模型，即按照客户的需求情况来决定处理订单的实际时间；求解算法方面，订单的分批采用改进的k-means聚类算法进行，拣货路径的规划由遗传算法求解给出。最后通过数据实验，从服务时间、完成订单数量、有效订单数量、延迟时间等多方面，将本研究算法与传统算法分批结果进行对比分析，以证明模型和算法的有效性，为仓储管理部门提高订单处理服务质量提供决策支持。

1 问题描述和数学建模

1.1 问题描述与符号说明

在OOBP中，运输存货单位（stock keeping unit，SKU）被用于区分仓库内的N种产品类型，在某一时刻下库存量为X={x1,x2,…,xN}，其中i=(1,2,…,N)表示第i个SKU。每个i都具有变量wi给出的标准重量/体积，并且拣选一次的容量（拣选小车容量）由G≥max{wi,i=1,2,…,n} 进行限制。一个工作周期内的PO是由PO={O1,O2,…,On} 表示的n个订单集合，Oj表示第j个订单。PO中对xi的总需求由Qi表示，PO中单个订单Oj对xi的具体需求由qij表示，其中Oj={q1j,q2j,…,qNj} 。不同客户在同一时间段下达订单的情况很常见，PO中可能具有处于不同订单的相同SKU，并且各订单的需求不相同。因此必须将PO分为多个拣选批次，这些批次将具有一种或多种SKU，最终由拣选员按照一定顺序进行拣选。故PO又可以由集合PO={B1,B2,…,Bm} 表示，其中下标m是总批次数，而Bk表示第k批次∀k={1,2,…,m}，每个Bk是由Bk={q1,q2,…,qN}表示的PO的子集，而qi是一个或多个订单的某个SKU 的需求数量。在本文的订单分批拣选系统中需要考虑：（1）应将哪些客户订单分配给同一批次；（2）每个批次开始拣选的时间；（3）每批订单应由哪个拣选员进行拣选。根据以上订单分批过程和系统要求，得出防止订单拣选过早或延误的拣选次序规划，并最大程度地减少拣选路径。

仓库为双区型矩形布局仓库，每一区域都包含10个高层货架（五层），两个区域的货架可以细分为1 600个仓储模块。这些模块由集合M={m1,m2,…,m1600} 表示，其中下标表示仓储模块。仓库设有一个进出口m0，拣货员从此口出发拣货并回到这个地点，因此批次Bk的拣货路径可以表达为RBk={m0,m1,…,mu,…,ms,m0} 。仓库存储策略为ABC 分类法，根据货物的出库频率划分储位，图1 显示了仓库的布局，其中不同的颜色表示ABC类中的SKU位置。货架巷道从进出口由近到远依次为巷道1 至巷道10，每个双排仓储模块为D1×D1的矩形模块，单排仓储模块为，货架间巷道宽度为D2，双区之间主通道宽度为D3。货位的储位使用[x,y,z]表示，其中y表示货物所处巷道的储位编号，双区货架从西到东依次由1到b表示，x表示货物所处的巷道数，z∈(0,1) 用于定义货架的前后排，后排货架(z=0)面向仓库进出口，前排货架(z=1)与后排货架面对面放置。仓库布局如图1所示。

图1 仓库布局图Fig.1 Warehouse layout

根据以上仓库参数，两货位mu、mh之间的最短距离由式（1）表示：

仓库进出口m0与任意储位mu的距离由式（2）表示：

Bk批次的拣选行走距离由式（3）给出，m个批次订单总的拣选行走路径由式（4）表示：

1.2 模型构建

本节描述在线订单分批拣选优化问题的数学模型：分批处理在线订单和生成批次内的拣货顺序，即如何将多个SKU分组为n个批次，在满足拣选载具容量和订单时间窗要求的情况下，减少拣货员在仓库内的拣选行程。

拣货员的行进速度为v，拣选第k批货物时行走时间可以由式（5）表示：

订单在仓库内的拣选时间以及订单拣选完成后的整理打包所花费的时间，由式（6）表示：

其中，Pti表示选取仓库内货物单元i所花费的时间，Sti是整理和包装每个独立订单所花费的时间。

基于以上内容，订单分批问题可以表述成如下模型：

目标函数表示最小化拣选时间，式（8）确保仓库可以满足订单的需求，式（9）表示每个批次的容量小于拣选设备的装载量。

2 基于规则的两阶段启发式算法

本文考虑解决具有多个拣货员的在线订单分批问题，其中没有有关即将到来的订单到达时间的信息。订单分批问题的离线模式属于NP-hard，而且其在线模式需要在合理的时间点内解决某些订单，因此本文提出了一种基于规则的启发式算法，以形成分批处理并形成拣货路径安排，将其分配给适当的拣货员进行拣货活动，目的是使所有批次的完成时间最小化。

2.1 整体算法思路

在订单拣选系统中区分三种类型的决策点：

A：至少一个拣货员无工作任务而且有一组订单未被处理的时间点。

B：订单到达的时间点，至少有一个拣货员无工作任务，处于空闲状态。

C：最后一个客户订单到达的时间点。

在每个决策点，都需要获取离线版本问题的解决方案，如图2。在时间t（每个决策点类型为A、B或C），将未处理的订单输入到批次生成系统中。如果存在未分配给任何批次的未处理订单，则使用批次启发式规则来生成一组批次，被输入到分批处理操作系统中通过分配规则（HA1、HA2和HA3）选择拣货员进行拣货。

图2 基于在线规则的算法流程图Fig.2 Algorithm flow chart based on online rules

HA1：使用选择规则为每个空闲的拣货员选择一个批次，拣货员立即启动所选批次的拣配任务。

HA2：将所有未处理的批次分配给空闲的拣货员，开始所有批次的拣配工作。

HA3：根据等式WTj=2ri+stj-sti，计算每个未处理批次定义等待阈值时间。在此等式中，j表示批次的索引，而i表示该批次中最长服务订单的索引。ri代表客户订单i的到达时间。stj和sti分别代表批次j和订单i的服务时间。根据批次的等待阈值，选择具有最大等待阈值的批次和空闲拣货员以等待可能的即将到来的订单。然后将剩余的批次分配给其他闲置的拣货员。如果只有一个批次和一个空闲拣货员，则根据此规则，空闲拣货员和批次将等待可能的即将到来的订单。当空闲拣货员和批次正在等待时，如果在出现新的决策点之前经过了等待阈值时间，则空闲拣货员立即开始选择批次进行拣货任务。

2.2 分批算法

分批处理算法将采用k-means聚类算法，其在处理样本量较大的分类问题时可以快速得到近似最优解[15]。由于订单分批问题的样本属于分类型数据，采用欧式距离定义其特性不能很好地划分数据之间的相似性。本文根据仓库的具体环境，以及订单分批的数据类型和数学模型结构，重新定义类中心和订单到类中心的距离。

订单分批的目标是减少同一批次所包含的商品种类数，加快拣选过程，因此设计两种类中心：一种是按照商品种类划分，定义某批次待拣商品种类为该批次的类中心。例如批次覆盖3个订单，订单1商品集合为{C,D}，订单2商品集合为{A,C,D}，订单3商品集合为{D,E}，(1,0,1,1,1) 则被用来表示此批次的商品类中心。另一种是按照货架位置划分，定义某批次待拣商品所处货架位置为该批次的类中心。例如批次覆盖3 个订单，订单1商品涉及货架{2,4,5}，订单2商品涉及货架{1,2,5}，订单3 商品涉及货架{4 ,5},(1,1,0,1,1) 则被用来表示此批次的货架类中心。这两种类中心通过权重进行合并，综合考虑拣货员的拣货种类和拣货行走距离。

2.3 拣货路径规划算法

遗传算法在订单分批问题的研究中应用广泛，充分证明了它在解决订单分批问题上的可行性，且遗传算法有很强的全局搜索能力和较强的鲁棒性。本文设计了遗传算法来分配批次订单给相应的拣货员，并对批次内的订单进行排序，获得较优的拣货路径。

在路径规划遗传算法中，染色体通过SKU 对应的储位单元进行编码。因此，据表1中的示例，拣货序列由每个批次中的具体商品对应的集合M={m1,m2,…,m1600}组成，并将m0输入到序列的初始位置和最终位置。

表1 遗传算法染色体结构Table 1 Chromosome structure of genetic algorithm

本文选择机制借鉴轮盘赌模式，在初始解集中挑选出进行交叉变异的父代。染色体随机两点交叉形成新的子代，变换方式如图3所示。生成的子代依据公式计算出的概率进行突变，突变方式如图4所示进行基因位的交换。完成上述操作后，对父代和子代分别进行适应度值排序，选取父代x%的优秀个体和子代(100-x)%的优秀个体组成新的种群，既防止算法过早地进入收敛，也可保证最优解不会丢失。算法进行多次迭代，达到停止标准后输出拣货序列。

图3 染色体交叉变换方式Fig.3 Chromosome crossover transformation method

图4 染色体变异方式Fig.4 Chromosome variation method

3 算例实验与结果分析

3.1 实验参数设置

本文采用文献[10]设计的数据进行实验，将拣选区域扩展为双区型仓库，包含10个拣选巷道和1 600种商品。车辆配送时间17：00—18：00，订单是14：00—18：00时间段内按照λ=14 的泊松分布随机产生。仓库拣选具体参数如表2所示。

表2 实验参数Table 2 Experimental parameters

3.2 结果分析

文献[10]基于巷道相似度进行订单的分批处理，并考虑订单的完成期限，设计实验将文献方法与本文提出的解决方案进行对比分析。在多拣货员的拣货系统中，拣货员数量对结果有显著影响，设立不同拣货员数量进行多组实验。

为明确订单规模对结果的影响和验证本文算法的有效性，设计实验分别处理500、2 000、5 000 规模的在线订单，在本文的在线订单系统中分别使用本文算法、遗传算法、蚁群算法、模拟退火算法进行三组实验。

由图5可知，当拣货员为2人时，根据本文算法求解出的有效订单数量较文献算法少，但拣货员数量多于2时，有效订单数、配送率（有效订单/总订单）、平均有效订单服务时间、订单延迟时间、剩余时间这5个指标，本文算法优于文献[10]算法。仿真结果表明，订单分批与拣货路径的联合调度方式可以有效减少订单的延迟或过早处理的情况。

图5 不同拣货员数量实验结果Fig.5 Experimental results of different numbers of pickers

图6～图8 分别为500、2 000、5 000 订单规模下拣货员行走里程的实验计算结果。收敛图表明k-means 算法与遗传算法的结合可以快速得到较优结果，并且其结果优于其他单一算法所得结果，尤其是在5 000 规模订单时可以得到远优于其他算法的结果，可以证明本文算法在一定程度上提升了仓库内的拣选效率。通过各算法之间的对比发现，k-means算法会首先将相关性较差的订单合并方式去除，随后采用遗传算法对结果进一步优化得出近似最优解。

图6 订购500规模下不同算法收敛过程Fig.6 Convergence process of different algorithms under order of 500 scale

图7 订购2 000规模下不同算法收敛过程Fig.7 Convergence process of different algorithms under order of 2 000 scale

图8 订购5 000规模下不同算法收敛过程Fig.8 Convergence process of different algorithms under order of 5 000 scale

4 结束语

本文考虑了人工订单拣选仓库中具有多个拣货员的在线订单批处理和调度问题。难点在于从动态到达的订单中形成批次，将其分配给拣货员，并以最小化所有批次的最大完成时间为目标的拣配过程。为了使模型具有实际意义，将所有批次的最大完成时间作为目标函数，一方面它可以减少拣货员的正常工作时间和加班时间，另一方面它可以减少交货时间，从而提高服务水平。采用k-means 算法和遗传算法构建基于规则的启发式算法，用以解决在线订单分批问题，并通过与相关文献方法的对比实验，验证所提出算法的有效性。

未来的研究目标应该是扩展本文提出的模型，以考虑除拣货工作以外的其他目标函数，并提出适当的算法来解决多目标问题。未来研究的第二个方向将是整合订单批处理和车辆路径问题，并共同优化它们。