0 引言

作为现代制造业重要组成部分, 仓储是连接生产制造与销售效劳的桥梁, 高效的仓储运营不但能实时响应客户需求, 还能有效降低本钱[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]
。然而, 非古板结构与古板仓储之间差别明显, 其货位分派优化问题是一个越发庞大的大规模组合优化问题, 现有的优化算法和古板仓储的货位分派要领为此提供了借鉴基础, 但并不可直接适用在此处
。因此, 研究设计高效的非古板结构仓储货位分派优化要领具有一定的学术意义和实际应用价值
。

1 问题描述与模型构建

1.1 Fishbone型结构

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

图1 Fishbone型结构   

1.2 结构参数

该仓储中货位的长和宽均为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点出发到目的货位历程在主通道的行驶距离, 其表达式为

1.3 货位分派优化模型

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

模型假设:

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

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

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

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

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

目标函数:

约束条件:

式 (3) 体现以货物收支库效率最高建立的目标函数, 式 (4) 体现以货架稳定性最优建立的目标函数
。式 (5) ～ (7) 为Fishbone结构中仓储货位分派的约束条件
。

1.4 多目标归一化

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

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

其中, 体现以货物收支库效率最高时的单目标函数的最优值, 体现以货架稳定性最优时的单目标函数最优值, w1和w2划分体现决策者对2个优化目标付与权重
。

2 自适应遗传算法

2.1 遗传算法

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

2.2 AGA设计

2.2.1 编码

编码是算法设计的要害一步, 编码方法多种多样, 需要针对求解问题及数学模型的特征设计相应高效的编码方法
。本文此处接纳矩阵式编码, 即单个个体的基因由一个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)
。

2.2.2 自适应战略

轮盘赌法是常用的选择算子, 可是这种要领会爆发较大的抽样误差, 容易造成“早熟”的现象
。为此, 本文在选择操作之前接纳自适应战略对适应度值进行变换:

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

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

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

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

2.3 AGA算法实现

输入: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算法结束, 输出最优货位分派计划
。

3 革新的粒子群优化算法

3.1 粒子群优化算法

粒子群优化算法 (particle swarm optimization, PSO) 是一种基于鸟群迁徙行为的群体优化算法, 其迭代寻优是一种由粒子速度与位置配合决定的庞大非线性变革历程[19]
。同时, 速度与位置的更新又与惯性权重 (ω) 和学习因子 (c) 密切相关, 而古板PSO中这2个参数恒定或线性递减的设定并不可反应粒子这一庞大历程
。因此, 本文接纳非线性变革动态更新惯性权重以实时变加速学习因子这2种战略对算法进行革新, 设计革新的粒子群优化算法 (modified particle swarm optimization, MPSO)
。

3.2 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
。

3.3 MPSO算法实现

输入: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算法结束, 输出最优货位分派计划
。

4 仿真实验

4.1 实例配景

某汽车零部件制造企业的非古板结构仓储中心货架按如图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
。

表1 AGA与MPSO参数值

4.2 仿真结果

附表3、4划分是由AGA和MPSO获得货位分派优化计划
。表2为3种差别要领获得货位分派计划的子目标函数值f1、f2以及归一化后子目标加权求和值F
。数值越小体现货位分派计划的效果越优, 由表2可知AGA对上述2个子目标函数值均有优化, 优化率划分为23.28%与44.56%;而MPSO的优化效果稍微弱一些, 优化率为21.32%与27.25%
。由此说明本文提出的2种要领关于提升非古板结构仓储收支库效率以及货架稳定性两方面均有效可行, 并且优化效果明显
。

表2 3种货位计划目标函数值

注:初始计划无法求得其单目标最优值故无法进行归一化处理, 因此其F值为空缺
。

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

图3 AGA优化总目标值变革曲线  

图4 MPSO优化总目标值曲线   

4.3 比照剖析

为了进一步验证本文提出的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更强
。虽然, 随着问题规模的扩大, 所有算法的优化效果值都在下降, 这是因为随规模扩大初始计划的目标函数值呈指数级扩大, 因此, 优化效果下降也是合理的
。

表3 4种算法对差别规模问题的求解结果  

表4 4种算法对差别规模问题的优化效果

5 结论

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

附表1 货物信息

附表2 初始货位分派计划 

附表3 AGA优化后货位分派计划 

附表4 MPSO优化后货位分派计划