摘要：本文以人工拣选作业路径优化问题为研究对象，完成了四区型仓库中人工拣选作业路径优化问题模型的构建，同时将改进后的猫群算法应用在实际问题之中进行检验，并与粒子群算法在同一问题的应用中进行对比分析，发现改进后的猫群算法具有比粒子群算法更好的效果，验证了改进猫群算法的有效性。

　　关键词：猫群算法;人工拣选作业;路径优化

　　1 引言

　　近几年，随着国民经济的迅猛发展，我国物流行业也飞速前进，成为受到众多专家和学者关注的重要领域，现代物流业作为国民经济的基础产业，伴随着整个经济的发展历程，成为国家重点鼓励和发展的行业。也成为现代衡量综合国力的重要指标之一。拣选作业是物流仓储中的一个重要环节，据有关研究表明，拣选作业的劳动量大约占到了配送中心总体作业量的60%，而作业时间也占到了整个物流作业时间的30%-40%[1]，提升拣选作业效率十分具有研究价值。目前，虽然一些大型企业开始探索现代化、无人化智能仓储，但是对于一些小批量、多品种的货物拣选，还是多采用人工拣选的方式进行。

　　2 人工拣选作业路径优化问题模型构建

　　2.1 人工拣选作业路径优化模型假设

　　在对人工拣选作业路径优化问题进行研究之前，要先对拣选作业中一些特殊情况进行假设。在不影响对该问题进行研究的条件下，本文所假设的内容如下：

　　(1)仓库选取多区型仓库，每个货架与通道都具有相同规格。

　　(2)拣选人员在通道内进行拣选时，忽略货架的高度以及在同一个通道内左右移动的距离。

　　(3)每个货位都被拣选一次且只能拣选一次。

　　(4)订单上各种类的货物之间相互独立，各类货物被拣选的概率各不影响。同种类货物可以分布在不同的通道上，但是被拣选的概率相同。

　　(5)拣选设备的容量及拣选人员的条件充分满足要求，每次订单拣选都是一次性完成拣选操作的。

　　(6)所有货物体积相同，且每个货位只存在一个货物。

　　2.2 人工拣选作业路径优化模型建立

　　人工拣选作业问题是路径规划问题，其模型建立的目标就是最小化拣选路径，使得拣选人员行走距离最短。在建立数学模型之前首先对模型中出现的符号进行说明，具体含义如表2-1所示。

　　表2-1 模型符号说明

　　在进行符号说明后，人工拣选作业路径问题可以建立如下的数学模型。

　　目标函数：D=min(d01x01+■ ■dijxij+dn0xn0) (2-1)

　　因x01与xn0是必经路线，因此x01与xn0取值均为1。上式可简化为：D=min(d01+■ ■dijxij+dn0) (2-2)

　　约束条件：

　　■xij=1，j=1，2…，n (2-3)

　　■xij=1，j=1，2…，n (2-4)

　　■xij≤k-1，k v，2≤k≤n-1 (2-5)xij=0或1 (2-6)

　　目标函数(2-1)与(2-2)表示拣选人员进行一次拣选作业行走路程的最小值，其中x01表示从0点(起始点)出发到第一个货物这条路径，xn0表示从最后一个货物返回0点(起始点)这条路径，由于拣选人员肯定会经过x01与xn0这两条路径，所以x01与xn0取值均为1。在约束条件中，式(2-3)与(2-4)表示每个货物只能被拣选一次。式(2-5)表示不存在小回路。式(2-6)表示对于任意两货物之间的路径xij，拣选人员有经过这条路径和不经过这条路径两种选择。

　　3 四区型仓库下人工拣选作业路径优化问题研究

　　3.1 四区型仓库设计分析

　　本文的人工拣选作业路径优化将按照四区型仓库来进行研究分析，四区型仓库是由一定数量相同宽度的巷道和货架组成，多条过道与拣选巷道垂直相通，拣选人员可以灵活选择路径，四区型仓库布局如图3-1所示。

　　假设仓库出入口0为拣选人员每次进行拣选作业的起始位置，拣选完所有货物后最终回到该点。四区型仓库中每个货位都对应相应坐标，拣选人员从这些货位拣选货位。本文中以起点0为原点建立直角坐标系，对于任意货位i的坐标就是(xi，yi)。其中xi表示横向距离;yi表示纵向距离。与x轴平行的通道宽度为b，与y轴平行的通道宽度为α，相互平行通道间通道宽度相等。货架宽度为h，货架长度为l。

　　图3-1 四区型仓库平面布置图

　　3.2 多区型仓库内人工拣选作业路径距离研究

　　假设仓库内任意两货位点为i和j，两货位点间最短距离为dij。dij(x)表示横向行走的距离，dij(y)表示纵向行走的距离。我们用取整的方式来计算待拣选货物所在的货架区域，若int(xi/(a+l))与int(xj/(a+l))相等则表示货物i和货物j位于同一区内。这里我们用Z(i)来表示货物所在区域。

　　(1)对d01进行求解，d01表示从起点到第一个货位的距离

　　d01=(x)=x1 (3-1)

　　d01=(y)=y1 ，其中y1=k(b+h)+■ (3-2)

　　d01=x1+y1 (3-3)

　　(2)对dij进行求解，dij表示任意两个待拣选货物位置的距离：

　　A：当两货物之间纵坐标相等时，即yi=yj时

　　dij=xi=xj (3-4)

　　B：当两货物之间纵坐标不相等时，即yi≠yj时

　　①若两货物位于同一区，即Z(i)=Z(j)时

　　即：dij(x)=minxi-Z(i)(a+l)-■+xj-Z(j)(a+l)-■l-[xi-Z(i)(a+l)-■]+l-[xj-Z(j)(a+l)-■]

　　即：dij(x)=minxi+xj-2Z(j)(a+l)-a2l-xi-xj+2Z(i)(a+l)-a (3-5)

　　dij(y)=yi-yi (3-6)

　　dij(y)=yi-yi+minxi+xj-2Z(j)(a+l)-a2l-xi-xj+2Z(i)(a+l)-a (3-7)

　　②若两货物不位于同一区，即Z(i)≠ Z(j)时

　　dij(x)=xi-xj (3-8)

　　dij(y)=yi-yj (3-9)

　　dij=xi-xj+yi-yj (3-10)

　　(3)对进行求解，dn0表示最后一个拣选货物的位置回到0点(起始点)的距离：

　　dn0(x)=xn (3-11)

　　dn0(y)=yn，其中yn=k(b+n)+■ (3-12)

　　dn0=xn+yn (3-13)

　　上文对多区型仓库内任意两货位点间最短距离的计算方法进行了设计，所有订单拣选完成后，将各项进行求和即可得到拣选路径总距离。

　　4.猫群算法及其算法改进

　　4.1猫群算法工作流程

　　Chu等人根据猫的这种行为模式模拟设计了猫群算法，这一算法把猫的行为模式分为搜寻模式和跟踪模式。猫群算法就是通过结合这两种模式来解决复杂问题，一部分的猫开展搜寻模式，其他的猫开展跟踪模式[2]。

　　猫群算法在搜寻模式和跟踪模式的基础上，将二者结合形成了完整的猫群算法，猫群算法的整体流程大致可以分为五个步骤。

　　(1)首先对猫群进行初始化，设定猫初始的状态，包括种群大小、位置、速度和分组率等必要参数。

　　(2)通过设定的分组率MR，将猫群分为执行搜寻模式的部分和执行跟踪模式的部分。

　　(3)根据猫的标志位的不同，执行不同模式来更新当前猫的位置，一般来说用0和1作为猫的标志位，对猫执行的模式进行选择。

　　(4)在执行完两种模式之后，计算当前所有猫的适应度值，按照需求找出适应度最优的猫，并对当前猫进行更新。

　　(5)判断算法是否已经达到最大迭代或者终止条件，如果达到终止条件则输出当前最优猫，结束算法;否则继续进行迭代，再次执行步骤2，直至算法达到结束条件。

　　4.2猫群算法的改进

　　猫群算法中的大多数猫都处于执行搜寻模式的状态，但是搜寻模式中变异方式比较单一，由于这种变异的简单性导致猫群算法在运行过程中经常会陷入到局部的最优解中。考虑到上述情形，在原始猫群算法的基础上，增加了算法在搜寻模式中的变异能力。猫个体在完成编码的步骤之后，在各体序列中随机选取两个位置i，j，其位置上的货物编号为cicj。对于■d←d(ci，ci+1)+d(ci，cj)>d(ci，cj)+d(ci+1，cj+1)，其中d(ci，cj)代表的是货物ci，cj之间的路径长度。当■d>0时，将基因位j与基因位i+1后面一位互换，这样整个拣选路径长度就得到了改善，通过随机选取插入点的位置，使选择多样性、变异多样化。

　　同时本文将原本固定的参数MR改为动态参数，使MR在算法前期比例较大，在后期逐渐减低。使算法前期进一步加大全局搜索的能力，后期在全局搜索已经处于一定优化的基础上在集中精力进行局部最优的推敲。通过公式(4-1)可以动态调整MR取值[3]。

　　MR=MRmax-■*T

　　其中MRmax和MRmin分别表示最大分配率和最小分配率。T为当前迭代次数，Tmax为最大迭代次数。

　　5 改进猫群算法在人工拣选作业路径优化问题中的应用

　　本文研究背景选在四区型仓库中，四区型仓库的纵向拣选巷道的宽度a=2，仓库的横向拣选巷道宽b=1，货架宽度h=1，货架长度l=5，由于拣选巷道的宽度并不大，所以拣选人员在巷道中进行拣选时可以双侧拣货。

　　客户订单到达具有随机性，本文选取订单大小为10的订单进行验证并且将粒子群算法作为对比。具体订单情况如表5-1.

　　表5-1 待拣选货物情况

　　通过验证得到了改进猫群算法和粒子群算法求解该订单的拣选路径的最终结果，如图5-1所示。

　　图5-1 CSO与PSO结果及平均值对比图

　　从结果图我们可以看出，粒子群算法虽然能够求解出最优路径，但是并不是每次都能得到最优解，但是改进后的猫群算法每次都能得到很好的结果，最优解率达到100%。同时改进后的猫群算法求解拣选路径时很快就能得到最优解，具体迭代图如图5-2，最终得到的最优路线图如图5-3所示。

　　图5-2 改进猫群算法迭代图

　　图5-3 拣选的实际路径图6 总结

　　拣选作业作为物流运作过程中必不可少的重要环节，在提高物流效率上具有很大的潜力。上文对配送中心中货物的拣选作业进行分析研究，通过改善人工拣选作业的拣选路径，从而达到提高拣选效率，减少物流成本的目的。对于配送中心拣选作业的研究一直具有很高的研究价值，具有很强的现实意义。研究表明，猫群算法在处理人工拣选作业路径优化问题上是可行的且具有较好的优化效果，特别是订单较大时能够大大缩短拣选作业时间，减少企业成本。C

　　(作者单位：北京物资学院)

　　参考文献

　　[1]程庆章. 医药物流中心人工拣选作业优化及其仿真[D].武汉科技大学,2010.

　　[2]马知也,施秋红.猫群算法研究综述[J].甘肃广播电视大学学报,2014,24(02):41-45.

　　[3]陶亚男,张军朝,王青文,张俊虎.基于改进猫群算法的物联网感知层路由优化策略[J].计算机工程,2019,45(02):13-17.