基于改进粒子群算法V型非传统布局仓库通道优化设计

刘建胜， 熊 峰, 胡颖聪

(1.南昌大学 机电工程学院，江西 南昌 330031; 2.南昌大学 经济管理学院，江西 南昌 330031)

0 引言

随着德国“工业4.0”项目计划，我国智能制造2025计划的相继提出，智能工厂、智能生产、智能物流以及整个生产制造供应链的智能化已成为理论研究和科研实践热点。仓储管理环节由原来不受重视的作业性、辅助性角色,上升为企业策略运作的重要环节及能为企业取得竞争优势、降低成本的利润源泉。长期以来，国内外大多数学者主要针对传统仓库布局方式开展研究，但是2009年美国学者Gue和Meller[1]提出了非传统布局方式，通过分解各类仓库业务操作成本，发现在一定的假设下，相比传统仓库布局模式，非传统型仓储布局方式能够减少平均约10%～20%左右的移动距离。非传统型的仓储布局方式在分拣路径优化方面表现出了优势，激发了科研人员对仓储布局设计优化的重新思考和放松假设条件的研究兴趣。仓库优化设计主要包含了三个方面的问题，一是布局设计，二是货位分配，三是路径优化[2]。国内蒋美仙等从角度建模和移动距离建模两个方面研究了基于fishbone的仓库布局优化设计[3]。S.S.Rao和G.K.Adil提出根据货物的需求将货物分成A、B、C三个等级，需求越大的货物所分配的存储货位离存取点越近[4]。目前国内外对非传统布局优化设计研究的成果不多，并且现有研究主要针对布局设计、货位分配及路径优化等内容的独立研究，没有结合研究。实际工作过程中，布局设计、货位分配及路径优化是业务上是相互联系，互相影响。本文针对非传统Flying-V新型仓库布局，每条拣货通道存取作业的概率也不同的现状，结合物动量ABC分类法进行概率分配的非完全随机策略，在此基础上进行主通道的设计，优化仓库平均拣货距离，并用实例验证算法有效性。

1 仓库布局设计

1.1 仓库布局

国内配送中心大多属于劳动密集型产业，而且现代的仓储自动化系统需要很高的成本，对于国内大多数配送中心尤其是配送量不大的配送中心来说，依靠廉价的人力成本的传统型仓储仍是较好的选择。如图1所示，是传统的双分区型仓库布局方式，仓库的设计一般都满足一些设计的规则：拣货通道之间相互平行且与主通道垂直，基于传统布局结构性质，一般传统型布局仓库运作效率不高。在仓库设计时，仓库面积利用率和平均拣货距离往往是两个互相矛盾的优化目标，传统仓库布局通道少，仓库的面积利用率高，拣货效率下降。从仓库主体作业流程分析，仓库作业时间的60%是分拣配货过程[5]，盲目的增加拣货通道数量来提高效率的需求在实际仓库管理中也是不可取的，因此合理的设计仓库的通道和结构，使得在尽可能保证仓库面积利用率的情况下提高货物存取的效率是非常有必要的。

如图2所示是非传统Flying-V型仓库布局，Flying-V型仓库布局打破了传统仓库设计的规则，对传统型布局中的主通道重新进行设计，由仓库存取点引伸出两条斜向的主通道，再由主通道进入到各条拣货通道，主通道与货架成了一定的角度，并且主通道也不是直线。当仓库的规模相同时，这种仓库布局相对于传统型的仓库布局能明显减少平均拣货距离，有效提高运作效率。

图1 双分区型布局

图2 Flying-V型布局

1.2 非传统V型布局设计

1.2.1 符号说明

Gue提出的Flying-V型仓库布局针对单元式货架仓库，基于仓库只有一个P&D点，假设每条通道具有连续并且相同的拣货作业，即人工去到每个货位点的概率是相等的[6]。但是实际的仓库使用中，尤其是人工拣货仓库，因为存储的货物种类、出入库频率等差异，如果使用随机的存储策略，无疑会增加仓库使用的成本。所以结合基于货物周转率的存储策略来设计Flying-V型布局，相关参数说明如下：

P&D：存取货物的入口；w：拣货通道和主通道宽度的1/2；a：拣货通道之间的水平距离；h：仓库的宽度；bi：第i条拣货通道在V型通道口的纵向距离(纵深值)，即y轴上的长度取值；qi：第i条拣货通道中对应的自P&D点经底部横向通道和经V型主通道到该点的距离相等的点，qi为该点到底部横向通道的纵向距离，即对应y轴上的长度取值；Di：第i-1条拣货通道和第i条拣货通道之间的V型主通道的长度；y：货位到仓库底部的距离。

1.2.2 Flying-V型布局建模

如图3所示，在单元式货架仓库中仓库通道由竖直的拣货通道、V型主通道和底部横向通道组成，在模型中，V型主通道看成是由多个离散的点连接而成，每一条拣货通道分别对应一个点，模型的优化目标是仓库的平均拣货距离最短。

图3 Flying-V型仓库布局建模

假设通道的宽度均为2w，插入主通道会使得仓库的存储空间减少。考虑到主通道与拣货通道并不是垂直的，所以主通道的宽度会小于2w，忽略这个因素的影响。由于仓库的布局是对称的，所以只需要对仓库的半侧进行建模分析。假设仓库的一边有n+1条拣货通道(包括中间的通道0)，则根据勾股定理，相邻拣货通道i-1和拣货通道i之间的主通道的长度Di为：

(1)

bi并不一定大于bi-1,所以模型能够考虑到主通道所有可能的位置。对于每一条拣货通道i，都有一个临界点qi，使得从底部主通道经拣货通道到该点的行走距离和从V型主通道经拣货通道到该点的行走距离相等，即：

(2)

可以得到：

(3)

图4 V型通道优化模型

不同货位的拣货距离是不同的，qi与bi并不是相互独立的，qi的值随着bi的值变化，qi可以简化拣货距离公式。用Di(y,b)来表示拣取第i条拣货通道内距离底部横向通道距离为y的货位上货物时拣货距离。

如图4中所示通道1、2、6、7所示，当通道i上存在满足条件的qi时，对于i≥1的拣货通道，拣货距离Di(y,b)如下：

(4)

如图4中的通道3、4、5所示，当通道i上不存在满足条件的qi时，对于i≥1的拣货通道，拣货距离Di(y,b)如下：

Di(y,b)=ia+y

(5)

则对于i≥1的拣货通道，对不同位置的货物拣取时要选择主通道使得拣货距离最短，当通道i上存在满足条件的qi时，则该拣货通道的平均拣货距离如下：

(6)

当通道i上不存在满足条件的qi时，通道i对应的平均拣货距离为：

(7)

在通道0拣货时不用考虑横向的选择，所以通道0的平均拣货距离如下：

(8)

即平均拣货距离会比b0>0时小，所以当通道的宽度为2w时，b0的最优解为w。

则当考虑随机存储策略时仓库总的平均拣货距离为：

(9)

此时的目标函数如下：

(10)

1.2.3 物动量ABC货位分配策略

在仓库布局设计时，可以结合对仓库的EIQ定量分析[7,8]，仓库订单信息中的E(订单件数：OrderEntry)、I(货品种类：Item)、Q(数量：Quantity)是物流特性中的关键因素，所以可以通过对这三个物流关键因素进行分析，从而选择合适的物流作业方式和布局, 田歆[9]具体分析了ABC管理的库存控制、订货补充、储位分配等应用策略的整体作用、改善程度以及策略之间的影响，推导出ABC管理后分拣配货作业效率提高率的公式，从定量的角度验证了EIQ-ABC分析法能够大幅改善分拣配货的效率。

考虑到仓库的布局主要的影响因素是货物的物动量大小，所以主要对仓库数据进行品项数量(IQ)分析，即了解各类产品出货量的分布状况，分析出货商品品项与出货量的关系。用E1、E2、E3、…、Ei表示一段时间内仓库处理某种货物的订单，用I1、I2、I3、…、Ii表示货物品种，用Q1、Q2、Q3、…、Qi表示对应货物周转量。则货物物动量分析表如下：

表1 物动量ABC分析表

如表1中所示，按照货物周转量Qi由大到小的顺序进行，并计算周转量比重和累计周转量比重，可以将累计周转量百分比在60%～80%的定义为A类货物，将累计周转量百分比在20%～30%的定义为B类货物，其余定义为C类货物。

为了优化仓库结构，增强仓库的运作效率，可以根据货物的ABC分类结果对仓库货架进行ABC分类，分类的原则主要是货架距离I/O的距离，见表2。

表2 仓库货架ABC分析表

在仓库的实际使用过程中，货物的存储往往要结合适当的存储策略，常用的存储策略有随机存储、定位存储、分类存储等方式。在一般情况下，货位分配的优化目标主要有两个[10]：

(1)使货架的重心最小，以满足货架稳定性的要求。

(2)对存取效率的要求，频繁存取的物品应放在能够快速取到的位置上。

图5 按货物周转率划分仓库区域

在此假设所研究的是单层货架仓库，在仓库的设计时，考虑产品入库货位分配时主要考虑基于产品出入库频度的货位分配原则。如图5所示，在仓库中，根据表1中的原则按货物周转率对货物进行分类，A类货物周转率最高，C类货物周转率最低，在仓库的实际使用中，应该将周转率越高的货物存放地离P&D点越近，故可以对应的对仓库进行分区，A区、B区、C区分别放置对应周转率的货物，这样有利于货物的存取。

(11)

并且有：

(12)

在考虑pi的值时，可以依据仓库所存储不同种类货物所占比重和周转率进行设置。则仓库所对应的平均拣货距离如下:

(13)

则优化的目标函数为：

(14)

2 V型布局算法设计

2.1 算法设计

粒子群优化(Partice Swarm Optimization，PSO)算法于1995年由Kennedy和Eberhart[11]两位博士提出，该算法通过模拟自然界中的鸟群的觅食运动来实现对于最终问题的求解。PSO算法一经出现即引起了广大学者的研究兴趣，目前已经广泛用于解决各类优化问题，但是经典PSO算法也存在易陷入局部最优以及算法性能问题，本文采用极值扰动算子，结合并行搜索策略，提出一种改进粒子群优化算法(particle swarm optimization algorithm with extreme disturbed operator, EDO-PSO)求解，利用极值扰动算子解决算法易于陷入局部最优的问题；并采用并行搜索策略，将粒子种群按粒子适应度大小分成两个子种群，适应度较好的子种群采用较小的惯性权值进行局部搜索，适应度较差的子种群采用较大的惯性权值进行全局搜索，以此增强种群的寻优能力，并与其他改进粒子群算法用Benchmark函数对比验证算法有效性。

假设仓库的布局是对称分布的，所以只需对仓库的一侧进行建模分析。仓库共有2n+1条拣货通道，每一列货架有h个货位，则问题的维度为n维(b0=w)，可行域为(0,h)。问题对应的解为[b0,b1,b2,b3,…,bn],则仓库的V型主通道即为b0,b1,b2,b3,…,bn所对应的点依次连接而成的通道。粒子群的规模为M，算法迭代次数为eranum，则粒子i在第t次迭代过程中所达到的位置状态表示为：

Xi(t)={xi1(t),xi2(t),…,xin(t)},i=1,2,…,M

(15)

粒子的飞行速度定义为：

Vi(t)={vi1(t),vi2(t),…,viN(t)},i=1,2,…,M

(16)

则粒子i在第t时刻的第j(j=1,2,…,n)维的飞行速度调整为下式：

vij(t)=εvij(t-1)+c1r1[r3pij-xij(t-1)]+

c2r2[r4gj-xij(t-1)]

(17)

(18)

其中，c1和c2为加速因子，通常c1和c2均取2，r1和r2是[0,1]内的随机数，pij为粒子i在t时刻第j维粒子自身所经过的最佳位置，gj为整个种群第j维上的最优值，tg为极值扰动阈值，sg为算法停滞代数。

在粒子群算法中，当粒子的速度超出了上下极限时，则粒子的速度则被固定为极限值。即：

(19)

ω为惯性权值，ω值较大时，可以增强全局搜索能力；反之，ω值较小时，可以增强算法的局部搜索能力。所以选取合适的ω值对算法的影响很大，有很多学者提出了动态惯性权重调整策略，Y.Shi和R.C.Eberhant首先提出了惯性权重典型线性递减策略[12]，之后有学者提出了很多不同的非线性[13]和自适应惯性权重策略[14,15]，大大的改进了粒子群算法的性能。主要的思想是考虑到在算法初期，应该保证惯性权值ω足够大并且减小的速度较小以此来使得粒子能够更好的搜索全局最优解，在算法后期惯性权值可以快速减少以此在之前搜索到的解附近搜索最优解，加速收敛。

本文采用一种并行搜索的方法，即对每次迭代后的种群按照适应度值分为两个小种群，种群1(pop1)是适应度较好的个体组成的种群，种群2(pop2)是适应度较差个体组成的种群,种群1与种群2的大小为2：1，本文中采用的种群数大小为30，则种群1有20个粒子，种群2有10个粒子。对于个体适应度较差的种群，则在下次迭代中使用较大的惯性权值；对于个体适应度较好的种群，在下次迭代中使用较小的惯性权值。

(20)

并且为了更好的寻找最优解，种群1采用深度搜索策略，即令c2=0，让粒子从自身最优位置进行学习。此时速度的更新公式为：

vij(t)=ωvij(t-1)+c1r1[r3pij-xij(t-1)]

(21)

参考文献[16]，通过严格的数学推导，可以得到:

(22)

所以当算法处于进化停滞时，粒子群中的粒子都会出现早熟，如果所有粒子在靠近p*的过程中没有找到比pg更好的解，则算法即陷入局部最优解。为了算法能够突破进化停滞的局面，更好的寻找最优解，所以采用局部扰动策略，该策略引进了进化扰动代数，增加了极值扰动算子，当算法进化出现停滞时，则使用极值扰动因子调整pb和pg，对个体极值和全局极值同时进行随机扰动，使粒子向新的p*靠近，从而使粒子快速跳出局部极值点。

本文中当全局极值pg连续tg代没有改变时，本文中tg设置为20，则通过极值扰动因子同时调整当前的个体极值pb和全局极值pg，通过使粒子转向新的搜索路径和区域来帮助粒子跳出局部最优解。

粒子i在t时刻的位置更新可由下列公式计算所得：

xij(t)=xij(t-1)+vij(t)

(23)

2.2 算法实现

输入：n(拣货通道的数量);a(相邻拣货通道的间距);h(仓库的宽度);pi(每条拣货通道上进行存取货物作业的概率);w(通道宽度的一半)。

输出：主通道的最优位置bi

Step1输入仓库的参数n，a，h，pi，w。

Step2初始化粒子群算法参数eranum，popsize,c1,c2,tg。

Step3算法开始,初始化种群。

Step3.1更新gbest, pbest。

Step4判断是否达到迭代次数，如果否则继续，如果是则继续Step5。

Step4.1按照公式(17)(21)(23)分别更新种群1和种群2中每个粒子的速度和位置。

Step4.1.1判断速度是否越界，如果是则按公式(19)更新速度。

Step4.2根据公式(14)评估每个粒子的适应度函数。

Step4.3更新每个粒子的历史最优。

Step4.4更新群体的全局最优。

Step4.5按照粒子适应度大小将种群分成两个小种群。

Step4.6判断迭代次数是否满足扰动条件，如果是则按公式(18)进行扰动Step4.6.返回Step4。

Step5算法结束，输出最优主通道的位置。

2.3 算法性能分析

为了说明本算法的有效性，本实验选用了几个经典的Benchmark函数来检验算法的性能，表3中给出了各测试函数的表达式、取值范围和达优值，所有的测试函数均取30维，并且函数的最优值均为0。算法编程用matlab 2015b工具实现，计算机CPU为2.60GHz。

其中，函数1，函数2为单峰值函数，Sphere函数是简单的单峰值函数，可以检验算法的执行性能；Rosenbrock是一个比较复杂的非凸病态函数，其全局最小值位于一个平滑的、弯曲路径上的谷底，所以该函数在一般情况下很难搜索到最优解，故通常用该函数来评价智能优化算法的性能。函数3、函数4、函数5都是多峰函数，都有很多个局部极小值点，一般都较难搜索到全局最优解，所以通常用这些函数来检验函数的跳出局部最优解的能力。

表3 测试函数

所有实验的种群规模均取30，迭代次数为1000次，每个函数的测试独立运行100次，算法参数设置同前文。为了说明优化粒子群算法的性能，将本文算法和动态改变惯性权值的自适应粒子群算法(DCWPSO)[17]、惯性权重线性下降的标准粒子群算法(LWPSO)[12]、均匀搜索粒子群算法(UPSO)[18]进行比较，对比组的算法参数设置与参考文献中相同，得到优化结果平均值、方差和达优率作为算法的衡量标准，测试结果如表4所示。

表4 测试结果

从表4中的数据可以看出，周期性极值扰动因子可以有效地帮助算法跳出局部最优解，大大的改善了算法的性能，而采用了并行搜索策略和深度搜索策略，使得粒子能够快速的收敛到较优的解，相比于其他改进粒子群算法有明显的优势。为了更好的说明算法性能的改善，针对函数2、函数3、函数4、函数5这四个复杂的优化函数做出平均适应度变化曲线。为更直观的对比各算法的性能，对适应度取对数后做适应度随时间的变化曲线，四个Benchmark函数对应的进化曲线如图6所示。

图6 测试函数平均适应度变化曲线

从平均适应度变化曲线中可以看出，本算法在求解Rastrigrin、Griewank和Schaffer函数时能够很好的跳出函数的局部最优解，较快的收敛到函数最优解，在求解Rosenbrock函数时有较快的收敛速度，虽然收敛的结果相对于其他算法没有很大的优势，但是算法的稳定性很强，算法最终结果的方差明显优于其他算法，并且达优率能够达到100%。从表4和图5的测试结果中可以看出，本算法有很好的寻优能力，下文中将该算法应用到仓库的主通道设计的求解当中。

3 案例分析

3.1 方案设计

参照文献1，设拣货通道和主通道的宽度均为2.5个单位，相邻拣货通道之间的距离为4.5个单位。根据物动量ABC分析按根据货物周转率由大到小计算累计周转率比率，周转量累计百分数在60%～80%之间的定为A类，周转量累计百分数在20%～30%之间的定为B类，其余定义为C类。将不同的货物进行分类并存储到指定区域，而在相应的区域内货物的存储是遵循随机原则。针对公司H的仓库订单进行EIQ-ABC分析的结果如表5所示，按照如图4的方式和表5中的数据进行仓库分区，则最靠近P&D点的3/10区域存放A类货物，仓库中间3/10区域存放B类货物，远离P&D点的4/10区域存放C类货物。

表5 仓库货架ABC分析表

在仓库规模相同的情况下，给出两种设计方案，方案一是仓库共有21条拣货通道，每一列货架有100个货位；方案二是仓库共有41条拣货通道，每一列货架有50个货位。

针对假设的仓库，结合仓库分区标准，方案一中根据公式(11)计算结果大致得出人工去到不同拣货通道进行拣货作业的概率依次为:

p0～10=[0.0558 0.0558 0.0555 0.0547 0.0531

0.0516 0.0488 0.0462 0.0423 0.0368 0.0273]

方案二中人工去到不同拣货通道进行拣货作业的概率依次为：

p0～20=[0.0464 0.0464 0.0461 0.0453 0.0439 0.0421

0.0403 0.0374 0.0334 0.0276 0.0185 0.0141

0.0133 0.0125 0.0112 0.0086 0.0073 0.0073

0.0073 0.0073 0.0073]

(因为仓库布局是对称分布，所以只列出了从通道0开始的仓库右侧通道所对应的概率)。

3.2 仿真结果

利用本文中的提出的改进粒子群算法EDO-PSO，在matlab中实现，按照前文中建模推导出的公式(14)为目标函数。按照上文中设定的算法参数，迭代次数为3000，运行求解后的结果如下：

对于方案一，w=1.25,a=4.5,h=100,n=10横向通道的节点bi如下：

b0～20=[1.25,8.28,14.66,20.49,25.83,

30.75,35.28,39.48,43.36,46.96,50.31]

对于方案二，w=1.25,a=4.5,h=50,n=20,横向通道的节点bi如下:

b0～20=[1.25,5.972,10.12,13.86,17.1,19.89,22.49,

24.76,26.69,28.33,29.86,31.05,32.26,33.16,

33.8,34.51,34.96,35.44,35.94,36.44,36.6]

所得结果如图7、图8所示。按照相同的分配策略，两种方案的平均拣货距离相对传统型的双分区型仓库布局的对比如表6所示。

图7 21条拣货通道设计结果示意图

图8 41条拣货通道设计结果示意图

随机存储双分区型仓库物动量ABC分类法双分区型布局随机存储V型布局物动量ABC分类法V型布局21条拣货通道73.5771.2464.1862.5541条拣货通道71.1054.5862.9247.85

从仿真的结果中可以看出，物动量ABC分类法更加适合长宽相差较大的仓库，因为这种仓库人工去到最里面的货架进行仓储作业需要更长的路程，则应尽量减少这一部分货架的使用率，即用这一部分货架存储物动量较小的货物，因此物动量ABC分类法在这一类仓库中应用的效果会更加明显。

4 结语

论文在Flying-V型仓库布局的基础之上，考虑传统型人工拣货方式的仓库，每次存取单个货物，结合物动量ABC分析法对仓库进行分区，基于非完全随机的分配原则来建立主通道设计模型，提高仓库的运作效率。并对粒子群算法进行改进，用Benchmark函数对比检验改进粒子群算法的性能，并应用于符合实际约束问题中，能够较快的得到满意的结果，实验结果表明该方法有效应用于V型仓库主通道设计中，在物动量ABC货位分配策略下，相比随机策略的主通道设计方案能够有效的减少仓库平均拣货距离，提高仓库的运作效率。