基于遗传算法对环形输送线调度优化研究

章俊哲，李金村，徐 健，吴宗毅，王 鹏

（1.北京机械工业自动化研究所，北京 100120；2.北京机械工业自动化研究所有限公司，北京 100120；3.北自所（北京）科技发展有限公司，北京 100120）

0 引言

在当今全球化和市场化的潮流下，物流对于促进世界经济、贸易和电子商务的发展有着巨大的意义。输送线是物流仓储中心的重要组成部分。托盘和货物都需要经过输送线送至目的地，输送线的效率和稳定性决定了整个系统的效率。输送线就像是人体中的血管，对整个系统起到了至关重要的作用。

随着物流规模的扩大，很多学者开始对其中的环节进行研究和优化。贺道坤等人为了解决环形输送线拣选问题，利用条码识别的方法对不同工件进行分拣[1]。王鹏等人为了解决纸箱自动输送的效率能够满足生产需求，对PLC控制程序进行了优化[2]。刘焕牢等人为了解决生产线效率和人工等问题，对输送线的机械结构进行了分析，使得系统实现了全自动化且节约了人力[3]。以往的学者对输送线的研究基本上都在于对机械结构和控制程序的方面，很少有对于输送线调度程序方面进行优化。

本文根据约束松弛条件对输送线系统建立数学模型，再通过遗传算法对系统进行研究。利用仿真，找到系统的最优解，根据比较得到遗传算法对系统的优化效果。

1 遗传算法介绍

1.1 遗传算法概述

遗传算法是基于达尔文进化论和孟德尔的遗传学说所推理出来的。遗传算法模拟自然界中生物繁衍和进化的过程，将有利种群的特征得到延续，由此发展出的全局概念法[4]。遗传算法借鉴生物进化中的一些思想，通过生成种群、自然选择、交叉、变异等操作，增强想要得到的属性。

遗传算法其中包括几个重要的条件：

1）个体指带有特征的实物，生物学中也成为染色体。个体通常的表现方式为二进制串和符号串等。

2）基因是染色体中的某些特征单位，代表了个体的独有特性。

3）种群是由所有个体组成的群体。在遗传算法中，群体的规模一般设置为10～100之间。

4）适应度是指个体对于约束条件的适应情况。能够更好适应约束条件的个体，有更高的概率进行遗传，将基因传递给下一代。

5）编码是指将现实问题的解映射到遗传空间。

6）解码是指将遗传空间的解映射到现实问题。

7）遗传算子是遗传算法模拟生物进化的重要手段。其中分为三种：选择算子、交叉算子和变异算子[5]。

1.2 遗传算法的基本流程

1）设置遗传所需要的具体参数。

2）将现实问题映射至遗传空间，进行编码。

3）生成初始化种群。

4）找到适应度函数进行计算，根据计算出的个体适应度，选出合适的个体进入下一代。

5）交叉变异。

6）不断地迭代，直到满足算法的终止条件。将种群中适应度最高的解输出，作为最优解。

2 实例分析

2.1 系统概述

图1是A厂的环形输送线示意图，主要设备为辊筒输送机。

图1 A厂环形输送线系统示意图

图1左侧为入环形输送线端口，右侧为拆垛区域。托盘由输送线输送至拆垛区域。每个拆垛区域由机器人和输送线组成，分别有一个入满托盘口和出空托盘口。托盘在拆垛完成以后，空托盘经过环形输送线运送至出口。空托盘汇入输送线不会影响满托盘的输送节拍。

2.2 环形输送线调度模型建立

本章将针对环形线体系统的托盘调度问题进行研究，对于传统的输送线而言，托盘是否进入线体和送出线体仅仅依靠人为设置好的去向去分配，托盘会按照均分进入或者送出输送线的原则进行分配。这种方法不会根据实际情况进行调节，从而导致整体效率下降。

本文将用遗传算法对环形输送线货物的调度系统进行优化。该系统的布置示意图如图2所示。

图2 环形输送线系统示意图

图2中，Ei表示入环形输送线的端口，Uj表示出环形输送线的端口。为了简化系统便于研究问题，该系统的约束松弛条件如下：

1）线体为单向运行（逆时针），不能反转。

2）每段输送线只能存放一个托盘。

3）输送线被分配任务以后，到达相应的出入端口，立即执行，不存在等待时间。

4）每送出14个托盘被视为一个调度任务周期。

5）输送线在运行过程中，若发生故障，则停止系统的调度，不会对整体系统的调度优化过程造成影响。

6）L1、L2和L3入环形输送线端口的货物视为无穷，进入输送线顺序按照分配进入。

托盘一次作业包括进入线体、输送、托盘送出线体三个过程，三个过程所用时间为：

上式中，T为输送机完成一次输送作业所需的时间，tw为托盘运行在输送线上花费的时间，它包括托盘加减速ta，托盘匀速行走时间tc和托盘等待向前输送时间tp。tl为托盘出入线体的输送时间（定值）。由以上公式可以推出，tw决定了整个系统的运行时间。而tw和托盘在输送过程中是否出现堵塞相关。线体堵塞越严重，输送时间就越长。想要优化整个系统的效率，可以从减少堵塞次数这方面解决问题。

根据提出的解决方案，建立相应的数学模型：

式(3)中，Bc（q）为第n个托盘内由于前方输送机堵塞而等待的次数，即

约束条件：

2.3 改进单亲遗传算法设计

2.3.1 染色体编码

将托盘的队列进行编码，具体编码方式如下：

编码方式中的Xik表示第k个托盘在第i周期进入线体的起始端口，Yik表示第k个托盘在第i周期被送出线体的目的端口。例如0103表示托盘先在E1口进入线体，再去U3被送出线体，进入拆垛区域，即托盘完成本次作业。

2.3.2 初始化种群

种群规模过大或过小对实验效果均不好，故设置种群规模为50。单个染色体形成的具体方法为：

托盘进环形线体端口为：P1，…，Pk，…，Pk+i，…；

托盘出环形线体端口为：Q1，…，Qk，…，Qk+i，…；

从托盘进环形线体端口中随机选取Pk赋给从托盘出环形线体端口中随机选取Qk赋给再从托盘进环形线体端口中随机选取Pk+i赋给从托盘出环形线体端口中随机选取Qk+i赋给直到形成合格的染色体为止。

2.3.3 适应度函数

适应度函数是判断种群中个体好坏的标准，根据以上分析可得到相应的目标函数：

堵塞次数最少：

为了解决目标问题，将适应度函数定义为在一个周期内找到问题。本章将把问题用一个适应度函数表示：

其实把问题简化为了找到F的最小值，即在一个调度周期内的拥堵次数的最小值。我们将具体说明适应度值的计算过程。

随机生成一组染色体：

0205，0107，0304，0202，0304，0106，0303，0306，0101，0107，0205，0305，0306，0102

堵塞次数如下计算：

例如0205，0107这样的基因串就会有堵塞的情况，前托盘先在2号入口进线体，去5号出口送出托盘。后托盘在1号入口进入线体，去7号出口送出托盘，若前托盘走过1号端口则在送出托盘的过程中，会导致后托盘堵塞一次。若前托盘没走过1号端口则在1号端口送托盘的过程中，会导致前托盘堵塞一次。故不管出现什么情况，均会导致堵塞一次。0107，0304这样的基因串不会出现堵塞，前托盘先在1号入口进线体，去7号出口送出托盘。后托盘在3号入口进入线体，去4号出口送出托盘，故不会堵塞。可以得到当时，会使托盘拥堵一次。

2.3.4 遗传算子设计

本文选择算子采用混合选择的方法，即采用保留优秀个体和轮盘赌法结合。具体操作如下：

第一步随机生成染色体，将适应度大于平均适应度的个体去除，保留下适应度小于平均适应度的个体。保留下来的个体进入下一代；

第二步利用轮盘赌法将去除的个体进行选择，与第一步中保留下来的个体组成下一代种群。

得到的种群在利用基因重组的方法进行单点换位算子，对每代染色体个体中进行m次单点换位，计算模型如下：

式(7)中ceil是向上取整，fmin是种群中个体的最小适应度，favg是种群的平均适应度，fi是要单点换位的个体的适应度，M为定值，即最大次数，设为5。

2.3.5 终止条件

在遗传算法中，通常由两种终止条件：第一种是得到最优解以后算法终止。第二种是迭代至设置的值以后算法终止。本文采用第二种方法，设置迭代次数为500次。

3 仿真分析

3.1 仿真建立

通过上面分析，通过MATLAB进行编程，可以得到详细的算法，本文将以改进的单亲遗传算法对货物调度系统模型进行优化，具体步骤入图3所示。

图3 遗传算法MATLAB设计流程图

3.2 仿真数据分析

利用MATLAB进行仿真。利用上文中的方法进行数据仿真，进行分析。

1）随机生成一个调度周期内的作业，如下：

托盘进环形线体作业：01，03，02，01，02，03，02，01，03，02，01，02，03，02；

托盘出环形线体作业：05，06，02，03，01，07，04，06，02，05，01，07，01，03；

2）随机生成初始化种群，如下：

0105，0306，0202，0103，0201，0307，0204，0106，0302.，0205，0101，0207，0301，0203。

按照算法计算可得到堵塞次数为7 次。利用MATLAB软件进行仿真，得到最优解个体如图4所示。

图4 第一次调度周期最优个体

最优解个体的堵塞次数为2次。

其中一个最劣解个体堵塞次数为9次，具体如图5所示。

图5 第一次调度周期最劣个体

图6和图7分别为最优解随进化代数的变化趋势和平均值随进化代数的变化趋势。从图6可以看出最优解的堵塞次数在20代左右出现变化，进化到180代左右收敛得到了种群中的最优解个体。图7的变化趋势与图6基本一致，也是在180代左右收敛最佳。

图6 最优解随进化代数的变化趋势

图7 平均堵塞次数随进化代数的变化趋势

利用上述方法将得到第二次周期，第三次周期的变化趋势，进行比较，如表1所示。

表1 优化前后堵塞次数

由表1可以根据仿真优化前后得出环形线经过本文设计的遗传算法模型，减少一个周期内的堵塞次数，提升输送线系统效率。

4 结语

本文提出了一种基于遗传算法规划环形输送线系统的方法，并针对环形输送线系统的瓶颈进行分析。通过对系统进行分析，得出适应度函数，从而设计出改良单亲遗传算法。通过仿真验证遗传算法运用在该系统的优越性，提高了物流效率。

现代化的物流系统还有许多其他的环节，例如RGV系统、AGV系统等。这些系统的货物调度程序均可以用遗传算法进行优化。