孙军艳， 闫春妍， 陈智瑞， 牛亚儒
(陕西科技大学 机电工程学院， 陕西 西安 710021)
拣选作业作为配送中心的核心工序之一，其效率水平直接影响着配送中心的效率和水平。影响拣货作业效率的主要有拣选路径、储位分配、订单分批、拣选单排序等因素，国内外学者分别在这方面做了大量的研究。
在拣货路径优化方面，国内外学者大多采用智能算法如遗传算法、混合蚁群算法、禁忌搜索算法等对拣货路径和时间进行优化，以最大限度地减少拣选行程距离和时间，从而提高仓库运营效率。闫军等[1]对货物拣取路径顺序进行优化，以最短拣货路径为目标，建立了TSP模型优化拣货路径，将GASA算法和GA算法进行比较，结果表明GASA算法优于GA算法，拣货路径比之前节约了0.6% 。Zhou等[2]针对V型仓储布局，建立了返回型随机拣选路径模型，利用大数据技术进行仿真，验证了返回型拣货路径策略优于S型，提高了拣货效率。张水旺等[3]针对多区型仓库，建立了拣货路径优化模型，并采用人工鱼群算法求解，验证了算法的有效性。
科学的货物存储分配方法可以缩短步行距离，减少搜索时间，提高仓库拣选效率。在货物动态存储策略方面，Hadi等[4]开发了一种动态存储分配模型，动态确定货物的适当存储位置，从而提高了系统性能。Li等[5]基于贪婪遗传算法，应用数据挖掘技术计算了产品间的关联度，解决了动态货物存储位置分配问题，该算法计算效率较高，且显著改善了拣选订单的行程距离。Manzini等[6]建立了混合整数线性规划模型，基于时间将存储区域内的货物动态分配给不同的储位，该模型可优化复杂的仓储系统拣货决策。
在订单排序或者拣选单排序方面，叶楠等[7]通过分配拣货单的顺序，使各拣货单的复核台位置首尾相连，使用遗传算法动态优化拣货路径，该动态调整算法可为大规模、复杂仓库提供更高效的拣货路径规划。胡金昌等[8]通过建立0-1整数规划模型来求解同时分拣多客户订单的订单排序问题，提高了系统的拣选效率。夏德龙等[9]提出了一种适用于"货到人"的订单排序模型，并用改进k-means聚类算法求解了拣选台内相邻订单和拣选台之间订单的共用货架数量，以减少货架的搬运次数。
显然，拣选作业过程中，路径规划、存储分配、订单分批、拣货单排序之间相辅相成、相互影响，各环节的独立优化很难做到全局的优化。有学者进行了两两联合优化，比如Ardjmand等[10]针对基于拣选台的分拣系统，研究订单分批和路径优化问题，提出了一种基于列表的模拟退火算法(LBSA)和一种混合遗传算法(GA-LBSA)。研究发现，对于较小规模的问题，LBSA在解决方案的质量方面是一个更好的选择，而当考虑CPU时间时，根据问题的大小，GA-LBSA可能是更好的选择。Kübler 等[11]建立了动态存储位置分配和拣货路径联合优化模型，提出了一种迭代启发式算法，结果表明，这种方法可以显著节省行程距离。Cano等[12]对分批后的拣货单进行排序并优化拣货路径，建立了联合拣选模型，同时最小化总行程和客户订单延误，提高了订单分拣流程的效率。Cai等[13]对存储位置分配和路径进行协同优化，考虑了货物位置分配和路径规划之间的关系，提出了一种货架周转的位置分配策略，通过模拟研究确定了该方法的有效性。
两两联合优化明显提高了拣货作业效率，但仍存在一定的局限。在拣货流程中，订单分批、拣货单排序、货物动态协同、拣货路径优化等是一个系统工程，两两联合优化依然只是局部优化，很难达到系统全局的优化。
本文在订单分批形成拣货单的前提下，对拣货系统中最重要的环节——拣货单排序、货物动态协同、拣货路径优化三者进行联合优化，以求在系统层面实现全局最优。具体研究思路为：将拣货单排序的思想融入货物动态协同与拣货路径优化中，设计了一种拣货单路径优化-货物动态协同-拣货单排序的多阶段循环拣货策略，利用拣货单之间、最优路径之间的相似性，尽最大可能利用拣货车的剩余容量，减少后续拣货单的拣选距离，从整体上对拣货作业进行优化。
对于拣选作业，通常情况下，在一个拣货周期内，拣选系统会根据一定的规则和拣货车的容量，将具有相似性的订单形成拣选单，拣货员根据拣货单最优路径循环完成拣货作业，以达到减少拣选员的行走路径，提高拣货效率的目的，我们将该策略称为传统拣货策略。
为进一步提高拣货效率，一种动态拣货策略被提出[14]，其主要思想是利用相邻拣货单之间共同的拣选路径，在拣选上一张拣货单h的同时，提前将下一张拣货单h+1上的某个货品顺路拣出，以最大可能地减少下一张拣货单h+1的拣选路径，以此类推，最终实现所有拣货单总拣货时间的缩减，提高拣货效率。
本文将上述动态拣货策略与拣货单排序相结合，提出了对拣选作业进行“路径优化-货物动态协同-拣货单排序”的循环拣货策略(简称“排序协同策略”)，该策略的核心思想是：首先对所有拣货单进行路径优化，然后计算在拣选拣货单h的货物时能够协同拣选的拣货单h+1的货物组合，要求使拣货单h+1的最优路径减少最多，以此类推，得到两两拣货单之间能够使对方路径减少最多的路径节约矩阵；
最后以路径节约矩阵为基础进行拣货单排序，以“边排序边协同”的方式，达到缩短所有拣货单拣选时间的目的。
具体流程见图1，具体步骤如下。
图1 基于拣货单排序的货物动态协同与路径协同优化流程图Fig.1 Flow chart of dynamic cargo collaboration and path collaboration optimization based on picking orders sorting
Step1：初始条件设置
确定仓库布局，在拣货台处设置一个位置，作为被协同货物的临时存放处。明确货位信息、拣货车容量、货位之间、货位与拣货台之间的距离等信息。
Step2：拣货单最优路径模型的建立
建立以拣货时间最短为目标的数学模型，设计启发式算法，求解各拣货单的最优路径。
Step3：建立拣货单列表，求解各拣货单的最优路径集合
根据一个周期内拣货单h(h=1,2,…,M)的数量M，建立拣货单列表H={拣货单1,拣货单2, …,拣货单M}，基于Step1中的模型和算法，循环求解各拣货单h的最优路径。
Step4：建立动态协同货物组合最优模型
对于拣货单h和拣货单g，在满足拣货车容量的前提下，根据共同路径，在拣取拣货单h的同时，协同(捎取)拣货单g的某些货物，以使拣货单g的最优路径减少最多，得到拣货单h协同拣货单g的最优货物组合，以此类推，建立最优协同货物矩阵。
Step5：建立拣货单循环排序模型
根据最优协同货物矩阵，计算当各拣货单去掉被协同货物时，最优路径的减少值，建立最优路径节约矩阵。
Step5.1：当前没有排序优先的拣货单。从最优路径节约矩阵中找出节约值最大的一对拣货单，将协同拣货单作为排序优先的拣货单，被协同拣货单作为下一个拣货单。
Step5.2：当前有排序优先的拣货单。将当前排序优先的拣货单作为协同拣货单，在最优路径节约矩阵中，定位当前排序优先拣货单所在的行，找出最大值，将其对应的拣货单作为被协同拣货单，被协同拣货单作为下一个拣货单。
Step6：对排序优先的拣货单和被协同货物组合进行协同拣选
对排序优先的拣货单根据最优路径进行拣选，同时对共同路径上的下一张拣货单的最优货物组合进行协同拣货，将其捎取到拣选台被调整处。
Step7：更新被协同拣货单的拣货任务
更新拣货单列表H。将排序优先的拣货单从中删除，更新被协同拣货单的拣货任务，并将其更新为排序优先的拣货单。
如果排序优先的拣货单有拣选任务：更新被协同拣货单的最优路径。更新最优协同货物矩阵，删除排序优先的拣货单所在的行与列，根据更新后的拣货单列表，更新被协同拣货单所在的行。更新最优路径节约矩阵，删除排序优先的拣货单所在的行与列，根据更新后的最优协同货物矩阵，更新被协同拣货单所在的行。将被协同拣货单更新为排序优先的拣货单。进入step8.1。
如果排序优先的拣货单没有需要拣选的货物，则将其从拣货单列表H中删除，更新拣货单列表。更新最优协同货物矩阵，删除其所在的行与列。更新最优路径节约矩阵，删除其所在的行与列。进入step8.2。
Step8：判断拣货单列表中是否有拣货单
Step8.1:根据拣货单列表H，判断排序优先的拣货单是否是最后一个拣货单，如果否，进入step5.2；
如果是，根据最优拣货路径完成该拣货单的拣货任务，结束。
Step8.2：根据拣货单列表H，判断拣货单列表H中拣货单的数量。如果有2个及2个以上的拣货单，进入step5.1；
如果有1个拣货单，根据最优拣货路径完成该拣货单的拣货任务，结束；
如果没有拣货单，结束。
2.1 基本假设
1) 采用摘果式“人到货”的拣货方式进行拣选；
2) 拣货员可以沿纵向和横向的通道双向行走；
3) 每个货位存储一种货物，即货位和品项一一对应；
4) 货位足够大，拣货过程中不存在货位缺货现象；
5) 订单中货物、各货位的数量及其存储位置已知；
6) 订单分批形成拣货单，订单分批时不允许进行分割，保证一个订单一次拣完，每张拣货单的大小不超过拣货车的最大容量；
7) 拣货员一个循环完成一个拣货单的拣选，一个工作周期内完成多个拣货单的拣选任务；
8) 每张拣货单在拣选过程中可以协同下一个拣货单的多个货物；
9) 在拣货台设置一个临时存放处，用于暂存下一个拣货单的被调整货物。
2.2 参数设置
基本参数与符号定义如表1所示。
表1 基本参数和符号的定义Tab.1 Definition of basic parameters and symbols
变量定义如下：
2.3 模型的构建
由图1可以看出，本文提出的排序协同策略涉及三个数学模型：拣货单最优路径数学模型、货物动态协同选择的数学模型、拣货单循环排序模型。
三个模型中，以模型3为中心，在运行模型3时，首先需要调用模型1，计算各拣货单最优路径，建立拣货单列表；
接着调用模型2，计算最优的货物动态协同矩阵，得到最优的路径节约矩阵；
以此为基础，运行模型3得到排序优先的拣货单和被协同拣货单，拣选完成后更新拣货单列表。以此类推，模型3重复调用模型1和模型2，直到所有的拣货单被排序。
2.3.1模型1：拣货单最优路径数学模型
对于拣货单h，以拣货单最短路径为目标建立数学模型。
目标函数为：
(1)
约束条件：
1)
(2)
2) 拣货单h中每个货物的货位都要被访问1次：
(3)
(4)
3) 拣货单h的体积小于拣货车容量Q：
(5)
4) 拣货单h所包含的货位的数量不能大于货位的总数量：
(6)
决策变量：
(7)
2.3.2模型2：货物动态协同选择最优模型
拣货单h协同拣货单g时，以剩余拣货单g最优路径减少最多为目标，建立拣货单h的最优协同货物选择模型。
目标函数为：
(8)
(9)
(10)
约束条件为：
1)
(11)
2) 拣货单g中每个货物对应的货位都要被访问1次：
(12)
(13)
3) 拣货单g的体积小于拣货车容量Q：
(14)
4) 拣货单g所包含的货位的数量不能大于货位的总数量：
(15)
5)
(16)
6) 拣货单g中，被协同的货物与剩余的货物之和等于拣货单g上所有的货物：
(17)
7) 去除协同货物后，拣货单g剩余货物的货位都要被访问1次：
(18)
(19)
8) 被协同货物不能超过拣货车剩余容积：
(20)
9) 协同货物数量不能超过共同路径上的货物数量：
(21)
决策变量：
2.3.3模型3：拣货单循环排序模型
(22)
其次，基于最优路径节约矩阵ΔS，得到最优协同货物矩阵：
(23)
(24)
1) 模型3.1：当前没有排序优先的拣货单
以最优路径减少最多为目标，在最优路径节约矩阵中，寻找排序优先拣货单和被协同拣货单，目标函数为：
(25)
其对应的h即为排序优先拣货单，g为被协同拣货单。
2) 模型3.2：当前有排序优先的拣货单h
以最优路径减少最多为目标，在最优路径节约矩阵中，在第h行中寻找被协同拣货单g，目标函数为：
(26)
2.3.4所有拣货单的总作业时间
在拣货单排序的协同优化策略下，对于排序为k的拣货单，除了需要根据前一个拣货单k-1已经捎取的货物，更新排序为k的拣货单的拣货任务；
另一方面，需要采用循环判断找出可使下一个拣货单k+1拣货距离减少最多的货物组合，对其进行动态调整。若排序为k的拣货单为拣货单h，则排序为k的拣货单的拣选时间包括三部分：更新后的行走时间、更新后的作业时间、协同货物时间。优化后，1个周期内所有拣货单总的拣货时间TC为：
(27)
(28)
其中：
每个排序位置只能有一张拣货单。
3.1 算法设计
根据协同拣货策略和数学模型可知，该问题属于三阶段循环NP-hard决策问题。由于各阶段决策密不可分，环环相扣，循环更新，具有连贯性、协同性、多约束等特点，除了算法的可靠性以外，算法的效率至关重要。本文算法的设计思想是在确保解合理性的前提下，尽量提高各阶段算法的运算效率。
1) 模型1，采用混合遗传模拟退火(GASA)算法对拣货单路径进行优化。GASA算法将模拟退火算法(SA)较强的局部搜索能力与遗传算法融合，解决了群体的多样性和收敛速度的矛盾，可避免算法陷入局部最优，同时提升了算法的收敛速度。具体步骤如下。
Step1：编码设计。对拣货单的拣货位编号采用自然数编码。例如，对于有6个拣货位的拣货单，该拣货单的编码串(即染色体C1)为[2，15，22，13，53，7]，其中基因值为需拣取的拣货位编号，基因位对应拣货位的排序，此编码串表示该拣货单的拣货顺序为2-15-22-13-53-7。随机生成初始种群。
Step2：适应度函数。适应度函数f1为拣货单最优路径Sh的倒数。计算种群中所有个体的适应度值：
Step3：遗传操作。由于本文在设计交叉和变异算子时，新解只能在可行区域内产生，所以遗传交叉过程中只会产生可行解。
a) 选择算子，采用线性排序选择。通过排序给每个个体安排相应的选中概率。种群中的个体首先根据适应度值进行排序，然后给所有个体赋予一个序号，最好的个体序号为N，被选中的概率为Pmax，最差的个体序号为 1，被选中的概率为Pmin，设Pi为第i个个体被选中的概率，则
b) 顺序交叉算子，交叉概率为Pc。如图2所示，在两个父代中随机选择起始和结束位置，将父代1中选中的基因复制到子代1相同的位置，在父代2中将其缺少的基因按顺序填入，另一个子代以相同的方式得到。
图2 交叉操作示意图Fig.2 Cross operation diagram
c) 变异算子，变异概率为Pm。随机选择一个插入位和一个基因位，把染色体中的基因位移到插入位，将其之后的基因顺移。例如，插入位是第3位，基因位是第6位，则变异后的染色体如图3所示。
图3 变异操作示意图Fig.3 Mutation operation diagram
Step4：模拟退火操作。
a) 模拟退火初始化。初始化模拟退火参数，包括初始温度T0、降温速率θ和温度下迭代次数L，并以遗传操作产生的子代作为初始解。对当前解Cj作随机扰动，过程如图4所示，随机选择两个拣货位然后交换它们的位置，产生一个新解Cj′。计算新解的适应度值f(Cj′)。
图4 产生新解的过程示意图Fig.4 Diagram of the process for generating a new solution
b) 降温函数。在未满足终止退火条件，同时已达到温度下迭代次数时，进行降温操作，迭代n+1次时的温度为Tn+1=θ×Tn。
c) Metropolis准则。遵循Metropolis准则给出的以一定概率接受新状态，计算适应度函数值增量Δf，令Δf=f(Cj)-f(C′j)，若Δf≤0，则接受该新解为当前解；
否则，若exp(-Δf/T)大于[0,1]之间的随机数，则接收当前解为新解。
Step5：判断是否达到最大迭代次数，如果是，则输出最优路径结果，否则返回Step3。
2) 模型2，动态协同货物选择的最优。由于最优协同货物模型是一个多约束的嵌套组合问题，它是以协同货物组合的可行解为基础，循环调用模型1，根据拣货单最优路径的节约值的变化，不断的在协同货物组合的可行解中寻优。本文提出一种嵌套GASA算法，外层采用遗传算法对拣货单协同货物组合进行优化，内层采用GASA算法对拣货单路径进行优化。具体步骤如下。
Step1：调用GASA算法计算各拣货单的最优路径。
Step2：计算两两拣货单之间共同路径上的货位的货物，得到协同货物矩阵D。
Step3：计算D中的各元素Dh,g(h≠g,h∈H,g∈H)的最优协同货物组合。
Step4：编码设计。采用二进制编码，对协同货物矩阵D中的元素Dh,g，即拣货单g的可能被协同货物进行编码设计。染色体C2=[i1,i2,i3,…,im,…,in]，基因位对应拣货位编号，基因值im为0时，代表该货物被拣货单h协同，基因值im为1时，代表该货物留在拣货单g中拣选，随机生成初始种群。
Step6：产生新个体。选择操作采用轮盘赌法，交叉操作采用多点交叉算子，变异操作采用单点突变法，产生新种群。
Step7：判断是否达到最大迭代次数，若是，则生成拣货单g的最优路径节约值和最优协同货物组合；
若否，则判断新种群的新个体是否满足拣货车剩余容量，若满足，则返回Step5，若不满足，则返回Step6产生新个体。
3.2 实例分析
本文以双区型仓库为实例，如图5所示。设货架的长和宽均为1m，每个巷道的宽度为1m。纵向有20列、横向有40排货架，共800个货位。
图5 仓库布局图Fig.5 Warehouse layout
3.2.1初始参数设置
模型的参数设置：拣货人员的平均行走速度v=1 m/s，正常拣货时间tu=2 s，协同拣货时间t′u=2.5s，拣货车容量Q=80 m3。种群规模N=80，T0=50 000，交叉概率Pc=0.4，变异概率Pm=0.08。实验数据来源于某电商的订单数据，每张拣货单包含了若干张订单，每个订单中包含了不同货物的品类与数量。
3.2.2策略的合理性验证
首先以5张拣货单为例，利用上述嵌套GASA算法对其进行求解，拣货单拣选顺序为3-2-1-4-5，总拣货时间为1 627 s，总拣货路径为1 291 m。每张拣货单具体路径如图6所示。图6(a)为排序第1的拣货单3，黑点为拣货单3中的拣货位的货物，红点为被协同的拣货单2的拣货位的货物，可以看出，在进行拣货单3的拣选时，拣货单2的4个货物被协同拣选。图6(b)的黑点为拣货单2剩余的拣货位的货物，6个红点为被协同的拣货单4的拣货位的货物，绿点对应图6(a)的红点，为被拣货单3已经提前拣选的4个货物。以此类推，可知后续拣货单的货物协同情况。对比表2所示的传统拣货策略，本文提出的排序协同拣货策略的拣货时间节约了185 s，拣货距离缩短了191 m；
和动态拣货策略相比，协同货物增加了6个。验证了该策略的合理性。
表2 三种拣货策略对比分析Tab.2 Comparative analysis of three kinds of picking strategies
图6 货物动态协同优化路径图Fig.6 Dynamic cargo collaborative optimization path map
3.2.3算法有效性分析
为验证本文提出的嵌套GASA算法的有效性，将其与嵌套GA算法进行对比，如表3所示。
由表3可知，对于不同拣货策略，在对规模大小不同的拣货单进行求解时，嵌套GASA算法的求解结果均优于GA算法。传统策略下，GASA比GA算法的拣货时间平均少2.4%，动态策略下少5.1%，排序协同策略下少5.4%。可以看出， 不论哪种策略，GASA均优于GA算法，并且在排序协同策略下效果更好。
表3 不同算法下拣货时间的对比结果Tab.3 Comparison results of picking time by different pick methods
3.2.4不同规模拣货单的对比分析
分别以5张、13张、54张拣货单为例进行仿真实验，如表4所示。
由表4可以看出，与传统拣货策略相比，排序协同策略的拣货时间分别节约了12.8%、17.9%和24.7%，拣货距离节约了16.7%、23.8%和39.7%。
表4 不同规模拣货单的对比Tab.4 Comparison of picking lists of different sizes
与动态策略相比，排序协同策略的拣货时间分别节约了5.13%、12.05%和15.69%，拣货距离节约了6.69%、16.02%和24.20%。说明采用排序协同策略可使拣货效率明显提升，且随着拣货单数量的增加，拣货效率提升越发明显。
本文基于“边拣货边协同货物”的协同优化思想，设计了路径优化-货物动态协同-拣货单排序”的循环拣货策略，以总拣选时间最短为总目标，设计了一种多阶段循环求解算法，首先基于GASA算法对拣货单路径进行优化，然后使用嵌套GASA算法求解最优协同货物组合，最后采用遍历法对拣货单进行动态排序。
算例表明：与传统拣货策略或者动态拣货策略相比，本文提出的排序协同策略在拣货时间和拣货路径方面均具有一定的优越性，且随着拣货单数量的增加，优越性越发明显。本文的拣货策略、模型和数值仿真结果可为电商企业拣货提供决策参考。
猜你喜欢货位排序货物排序不等式中学生数理化·七年级数学人教版(2022年11期)2022-02-14货位指派和拣货路径协同优化及算法研究物流技术(2020年5期)2020-06-27恐怖排序科普童话·学霸日记(2020年1期)2020-05-08逛超市小猕猴学习画刊(2019年9期)2019-11-08节日排序小天使·一年级语数英综合(2019年2期)2019-01-10基于蚁群算法的智能生产物流体系构建研究∗计算机与数字工程(2018年11期)2018-11-28山小天使·三年级语数英综合(2017年6期)2017-06-07基于萤火虫算法的自动化仓储货位优化分配研究电测与仪表(2016年13期)2016-04-11基于遗传算法的自动化立体仓库货位优化模型研究管理现代化(2016年6期)2016-01-23路遥知马力娃娃画报(2009年11期)2009-12-07