基于变邻域NSGA-Ⅱ算法的多目标货位优化研究*

罗 焕，闫富乾，宋小欣，张 剑

（西南交通大学 先进设计与制造技术研究所，成都 610000）

0 引言

随着经济环境和相关政策的影响，全球仓储业的效率和管理水平得到迅速提高并稳步发展。各仓储企业不断追求仓储的自动化与无人化，以释放劳动力、提高仓储作业运转效率等，促使自动化立体仓库的货位优化成为研究热点[1]。

焦玉玲等[2]针对自动化立体仓库的工作效率和安全性要求，以出入库作业时间、整体货架的等效重心和相关产品的相对积累程度为多目标函数，建立了多目标货位分配优化的数学模型，提出了多种群遗传算法进行求解；唐文献等[3]提出自动化立体仓库分区存放策略，以多巷道货架为对象，开展货位优化研究。蔡锦文等[4]在传统的以存储频率为中心的存储分配策略的基础上，考虑了工作负载平衡问题，提出了两种新的自动化仓库存储分配策略；杨玮等[5]以出库效率和货物重量为目标将仓库进行分区，然后对比HPSO、GA、PSO三种算法的求解效果；宋贺腾等[6]以堆垛机的立体仓库货架重心最低和总取货时间最短为目标，同时保证调整时间最短，采用改进自适应遗传算法进行求解。

综上所述，目前国内外学者在构建货位优化模型时，多以出入库效率为首选目标，再进行目标和约束扩展，而现有文献往往忽略了同类货物在仓库中的分布情况以及各条巷道堆垛机工作量均衡问题，导致仓库作业过于集中和不平衡，容易造成通道堵塞[7]。为此，本文以出入库效率、货架稳定性、同类货物就近存放和堆垛机工作量均衡创建多目标优化数学模型，提出一种变邻域NSGA-Ⅱ算法对遗传操作后的部分个体进行变邻域操作，以增强算法的求解搜索能力，并通过实例验证了算法的有效性。

1 货位分配模型

1.1 问题描述

自动化立体仓库由货架、堆垛机、传送带组成如图1所示。货位分配优化问题可以描述为：已知一系列货物的类型、重量和出入库频率等相关属性，按照一定的货位分配原则，通过传送带和巷道堆垛机将这些货物放置在第x排y列z层的货位上，以实现同类货物在各巷道两侧的货架上分布均匀，各巷道堆垛机工作量均衡，同类货物就近存放，提高货架整体稳定性和货物出入库效率。

图1 自动化立体仓库示意图

货位分配过程满足如下假设：每个货位只存放一个货物；堆垛机和传送带以平均速度运行，不考虑启动和停止时间且可存取巷道左右两排货架上的一个货物；不考虑货架自身、货箱以及托盘的重量，且货物重量不影响存取时间，货位重心位于该货位的几何中心；巷道为单向出口，出入库口位置坐标为（0,0,0）。

1.2 符号说明

模型中相关参数说明：

x：仓库第x排货架，x={1,2,3….X}；

y：仓库第y列货架，y={1,2,3….Y}；

z：仓库第z层货架，z={1,2,3….Z}；

vx：传送带沿水平方向的平均速度；

vy：堆垛机沿巷道方向的平均速度；

vz：堆垛机沿竖直方向的平均速度；

pji：i类货物中第j个货物的出入库频率；

mji：i类货物中第j个货物的重量；

L：货位的宽度；

L0：巷道宽度；

J：第i类货物的总数；j={1,2,3….J}；

h：巷道序号，h={1,2,3….H}；

H：巷道总数；

G（x）max：第x排货架的最大承重；

(Ai,Bi,Ci)：第i类货物的中心坐标；

(xji,yji,zji)：第i类第j个货物的货位坐标；

t(xji,yji,zji)：第i类货物中第j个货物从仓库出口到货位的时间。

1.3 数学模型

式(1)为多目标函数集合，表示出入库效率、货架整体重心、同类货物间距离、巷道堆垛机工作量均衡最小化，其中各部分计算如式(2)～(5)所示，式(2)表示出入库效率f1，式(3)表示货架整体重心f2，式(4)表示同类货物间距离f3，式(5)表示巷道堆垛机工作量f4。式(6)表示第i类货物中j货物入库所消耗时间。

约束条件：

其中：式(7)表示货架x存放货物总重量不能超过货架最大承重；式(8)表示货物j是否在巷道h中。

2 变邻域NSGA-II算法

传统的多目标优化是将不同的目标分配一定的权重以转化为单目标优化，而目标的权重系数往往根据经验或试错法得出，难以适应问题的变化和需求，采用NSGA-II可以优化出适用多目标问题的非支配解种群[8]，其主要思想是对种群中个体的各个目标函数值进行非支配解分层，同层个体为非支配关系，其非支配解更倾向于选择拥挤度大的个体以得到目标函数最优值。本文提出一种变邻域NSGA-Ⅱ算法对遗传操作后的部分个体进行变邻域操作以增强其搜索能力，其算法流程图如图2所示。

图2 变邻域NSGA-Ⅱ算法

变邻域NSGA-Ⅱ算法步骤如下：

1）初始化参数：设置种群大小PopSize，交叉概率为Pc，变异概率为Pm，最大迭代次数为Gmax，最优前端个体系数PF，邻域初始种群大小VNSize，变邻域最大循环次数VNS_Gmax。

2）初始化种群：采用实数编码随机生成初始种群Initial_Pop。

3）目标函数值的计算：根据式(2)～式(5)计算四个目标函数值f1、f2、f3、f4。

4）非支配排序和拥挤度计算：

（1）非支配排序：根据目标函数值进行个体序值的计算。

（2）拥挤距离计算：对四个目标分别计算相应的拥挤距离，再将四个目标函数的拥挤距离相加得到最后的拥挤距离。

5）遗传操作：

（1）选择操作：锦标赛选择。根据序值和拥挤度进行选择操作，对于种群中的两个随机个体，当序值不同时，序值小的个体将被选中；当序值相同时，拥挤距离大的个体将被选中。

（2）交叉：单点交叉。并运用同位基因的思想进行交叉前的处理。

（3）变异：为避免在前两个操作中优秀基因的丢失，选择随机性更大的对调基因位的变异方式。

6）变领域操作：从变异后种群中随机选部分个体进行变邻域操作。首先，随机选择一种邻域结构对初始邻域种群进行邻域操作，再将变邻域产生的种群与初始邻域种群进行合并，对合并后的种群进行选择得到新一代邻域种群。最后，判断是否满足邻域终止条件，满足则结束，不满足则返回再执行变邻域操作直到满足邻域终止条件。

7）种群合并：将变领域搜索产生的个体与变异之后未进行变邻域操作的个体合并再与初始父种群合并。

8）生成新种群：根据父代种群规模对合并后的种群进行修剪生成新的父代种群。

9）判断是否达到终止条件，若满足则结束，否则，转去执行步骤5）。

2.1 染色体编码

本文针对货位优化设计了一种基于货位和货物类型顺序的编码方式。货位由仓库货架的排、列、层组成，则每条染色体长度为3N，N为货物总数。如图3 所示，假设一批货物分为两类，第一类货物总数为4在货架上的货位为(1,2,1)，(2,4,5)，(4,3,1)，(5,4,3)，第二类货物总数为3在货架上的货位为(1,4,3)，(1,5,3)，(3,4,1)。

图3 染色体编码

2.2 变邻域操作

设计三种邻域结构进行变邻域操作：

1）邻域1：前插入操作，从染色体基因序列中随机选择两个不同的基因位点，在前基因位之前插入后基因，如图4所示。

图4 前插入变邻域操作

2）领域2：后插入操作，从染色体基因序列中随机选择两个不同的基因位点，在后基因位之前插入前基因，如图5所示。

图5 后插入变邻域操作

3）领域3：基因片段倒序，从染色体基因序列中随机选择两个不同的基因位点，然后将基因片段进行倒序操作，如图6所示。

图6 基因片段倒序变邻域操作

3 实例验证及分析

为了检验优化模型的有效性和变邻域NSGA-Ⅱ算法的优越性，以某车间自动化立体仓库的实际数据进行了实验分析。

1）数据与参数

自动化立体仓库共3条巷道和一条传送带，即巷道编号h从1到3，堆垛机工作巷道的宽度为1.5m。仓库货架6排6列5层，每个货位的长、宽、高都为1m，传送带平均速度Vx=1.5m/s，堆垛机沿巷道方向平均速度Vy=1m/s，堆垛机沿巷道竖直方向平均速度Vz=0.5m/s。货架平面布局图如图7所示。有5种类型的货物共100个需要分配到合适的仓库位置。货物基础信息如表1所示。NSGA-Ⅱ算法和变邻域NSGA-Ⅱ算法参数赋值如表2所示。

表1 货物信息表

表2 变邻域NSGA-Ⅱ算法参数赋值及含义

图7 货架平面布局图

2）实验结果与分析

通过上文的方法进行编码和求解，先运用NSGA-Ⅱ算法求解无巷道堆垛机工作量平衡目标和考虑巷道堆垛机工作量平衡目标，验证模型的有效性；再运用变邻域NSGA-Ⅱ算法求解考虑巷道堆垛机工作量平衡目标，并与NSGA-Ⅱ算法求解结果进行对比，验证算法的优越性。应用MATLAB R2014a软件编程实现算法，分别运行10次取运行结果的平均值进行比较，如表3所示。

通过表3对比NSGA-Ⅱ算法求解考虑和不考虑巷道堆垛机工作量均衡目标可以得到，出入库效率、货架整体重心、同类货物间距离变化很小，而巷道堆垛机工作量平衡性提高了13.06%。通过对比变邻域NSGA-Ⅱ算法与NSGA-Ⅱ算法求解考虑巷道堆垛机工作量均衡目标的计算结果可以看出，其他目标值变化不大，而巷道堆垛机工作量平衡性提高了54.39%，得到极大地提高。显而易见，所提出的变邻域NSGA-Ⅱ算法优化结果更好。

表3 变邻域NSGA-Ⅱ与NSGA-Ⅱ计算结果对比表

4 结语

本文基于巷道堆垛机工作量均衡进行货位分配并创建多目标优化数学模型，采用变邻域NSGA-Ⅱ算法对遗传操作后的个体进行变邻域操作以增强算法搜索能力，实验结果表明改进算法结果更优，而考虑巷道平衡后各条巷道的堆垛机工作量更加均衡，各类货物在各条巷道的分布也更加合理。