基于AGA与MPSO的非传统布局仓储货位分配优化

作为现代制造业重要组成部分, 仓储是连接生产制造与销售服务的桥梁, 高效的仓储运营不仅能及时响应客户需求, 还能有效降低成本[1]。而仓储效率又受多方面因素影响[2], 其中非传统布局仓储是当前重点议题之一。

Gue等[3]打破传统布局的思维禁锢, 在一定条件下得出Flying-V型能比传统型平均减少11.2%的拣货路径, 而Fishbone型优化效果更明显, 拣货路径可减少20.7%。这表明传统布局可能并不是最优的, 从而也启发了业界对布局设计的重新思考和放松假设条件的研究。Pohl等[4]基于双命令模式下探讨了Fishbone型的最优布局设计, 后来又对不同需求偏态下的布局设计进行了分析[5]。ztürkoglu等[6]在Fishbone型基础上进一步放松假设, 设计了某些场景下更优的Chevron型布局。Martínez[7]则从最佳主通道角度对Fishbone型特点进行分析, 着重研究了主通道斜率设计的问题。另外, Clark等[8]和Cardona等[9]则考虑货架高度对作业时间的影响, 提出了对作业时间模型进行修改。国内方面, 周丽等[10]在2种拣选方式下对Fishbone型和传统型的拣货行程距离进行了仿真, 得出的结论与Gue等[3]的相似。而蒋美仙[11]和李乐等[12]则在Fishbone型中结合贯通式思想, 提出改进的Fishbone型设计, 并结合实例进行了验证。由此不难看出非传统布局是当前仓储领域的新热点, 不过, 以上文献均是探讨非传统布局中通道的优化设计, 都没有涉及到货位分配问题。

货位分配是仓储作业中极为重要的环节, 良好的货位分配既显著减少货物存取的行程时间又能保证货架结构的稳定性[13]。货位分配优化方法一直也是管理者密切关注的焦点也是学术界研究的热点, 现已有相对丰富的成果[14,15,16]。然而, 非传统布局与传统仓储之间差异明显, 其货位分配优化问题是一个更加复杂的大规模组合优化问题, 现有的优化算法和传统仓储的货位分配方法为此提供了借鉴基础, 但并不能直接适用在此处。因此, 研究设计高效的非传统布局仓储货位分配优化方法具有一定的学术意义和实际应用价值。

Fishbone型是一种典型的非传统布局方式 (如图1所示) , 整个仓储可均分为4个货区, 其中存取点 (pickup and deposit point, P&D点) 位于仓储前端底部中心, 左右两边有各有1条主通道 (cross aisle) , 若干条拣货通道 (pick aisle) 与主通相交, 由此整个仓储布局呈Fishbone型。

该仓储中货位的长和宽均为l, 高为h。k (k=1, 2, 3, 4) 为货区号, 从左下角区域开始按逆时针方向分别为1区、2区、3区、4区;x (x=1, 2, …, xmax) 为货位的排数;y (y=1, 2, …, ymax) 为货位的列数;z (z=1, 2, …, zmax) 为货位的层数。位于k区x排y列z层的货位记 (k, x, y, z) , 例如 (4, 2, 7, 3) 表示该货位位于4区2排7列3层。i (i=1, 2, …, imax) 为货品的编号, mi为货品的质量, ri为货品的存取频率, ji (j=1, 2, …, jmax) 为第i类货品的数量。v1为AGV (automatic guided vehicle) 的水平运行速度, v2为其竖直运行速度。另外, 货架的列数ymax随着x不断变化, 其表达式为

式 (1) 中, Y为最大列数, 即第一排货架的列数。

Lx为AGV小车从P&D点出发到目的货位过程在主通道的行驶距离, 其表达式为

货位分配优化的目的是根据货物以及货架的特性为待入库的货物分配合适的存储位置, 从而降低仓储作业成本, 提高作业效率, 使得仓储效益最大化。在进行货位分配时一般要遵循一些基本原则, 如先进先出原则、高近低远原则、上轻下重原则等[16]。因此, 本文将出入效率和货架稳定性作为优化目标, 建立多目标货位分配优化模型。

模型假设:

(1) 货位分配前待入库货物的数量、质量、存取频率等信息已知。

(2) 同一类的货物可以存放于不同货位, 但一个货位只能存放一个货物。

(3) v1与v2已知且不考虑AGV的启动与制动时间。

(4) 单次行程中AGV只能访问一个货位。

(5) 拣货通道宽度与单排货架的宽度相等。

目标函数:

约束条件:

式 (3) 表示以货物出入库效率最高建立的目标函数, 式 (4) 表示以货架稳定性最优建立的目标函数。式 (5) ～ (7) 为Fishbone布局中仓储货位分配的约束条件。

当前, 处理多目标优化问题的方法比较多, 普遍采用的是赋权法[14,15], 这种方法特征明显且简单易执行。但本问题中由于2个目标函数量纲不同, 值域范围差别大, 如果直接采用简单赋权法可能会造成某些目标被弱化, 很难得到整体最优效果[17]。为此, 本文采用一种“量纲归一化”方法来消除量纲差异, 弥补简单赋权法的缺陷, 具体来说就是先求得单目标情况下的最优值, 然后将各个单目标函数的量纲归一化。再由决策者根据实际情况对各个子目标函数进行赋权, 最后可将多目标问题转化为单目标问题。

量纲归一化得到的子目标函数F1、F2, 总目标函数F及适应度函数G如下:

其中, 表示以货物出入库效率最高时的单目标函数的最优值, 表示以货架稳定性最优时的单目标函数最优值, w1和w2分别表示决策者对2个优化目标赋予权重。

遗传算法 (genetic algorithm, GA) 由Holland教授提出后得到长足发展, 尤其在处理组合优化问题上更是被广泛运用。然而, 该算法也存在着诸如进化初期易“早熟”、进化末期难收敛等问题[18]。因此, 本文采用一种动态自适应策略即自适应遗传算法 (adaptive genetic algorithm, AGA) 对算法的选择、交叉、变异算子进行改进, 使得算法在初期具备较强的全局搜索能力, 而到后期又增强其局部搜索能力, 从而有效解决上述问题。

编码是算法设计的关键一步, 编码方式多种多样, 需要针对求解问题及数学模型的特征设计相应高效的编码方式。本文此处采用矩阵式编码, 即单个个体的基因由一个imax×a的“伪二进制”矩阵表示。其中, 第i行代表第i个货物被分配的货位, 而列长a则由仓储货区数k、货架的最大排数xmax、货架的最大列数Y以及货架的最大层数zmax共同决定。例如有5个货物需要存放, 且仓储参数k=4、xmax=9、Y=13、zmax=4, 则某个体基因编码方式如图2所示。

在个体编码矩阵中, 第1～2列代表货位的货区数, 第3～6列代表货位的排数, 第7～10列代表货位的列数, 第11～12列代表货位的层数。在上述矩阵中第1行代表的货位为 (4, 9, 13, 4) , 而第2行代表的货位为 (1, 1, 1, 1) 。

轮盘赌法是常用的选择算子, 但是这种方法会产生较大的抽样误差, 容易造成“早熟”的现象。为此, 本文在选择操作之前采用自适应策略对适应度值进行变换:

式中Gmax为当前种群最大适应度值, Gmin为当前种群最小适应值, t为当前遗传代数, T为终止遗传代数, 再按照概率进行选择操作。

在进化初期时, G1 (j) 被选择概率弱化, 有利于保持种群的多样性, 避免“早熟”;而在进化后期时, G1 (j) ≈G (j) , G1 (j) 被选择概率增强, 有利于加快收敛到最优解。

另外, 在交叉与变异算子中也采用自适应策略动态调整参数, 使交叉率和变异率随适应度值进行动态变化。如此, 能够使算法在初期保持全局搜索能力强而后期又可充分发挥局部搜索能力, 加速收敛到最优解。

式中, Pcmax和Pcmin表示交叉率取值的上限与下限, Pmmax和Pmmin表示变异率取值的上限与下限, Gavg为当前种群平均适应值, 为交叉的2个个体中较大的适应度, G (j) 为待变异个体的适应度。

输入:imax, mi, ri, v1, v2, l, h, w1, w2。

输出:最优货位分配方式。

步骤1输入货位分配优化模型参数:imax, mi, ri, v1, v2, l, h, w1, w2。

步骤2设置AGA参数:T, J, Pcmax, Pcmin, Pmmax, Pmmin。

步骤3算法开始t=1, 运用2.2.1中矩阵编码方式生成初始种群J。

步骤4判断进化次数是否超过终止进化代数 (t>T) , 若是则转步骤5, 否则继续。

步骤4.1计算个体的目标函数值F以及适应度G;

步骤4.2选择算子, 采用式 (12) 对适应度值进行G变换为G1;

步骤4.3交叉算子, 采用式 (13) 对交叉率进行自适应调整;

步骤4.4变异算子, 采用式 (14) 对变异率进行自适应调整;

步骤4.5进化次数t=t+1。

步骤5算法结束, 输出最优货位分配方案。

粒子群优化算法 (particle swarm optimization, PSO) 是一种基于鸟群迁徙行为的群体优化算法, 其迭代寻优是一种由粒子速度与位置共同决定的复杂非线性变化过程[19]。同时, 速度与位置的更新又与惯性权重 (ω) 和学习因子 (c) 密切相关, 而传统PSO中这2个参数恒定或线性递减的设定并不能反映粒子这一复杂过程。因此, 本文采用非线性变化动态更新惯性权重以及时变加速学习因子这2种策略对算法进行改进, 设计改进的粒子群优化算法 (modified particle swarm optimization, MPSO) 。

货位分配优化问题的解在空间呈离散分布, 此处借鉴离散思想对MPSO进行编码[20], 使粒子位置与货位分配方案进行一一映射。每个货位有4个维度, 则搜索空间维度为D (D=4×imax) , 种群为X= (X1, X2, …, Xn) , 其中N (n∈N) 为种群规模, 第i个粒子在第t代的位置与速度则表示为

并且在迭代选优过程中采用如下公式更新粒子状态:

其中, Ptid为粒子i的个体极值, Ptgd为种群的群体极值。r1、r2为介于[0, 1]之间的随机数;ω为惯性权重, 一般设为常数或线性递减函数;c1、c2为学习因子, 一般为非负常数。然而考虑到PSO实际寻优是非线性变化过程, 本文根据群体最优解的变化采用非线性函数来更新惯性权重ω (初始ω0=0.9) , 保证算法能够跳出局部最优解而在快接近最优解时又能加快收敛到全局最优解, 具体更新过程如下所示。

由PSO理论可知, c1反映的是粒子自身学习能力, 而c2为群体学习能力, 如果在迭代初期设置c1>c2, 粒子则能够趋向种群最优;而在迭代末期c1<c2, 则将有利于粒子收敛于全局最优解。因此, 本文对于c1、c2的改进如下所示:

其中, c1i、c2i、c1f、c2f为初始设置的常数, t为当前迭代次数, T为最大迭代次数。研究表明[21], 当c1从2.5变化到0.5、c2从0.5变化到2.5时, 最有利于搜索到最优解, 因此, 本文设置c1i=c2f=2.5, c2i=c1f=0.5。

输入:imax, mi, ri, v1, v2, l, h, w1, w2。

输出:最优货位分配方式。

步骤1输入货位分配优化模型参数:imax, mi, ri, v1, v2, l, h, w1, w2。

步骤2设置MPSO参数:T, N, c1i, c2i, c1f, c2f, ω0。

步骤3算法开始t=1, 随机生产初始粒子群N的位置及速度。

步骤4判断迭代次数是否超过最大迭代次数 (t>T?) , 若是则转步骤5, 否则继续。

步骤4.1计算个体的目标函数值F以及适应度G;

步骤4.2更新粒子的个体最优Pit以及群体最优Pgt;

步骤4.3根据式 (19) ～ (21) 更新惯性权重ω与学习因子c1, c2;

步骤4.4根据式 (17) 与式 (18) 更新各个粒子的位置与速度;

步骤4.5迭代次数t=t+1。

步骤5算法结束, 输出最优货位分配方案。

某汽车零部件制造企业的非传统布局仓储中心货架按如图1的Fishbone型摆放。其中, 货位的长和宽均为l=1 m, 货位的高为h=1 m, 第一排货架的货位数为xmax=9, AGV的水平速度v1=1 m/s, 竖直速度v2=0.5 m/s, 决策者偏好权重w1=w2=1。货物信息如附表1所示 (50类物品共占203个货位) , 这些货物按照人工方式进行存放得到的初始分配方案如附表2所示。由于算法参数的设置对最终优化结果优劣程度有较大影响, 为保证仿真结果的客观性, 根据初始实验本文设置AGA与MPSO的参数信息如表1所示。设计采用Matlab2015b编译, 运行环境Intel (R) Xeon (R) 2.10 GHz 16 GB, 操作系统Windows 7。

附表3、4分别是由AGA和MPSO得到货位分配优化方案。表2为3种不同方法得到货位分配方案的子目标函数值f1、f2以及归一化后子目标加权求和值F。数值越小表示货位分配方案的效果越优, 由表2可知AGA对上述2个子目标函数值均有优化, 优化率分别为23.28%与44.56%;而MPSO的优化效果稍微弱一些, 优化率为21.32%与27.25%。由此说明本文提出的2种方法对于提升非传统布局仓储出入库效率以及货架稳定性两方面均有效可行, 并且优化效果明显。

在相同环境下运行, AGA与MPSO 2种算法总运行耗时分别为412 s与527 s, 其中图3、图4分别给出了2种算法的收敛过程, AGA在第604代开始收敛于最优值, 而MPSO则于627代后开始收敛。AGA整体的收敛速度比MPSO更快一些, 并且再结合上述优化结果则表明在求解该问题时, AGA的整体优化性能比MP-SO更强一些。

为了进一步验证本文提出的2种算法通用性以及对比算法的优化性能, 本文在4组不同规模的货位分配优化问题下, 对4种算法基本GA (simple genetic algorithm, SGA) 、AGA、基本PSO (simple particle swarm optimization, SPSO) 、MPSO再次进行仿真实验, 其中, SGA与SPSO为无改进的基本算法, 其他参数设置与AGA和MPSO设置相同。由于归一化加权后的总目标函数F值并不能直接反映优化效果, 因此本文选取更为直观的出入库效率目标函数值f1和货架稳定性目标函数值f2以及收敛代数Gconv等3个指标, 在相同环境下分别运行10次, 计算上述3个指标的均值, 得到如表3所示结果。

根据表3, 从收敛代数来看, 在问题规模较小情况下, 基本算法与本文提出的改进算法收敛代数也大致相同, 同样AGA与MPSO的收敛代数值也相当, 这是因为在问题规模不大时, 最优解相对来说比较容易求得。但随着问题规模的扩大, 本文设计的2种改进算法相比基本算法在求解效率方面的优势开始显现, 这一结果也验证了改进策略可提升算法末期的局部寻优能力, 加速收敛。而AGA和MPSO单独对比分析可知, 随着问题规模扩大, AGA收敛速度波动较小, 算法鲁棒性更强。

结合表4, 在优化效果方面, 相比基本算法, 在不同规模问题下AGA与MPSO的优化效果均高于相应的基本算法, 说明改进策略也提升了算法的全局寻优能力, 得到的货位分配方案改善了出入库效率, 增强了货架的稳定性, 而从AGA与MPSO二者单独的对比则再次验证了AGA整体优化性能比MPSO更强。当然, 随着问题规模的扩大, 所有算法的优化效果值都在下降, 这是因为随规模扩大初始方案的目标函数值呈指数级扩大, 因此, 优化效果下降也是合理的。

本文以实际问题为背景, 分析了非传统布局仓储及货位分配优化问题的特征, 构建了以货物出入库效率最高和货架稳定性最优为目标的多目标货位分配优化模型。然后, 针对优化模型分别设计了适用于解决此类问题的自适应遗传算法 (AGA) 和改进的粒子群优化算法 (MPSO) , 并采用Mtalab实现了问题的仿真以及算法求解。结果表明, 本文提出的2种方法均能更有效地提高货物出入库的效率, 降低货物存放重心, 提高货架的稳定性。此外, 4种算法性能对比的结果则说明本文设计的改进算法相比基本算法对于优化货位分配效果更加明显, 同时也表明AGA整体优化性能比MP-SO更优, 鲁棒性更强。但如何提高算法求解大规模以及超大规模问题的求解速度与优化精度仍然有待进一步研究。