基于AGV的智能仓库系统订单分批问题研究

李珍萍，付红叶，卜晓奇，张国维，吴凌云

(1.北京物资学院 信息学院,北京 101149; 2.中国科学院 数学与系统科学研究院,应用数学研究所,管理、决策与信息系统重点实验室，国家数学与交叉科学中心,北京 100190; 3.中国科学院大学 数学科学学院,北京 100190)

0 引言

随着电子商务的迅速发展，电商每天要处理的订单数量日益增长，在订单处理过程中，超过50%的时间耗费在订单拣选作业上[1]。因此，缩短订单拣选时间是提高物流效率、降低物流成本的有效途径。传统配送中心采取拣选人员在货架中来回穿梭的人到货拣选模式，劳动强度大、耗时长，且拣选过程容易出现差错。近年来出现的基于自动引导小车(AGV)的智能仓库中，拣选人员站立在固定的工作台前，由仓储机器人把货架搬运到拣选人员面前，完成订单拣选工作。这种新型的货到人拣选作业模式，将拣选人员从繁重的工作中解放出来，大大提高了拣选工作效率[2]。无论是在传统的人到货拣选仓储系统还是最新的货到人智能仓储系统中，单个订单中包含的物品种类和数量都不多, 为了提高订单拣选效率，配送中心通常将多个订单合并成一个拣选单进行拣选。订单分批问题就是将订单池中的众多订单按照一定的规则划分成若干个批次, 每一批次的订单构成一张拣货单并在一次作业中完成拣选[3]。在基于AGV的智能仓库中，采取合理的订单分批策略可以大大减少工作人员的拣选操作次数和仓库机器人搬运货架的次数，降低拣选成本、提高拣选效率。

针对传统人到货拣选模式下的订单分批拣选问题的研究成果已经非常丰富[4～11]。由于基于AGV的货到人拣选仓库系统的工作流程与传统的人到货拣选仓库系统的工作流程不同，已有的针对人到货拣选系统中订单分批问题的研究成果不能直接用于解决货到人智能仓库系统中的订单分批拣选问题。近年来，部分学者针对货到人智能仓库系统中的订单分批拣选相关问题开展了研究工作。张彩霞等综合考虑订单分批、路径、任务分配等三个过程，研究了基于AGV的“货到人”拣选模式的优化方法和模型[1]。王艳艳等以并行自动分拣系统为研究对象，运用迭代优化、聚类分析等工具，研究了智能仓库中订单拣选拆分优化、系统调度优化及补货缓存优化问题, 建立优化模型并设计了启发式自适应遗传算法[12]。王善超以订单是否拆分为准则，建立基于通道相似度的订单不可拆分模型和基于车辆路径问题的订单可拆分模型，分别设计了求解两种模型的算法，并比较了在两种独立分拣模式下不同订单分批方法的工作效率[13]。Lenoble Nicolas等人在具有多个垂直升降模块的自动化仓库中进行实验，以完成订单拣选时间最短为目标建立优化模型，并设计了求解模型的元启发式方法[14]。王旭坪等人研究了基于相似度聚类的订单分批策略，利用相同通道数系数作为衡量订单间相似度的指标[15]。Xi Xiang等人研究了Kiva系统中的储位分配和订单分批问题，以最小化货架的访问次数作为订单分批的目标。通过最大化顺序关联或最小化顺序异化获得初始可行解，并采用变邻域搜索算法对可行解进行改进[16]。

针对订单分批问题的研究大部分都是根据订单相似度进行聚类。在传统人到货仓储系统中，拣选人员穿越通道的数量是影响拣选效率的主要因素，因此订单相似度主要根据订单中物品所在的通道是否相同进行定义。基于AGV的智能仓库系统中，机器人搬运货架的次数和拣选人员从货架上拣取物品的次数是影响订单拣选效率的两个主要因素，现有文献大都基于其中一个因素定义订单相似度，尚未发现同时考虑两种因素的研究成果。

本文将研究基于AGV的智能仓库系统订单分批拣选问题，在给定仓库布局、货位分配信息的前提下，同时考虑订单中包含的商品信息和订单中商品所在的货架信息，构建加权订单相似度指标，并基于该指标研究订单分批策略。建立订单分批问题的数学模型并设计求解模型的算法，同时兼顾工作人员从货架上拣取商品成本和AGV搬运货架成本，使智能仓库系统完成订单拣选的总成本达到最小。

1 问题描述与分析

基于AGV的智能仓库订单分批问题可以描述为:已知仓库中有S个货架，每一个货架上有h个货位，每个货位最多存放一种商品，仓储中共存放着M种商品，且每种商品的货位已知。假设该仓库某时刻的订单池中有N张订单需要拣选，已知每张订单上包含的商品品项信息、工作人员从货架上拣取一种商品的成本、AGV搬运一次货架的成本。问如何将N张订单进行分批才能使订单拣选的总成本最低？

为了简化问题，假设每张订单中的商品均不缺货；每种商品在货架上的货位固定，每个货架在仓库中的位置固定；拣选每个批次的订单时都需要AGV把包含该批次订单商品的货架搬运至拣选台，等待工作人员从货架上取下待拣选商品后，再将货架搬回仓库中原来的位置；拣选下一个批次订单时需要重新搬运货架，即不同批次订单中的同种商品不能合并拣选。

在以上假设下，影响每个批次订单拣选效率和拣选成本的主要因素包括两个方面，一个是工作人员从货架上拣选商品的次数；另一个是AGV将货架搬运至拣选工作台的次数和来回行走距离。由于每个货架在仓库中的位置是确定的，为了简化问题，计算订单拣选成本时可以不考虑货架搬运距离，只考虑货架搬运次数。

基于以上假设，为了提高订单拣选效率、降低拣选总成本，在对订单进行分批的时候，应该重点考虑减少工作人员从货架上拣取商品的次数、和减少AGV搬运货架的次数。如果两个订单中包含的商品品项相同，若将它们合并拣选可以使工作人员从货架上拣取商品的次数减少一半；如果两个订单中包含的商品存放在同一个货架上，若将它们合并拣选，可以使AGV搬运货架的次数减少一半。因此在进行订单分批的时候，应该综合考虑订单中包含的商品品项信息和订单中包含的商品所在货架信息。

2 订单分批问题的整数规划模型

为了建立订单分批问题的数学模型，定义如下符号。

索引：

i,j：订单索引，i,j=1,2,…,N；

k：批次索引，k=1,2,…,K；

s：货架索引，s=1,2,…,S；

t：商品索引，t=1,2,…,M。

参数：

q：每个批次允许的最大订单数量；

c1：从货架上拣取一种商品的成本；

c2：搬运一次货架的成本。

决策变量：

基于以上符号，订单分批问题可以表示成如下0-1规划模型:

(1)

(8)

目标函数(1)表示极小化订单拣选的总成本，其中第一项表示从货架上拣取商品的成本，第二项表示货架搬运的成本；约束条件(2)表示每个订单恰好被分配到一个批次中；约束条件(3)表示分配到每个批次的订单数量不超过规定的最大数量；约束条件(4)表示如果批次k中有任意一个订单包含商品t，则该批次就包含商品t；约束条件(5)表示如果批次k包含商品t，则拣选该批次时需要搬运包含商品t的货架；约束条件(6)～(8)表示决策变量取值约束。

定理1智能仓库系统订单分批问题属于NP-hard问题。

由于订单分批问题属于NP-hard问题，对于小规模问题，可以直接利用商业求解器如Lingo、Cplex等求解整数规划模型得到最优解，对于大规模问题，需要设计快速有效的近似求解算法。

3 订单加权相似度

从订单分批问题数学模型的目标函数和约束条件可以看出，影响订单拣选成本的主要因素是各个批次中包含的商品品项数量和满足各个批次拣选需求的货架数量。因此，合并包含相同商品品项或需要相同货架的订单，就可以有效降低订单拣选的总成本。基于以上思想，本节先分别按照订单中包含的商品品项是否相同、订单中包含的商品所在的货架是否相同定义两种描述订单相似度的指标：基于商品品项的订单相似度和基于货架的订单相似度，进一步定义加权相似度作为订单分批的依据。

3.1 基于商品品项的订单相似度

基于商品品项的订单相似度是根据两个订单中包含的相同商品品项数量与两个订单中的总商品品项数量之比定义的。

假设订单i和订单j中包含的商品品项集合分别为Ii,Ij，则基于商品品项的订单相似度rij可以定义为:

(9)

3.2 基于货架的订单相似度

基于货架的订单相似度定义为两个订单中的商品对应的相同货架数量与两个订单中商品对应的总货架数量之比。

假设订单i和订单j中商品所在的货架集合分别为Si和Sj，则基于货架的订单相似度lij定义为:

(10)

表1 仓库中3个货架的各个货位存放的商品信息

3.3 加权相似度

基于商品品项的订单相似度反映了订单中包含的相同商品的比例，将商品品项相似度大的订单合并拣选，可以减少从货架上拣取商品的次数；基于货架的订单相似度反映了订单中商品所在的相同货架所占的比例，将货架相似度较大的订单合并拣选，可以减少货架搬运的次数。由于从货架上拣取商品的次数和货架搬运的次数均是影响拣选效率和拣选成本的主要因素，因此，本文综合考虑两方面因素，分别赋予两种相似度权系数λ和1-λ(其中 0≤λ≤1)，定义订单i和订单j之间的加权相似度如下:

(11)

对于某个批次k,若其中包含p个订单p≥2，不妨设批次k对应的订单集合为:Batch(k)={Ok1,Ok2,…,Okp},则批次Batch(k)中包含的订单之间的平均加权相似度Z(Batch(k))为

(12)

加权相似度综合考虑了商品拣选的成本(次数)和货架搬运的成本(次数)。根据加权相似度进行分批，使同一批次内订单的平均加权相似度极大化等价于使商品拣选的次数和货架搬运次数的加权和极小化，因此根据加权相似度进行分批可以使订单拣选的总成本达到最小。

4 求解订单分批问题的贪婪算法

由于实际问题中涉及到的订单数量、商品品项及货架数量都很多，其对应的订单分批问题规模很大，无法在短时间内通过直接求解整数规划模型得到精确解，因此需要设计快速有效的近似求解算法来得到近似最优解。本节基于订单之间的加权相似度设计求解订单分批问题的贪婪算法。

算法的基本思想：首先根据待拣选订单中包含的商品品项及各种商品所在货架信息计算订单之间的加权相似度；先将每个订单单独作为一个批次；再分别计算任意两个批次合并以后，平均加权相似度的增加量，依次选择合并后满足批次内订单总数容量约束并且平均加权相似度增量达到最大的批次进行合并，直到平均加权相似度不再增加或者不存在合并后满足容量约束的订单批次为止。

基于加权相似度的订单分批问题贪婪算法基本步骤如下：

输入：待拣选订单中包含的商品品项信息及各个货架上存放的商品品项信息，加权系数λ。

Step1计算任意两个订单之间的加权相似度Tij，得到加权相似度矩阵

Step2将每个订单单独作为一个批次，记录各个批次中的订单数量，初始化每个批次内部订单之间的平均加权相似度为0(此时每个批次包含的订单数量均为1)

Step3对于任意两个批次u,v(u≠v)，按照公式(13)计算将批次u,v合并为一个批次Batch(u)∪Batch(v)以后，平均加权相似度之和的增加量Δuv以及两个批次合并以后总订单数量Nuv

Δuv=Z(Batch(u)∪Batch(v))-

Z(Batch(u))-Z(Batch(v))

(13)

Step4在满足容量约束Nuv≤q的批次中找出Δuv的最大值maxΔ及对应的批次u*,v*。

Step5若maxΔ>0，将批次Batch(u*),Batch(v*)合并为一个批次，转Step 3;若maxΔ≤0，或者不存在满足Nuv≤q的订单批次，则结束计算。

输出：各个批次对应的订单集合。

定理2对于N个订单，S个货架，M种商品，需要将订单划分为K个批次的问题，用贪婪算法求解的时间复杂度为O(N2M+N3)。

5 模拟计算与分析

5.1 算例描述

某电商企业采用基于AGV的智能仓库系统，该企业经销的100种商品(商品编码为1～100)存放在20个货架上(货架编码为1～20)，每一个货架上有5个货位，每个货架上的5个货位摆放的商品品项信息如表2所示。

该公司在某段时间内收到100个订单，每个订单中包含的商品品项信息如表3所示。假设工作人员从货架上拣取一件商品的成本为0.6元，AGV搬运一次货架的成本为0.4元，问如何对100个订单进行分批才能使总拣选成本最低？

表2 货架-商品关系表

表3 订单-商品关系表

5.2 订单分批结果与分析

本例中工作人员拣选一种商品的成本c1=0.6元，AGV搬运一个货架的成本为c2=0.4元，为了利用贪婪算法求解整数规划模型，首先要分析贪婪算法中参数λ的取值与整数规划模型中目标函数系数c1,c2取值的关系。不妨让参数λ分别取[0,1]之间的不同值，计算加权相似度。利用MATLAB编写的贪婪算法实现程序，按照不同参数下的加权相似度运行贪婪算法程序，得到各种参数对应的订单分批结果，并计算分批结果对应的各个批次中包含的不同商品品项n1(即拣选各个批次订单时，工作人员从货架上拣取商品的总次数)、各个批次中的商品对应的不同货架数量n2(即拣选各个批次订单时，AGV需要搬运货架的总次数)，以及拣选订单的总成本f(即整数规划模型的目标函数值)，其中拣选订单总成本计算公式为f=c1·n1+c2·n2，具体计算结果见表4。

表4 不同参数下的订单分批结果及对应的拣选成本指标

由表4可以看出，参数λ的变化直接影响订单分批结果。参数λ表示在加权相似度指标中基于商品品项的订单相似度所占的比重，当λ取最小值0时，基于商品品项的相似度所占比重为0，此时订单分批主要根据基于货架的相似度，分批结果对应的工作人员拣选商品的总次数最多，AGV搬运货架的总次数最少；当λ由小到大变化时，基于商品品项的相似度所占比重越来越大，基于货架的相似度所占比重越来越小，因此分批结果对应的工作人员拣选商品的总次数呈现递减趋势，AGV搬运货架的总次数呈现递增趋势；当λ取最大值1时，基于商品品项的相似度所占比重达到最大值1，基于货架的相似度所占比重为0，此时的分批结果对应的工作人员拣选商品的总次数达到最少，AGV搬运货架的总次数达到最多。因此，λ的取值很好的体现了订单拣选过程中工作人员的拣选成本和AGV搬运货架的成本所占的比重。由于订单分批问题整数规划模型的目标函数是极小化订单拣选总成本，为了分析最优的订单分批结果与参数λ取值的关系，本文直接取c1=0.6，c2=0.4计算各种分批结果对应的订单拣选总成本(见表4最后一列)，从总成本的变化情况可以看出，当λ=0.6时的分批结果对应的拣选总成本达到最小。此时的参数λ与c1、c2的取值恰好满足下面的关系式(14)。

(14)

本例中当λ*=0.6时，利用贪婪算法得到的订单分批结果为：将100个订单分为25个批次，各个批次中包含的订单序号见表5，其对应的订单拣选总成本(整数规划目标函数值)210.6达到最小。

表5 λ=0.6时的订单分批结果

5.3 贪婪算法的计算时间和计算效果分析

为了分析贪婪算法的运算时间和计算效果，本节模拟产生了一批不同参数下的小规模算例，分别利用Lingo软件编程求解整数规划模型得到精确最优解，然后利用贪婪算法求出近似最优解，并将精确最优解和近似最优解对比，分析各种参数发生变化时贪婪算法的计算时间和近似比的变化规律。

(1)参数λ发生变化时的求解效果分析

为了分析参数λ发生变化对贪婪算法求解效果的影响，模拟生成20个订单、20种商品、5个货架的小规模算例。首先取不同参数c1,c2(c1+c2=1)利用Lingo软件编程直接求解本文的整数规划模型得到精确最优解，然后令参数λ=c1利用贪婪算法求出近似最优解，并将各种参数下贪婪算法得到的近似最优解与精确最优解进行对比。分析两种算法的运算时间和得到的最优解对应的总拣选成本。具体计算结果见表6。

表6 参数λ发生变化时贪婪算法和Lingo精确求解的计算时间和计算效果对比

通过分析发现，对于包含20个订单的小规模算例(5个货架，20种商品)，在不同参数下，用Lingo直接求解整数规划模型的计算时间差别较大, 当c1取0或1的时候计算时间较短，c1取其它值时，计算时间均超过了20分钟，最长的时间超过了1小时。而贪婪算法在各种参数下的最长计算时间不足0.1秒。比较两种方法得到的目标函数值可以看出，对于包含20个订单的小规模算例，贪婪算法得到的近似最优解在最坏情况下对应的近似比不超过1.35。

(2)订单总数发生变化时的求解效果分析

为了分析订单总数变化对求解效果的影响，对于20种商品、5个货架的算例，固定c1=c2=λ=0.5，选取不同的订单数目生成算例，分别进行求解，结果见表7。

从表7可以看出，当订单数从5增加到25时，贪婪算法的求解时间变化不大，均未超过1秒钟，但Lingo软件的求解时间增长迅速，当订单总数为20和25时，Lingo软件求解整数规划模型需要的时间均达到1小时。随着订单数量的增加，贪婪算法的近似比会有小幅度的波动，最坏情况下的近似比不超过1.31。

表7 订单数发生变化时贪婪算法和Lingo精确求解的计算时间和计算效果对比

(3)物品总数发生变化时的求解效果分析

为了分析物品总数变化对求解效果的影响，固定20个订单、5个货架，固定c1=c2=λ=0.5，选取不同的物品总数并按照每个货架上存放的商品数量相同的原则生成算例，分别进行求解，结果见表8。

表8 物品数发生变化时贪婪算法求解和Lingo软件精确求解的计算时间和计算效果对比

从表8可以看出，随着物品总数的增加精确求解的计算时间增长迅速，当物品总数为20种时，精确求解的计算时间已经超过2小时，当物品总数为25种时，精确求解需要的时间超过5个小时，由于运算时间太长，我们记录了Lingo软件运行2小时得到的局部最优解与贪婪算法的求解结果进行对比，发现贪婪算法得到的近似最优解优于Lingo软件运行2小时得到的局部最优解。

(4)货架总数发生变化时的求解效果分析

为了分析货架总数变化对求解效果的影响，固定20个订单、20种商品，固定c1=c2=λ=0.5，选取不同的货架总数并按照每个货架上存放的商品数量尽量相等的原则生成算例，分别进行求解，结果见表9。

由表9可以看出，当货架总数为5时，用Lingo软件精确求解的运算时间已经超过2小时，对于货架总数超过5的算例，表9中记录了Lingo软件运行2小时得到的局部最优解，可以看出，贪婪算法在不足1秒的时间内得到的近似最优解优于Lingo软件运行2小时得到的局部最优解。

表9 货架数量发生变化时贪婪算法和Lingo精确求解的计算时间和计算效果对比

由表7～ 9中的计算结果可以看出， Lingo软件求解整数规划模型需要的运算时间随着物品总数、订单总数、货架总数的增加呈指数增长，而贪婪算法在求解小规模问题时运算时间均未超过1秒钟，且贪婪算法得到的近似比均未超过1.31。

对于前一节中的100个订单、100种商品的算例，我们也尝试用Lingo软件编程直接求解整数规划模型，结果发现Lingo程序运行24小时仍然没有得到最终结果，而用贪婪算法运行时间不足5秒就可以得到近似最优解，这说明贪婪算法适合求解大规模订单分批问题。由于实际中的订单分批问题都是大规模的在线问题，必须在短时间内得到近似最优结果，因此本文设计的贪婪算法是求解这类问题的有效方法。

6 结论

本文研究了基于AGV的智能仓库系统订单分批拣选问题，分析了智能仓库中影响订单拣选效率和拣选成本的两种主要因素分别是工作人员从货架上拣取商品的次数和AGV搬运货架次数，以订单拣选总成本极小化为目标建立了订单分批问题的整数规划模型，进一步根据订单中包含的商品信息和商品对应的货架信息构建了订单相似度指标，并设计了基于订单之间的加权相似度贪婪算法。最后利用具体算例进行了模拟计算，分析了加权系数λ的变化对订单分批结果的影响，以及加权系数λ的取值与工作人员拣取一件商品的成本c1和AGV搬运一次货架的成本c2之间的关系，得到了贪婪算法中加权系数λ的确定方法。进一步分析了物品总数、订单总数、货架总数等发生变化时，贪婪算法的计算时间和计算效果。结果显示，本文设计的贪婪算法具有较高的求解效率，由于本文的模型和算法同时考虑了商品拣取成本和货架搬运成本，通过适当选取加权系数，利用贪婪算法可以得到总拣选成本最低的订单分批结果。

本文结合我国电商企业智能物流系统的实际业务场景开展研究，目前，京东、菜鸟等大型电商平台已经实现了分拣作业中心无人化，物流系统根据订单发布任务，就近调配机器人；机器人搬运货架至拣选台，机器人可以自由旋转保证货架上的商品直接调配到拣选员面前；完成拣选任务后，系统可以根据实时订单信息变化动态调整货架的存放位置。本文给出的订单分批方法为设计智能物流系统后台控制系统提供了理论依据，本文的方法不仅适用于解决基于AGV的智能仓库系统订单分批问题，对于解决其他类型的无人仓系统(如基于旋转货架和传送带的无人仓系统)中的订单分批问题，同样具有参考价值。

本文在研究订单分批问题时做了一些必要的简化假设，如没有考虑商品缺货、大订单拆分、紧急订单插单等实际情况，实际中订单拣选过程中可能遇到某些畅销商品缺货的情况；由于每个货位上的商品数量有限，有些订购商品数量较多的订单可能需要拆分多个拣选单；而且不同订单的优先级不同，遇到优先级高的订单往往需要加急处理等情况。以上情况在本文研究的问题中均未考虑，后续研究中可以进一步考虑这些因素，扩展本文的模型和算法。另外，本文设计的贪婪算法还有很大的改进空间，后续研究中可以针对模型的特点，改进贪婪算法或设计近似度更高的智能算法。