基于鱼骨型仓库布局的多车拣选路径问题优化

胡小建，袁 丁

(合肥工业大学 1.管理学院；2.过程优化与智能决策教育部重点实验室，安徽 合肥 230009)

鱼骨型仓库布局是一种非传统的仓库布局模式，其主要布局特征是两个对角线通道呈现“V”字型。Gue等[1]指出合理规模下鱼骨型仓库布局的人工拣货距离比传统仓库布局降低20%左右。另外，订单拣选是提高仓库生产效率首要考虑的运营活动，其作业成本占仓库总运营成本的55%，订单拣选的任何不足都可能导致客户满意度下降以及仓库运营成本增高，进而影响整条供应链[2]。订单拣选时间由行走时间、寻找货物时间、拣取货物时间等组成，而拣货人员在进行拣货作业时所耗费的行走时间占总拣选时间的五成[3]。因此，研究如何优化鱼骨型仓库布局下的拣货路径，减少拣货人员的行走时间，对提高仓库拣货作业效率和降低仓储运营成本有着显著意义。

关于仓库布局的研究，国外学者给出了许多重要的研究成果。Roodbergen等[4]提出一种确定仓库拣选区域布局的方法，可以让订单的拣选距离最小化。Parikh等[5]指出影响订单拣选效率的决定性因素是仓库的布局。Pohl等[6]研究非传统仓库中周转率高的物品的最佳存储位置，并以鱼骨型仓库布局为例，提出最佳性能的布局设计。Cardona等[7]对比鱼骨型和传统型仓库设计的性能，并使用数值算法和精确算法求解鱼骨型设计的重要特征(对角交叉通道的斜率)。Cardona等[8]针对鱼骨型仓储布局最重要的特征(即对角交叉通道的斜率)，研究得出最佳斜率为1，且偏离最佳斜率也不会显著增加运营成本。Gue等[9]提出在鱼骨型仓库布局下，可行的范围内，存、取货点应置于仓库中间。后续学者在基于鱼骨型仓库布局下，转向研究仓库内部的路径优化问题。罗志文[10]基于改进的鱼骨型仓库布局，建立一单一车和一单多车拣货模型，并运用传统启发式算法进行求解。张新艳等[11]基于鱼骨型仓库布局运用一种混沌模拟退火粒子群算法对拣货路径优化问题进行求解。Zhou等[12]采用遗传算法、蚁群算法和布谷鸟算法对鱼骨型仓库布局的拣选路径进行优化。刘建胜等[13]考虑新型鱼骨型仓库布局的特点，引入有载重限制的多车调度模型，并提出一种混合粒子群优化算法进行求解。

由上述研究可以看出，关于鱼骨型仓库的研究逐渐由布局设计转向拣选路径的优化，目前多数关于拣选路径优化问题的研究都是基于传统启发式算法，且研究的模型鲜有考虑拣货小车载重、容积等约束条件。本文针对鱼骨型仓库布局下的多车拣选路径优化问题，构建待拣货点距离计算模型和以拣货距离最短为总目标、考虑载重和容积约束的拣选路径优化模型，并提出一种基于遗传算法[14]、粒子群算法[15]、蚁群算法[16]3种启发式算法的混合算法对模型进行求解，有效降低拣货小车的拣选距离，提高仓储的拣选效率，为不同规模待拣货点的拣选路径选择提供有效的解决思路与方案。

1 问题描述

本文所研究的鱼骨型仓库布局示意图如图1所示。假设仓库只有一个出入点，每次开始执行新一轮指定拣货任务都是从出入点出发，完成拣货任务后，都必须返回出入点，以等待下一轮分配的拣货任务，因而这里的出入点也是仓库的存取货品点，简称P&D(picking and deposit)点。仓库内的拣货作业是由拣货人员按照指定的某一拣货任务分一轮多次完成，由P&D点出发，通过操作拣货小车，按照拟定的拣货顺序去指定待拣货点上进行拣货作业，

图1 鱼骨型仓库布局Figure 1 Fishbone warehouse layout

若所拣选货物的重量或体积达到拣货小车的限载量，则立即返回P&D点，即为完成一次分拣货作业；若拣选完所有指定待拣货点，并返回出入点，即为完成一轮拣货作业。每次分拣货作业的拣选距离取决于拣货小车遍历待拣货点的顺序，以及任意两个待拣货点之间的路径选择，最终拣货小车完成一轮拣货作业所行走的路径距离之和，即为本轮拣货作业的总拣选距离。优化目标就是让一轮拣货作业的总拣选距离最短。

1.1 问题参数及假设条件

本文研究的鱼骨型仓库分为4个库区，即A、B、C、D区，每个库区均设有6条拣货巷道，巷道旁设有一排或列货架，货架内的格子表示独立的待拣选货位。其中，wc为仓库左右两侧边界及上、下侧距离货架的长度；ga为货位的长度；gb为货位的宽度； θ为斜拣货通道与仓库下侧水平线的夹角角度。

鱼骨型仓库布局的拣选条件假设如下。

1）鱼骨型仓库采用的布局是A、B区和C、D区两个部分关于中心对称，A、B区以及C、D区又各自关于中心对称。

2）鱼骨型仓库布局下的各排或列货架、拣货巷道、斜拣货通道的排列方式见图1所示。其中，每个库区的拣货巷道数相等，均设定为6，另外仓库设有两条斜拣货通道。

3） 鱼骨型仓库布局下的斜拣货通道与仓库下侧水平线的夹角角度θ=45°；每个货位(货格)长度和宽度、仓库左右两侧边界及上侧距离货架的长度、仓库下侧边界距离货架的长度都相等，即ga=gb=wc=1，1表示单位长度。

4）当拣货作业开始时，拣货人员按照拣货清单由P&D点出发，完成指定拣货任务后，返回P&D点。

5）待拣选货物存放于货架之上，货架由独立的货格组成，拣货人员在实施拣货作业时，忽略竖直方向的位移，即不考虑货架的高度。

6）在实施指定的拣货作业前，仓库内现存的货物能够满足订单的需求，即拣货人员进行拣货作业的过程中不会发生缺货现象。

7）拣货人员拣货距离的计算，不考虑竖直方向发生的位移，忽略搬运过程中以及往返P&D点所发生的垂直方向的位移。

8）拣货人员拣货距离的计算，忽略对巷道两侧货架进行拣货时所发生的的横向位移。

9）拣货小车的载重和容积能力有限，每辆拣货小车的最大载重量设定为20，最大容积设定为2。

1.2 鱼骨型仓库布局的拣选路径优化模型

基于上述鱼骨型仓库布局的参数设定以及拣选条件的假设，本文所建立的拣选路径优化模型如下。

目标函数：

具体符号说明见表1所示。

表1 符号说明Table 1 Symbolic Description

式(1)是优化目标函数，表示空闲拣货小车由P&D点出发，拣选完一批订单集合中所有待拣货点，再返回P&D点的拣货行走总距离最小。约束条件(2)表示载重约束，即每辆拣货小车拣选待拣货点时，总的载重量不能大于拣货小车所能承受的最大拣货重量。约束条件(3)表示容积约束，即每辆拣货小车拣选待拣货点时，总的拣货体积量不超过拣货小车所能承受的最大体积量。约束条件(4)、(5)表示访问唯一性约束，即每个待拣货点只能被拣货小车拣选一次。约束条件(6)表示拣货小车对待拣货点进行拣选时，不存在小回路。约束条件(7)表示决策变量，即第m辆 拣货小车拣选完待拣货点i后，继续拣选待拣货点j，则取值1，否则取值为0。

1.3 鱼骨型仓库布局的待拣货点距离计算模型

鱼骨型仓库布局的多车拣选路径优化问题涉及到待拣选货物品种多、待拣货点拣选顺序复杂等问题，难以通过传统算法获得精确解，属于NP-hard问题。因此，本文通过运用启发式算法求解该问题。考虑到鱼骨型仓库布局的货格排列具有一定规律性，且为了便于计算待拣货点之间的距离，采用合理的编码方式对每一个货格进行定位，具体的编码规则是[分区位置编码—巷道位置编码—货架位置编码—货格位置编码—货物重量编码—货物体积编码]。在分区位置编码中，按照给出的鱼骨型仓库布局平面图由左至右依次为A、B、C、D区，编码为1、2、3、4；巷道位置编码，A区和D区按照从下到上依次进行编码，B区和C区以鱼骨型仓库平面布局图的垂直中心线为基准，分别按照从右到左、从左到右依次进行编码，第1条巷道编号为1，第2条巷道编号为2，以此类推；货架位置编码，A区和D区按照待拣货点位于所在巷道的上侧和下侧进行编码，B区和C区按照待拣货点位于所在巷道的左侧和右侧进行编码，下侧或左侧编号为1，上侧或右侧编号为2；货格位置编码，各分区均按照由边界向P&D点进行编码，即A区按照从左至右进行编码，D区按照从右至左进行编号，B区和C区均按照从上到下进行编号，第1个货格编号为1，第2个货格编号为2，以此类推。

在上述具体的货格编码规则下，现对库区中涉及到待拣货点之间距离计算的相关参数进行设定，具体如下。

Li为待拣货点i所在巷道总长度(由巷道所在的边界到最近斜通道的距离)；

li为待拣货点i到所在巷道边界的距离；s为相邻直巷道在斜通道之间的距离；t为相邻直巷道之间的距离；

xi为待拣货点i所在的巷道编号；

Zi为待拣货点i所在的分区编码，从左至右，依次编码为1、2、3、4。

根据鱼骨型仓库布局下具有高度对称性、规则性等特点，A区和B区、B区和C区、C区和D区、A区和D区高度对称，只需考虑某一区到另一区的情况，具有互逆性；A、B区与C、D区距离计算方式相同，A、C区与B、D区距离计算方式相同，即只需各考虑一种情况。综合上述分析，考虑将4个库区中任意两个待拣货点以及任意一个待拣货点到P&D点之间的距离计算分为以下7种情况进行讨论。

7) 4个库区中任意一个待拣货点到P&D点的距离计算公式为

2 模型求解

鱼骨型仓库布局的拣选路径优化问题属于NPhard问题，因此本文设计一种GA-PSO-ACO混合启发式算法对该问题进行求解。该混合算法的设计吸纳了传统遗传算法、粒子群算法以及蚁群算法的优点，主要设计思路如下。

遗传算法是模拟种群基因的进化过程，通过染色体的选择、交叉以及变异，获得适应度最优的染色体；粒子群算法模拟粒子的运动过程，通过计算当前位置的适应度值，利用个体当前解、个体最优解和历史全局最优解3个解的信息，来引导粒子下一轮迭代的方向；蚁群算法则是模拟蚂蚁在移动过程中释放信息素，以此来传递信息并引导自身的移动方向。GA-PSO-ACO 混合算法的设计思路是让蚂蚁携带“粒子”的特性，初始化拣货路径后，通过记录个体极值及其对应的拣货路径，全局极值及其对应的拣货路径；再融入蚁群算法的机理，让蚂蚁根据上一轮行走路径留下的信息素进行更新，得到新的行走路径；最后引入传统遗传算法中的交叉、变异操作，对于鱼骨型仓库布局的拣货路径优化问题，蚂蚁当前的解是拣货路径，即一条染色体，让当前解与个体最优解和全局最优解分别作交叉操作，再作变异操作，操作过程中解的适应度变差，则拒绝，变优，则接收，获得蚂蚁行走的新路径，即新的拣货路径。

GA-PSO-ACO混合启发式算法的流程如图2所示。

图2 GA-PSO-ACO算法流程Figure 2 GA-PSO-ACO algorithm flow

GA-PSO-ACO混合启发式算法的步骤如下。

步骤1 算法参数初始化；根据上述编码规则计算出待拣货点间的距离矩阵，P&D点到各个待拣货点间的距离；随机生成一批订单集合中需要访问的待拣货点的重量和体积。

步骤2 初始化拣货路径100条，并计算出每条拣货路径的适应度值(完成一批订单集合的总拣选距离)，选出其中总拣货距离较短的30条拣货路径，并记录这些拣货路径的信息素。

步骤3 根据计算出的适应度值lop0，将当前适应度值设置为个体极值pibest，当前拣货路径为个体极值拣货路径plbest，根据各个蚂蚁的个体极值pibest，找出全局极值gibest和全局极值拣货路径glbest。

步骤6 根据各蚂蚁的行走路径长度Lk,k=1,2,3,···,m，记录当前的最优适应度值及其对应的行走路径。

步骤7 根据当前各只蚂蚁的行走路径，按照蚁群信息素迭代方程τij(t+n)=ρτi j(t)+Δτij更新轨迹信息素浓度值。

步骤8 对各边弧(i,j)，不断进行迭代，即0 →Δτi j, nc →nc+1。

步骤9 若 nc 小于初始化设定的迭代次数，且未出现退化现象 (即搜索到的都是同一解)，则转至步骤2。

步骤10 输出算法最优解，并通过对最优解进行解码，得到各个拣货小车的拣货顺序。

3 仿真实验与分析

本文仿真实验的研究对象为鱼骨型仓库，具体布局方式见图1所示，假设条件以及具体参数设定在问题1.1中已给出，详细的拣货流程在问题描述中予以阐述。仿真实验运用3种启发式算法对鱼骨型仓库布局的拣货路径优化问题进行求解，分别是GA算法、GAPSO算法以及GA-PSO-ACO混合算法。GA算法通过模拟种群的进化过程，搜索空间大，可以有效避免陷入局部最优解，全局搜索能力较强，但收敛速度较慢；GAPSO 算法是基于遗传算法，通过引入粒子群算法的思想，在染色体交叉过程中，让染色体与个体最优解以及全局最优解进行交叉，若解的质量提高，则接受，反之拒绝，有效提高了新群体的适应度，使得算法收敛速度加快；GA-PSO-ACO混合算法则是利用蚁群算法更强的搜索能力，获得复杂问题更为精确的解，同时引入遗传和粒子群算法的思想，提升算法的综合性能。

仿真实验通过运用GA算法、GAPSO算法以及GA-PSO-ACO混合算法对不同规模的待拣选货位进行寻优计算，通过对比各个算法在迭代到一定代数时的适应度值、达到最低适应度值的迭代次数以及算法的稳定性及收敛速度，分析3种算法在计算不同规模下的待拣选货位的性能。实验运行环境为Inter(R)Core(TM)i5-4 590 CPU @3.30 GHz，操作系统为Windows7，仿真软件为MatlabR2017b。算法具体参数设置见表2所示。

表2 GA、GAPSO以及GA-PSO-ACO算法参数设置Table 2 Parameter settings of GA、GAPSO and GA-PSO-ACO algorithm

仿真实验的待拣货点按照前文编码规则随机选取，实验所用到的30个待拣货点具体编码见表3所示。

表3 30个待拣货点编码样本Table 3 Code samples of 30 points to be picked

GA算法、GAPSO算法以及GA-PSO-ACO混合算法对鱼骨型仓库布局下的拣货路径优化模型的求解结果见表4所示。由表4中统计的数据可以看出，混合算法在4种待拣货点规模下的适应度值(拣货路径的总距离)以及收敛速度都明显优于 GA、GAPSO算法，由此可以看出混合算法集成了遗传算法的强全局搜索能力、蚁群算法的强局部搜索能力以及粒子群算法的高收敛速度，可以更快、更精确地获得问题的解。当然，由于混合算法整体设计流程基于蚁群算法，算法计算量大，在迭代相同的代数时，混合算法较另外两种算法所需的运行时间稍长，但其收敛速度快，在待拣货物规模为15、20、25以及30下，平均迭代次数分别在20.4次、18.5次、35.5次以及68.2次时，适应度值已逼近最优解，迭代次数远远小于其余两种算法。

表4 GA、GAPSO以及GA-PSO-ACO算法性能比较Table 4 Performance comparison of GA、GAPSO and GA-PSO-ACO algorithm

GA、GAPSO以及GA-PSO-ACO算法的收敛曲线如图3所示。由图3中所示结果可以看出，在4种不同待拣货点规模下，混合算法的适应度值、迭代次数以及收敛速度都比另外两种算法要优。

图3 GA、GAPSO以及GA-PSO-ACO算法收敛图Figure 3 Convergence curve of GA, GAPSO and GA-PSO-ACO algorithm

GA-PSO-ACO混合算法对鱼骨型仓库布局的拣货路径模型在4种不同待拣货点规模下的各拣货小车的拣选顺序如下。

以15个待拣货点为例，经GA-PSO-ACO混合算法优化过后，仓库内部拣货人员的最优拣货路径示意图如图4所示。

图4 15个待拣货点的拣货路径示意图Figure 4 Schematic diagram of the picking route of 15 picking points

4 总结

本文的研究基于鱼骨型仓库布局的拣货路径问题，对建立的拣选路径优化模型和待拣货点距离计算模型，采用GA算法、GAPSO算法以及GA-PSOACO混合算法进行求解。其中混合算法基于蚁群算法的整体设计流程，具备较强的局部寻优能力，再融入粒子群算法局部最优信息和整体最优信息的设计思路，使得混合算法更快逼近最优解，增强混合算法的收敛性。另外，通过引入传统遗传算法的交叉、变异过程，使得每代个体具有多样性，让混合算法在寻优过程中具备较强的全局搜索能力，避免蚁群算法难以跳出局部最优解的问题。在仿真实验设计中，通过设置不同规模的待拣货点，运用3种算法分别对拣货路径进行寻优，分析并比较各算法的性能优势。仿真实验结果证实GA-PSO-ACO混合算法在适应度值、迭代次数、收敛速度上都优于GA算法和GAPSO算法。

本文针对鱼骨型仓库布局的多车拣选路径优化问题，提出的混合启发式算法在一定程度上可以减少仓库内部的拣货距离，提高拣货效率，为鱼骨型仓库布局下待拣选点规模不同的拣货人员拣货路径的选择提供参考。在后续的研究中可考虑融入订单分批的优化问题。