1 问题描述

本文所研究的鱼骨型仓库布局示意图如图1所示，该仓库应用人到货的拣货系统。拣选作业由拣货员操作叉车进行作业，以存取货品点为起点。拣货员从不同的存储位置上收集订单上的货品。假设仓库只有一个出入点，每次完成存取作业后都必须回到出入点等待下一次的仓储作业，因此仓库的出入点就是仓库的存取点，简称P&D（Picking and Deposit）点。该仓库采用的是左右对称的仓库布局，其中有三条拣货主通道，三条主通道都通过P&D点。

图1 鱼骨型仓库布局

Fig.1 Fishbone warehouse layout

1.1　问题参数与假设条件

参数设定如下：

W：仓库的宽度；

Wr：两侧拣货通道和后部拣货通道的宽度；

Wd：两条斜拣货通道的宽度；

Wh：存储货格的长度；

L： 仓库长度的一半；

L1：拣货通道的宽度；

L2：双排货架的宽度；

α： 斜拣货通道的角度；

仓库的拣选环境假设如下：

1） 鱼骨型布局仓库左右两部分关于中心对称；

2） 鱼骨型布局仓拣选通道的排列方式如图1所示，堆垛区1、2、3、4拣选通道数量相等，为m；

3） 鱼骨型布局仓库斜拣货通道角度α=45°；每个货格的长度、宽度、拣货通道宽度三者相等，即Wh=12L2=L1，Wr=L1；

4） 拣选车辆在拣选作业开始时从P&D点出发，结束后回到P&D点；

5） 拣选作业开始之前，满足所有订单的要求，且拣选作业过程中不会发生缺货现象；

6） 待拣选货物存储于货架之上，货架由货格组成，每个货架的长度和宽度相等，不考虑货架高度；

7） 拣选距离计算只考虑P&D与待拣货物所在位置的距离，垂直方向上的拣货距离忽略不计；

8） 拣选距离计算不考虑拣选通道两侧货架的待拣货物所发生的左右移动距离；

9） 一次拣选订单总量小于拣货车辆最大承载量；

1.2　鱼骨型仓库布局拣货路径模型

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

目标函数：

即

约束条件：

式中：D为拣选车辆完成一次拣选作业总行走距离； i，j为任意两货位；n为最后一个拣选货位；dij(1≤i,j≤n,i≠j)为货位i到货位j之间的最短距离；d01为P&D点到货位i的拣货距离，即从P&D点开始拣货作业；dn0表示货位i到P&D点的拣货距离，即完成拣货作业回到P&D点。

目标函数式(1)表示在一次拣选作业中最短的总行走距离；式(2)和式(3)表示所有待拣选点所在货位都被拣选且仅一次；式(4)表示除去未包含某个拣货点的路径解，即不存在小回路；式(5)表示货位i与货位j之间是否存在拣货路径；式(6)表示拣选车辆在进行拣选作业时从P&D点出发，拣选作业结束后需回到P&D点。

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

鱼骨型布局仓库中的拣选路径优化问题属于NP难问题，把目标函数设定为拣选行走路径的总距离最短。为计算上述拣货路径优化模型中的d01、dn0和dij，首先，假设任一待拣选点的序号为(s,x,y,z)，其中，s=1,2,3,4表示待拣选物品所在堆垛区的编号；x=1,2,...,X，表示待拣选物品所在的拣货通道的编号，x≤7(本文中的鱼骨布局仓库的通道数，如图3-2所示，共有7条)；y=0,1，表示待拣选物品所在通道内的两侧，如果物品在通道的下侧或者右侧，则y=0，相反，如果物品在拣选通道的上侧或者左侧，则y=1；z=1,2,3,...,Z，表示待拣选物品在第几个货格里，编号方法为离两侧和后部过道近的货格的编号为1，并依次编号为1,2,3,...,Z。假如待拣选点的序号为(1,2,0,3) 所表示的是位于堆垛区1，拣货通道2，下侧的货架，从左侧过道向右数第3个货格。P&D点的位置设为(0,0,0,0)，编码为0。现假设有任意两个拣选点i,j，序号分别为(si,xi,yi,zi)和(sj,xj,yj,zj)，dij表示两点之间的距离。

首先，对d01求解，数字1是指待拣选的第一个货位，可以是待拣选点中的任意一点，此处假设为1点，序号为s1,x1,y1,z1，d01可表示为

设dn0表示从最后一个拣选点回到P&D所行走的距离，此处假设点n为最后一个拣选点，点n的序号为sn,xn,yn,zn，此时，dn0 可表示为

dij表示任意两个拣选点i,j之间的距离，可表示为

1)　当i,j两拣选点位于同一拣选通道时，即xi=xj时

2)　当i,j两拣选点位于不同一拣选通道时

3)当i,j两拣选点位于不同堆垛区内时，分以下情况讨论：

(1)当i,j两拣选点分布在堆垛区1和堆垛区4两个不同区域内时

(2)当i,j两拣选点分布在堆垛区1和堆垛区2或堆垛区3和堆垛区4两个不同区域内时

(3)当i,j两拣选点分布在堆垛区1和堆垛区3或堆垛区2和堆垛区4两个不同区域内时

(4)当i,j两拣选点分布在堆垛区2和堆垛区3两个不同区域内时

式(7)到式(14)包含了图1所示鱼骨型仓库布局下任意两拣选点之间距离的求解方法。

2 模型求解

拣货路径规划问题是一个NP 难问题，因此采用粒子群算法(PSO, Particle Swarm Optimization)对该问题模型进行求解。在粒子群算法中，许多粒子被放在某个问题的搜索空间中，并以一定的速度在搜索空间探索^[10]。在一个D维的目标搜索空间中，由N个粒子组成的粒子群落，其中第k个粒子的位置表示为x⃗k=(x⃗k1,x⃗k2,...,x⃗kD),k=1,2,...,N，速度表示为v⃗k=(v⃗k1,v⃗k2,...,v⃗kD),k=1,2,...,N；个体极值是第k个粒子迄今为止搜索到的最优位置，可表示为p⃗k=(p⃗k1,p⃗k2,...,p⃗kD),k=1,2,...,N，适应度记为pbest；全局极值是整个粒子群落迄今为止搜索到的最优位置，可表示为p⃗g=(p⃗g1,p⃗g2,...,p⃗gD),k=1,2,...,N，适应度记为gbest。在每次迭代中，粒子的速度和位置基于公式(15)和公式(16)更新，直到满足最大迭代次数后停止。

其中w表示惯性权重，使其有拓展搜索空间的能力；φ1和φ2表示学习因子，即每个粒子推向p⃗k和p⃗g位置的统计加速项的权重大小；rand1和rand2是在[0,1]范围内均匀分布的随机数。

为解决粒子群算法计算过程中振荡与过早收敛的问题，提出混沌模拟退火粒子群优化算法(SAPSO, Simulated Annealing Particle Swarm Optimization)，即在粒子群算法中引入模拟退火算法的概率突跳特性，使粒子群算法不但可以接受好的解，也能以一定概率接受不好的解，以提高算法的全局搜索性能^[8]。为提高算法的收敛速度，利用非线性自适应惯性权重w(t)代替公式(15)中的惯性权重值，其表达式为公式(17)，使算法在前期跳出当前极值，在后期较快收敛。为优化粒子种群运动，提高搜索空间的多样性，本文采用混沌理论对rand1、rand2进行动态调整。采用Logisitic模型产生混沌序列^[8]如公式(18)所示。

其中w(t)表示第t次迭代时的惯性权重取值，tmax表示最大迭代次数，t表示当前迭代次数，姜建国^[11]等提出wmax=0.95，wmin=0.4时算法性能最优，本文采用此取值。

其中，randqt表示randq在第t次迭代时的值，由混沌理论可知，当randq1不等于0.25、0.5、0.75时，序列能呈现完全混沌的特性，变量randq可以不重复地遍历整个搜索空间，以提高变量randq的随机性。

混沌模拟退火粒子群算法的流程图如图2所示：

图2 混沌模拟退火粒子群算法流程图

Fig.2 Flow chart of chaotic SAPSO

混沌模拟退火粒子群算法的步骤如下：

STEP 1 初始化参数设定。最大迭代次数tmax、粒子的速度v⃗k、位置x⃗k、学习因子φ1φ2、惯性权重w、模拟退火因子φsa。

STEP 2 初始化拣货路径。随机生成一系列初始路径集合，用随机模拟方法判断初始路径群体是否满足满足约束条件(2)-(6)，以确保种群达到粒子群算法所需规模。

STEP 3 粒子群算子操作。按φ1=φ1(1-t/tmax)，φ2=φ2(1-t/tmax)，φsa=φsa×0.97更新学习因子和模拟退火因子，同时按式(15)和(16)更新各粒子的位置和速度。

STEP 4 交换序操作。确定个体到个体最优解和全局最优解的交换顺序，混沌产生rand1、rand2序并和φ1、φ2比较选择执行的交换序，进行交换。

STEP 5 计算粒子适应度。对新种群的位置，计算适应度函数，即一次拣选作业完成行走总距离，如公式(1)所示，并更新个体的最优位置和最优适应值。

STEP 6 模拟退火操作。

1) 生成模拟退火初始解S1；

2) 插入扰动因子，生成模拟退火的新解S2；

3) 计算新解S2的适应度函数；

4) 判断新解S2的适应度函数值是否小于初始解S1的适应度函数值。若不大于，则用新解S2代替模拟退火初始解S1，并转至步骤6)。若大于，则以φsa的概率大小接受新解，并转至步骤5)；

5) 产生伪随机数r，并判断φsa是否大于r。若大于，则用新解S2代替模拟退火初始解S1，并转至步骤6)。否则，则直接转至步骤6)；

6) 降低温度；

7) 判断当前温度是否达到最低温度。若已达到，则退出模拟退火操作，并转至STEP 7。若未达到，则返回步骤1)。

STEP 7 种群评估与优选。根据个体的最佳适应值，选出种群的最佳位置和最佳适应值，并保存下最佳适应值。

STEP 8 判断算法终止。若满足最大迭代次数或目标函数减少幅度趋于收敛的预设条件，则输出拣选作业路径总距离以及对应的具体路径方案，算法终止；否则，返回STEP 3。

3 仿真及分析

仿真对象为鱼骨型仓库布局，其各项参数取值参见1.1问题参数与假设条件。由于遗传算法的全局搜索能力强，所以选用遗传粒子群算法^[13] (GAPSO, Genetic Particle Swarm Optimization)与混沌SAPSO算法对比，以验证混沌SAPSO算法所得优化结果是否具有全局最优的特点。同时，PSO算法具有收敛速度快的优点，则选用PSO算法与混沌SAPSO算法对比迭代次数与收敛速度。

仿真实验在Inter® Core™ i5-7300HQ，CPU主频为2.50GHz、8.00GB内存、Windows 10操作系统下进行，并利用MATLAB2016仿真工具编程实现。算法参数设置如表1所示：

拣选点样本设置（以10个拣选点为例）如表2所示：

PSO、混沌SAPSO和GAPSO算法对鱼骨型仓具布局下的拣选路径优化模型的求解结果如表3所示。从表中可以看出，混沌SAPSO算法在四种问题规模下的适应度值和收敛速度都要优于PSO和GAPSO算法，可见混沌SAPSO算法避免了PSO算法易陷入局部最优的缺点，同时适应度值比GAPSO算法所求得的结果更优。另外，混沌SAPSO相对PSO平均运行时间在问题规模为10、20、30、40时分别提高了42.01%、10.13%、4.18%、9.29%，混沌SAPSO相对GAPSO平均运行时间分别提高了2.74%、39.50%、54.46%、53.58%。

PSO、混沌SAPSO和GAPSO算法的适应度曲线如图3所示，从图中可以看出在四种问题规模下混沌SAPSO算法的收敛速度都比PSO和GAPSO算法要快，同时振荡现象得到了明显地改善。

(a) 10个待拣选点

(b) 20个待拣选点

(c) 30个待拣选点

(d) 40个待拣选点

图3 PSO、混沌SAPSO及GAPSO算法适应度曲线比较

Fig.3 Fitness Curve comparison between PSO, Chaotic SAPSO and GAPSO in 10 experiments

混沌SAPSO算法求解所得路径解的拣选顺序如下：

10个拣选点0→10→9→8→7→6→4→3→1→2→5→020个拣选点0→1→11→10→6→7→5→4→3→2→8→9→13→14→16→17→15→18→19→10→12→0

30个拣选点0→15→16→5→12→11→9→10→8→6→7→4→3→13→14→23→24→25→22→21→27→26→28→29→30→2→1→20→19→17→18→040个拣选点0→22→39→40→23→21→24→25→26→36→34→28→27→29→30→31→32→33→35→38→37→2→1→18→3→4→7→6→5→16→14→13→11→9→10→8→12→15→17→19→20→0以10个拣选点为例，优化后拣货路径示意图如图4所示。

图4 10个拣选点的拣货路径示意图

Fig.4 Order picking route of 10 picked locations

4 结论

本文的研究基于鱼骨型仓库布局的拣货路径问题，对建立的拣货距离计算和拣货路径优化模型，采用混沌模拟退火粒子群算法进行求解，混沌模拟退火粒子群算法采用混沌理论对粒子群优化算法中的参数rand1和rand2进行动态调整，同时引入模拟退火算法对粒子群优化算法中的每个粒子位置局部寻优，并设置不同的问题规模，对算法的性能进行了分析。仿真结果表明，混沌模拟退火粒子群算法在适应度值、迭代次数、收敛速度、运行时间和振荡效果方面都优于粒子群优化算法和遗传粒子群算法。

本文的拣货距离计算和拣货路径优化模型可为鱼骨型仓库布局的研究提供决策参考，在后续研究中可进一步考虑鱼骨型仓库布局下的订单分批问题。

参考文献