动态并行分区拣选系统下订单分批问题研究

2019-06-03 00:35胡小林徐菱

物流技术 2019年5期

胡小林，徐菱,2

（1.西南交通大学交通运输与物流学院，四川成都 610031；2.西南交通大学综合交通运输智能化国家地方联合工程实验室，四川成都 610031）

1 引言

B2C电子商务环境下订单多采用分区存储策略，并具有种类多、数量少、需求不确定、时效性强等特征，分区存储可以有效提高动态环境下的订单拣选效率，因此有必要研究动态并行分区拣选系统下的订单拣选问题，如何在资源有限的情况下快速制定订单分区拣选策略是本文解决的主要问题，本文将协同运用订单分批与分区拣选方式。

国内外学者多采用启发式算法求解订单分批问题，最常用的三种启发式算法包括种子算法[1]、节约算法[2]和优先规则算法，还有一部分学者采用遗传算法[3-5]、邻域搜索算法[6-7]、聚类分析算法[8-9]等进行订单分批研究；当前对于多拣选人员的订单分批拣选主要集中在如何解决拣选通道的堵塞问题[6，10-12]；对于在线订单分批问题，王旭坪等[13]研究了基于紧急程度的在线订单分批算法，Chen[14]提出Green Area实时规划调整拣选人员的拣选路径，同时解决了订单分批、批次分配和路径规划问题，相较于其他算法，Green Area更适合实时订单环境下的订单分批问题。

本文研究动态并行分区拣选系统下的订单分批拣选问题（Order Batching Problem under Dynamic Synchronized Zone Picking System,OBPDSZPS），目前针对分区拣选的研究主要考虑分区批次商品数量、分区形状等因素对拣选系统的影响[15-16]，还有的学者将订单分批与分区拣选结合考虑[17-18]，也有学者考虑按分区工作量均衡原则进行优化，张珺[19]和王旭坪等[20]则研究了考虑分区工作量均衡和总拣选时间最短的双目标优化问题，并设计了改进的遗传算法求解。

综上所述，分区拣选的研究成果尚未考虑对分拣的优化，并且缺乏动态并行分区拣选的研究，本文考虑到离线订单环境订单在各个分区的不均衡分布，综合考虑订单分批、批次分配、路径优化和批次分拣，研究动态并行分区拣选系统下的订单分批拣选问题。此外本文考虑根据订单拣选截止时间和拣选通道相似度构建一个综合相似度指标进行订单分批，目前研究成果主要是根据通道相似度构建订单分批指标。总的来说，本文借鉴订单分批、分区拣选研究成果，进一步研究订单分批拣选问题，并提出相应的算法求解，数值实验验证了算法的有效性。

2 研究问题与模型构建

本文研究动态并行分区拣选系统下离线订单分批拣选问题，研究对象为企业前一天晚上00:00到第二天白天06：00累计生成的n个需求点的订单，每个需求点有r个订单，衡量该问题效益的指标为由拣选时间、等待时间组成的订单总服务时间。问题的关键决策包括：（1）如何确定订单所属的拣选批次；（2）如何将一个批次分配到不同的拣选分区；（3）分区批次订单的分拣顺序根据什么规则确定。

2.1 问题描述与符号说明

考虑有N个拣选截止时间已知的需求点，每个需求点可拆分为vi1,vi2,...,vir共R个订单，其具体流程如图1所示，系统涉及的时间如下：批次开始拣选时间，批次路径时间，批次分拣时间，批次拣选完成时间，订单开始包装时间，订单等待时间，其中表示需求点第一个与最后一个订单到达分拣台包装的时间差。

图1 OBPDSZPS问题订单履行流程图

模型假设如下：

（1）商品均有足够库存，不考虑补货时间；

（2）仓库为单区型，存储区域由平行排列的货架组成；

（3）已知所需拣选货品存储货位；

（4）拣选路径忽略垂直方向上的位移；

（5）需求点位置和时间窗已知。

2.2 约束条件

（1）订单拆分约束。一个需求点的需求只属于一个拣选批次，同时订单不可拆分，即：

（2）容量约束

（3）拣选约束

①批次分配约束。每一个订单必须分配一个拣选批次，每一个拣选批次必须分配到相应的拣选分区，即：

②批次拣选顺序与时间约束，即：

③变量取值约束

2.3 目标函数

该模型的目标是订单总服务时间最小化，订单总服务时间主要由两部分组成，即拣选时间和等待时间。

（1）拣选时间t pick。拣选时间包括路径时间trouting和分拣时间tsorting两部分。

①路径时间为批次路径时间之和，则拣选路径时间为：

设拣选人员h的批次订单bm在通道i距离前端和后端通道的最远存储位置为，员工进入通道gi的位置=0或1，=0表示拣选人员从前端通道进入，=1则表示后端通道进入，其中Sg1bmoh=0；通道宽度和货架宽度相等为Lc，通道长度为La，每一拣选批次通道数为Gbmoh，最大通道序号为，则人员h拣选批次m时在通道gi的拣选距离计算如图2所示。

通道拣选距离计算如下：

图2 拣选距离计算示意图

则bmoh的拣选距离为：

vh是拣选人员的行走速度；t0是一个订单的拣选时间，是批次bm的拣选路径时间，则：

②分拣时间tsorting。订单的开始包装时间为，批次分拣时间是批次中所有商品进入分拣台到分拣台处理完所有订单的时间差，即：

（2）等待时间twait。在拣选阶段采用并行拣选分区系统会导致需求拆分拣选，同一个需求点的订单分属于不同的拣选分区，并分配给不同的人员拣选，因此在拣选分拣阶段会产生属于同一辆车需求点的等待时间。

则订单的拣选等待时间为：

3 算法设计

3.1 订单分批算法HB

根据Elsayed研究成果[1]，结合本文建立的综合相似度指标，采用表示订单vir和vjr拣选通道的相似度，|Aislevir⋂Aislevjr|表示两个订单之间相同拣选通道的数量，|Aislevir⋃Aislevjr|表示两个订单的总通道数量，则根据两个订单vir和vjr之间拣选截止时间的差值计算两个订单拣选截止时间的相似度，越小，表明两个订单的拣选截止时间越接近、相似度越大，则拣选截止时间相似度，则，其中α+β=1。

HB算法包括订单选择和订单合并两个步骤，订单选择阶段采用拣选截止时间-通道-储位的规则（Picking Due Date-Aisle-Storage Location Rule，PDD-A-SL）选择种子订单。订单合并阶段在剩余订单中选择与vseed综合相似度指标最大的订单与其合并为一个批次（Largest Comprehensive Similarity Rule，LCS），并与拣选装置容量比较判断该订单是否加入该批次，直至所有的订单分批完成，HB算法的具体步骤如下：

步骤1：初始化。待分批订单集合Vp、QVp、、Qmax，并设置分批集合B为空。

步骤2：订单容量Vp判断。如果QVp＞Qmax，执行步骤3；如果QVp≤h·Qc，则只有一个拣选批次，将Vp合并为一个拣选批次，记录B={bm}、bm=Vp，运行步骤9。

步骤3：种子订单选择。依据PDD-A-SL规则选择种子订单vseed。

步骤5：合并订单选择。依据LCS规则在集合Vp中选择simivseedvir最大的订单vir。

步骤6：计算订单拣选完成时间。调用批次分配和分拣算法计算bm={vseed，vir}的批次订单分拣完成时间t，bm={vseed，vir}的最小拣选截止时间为

步骤7：容量判断。对vseed和vir两个订单的合并容量(qvseed+qvir)进行如下判断：

I.如果（qvseed+qvir）＜Qvmax、t＜tmin，则满足拣选装置容量和拣选截止时间约束，合并订单vseed和vir为新的vseed，并记录批次集合bm={vseed，vir}，从集合Vp删除订单vir，更新QVp，返回步骤5。

II.如果(qvseed+qvir)=Qvmax、t≤tmin或(qvseed+qvir)＜Qvmax、t=tmin，则满足拣选装置容量和拣选截止时间约束，合并订单vseed和vir为人员h的一个拣选批次，即批次集合bm={vseed，vir}，从集合Vp删除订单vir，更新QVp，返回步骤8。

III.如果(qvseed+qvir)≤Qvmax、t＞tmin或(qvseed+qvir)＞Qvmax、t≤tmin，则不满足拣选装置容量和拣选截止时间约束，令V′=Vpvir，从V′中根据LCS规则选择订单vir，返回步骤6。

IV.如果(qvseed+qvir)＞Qvmax、t＞tmin，不满足拣选装置容量约束，运行步骤7。

步骤8：订单分批完成判断。输出批次bm，判断是否还有未分批订单，若Vp=φ，运行步骤9；若Vp≠φ，返回步骤2。

步骤9：分批结束。输出拣选批次集合Bm={b1,b2,...,bm}，则有m个拣选批次，并调用分配和分拣算法计算批次订单分拣完成时间。

3.2 批次分配算法HBD

本文根据批次订单存储位置进行动态分区，对每一个拣选批次进行通道分配，使得每一个拣选批次的分区拣选时间均衡，缩短订单的等待时间。

图3 订单分批流程图

订单的存储位置已知，在订单分批完成后，各个拣选通道的订单及其体积已知，本文通过枚举法对通道的分配方案进行对比，最后选择最优的通道分配方案计算各个分区的批次拣选路径时间，其分配算法HBD具体步骤如下：

步骤1：初始化。输入批次订单集合bm、仓库总的通道数量n、拣选人员数量h。

步骤2：位置标注。根据bm中订单vir的存储位置，计算各个通道订单的体积与重量，并标注各个订单位置，找出各个通道距离前端和后端通道的最远存储位置

步骤3：通道分配。分别设置i1=1:n、i2=i1+1:n、…、ih-1=ih-2+1:n。

步骤4：拣选路径时间计算。根据式（13）-（17）计算各个拣选人员拣选完所负责通道订单的拣选路径时间，并记录每种通道分配方案下各个拣选人员的分区拣选路径时间、时间标准差和体积，若对于i1,i2,...,ih-1存在订单总体积超过拣选装置体积约束，则将i1,i2,...,ih-1标记为不可行解。

步骤5：分区结果输出。选择时间差最小的通道分配方案，并输出各个拣选人员的批次拣选路径时间。

3.3 分拣优化算法HSO

综上所述，分拣算法Hso主要包括拣选分拣台分配和投放顺序，分拣台分配基于车辆离开时间规则VDT-D确定，投放顺序则包括订单选择与顺序确定两个步骤：订单选择基于最小化车辆离开时间和合并包装订单规则（Smallest Vehicle Depart Time and Spilt Order Rule，SVDT-SO）；顺序确定则基于最大化商品包装难度（Largest Package Difficulty Rule，LPD）规则确定，即bmoh一部分订单Vs={vir,vjr,...,vlr}，若difvir＜difvjr＜...＜difvlr，则Ovlr＜...＜Ovjr＜Ovir。Hso具体算法规则如下：

步骤1：初始化。确定批次bmoh订单集合Vbmoh，并设置bmoh的顺序集合V′为空、顺序记录Obmoh中所有订单的顺序为0。

步骤2：分拣台分配。根据VDT-D分配分拣台。

步骤3：指标计算。计算Vbmoh中所有订单的difvir。

步骤4：订单选择。根据SVDT规则选择订单集合Vs，其订单数量为Q(Vs)。

步骤5：容量判断。对该集合的数量Q(Vs)做如下判断：

I.如果Q(Vs)=1，在Obmoh中更新订单vir的分拣顺序，将Vs={vir}的订单vir加入V′，删除Vbmoh中Vs的订单集合，运行步骤8。

II.如果Q(Vs)＞1，即Vs={vir,vjr,...,vlr}，删除Vbmoh中Vs的订单集合，运行步骤6。

步骤6：订单选择。根据LPD原则选择Vs中订单vir。

步骤7：顺序确定。从Vs中删除订单vir，将订单vir加入V′，并在Obmoh中记录订单vir的分拣顺序。如果Vs≠φ，返回步骤6；否则运行步骤8。

步骤8：分拣顺序确定完成判断。判断是否还有未确定分拣顺序的订单，若Vbmoh=φ，运行步骤9；若Vbmoh≠φ，返回步骤4。

步骤9：分拣顺序确定结束。输出顺序集合V′和顺序记录Obmoh，则批次bmoh的订单分拣顺序为V′={v1,v2,...,vn}，计算批次分拣时间，并根据Obmoh中订单vir的拣选顺序和式（20）-（24）计算订单的分拣完成时间

4 仿真实验及其结果分析

4.1 实验参数设计

为验证模型和算法的有效性，将优化分拣包装顺序但分区固定的系统（算法A）、不优化分拣包装顺序但考虑静态分区拣选系统（算法B）、不优化分拣包装顺序的静态分区拣选系统（算法C）与本文拣选系统（算法H）进行对比，其他参数设置如下：

（1）需求点数量V=60，订单数量为200，即一个需求点有多个订单；

（2）仓库拣选区域存放1 000种商品，同一种商品存储位置相同，仓库包含20个拣选通道，每列货架有100个货位，通道宽度为5m，通道长度为100m，横向通道长度为100m；

（3）拣选人员有4个，拣选装置体积为8m3，行走速度为1.2m/s，单位订单拣选时间为5s，员工从最左边通道开始拣选，在通道内需要拣选左右两边货架的订单商品，拣选完成后再进行分拣；

（4）自动分拣线的传输速度为2m/s，订单投放间隔时间为3s，自动分拣线总共有4个分拣台，分拣台之间间隔为20m。

算法运用MATLAB R2016a在操作系统为Window10 64-bit、CPU为16GB的计算机上运行。

4.2 实验结果分析

为确保实验结果的可靠性，随机生成3种不同的订单规模环境，通过设置HB算法中综合相似度不同的α和β的取值，对比不同相似度参数环境下的批次拣选路径时间，寻找最优的综合相似度参数取值。

分别设置n=200,n=400,n=500三种订单规模，采用本文提出的订单分批和批次操作算法进行订单分批，三种订单规模环境下α、β不同取值的计算结果见表1。

表1 不同参数下数据

从表1可以看出，随着α取值的增加，批次拣选路径时间逐渐减少，当α=1，即按拣选通道相似度进行分批，批次的拣选路径时间最短，但是随着订单量的增加，按拣选通道相似度进行分批已经不适合大规模的订单分批问题；采用本文提出的算法求解，当α=0、β=1时，订单相似度根据其拣选截止时间确定，虽然不会出现订单延迟，但该种参数设置下批次订单在仓库过于分散，导致了批次拣选路径的增加；当α增加到0.7、β为0.3时，拣选通道相似度占总相似度的70%，使得批次订单包含了多个不同拣选截止时间的订单，开始出现了订单延迟，且随着α取值的增加，拣选路径时间急剧下降，但同时延迟订单数量和总延迟时间亦急剧增加，因此当α≥0.7、β≤0.4时，无法使所有订单在其拣选截止时间之前完成。从表1中可以看出，最优的参数取值为α=0.6、β=0.4。

图4 不同参数下指标变化图

本文提出考虑优化分拣包装顺序和分区拣选时间均衡的动态并行分区拣选系统，为分析该系统的效率，在α=0.6、β=0.4取值下，将算法A、B、C与算法H进行对比，分别设置n=200,n=500,n=800,n=1100四种订单规模，对四种算法的批次平均等待时间、批次路径时间标准差、分拣包装时间和订单处理时间进行对比分析，数据见表2。

从表2中可以看出，与算法A相比，本文提出的算法H优化了18%的批次订单平均等待时间和15%的订单履行时间，批次订单履行时间平均为0.639h，最高优化率达到了30%，批次路径时间有所增加，但批次路径时间的标准差优化率为24%；当n=800时，批次订单等待时间为0.2-0.6h，优化率为36%-56%，当n=500时，第二批次订单等待时间为0.591h，优化率为7%，这四个批次的批次等待时间仅为平均批次等待时间的50%-60%，同时优化率高于其他批次20%-30%，这是由于该种订单规模下，存在某些批次的容量远小于拣选装置容量，按本文提出的等待时间最小目标进行批次订单的分配可以使得各个拣选分区的工作量均衡，使订单拆分拣选后以最小的拣选路径时间差拣选，从而大大降低批次的等待时间，在拣选装置剩余容量较小时，批次的平均等待时间在0.2h-0.6h之间。

算法B的平均批次履行时间为0.719h、批次平均等待时间为1.479h，与算法B相比，算法H的批次路径时间相差不大，多个拣选批次的路径时间标准差相同，但是降低了26%的批次平均等待时间和12%的订单履行时间，同时算法H减少了对各个批次的分拣包装时间，平均优化率为7%，这说明本文提出的分拣包装顺序优化规则通过优先分拣拣选截止时间靠前和包装难度较大的订单可以减少订单的等待时间，同时在批次订单量较小的情况下，分拣包装时间优化率出现了负值，说明算法H的分拣包装规则对订单量较大的批次有更好的优化。

表2 不同参数下指标数据

算法C的平均批次履行时间为0.778h、批次平均等待时间为1.562h，与算法C相比，算法H优化了24%批次拣选路径时间标准差、31%的平均等待时间和18%的订单履行时间；同时通过A、B、C算法之间的对比分析，发现算法A和算法C相比，平均降低了17%的等待时间、3%的订单履行时间和分拣包装时间，算法B和算法C相比，平均降低了3%的等待时间和5%的订单履行时间，增加了1%的分拣包装时间，算法A和算法B之间没有可比性，再次验证了本文提出的考虑分区拣选时间均衡和优化分拣包装顺序的方法可以大幅度的降低订单等待时间和订单履行时间。

综上所述，可得出如下结论：

（1）本文提出的算法可以有效解决订单分批与批次调度问题，保证所有的订单在拣选截止时间之前拣选完成，并且经过多次实验发现，综合相似度参数最优取值为α=0.6、β=0.4；

（2）通过算法H与算法A、B、C的对比分析发现，算法H通过合理分配各个拣选分区的订单和优化订单分拣包装顺序，使得包装难度较大的订单先分拣，降低了18%-31%的平均等待时间、9%-24%的拣选路径时间标准差、5%-7%的分拣包装时间和12%-18%的订单履行时间。

5 结语

本文以最小化订单总服务时间为目标，研究动态并行分区拣选系统下订单拣选问题，构建了动态并行分区拣选系统下订单分批拣选模型，并设计算法求解。仿真实验表明，综合相似度中拣选截止时间相似度和拣选通道相似度最优的参数取值为，与算法A、B、C的对比分析则证明了本文提出的批次分配算法和分拣算法可以缩短订单的等待时间和订单的履行时间。本文提出的算法可以解决离线订单系统下订单拣选问题，对B2C电子商务企业处理凌晨00:00-06:00的订单拣选与配送问题具有一定的借鉴意义。但本文仅研究了需求量已知的情况，随着信息技术的发展，实时订单系统下并行分区拣选系统的订单分批拣选有待进一步研究。