基于JIT装配模式的网上超市订单分拣优化模型

黄敏芳，张源凯，王颜新，胡祥培

(1.华北电力大学经济与管理学院， 北京 102206；2.大连理工大学管理与经济学部，辽宁 大连 116024；3.北京联合大学商务学院，北京 100025;4.新能源电力与低碳发展研究北京市重点实验室(华北电力大学)，北京 102206)

1 引言

近年来，网上超市逐渐成为主流的商品零售方式之一。然而，高额的物流成本和低效的物流作业成为制约网上超市经营与生存的首要因素。从成本角度分析，订单分拣成本占配送中心运营成本的55%以上[1]。订单分拣环节的优化对订单履行成本的节约至关重要。如何在上百万种商品中将订单要求的商品高效、准确地分拣出来，是网上超市亟待解决的难题。

在分拣环节，网上超市每个订单都需经过分组、分割、拣货、集货复核、包装这一作业流程，大量个性化订单导致这一流程的组织和调度变得十分复杂。一般B2C电商采用的按单分拣或者基于整个仓库的批量分拣方法已远远满足不了大型网上超市在海量商品中拣选大批量个性化订单的需求。网上超市所销售的商品的种类和形态多样、成本高昂、需求的不稳定，企业在短期内无法实现全自动仓储管理，还需依靠人工手动完成拣货、集货理货、包装等作业。由于还缺乏科学规范的方法体系来指导人工作业，网上超市各个作业的效率和时间在这一复杂的多环节作业流程中都无法保障。网上超市订单分拣、包装作业与产品装配流水线具有相似性，即一个订单包裹为一个产品，订单拣选、集货理货、包装对应于产品加工的工序，因此本文借鉴大规模生产企业的成组装配流水作业模式以及针对多品种、小批量生产条件下的JIT装配模式的思想，建立在仓库内各独立的拣选区域进行并行拣货的大批量订单成组分拣方法，组织和协调订单的拣选、集货复核和包装三个关键作业环节，以指导作业人员的实际操作，确保网上超市订单分拣及包装作业流程能高效、准确、平衡、流畅运转。

基于JIT装配流水线的订单分拣作业的优化涉及两个方面：订单分批与批次订单的排序。已有的订单分批方法的优化策略主要集中在按订单到达的时间窗分批[2]、按订单中商品存储位置的邻近性分批[3]和以最小化总完成时间和最小化订单延迟时间为目标来实现订单分批[4-5]。学者们也提出了用于求解按不同策略建立的订单分批模型的精确求解方法[6]和启发式算法，如自组织神经网络分类方法[7]等。其中，Scholz等[8]和Hong和Kim[9]提出的启发式算法均能求解数量级为103的大规模订单的分批问题，但仅适用于订单包含一种商品的情况。近年来，有学者提出将客户订单的分批与排序[10-11]、订单的分批与拣选路径进行集成优化[12]，以及将订单分批、订单批次的分派、拣选路径的选择三个问题进行联合优化[13]。上述成果仅针对单个仓库内的订单拣选作业进行优化。近期也有学者研究了并行分区拣选下考虑工作量均衡的订单分批问题[14]。批次订单排序方面较有借鉴意义的成果主要集中在装配线中加工产品的排序问题上，其研究工作多是针对JIT生产系统。目前装配线排序问题一般都按多目标问题来研究。Sun Hui和Fan Shujin[15]针对一家门锁公司的混合装配线产品排序问题构建了整数规划优化模型。鲁建夏等[16]以最小化总调整时间、最小化超载和空闲时间为目标建立了混合装配线排序的多目标模型，运用混合人工蜂群算法求解模型得到目标函数的最优解。也有学者提出对平衡和排序问题进行联合优化，如，Kucukkoc和Zhang[17]针对混合装配线的双边装配线问题，运用蚁群优化方法为排序问题以及线路平衡问题提供了较优的解决方案。Manavizadeh 等[18]针对任务平衡和排序问题，提出以最小化周期时间、最小化工作站浪费和减少工作负荷为优化目标。

已有的关于订单分拣中订单分批问题与排序问题的优化工作都围绕最小化拣货行走距离或拣货时间这一目标，虽然提升了作业效率，有助于缩短订单分拣作业期，但都未从整个订单分拣流程角度出发，而仅仅是单个拣货环节的优化，效果较好但无法保证后续工作的效率，并且也未考虑网上超市订单由于包含多品项商品而被拆分在各个拣选区域需要合并打包的问题。基于JIT装配流水线中对加工产品在各道工序上排序的优化思想对本文有一定的借鉴作用，但对于同时加工多品种产品，单道工序中存在多台机器平行加工且需在下一工序中合并，这依然是该领域的一个难题。在网上超市每天需处理巨大订单量的情况下，如何保证每批商品总品项数和各个拣货区域工作量的均衡，如何将分布在各个拣选区域的同属于一个订单的商品能在恰当的时间送到包装车间进行合并打包，科学的订单分批与排序是解决上述问题提高订单分拣作业效率的关键，也是本文致力于研究的问题。

本文首先针对订单分拣三道工序提出作业时间计算模型，然后基于仓库内各存储区域并行拣货策略，建立订单分批与排序的联合优化模型，并设计两阶段启发式方法求解该模型。第一阶段提出基于工作量均衡的订单成组分批模型，设计订单分批方案生成策略，第二阶段将批次订单排序问题转化为置换流水生产调度问题，并采用经典的NEH算法求解。

2 基于并行分区系统的订单分拣作业流程分析与问题求解原理

由于庞大的商品种类数，网上超市的商品需按照商品关联度进行分类存储，形成多个独立的商品存储区域，由固定的拣货人员负责固定区域的商品，这一策略可使拣货员拣选商品的分布面积减小，减少通道拥挤，提高效率。网上超市单个订单中包含的商品往往分布在多个存储区域，因此需将各存储区域的商品拣选完毕都送至包装车间，才能进行该订单的包装工作。

按照流水线作业的原理和思想，将订单拣选、集货复核、包装作业作为顺次开展的三道工序来优化作业流程，合理规划三道工序的作业时间，可大大提高人员设施的利用率。在多个存储区域间进行并行拣货的订单批量分拣作业流程可抽象为如图1所示的包括多道工序的流水线作业图。

图1 基于分区并行拣货的订单分拣各工序作业示意图

以订单批次A和批次B的顺次分拣作业为例。订单批次A包含的商品分布在存储区域1和存储区域2，分别形成A11和A12两个拣选单，这两个区域的拣选人员各自将相应商品拣选完毕并在指定时间段内送至包装车间的缓存区域，集货后由复核人员按订单批次A中单个订单内容审核商品，包装人员按照订单进行打包并将包裹放置在相应的装货点上。订单批次B包含的商品分布在存储区域1、存储区域2和存储区域3，分别形成B11、B12和B13三个拣选单，拣货工序完成A11和A12工作后，即可进行B11、B12和B13的拣货工作。以此类推，完成订单批次A和批次B的订单分拣作业。图2示例了三个订单批次A、B、C在拣货、集货复核、包装三道工序上的流程作业的时间甘特图。

图2 三个订单批次ABC流水作业的时间甘特图

图3示例了订单批次B在经过订单拣选、集货复核、包装作业三道工序时的作业时间关系。

图3 订单批次B的各项作业时间关系图

本文研究的基于JIT模式的网上超市订单成组分拣问题包含两个优化问题：基于并行分区拣选的订单分批问题和订单批次排序问题。这两个问题既是顺次优化关系，又相互制约，如将两者进行联合优化，将有助于实现现有订单分拣与包装设施能力的最大化利用。

3 网上超市订单分批与排序的联合优化模型构建

3.1 问题假设及符号定义

模型的假设条件如下：

(1)顾客对所有商品需求概率一致；

(2)一个订单不允许分割在不同的批次进行拣选；

(3)当前批次订单分布在多个拣货区域的商品均被拣选完毕后，再进行下一个批次订单的拣选；

(4)订单集合确定后，不再插入新的订单，即不考虑紧急订单。

参数定义：

O一定时间段内到达的订单集合，O={1,…,n}；

J可行的订单分批方案集合，J={1,…,m}；

P拣选区域集合，P={1,…,pmax}；

i顾客订单，i∈O；

j订单批次，j∈J；

k订单批次被安排的序列位置，k∈K；

p拣选区域，p∈P；

jp订单批次j在拣选区域p的拣货单；

常量:

C单个批次最大订单数，与仓库集货复核等环节的规模配置相关，如订单分拣流程中某个薄弱工序在单位时间内可能处理的订单数量，可根据当前仓库订单分拣的现状凭经验确定；

sip订单i分布在拣选区域p的SKUs数量；

si订单i包含的SKUs数量；

tsetup单批订单拣货处理的准备时间；

tpick每单位SKU的拣选时间；

tsort集货复核时间常量；

tpack打包时间常量；

α,β系数，0<α,β<1；

变量：

Tmax所有订单批次的完工时间；

决策变量：

xij0-1变量，xij=1表示订单i分派到订单批次j，否则为0，i∈O,j∈J；

yjk0-1变量，yjk=1表示订单批次j分派到顺序位置k，否则为0，j∈J,k∈K。

3.2 订单分拣流程中各工序作业时间的计算

为构建网上超市订单分批与排序的联合优化模型，需计算订单分拣流程中订单拣选、集货复核、包装作业三道工序的作业时间。

(1)拣货作业时间计算

传统的订单分批一般以缩短单个存储区域内的拣货路径和拣货时间为目的，而本文站在整个订单分拣流程的角度来考虑某个拣货区域所需的拣货时间，因此为简化问题的求解，选取与拣货时间密切相关的单批订单拣货处理的启动时间和区域所需拣选商品品项数，得到批量订单在单个存储区域拣货时间的函数。订单批次j在分区p的拣货时间的计算模型如下：

(1)

订单批次j对应的存储区域所需拣货时间的最大值(如图3中的拣选作业B11)为订单批次j的拣货时间，该时间对应的存储区域能送货至包装车间的时间点可作为其它存储区域送货时间的参考。则订单批次j的拣货时间为：

(2)

(2)集货复核作业时间计算

根据调研，订单批次的集货复核时间与这批订单所包含的存储区域个数以及这批订单中包含的商品品项数相关，计算模型如下：

(3)

(3)包装作业时间计算

另外，订单批次j的包装作业时间与该批订单数量以及每个订单包含品项数相关，计算模型如下：

(4)

3.3 订单分批与排序的联合优化模型

该问题的数学模型描述如下：

MinTmax

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

xij,yjk∈{0,1}, ∀i,j,k

(13)

其中，目标函数(5)是最小化所有订单的总完工时间；式(6)为所有订单最大完成时间；式(7)确保一个订单只分配给一个批次；式(8)确保一个批次订单只在排序的一个位置上；式(9)确保在排序的一个位置上只能放置一个批次订单；式(10)一个订单批次所包含订单数不能超过最大订单数C；式(11)表示订单批次在第h阶段k位置的完工时间；式(12)表示订单批次在第h阶段k位置的开始时间；式(13)表示决策变量均为0-1变量。

4 网上超市订单分批与排序的联合优化问题的求解算法

订单分批与排序的联合优化模型属于非线性混合整数规划模型，使用精确算法仅能求解极小规模的问题。对于一般的问题，本文基于缩减求解空间的思想，提出按照“订单成组分批→批次订单排序”的两阶段启发式优化的思路来求解问题。

4.1 基于工作量均衡的订单成组分批方法

订单分拣流水线上的空闲等待时间是由各批次订单在各工序上作业时间的差异以及单个批次订单在同一工序的不同作业区域的作业时间的差异造成的。比如，在拣货工序，由于客户订单对各个分区中的商品的需求不同，导致一批订单分布在各拣货区域的工作量存在差异。本文提出在对订单进行分批时，通过均衡各个订单批次的规模和单个批次订单分割在各拣货区域的工作量这两方面来减少空闲等待时间。对于前者，根据订单分拣流程中各工序作业时间的计算模型，可知各订单批次在各工序上的作业时间均与该订单批次所包含的SKU数相关，因此，各批次作业时间的均衡可用每个批次所包含SKU数与批次平均SKU数的差异进行表示。对于后者，先根据所有订单包含的商品分割在各拣货区域的SKU数量按比例分配拣货人员，然后要求单个批次订单在单个分区工作量与所有订单分割在该拣货分区的平均工作量尽量均衡。基于上述思路，构建了以工作量均衡为目标的订单成组分批模型，目标函数为：

(14)

订单成组分批模型的约束条件为式(7)，(10)，(13)。目标函数(14)最小化了各个订单批次间的SKU数的差异，以及单个批次订单与所有订单分割在各个拣货分区的工作量的差异。由于订单分批涉及的订单规模庞大，变量较多，使得该模型很难利用已有的精确算法在短时间内有效求解。如1000个订单，20个订单分批，则变量xij的数量就可以达到20000个。因此，本文提出借鉴Local Search中Relocate和Exchange的思想，根据订单分批规模的限制条件，设计了两种订单分批方案生成的改进策略，并结合成本节约的思想，不断迭代改进，输出较优的订单分批方案。求解算法的具体步骤如下：

步骤2.按订单到达时间的先后顺次选取ω个订单组成不同批次，余下不足ω个订单组成一个批次；

步骤3.初始化参数CapCount=0，设置参数CapCost；

步骤4.随机选取两个订单分批A(包含订单数为C)和B(包含订单数为C或者少于C)，调整方法为：

i)Relocate策略：如果订单分批B的订单数小于C，则分别依次计算将订单分批A中的单个订单调整到B分批中的节约成本Δf(xij)，选取最大节约成本对应的订单，如果该节约成本小于GapCost，则GapCount++，否则将该订单由订单批次A调整至订单批次B；

ii) Exchange策略：如果订单分批B的订单数等于C，则顺次在A、B中分别选取一个订单进行交换，并计算节约成本，选取最大节约成本的两个订单，如果该节约成本小于GapCost，则GapCount++，否则将该两订单进行交换；

步骤5.不断循环迭代步骤4直到达到最大的迭代次数MaxIter或者GapCount达到最大的次数限制MaxGapCount。

4.2 批次订单排序方法

每个订单批次均需要经过分拣、集货复核、包装这三个工序，将每个订单批次看作是一个工件，则批次订单排序的子问题可以转化为置换流水生产调度问题(Permutation Flow Shop Problem)[19]，因此构建批次订单排序的置换流水生产调度模型，目标函数为式(5)，约束条件为式(6)，(8)，(9)，(11)，(12)，(13)。置换流水生产调度问题是典型的NP-hard问题，本文结合经典的NEH算法求解该子模型。NEH算法是Nawaz等[20]提出的求解置换流水车间调度问题的经典启发式算法，经过许多学者的比较，已经证明了NEH启发式算法是最具有竞争性的算法，目前有许多算法都是在此基础上提出来的[21]。

本文将批次订单对应为工件，订单处理的三个环节对应为工件的三道工序，从而直接调用NEH算法进行求解。其中，每个排序的完工时间调用式(11)和(12)迭代进行计算。

NEH算法求解批次订单排序的步骤如下：

步骤2:将订单批次按照总流程时间tj从大到小排序组成备选列表List。选取列表List的前两个订单批次，并评估两种可能的排序，选择完工时间较短的排序组成初始排序Schedule。

步骤3:逐次选择List中的其他订单批次j,j=3,…,m，然后通过将该订单批次放置在排序Schedule中j个可能的位置上找到当前最好的排序Schedule。输出最后的排序Schedule。

5 实验设计与结果分析

根据国内某大型网上超市销售商品的仓储布局及订单履行流程的实际情况，构造算例用于验证本文所提出的模型和求解方法。基于大多数实际仓库的分区配置，设定拣货分区的个数pmax=3。拣货时间的相关参数(tsetup，tpick，tsort，tpack，α，β)由该大型电商仓库实地调研所得，并与相关仓库调度运营人员沟通交流确定。单个批次最大订单数C由仓库调度人员经验进行确定。关于订单方面的相关参数，本文参考文献[22]中对大规模订单参数的设置，订单个数N从500 到3000，订单需求服从泊松分布λ=1.5。在此基础上，增加对订单为10000的超大规模问题的测试。

为了做对比研究，以该网上超市现有的波次分拣方法作为对比对象。目前大型网上超市或者其它网上零售商多采用订单波次拣选方法。订单波次拣选是指每隔一段时间(一般5～10分钟)，对“订单池”中具有相同属性的订单(如订单配送地址、商品种类)分成若干个订单批次。在该数值分析中，订单波次规模同本文参数C的取值。

初始实验参数如表1所示。

本文的订单分拣优化方法与波次拣货方法在求解不同规模的算例的对比结果如表2所示。由于计算效率均比较高(均小于1分钟)，因此仅对订单总完工时间进行对比分析。可以发现，相较于波次拣货方法，本文方法可以节省1.13%～8.34%的订单总完工时间，提高了网上超市订单处理作业的效率。并且随着网上超市订单规模从500个增加到10000个，本文方法得到的结果由节省308.34增长到816.5，可见本文方法可以有效解决大规模网上超市订单分拣的问题，并且随着订单规模的增大，节约的订单分拣作业时间越多。

表1 初始参数设置

表2 数值计算对比分析

由于批次订单容量C直接影响网上超市订单的分批与排序效果，因此本文在1000个订单规模的算例基础上针对批次订单容量的变化做了灵敏度分析，结果如图6所示。随着批次订单容量从10增长到35，本文方法相较于传统波次拣货方法的改进呈现一个先增长后减少的趋势。这说明存在一个最优的订单批次规模配置使得本文的方法能够达到最好的效果。

图6 批次订单容量改变下本文方法的改进变化

6 结语

本文结合大型网上超市订单数量庞大、订单包含品项多等特征，针对订单拣货、集货复核、包装这一作业流程，建立了订单分批与排序的联合优化模型，并提出了两阶段启发式优化方法。将JIT装配理论引入订单分拣领域，为网上超市订单分拣的优化决策提供了一种新方法，提高了订单分拣理论的实用性和普适性，有利于发展网上超市这一新型电子商务模式。在实践上，理论成果可为指导网上超市或其它B2C电子商务企业的配送中心的拣货人员的实际作业提供借鉴，有助于电子商务企业实现效率与客户服务水平的综合提升。

所取得的成果及创新之处可归纳为：(1)从缩减问题求解空间的角度出发，提出的基于仓库内各存储区域并行拣货的大批量订单成组分拣方法，考虑了包装车间的有限空间，保证各拣选区域仅在恰当的时间将正确的商品送至包装车间，提高了包装车间作业的有效性和高效性；(2)建立基于JIT装配流水线思想的订单分拣作业模式，将订单拣选、集货复核、包装作业作为顺次开展的三道工序来优化作业流程，有助于合理规划工序的作业规模和时间，实现订单分拣流程中各工序的高效、均衡运转；(3)建立的订单批次排序模型充分考虑了根据网上超市订单分拣的实际情况安排订单分拣作业投产计划，可通过加入订单权重等因素灵活调整排产优先级，使排序模型更具有实际应用价值。

未来研究方向有：订单分拣流程中的集货复核和包装两道工序有多个设施和人员同时操作下，订单分批与排序问题的研究；现实订单分拣流程会产生大量不确定性，进一步研究考虑流水线单个工序产生扰动的订单分拣问题。