基于小生境遗传算法的仓库拣货-复核路径规划

蒲 晶，谭代伦,b，郭 潇

（西华师范大学a.数学与信息学院；b.计算方法及应用软件研究所，四川 南充 637000）

引 言

随着近年来互联网经济的高速发展，淘宝、京东等互联网购物平台使用率飞快增长，对于其背后仓储物流系统的要求也越来越高。在仓储作业中，拣货作业则是配送中心的一个重要的环节，其作业效率研究成为近年来的重点研究课题。

在现代物流企业中，较大型货物仓库通常放置有很多组相对独立的货架，它们的基本布局有矩形［1-3］排列，鱼骨型［4-6］排列等形式。从存放货物的货架层数上，可以分为只考虑一层货架的平面型仓库和考虑多层货架的立体型仓库。从对拣货前后的复核台设置上，可以分为无复核台、单复核台和多复核台等形式。在仓库的日常拣货过程中，拣货员从复核台获取订单，沿着通道拣选两侧货架上的商品，当商品拣完后再返回复核台检验，形成拣货-复核路径。因此，如何合理地给出它们的拣货顺序，使得拣货-复核路径尽可能短，对提高仓库工作效率具有重要意义。

目前国内外学者针对各类型的仓库拣货作业进行了大量的分析和研究，包括使用不同存储分配策略［7］、不同的仓库布局［8］和订单分批［9］等方法来优化仓库的拣货路径。在仓库布局方面，孙慧［10］在双区型仓库下建立了拣货车容量受限的TSP 模型，设计出一种启发式算法对拣货路径进行优化处理；陈荣［11］针对多区型仓库人工拣货路径问题，提出了人工鱼群算法优化策略，极大地缩短了拣货路径的距离。在路径规划方面，Chen 等［12］基于订单采摘路线不确定拣选下的多订单拣选机制，设计了一种蚁群算法，来避免拣货通道的拥挤；Giannikas 等［13］设计了一种动态拣货策略，在拣货周期中更新订单分配和拣货路线；Kulak 等［14］采用基于聚类的禁忌搜索算法求解最佳拣选路径；刘建胜［15］考虑拣货小车载重约束条件，建立多车协同拣选调度优化模型，给出了一种混合粒子群算法；孙军艳［16］以拣货时间最短为目标函数构建数学模型，提出并设计了动态货位调整与人工拣货协同作业的动态拣货策略。

物流仓库的拣货-复核作业过程具有明显的旅行商问题（TSP）特征，因此将拣货点（含复核台）定义为TSP顶点，构建任意两点间的距离计算公式，从而将该问题转化为TSP 问题建模，然后选择小生境遗传算法[17]进行求解，进而为提高仓库拣货-复核作业效率提供更有效的解决方法。

1 仓库布局及其路径规划模型

1.1 仓库布局

选取货柜按矩形排列、单复核台、平面型的仓库布局形式，计算路径长度时要考虑货格和通道的尺寸大小，整个仓库平面布局如图1所示。

在图1中，每一个正方形小格子存放一类货物，称为一个货格，所有货格的尺寸都相同。一定数量的货格并排组成一列货架，每一列货架的货格数目相同，两列货架背靠背形成一个货柜。所有货柜以矩形排列构成整个仓库，同一行或同一列的货柜可称为一个货区。货柜之间留有等间隔的通道，用于拣货行走，仓库的四周也是通道。复核台设置在仓库的左侧边线处，领单和交货都要到复核台处完成。

图1 仓库布局图

为便于描述和计算，现以仓库的左下角为坐标原点建立平面坐标系，向右为x轴正方向、向上为y轴正方向。

1.2 拣货点及其坐标

设仓库内共有K个货格，矩形排列为M行N列，其中每一列货架均由T个货格构成。货格尺寸均为a，通道宽度均为w。

所有货格从左下角开始，按从左到右、从下向上统一依次编号。对每一个货格，取其面向通道的边中点处为拣货点。任意第i(i= 1,2,…,K)个货格的拣货点记为vi，它在仓库中从下向上的行号记为im、从左向右的列号记为in，则有：

其中：im= 1,2,…,M；in= 1,2,…,N；“mod”表示求余数。

于是第i个拣货点vi的坐标可表示为vi(xin,yim)，其坐标计算公式为：

复核台可视为一种特殊的拣货点，它处于最左侧通道的边线处（图1），不考虑本身的尺寸，取其与y轴重合的边线中点处为领单或交货复核点，记为v0(0,y0)。

1.3 任意两点间的距离

仓库内的拣货点既有货格，也有复核台。从图1可见，任意两点之间的路径，主要受行方向上的货区位置关系影响，可分为两种情形：一种情形是这两点分别在不同行货区中，另一种情形是这两点都在同一行货区内，如图2所示。

图2 任意两点之间的路径

设任意两点为vi(xin,yim)和vj(xjn,yjm)，由图2可知，这两点的实际距离dij需要在曼哈顿距离的基础上予以修正，以下分两种情形讨论。

（1）当这两点在不同的行货区时

如 图2 中 的 路 径：A0B1—A0B7，A1B1—A1B7，A2B1—A2B7，分析可知，若点vi在奇数列上，可将横坐标左移半个通道宽度；若点vj在偶数列上，可将横坐标右移半个通道宽度，通过平移后的两个点的横坐标分别为x′in和x′jn，则有：

经过坐标变换后，这两点间的曼哈顿距离为：

（2）当这两点在相同的行货区时

如 图2 中 的 路 径：A0C1—A0C8，A1C1—A1C8，A2C1—A2C8，出现绕行到货柜背后拣货的情况，此时只需选取其中一个点。例如选vj点，作其关于相邻行通道中间线的向上对称点v′j(xjn,y′jm)和向下对称点v″j(xjn,y″jm)，通过对称映射，就将“在相同行货区”变换为“在不同行货区”的情形。其中，y′jm和y″jm分别为对称映射后的两个点的纵坐标，其计算公式为：

接下来只需分别计算出点vi与v′j之间的距离d′ij以及点vi与v″j之间的距离d″ij，并求其最小值，即为在相同行货区 时 点vi与vj之间的距离。由于vi与v′j和v″j分别在不同行货区内，因此仍要按照式(3)对x坐标进行变换得x′in和x′jn，于是有：

式（6）中，dij为相同行货区内两点之间的距离。

1.4 拣货-复核路径规划数学模型

拣货员从复核台领取拣货单，出发去往各个拣货点拣选商品，最后返回复核台交验货物的过程，具有经过且只经过拣货点一次并最终回到起点的特点，这符合旅行商问题(Travelling Salesman Problem，TSP)的基本特征，因此可将这类问题转化为TSP问题进行建模。

将仓库内需要经过的复核台和拣货点看作TSP顶点，对其进行编号即构成TSP 问题的顶点集。设某次拣货单需要经过的复核台和拣货点共有S个，记为V={v0,v1,v2,...,vS} ，定义如下0-1变量：

则可建立如下0-1规划模型：

上述模型中，xij∈{0,1}；式（7）为目标函数，表示所经过的路径长度；式（8）和式（9）使得每一个顶点只能有一条边进和一条边出；式（10）和式（11）表示所经过的路径不构成任何子回路，其中集合U 是顶点集V 的子集，| |U表示该集合所包含顶点个数，它不少于2个顶点，但不超过S+1个顶点。

2 小生境遗传算法的设计

仓库拣货路径问题属于NP-hard 问题，现代智能启发式算法［18-19］是求解这类问题的主要方法。遗传算法在这类问题上已取得不错的成果，但容易出现“早熟”现象和后期收敛速度较慢等缺点。在自然界中，每个物种都有自己特定的生存环境。在生物学范畴内，把特定环境中的角色或功能称为小生境［20-21］。小生境在形成初期，小生境中的物种基因常常不同，缺乏一定的交流，使得物种间的基因差异得以保留。同时，又由于各个小生境中的进化方向不同，小生境间的个体差异就会不断扩大，使得小生境间的物种基因差异进一步扩大［22］。因此，本文引入了具有进化优势的小生境技术进行遗传算法的设计。

2.1 编码方案与种群初始化

根据1.4节的0-1规划模型，仓库内的全部拣货点（含复核台）都是路径节点，其中复核台的编号为0，其余拣货点编号为1到K，为此采用从0开始的不重复自然数编码方案，与这些路径节点一一对应。若某拣货单需要到S(S≤K)个拣货点去拣货，则每一个遗传个体可表示为：

其中，pi∈{1,2,…,S};i= 1,2,…,S。

个体的第一个基因编码固定取值为0，表示总是复核台出发且最终再回到复核台；其余基因编码取值为[1,K]中的不重复自然数，表示需要经过的那些拣货点的位置编号。

根据种群规模大小，利用不重复自然数的随机生成函数，可生成一组符合要求的遗传个体，构成一个种群。

2.2 适应度函数

适应度函数用于评估和区分种群个体的优劣，是进行遗传选择的依据。根据式（11）的基因编码方案，遗传个体的适应度不能直接采用式（6）作为适应度函数，而重新构造为以下函数：

上式中，d0S即为从最后一个拣货点返回复核台的距离。

2.3 选择策略

遗传算法选择策略的任务是按一定规则挑选出相同种群规模的适应度较优的个体遗传给子代。本文采用锦标赛选择策略。

该策略模拟了体育比赛中的分组联赛机制，基本思想是每次从种群中随机选择一定数目的个体构成一个小组，然后从该组中选择最优的一个个体进入子代种群。其具体步骤如下：

（1）设定锦标赛策略的分组大小r（也称为r元锦标赛）；

（2）从种群中随机抽取r个个体组成一个小组，在组内选择最优的一个个体进入子代种群；

（3）重复步骤（2），直到子代种群达到预定的种群规模。

2.4 交叉策略

交叉策略是把两个父代个体的部分基因作交换而生成新的子代个体。通过交叉，种群会产生新的基因组合，个体的多样性增加，可以获得比父辈更优秀的个体以达到进化的目的。

算法采用基因片段交叉与修复策略，其处理步骤为：

（1）随机产生2 个不同的正整数a和b(1 ＜a＜b)，确定出两个父个体中介于[a,b]内的基因片段，在两个基因片段中依序查找出相同的基因并作上标记。这里要求a＞1，即确保个体的第一个基因点（对应于复核台）不参与交叉。

（2）将两个父个体的基因片段按交叉概率进行交换。

（3）对交换后的每一个新个体，在基因片段外依次查找片段内未标记的基因（此为重复基因），从交换前的基因片段中按序取一个未标记基因予以替换，全部查找和替换完成后，即得到无重复基因的新子代个体。

2.5 基于小生境的变异策略

变异策略的目的是使个体基因突变，变异为新的个体，从而扩大寻优范围，避免陷入局部最优。采用普通的变异方法往往会破坏一些优秀个体，而且两个相似父代个体不利于产生较优的新个体，最终会出现“近亲繁殖”的现象。为避免该现象的产生，在此引入一种新的变异策略，即融入小生境生存竞争机制的变异策略。其具体步骤如下：

（1）从种群中随机选取两个个体P1、P2；

（2）随机产生两个基因点a、b(1 ＜a＜b)，将个体P1、P2 中介于[a,b]内的基因片段作逆转变异操作，得到两个变异个体P3、P4；这里仍然要求a＞1，即第一个基因点（复核台）始终不参与变异；

（3）设定一个阈值，求两个父代个体P1、P2 的适应度之和f1=fp1+fp2，以及两个子代个体P3、P4的适应度之和f1=fp3+fp4，若f1-f2的差大于给定阈值，则将两个变异个体P3、P4 遗传到下一代，否则将两个父代个体P1、P2遗传到下一代。

（4）重复步骤（2）和步骤（3），直到子代个体数达到种群规模。

2.6 小生境遗传算法流程图

综合上述算法设计，本文小生境遗传算法流程图如图3所示。

图3 小生境遗传算法流程图

3 仿真实验与分析

3.1 实验环境与初始数据

本文实验的硬件环境为Intel Corei7CPU/16GB/Win10 系统，编程环境为Matlab R2017a。仓库内总共有K=216 个货格，按矩形排列成的行数和列数为M=18，N=12，每一列货架的货格数为T=6，排列后形成3个行货区、6个列货区。货格边长a=0.8 m，拣货通道宽度w=2 m，复核台位置坐标为（0，11.2）。所有货格从左下角以自然数1开始编号，按从左到右、从下到上进行编号为1,2,…,216。为验证本文算法的有效性和实用性，拣货单数据选取如表1所示的4组不同规模数据。

表1 4组拣货单数据

为更好地体现算法性能，采用标准遗传算法(Standard Genetic Algorithm,SGA)和小生境遗传算法(Niche Genetic Algorithm,NGA)分别求解上述4 组拣货单数据，将相关结果进行比较和分析。求解时，遗传算法的参数设置为种群规模为100,200,300,300；交叉概率为0.9；变异概率为0.01。对拣货单为1,2,3,4；迭代次数分别设置为100,300,400,500。

3.2 实验结果

按图3 算法流程编写本文算法(NGA)程序以及参照标准遗传算法(SGA)流程分别求解表1中的4组数据。由于求解结果较多，后面将适当给出一个拣货单的求解结果。以下主要对求解结果进行统计和比较，见表2。

表2 两种算法求解4组拣货单数据的结果

从表2可以看出，随着仓库拣货点规模增大，小生境遗传算法求解结果所节约的路径也更多，节约路径长度的百分比也越来越大，相应地完成拣货任务的效率也更早。因此，小生境遗传算法在保留了优秀基因的同时，增加了种群的多样性，提高了局部搜索能力，具有较好的寻优能力。

为便于观察求解结果，这里以拣货单1为例，用本文算法求解结果：复核台→25→51→77→66→116→93→22→36→108→156→115→173→209→122→205→复核台，拣货路径总长度为161.28 m，仓库拣货-复核的最优路径如图4所示。

图4 拣货单1的路径示意图

3.3 算法性能分析

为了进一步测试本文算法的性能，下面分别从求解过程中，随机选取其中一次的适应度的进化曲线，对算法的求解精度与稳定性进行比较和分析。

采用标准遗传算法（SGA）和小生境遗传算法（NGA）求解表1 中4 组拣货单时，其适应度进化曲线如图5所示。

就收敛结果来看，在图5（a）中，小生境遗传算法相比于标准遗传算法的优越性较不明显。但在图5（d）中，当拣货点数量较多的情形下，适应度值和收敛性能都明显优于标准遗传算法。

其次，从图5（c）中可见，标准遗传算法在130代的时候适应值开始陷入局部最优解，没有达到理想的搜索结果。而小生境遗传算法在第80 代的时候开始趋于收敛。对比之下，图5 中小生境遗传算法的收敛速度都较标准遗传算法快，且搜索精度更高，能较好地跳出局部最优。

图5 两种算法求解的适应度进化曲线

为进一步评估和衡量本文小生境遗传算法的性能，将标准遗传算法（SGA）和小生境遗传算法（NGA）各自独立运行50次，分别统计两种算法的最好值、平均值和标准差，结果见表3。

表3 两种算法寻优精度对比

表3 中，“最好值”是指50 次独立运行算法程序所求得的最好近似最优值，“平均值”、“标准差”是指这50次求得的近似最优值的平均值和标准差。

从表3 可以看出，在4 组拣货单中，小生境遗传算法（NGA）独立运行50 次所求得的最好值均比标准遗传算法（SGA）更小，说明本文算法寻优结果质量更高。尤其是当拣货点越多时，拣货-复核路径规划的优化效果就越明显。此外，小生境遗传算法（NGA）独立运行50 次的最好值的标准差也均明显低于标准遗传算法（SGA），这表明本文算法的稳定性更强。

由此可见，小生境遗传算法不但增强算法的寻优能力，而且算法的稳定性也得到很大的提升。

4 结束语

基于矩形仓库布局路径规划研究的基础上，根据实际的拣货运作场景，借鉴TSP 问题的建模和求解思路，建立了关于矩形仓库问题的数学模型。采用遗传算法和小生境技术相结合的方式，设计一种小生境遗传算法。通过实验数据的验证，小生境遗传算法在一定程度上克服了遗传算法的早熟收敛现象，且收敛速度更快，提高算法搜索效率，能较好地跳出局部最优解。同时，求解结果能有效提升拣货效率，对提高仓储工作效率和仓储作业智能化具有重要意义。

本文的数学模型及小生境遗传算法仍然适用于数据规模更大的仓库拣货问题，还可以推广应用于其他物流企业的路径规划问题。但是由于实际生活中物流配送中心仓库拣货问题的复杂性，本文的方法仍有许多不足之处，如未能考虑多人拣货、多复核台运作、时间窗口和载重量等因素，有待今后继续进行研究和完善。