Research on scheduling optimization of circular
conveyor line based on genetic algorithm 章俊哲1，李金村2，徐 健3，吴宗毅3，王 鹏3
ZHANG Jun-zhe 1, LI Jin-cun 2, XU Jian 3, WU Zong-yi 3, WANG Peng 3
（1.北京机械工业自动化研究所，北京 100120；2.北京机械工业自动化研究所有限公司，北京 100120；
3.北自所（北京）科技发展有限公司，北京 100120）摘 要：分析现有环形输送线系统的一些不够完善的情况。根据环形输送线的约束松弛条件，建立出环 形输送线系统的数学模型。对系统进行分析，到影响系统效率的瓶颈，从而到系统相应的适应度函数。建立初始化种，利用改进单亲遗传算法对系统分析和研究，再通过动态系统仿真分析出遗传算法对系统的优化效果。
关键词：环形输送线系统；遗传算法
中图分类号：TP29 文献标识码：A 文章编号：1009-0134(2021)05-0099-04
收稿日期：2020-04-12
作者简介：章俊哲（1995 -），男，湖北襄阳人，硕士研究生，研究方向为控制理论与控制工程。
站台信息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中，E
i 表示入环形输送线的端口，U
j
表示出环
形输送线的端口。为了简化系统便于研究问题，该系统的约束松弛条件如下：
1）线体为单向运行（逆时针），不能反转。
2）每段输送线只能存放一个托盘。
3）输送线被分配任务以后，到达相应的出入端口，立即执行，不存在等待时间。
4）每送出14个托盘被视为一个调度任务周期。
5）输送线在运行过程中，若发生故障，则停止系统的调度，不会对整体系统的调度优化过程造成影响。
6）L1、L2和L3入环形输送线端口的货物视为无穷，进入输送线顺序按照分配进入。
托盘一次作业包括进入线体、输送、托盘送出线体三个过程，三个过程所用时间为：
(1)
(2)
上式中，T为输送机完成一次输送作业所需的时间，t
w
为托盘运行在输送线上花费的时间，它包括托盘
加减速t设备故障诊断系统
a
，托盘匀速行走时间t
c
和托盘等待向前输送时间t p。t l为托盘出入线体的输送时间（定值）。由以上公式
可以推出，t
w
决定了整个系统的运行时间。而t
w
和托盘在输送过程中是否出现堵塞相关。线体堵塞越严重，输送时间就越长。想要优化整个系统的效率，可以从减少堵塞次数这方面解决问题。
根据提出的解决方案，建立相应的数学模型：
(3)
式(3)中，B
c（q）
为第n个托盘内由于前方输送机堵塞而等待的次数，即
。
约束条件：
(4) 2.3 改进单亲遗传算法设计
2.3.1 染体编码
将托盘的队列进行编码，具体编码方式如下：
编码方式中的X i
k
表示第k个托盘在第i周期进入线
体的起始端口，Y i
k
表示第k个托盘在第i周期被送出线体的目的端口。例如0103表示托盘先在E1口进入线体，再去U3被送出线体，进入拆垛区域，即托盘完成本次作业。
其中需要注意的是：1≤X i
k
≤3，1≤Y i
k
≤7，1≤k≤14。
2.3.2 初始化种
种规模过大或过小对实验效果均不好，故设置种规模为50。单个染体形成的具体方法为：
托盘进环形线体端口为：P
1，…，P
k
，…，
P k+i，…；
托盘出环形线体端口为：Q
1，…，Q
k
，…，
电解抛光液Q k+i，…；
从托盘进环形线体端口中随机选取P
k 赋给X1
1
，从托
盘出环形线体端口中随机选取Q
k 赋给Y1
1
，再从托盘进
环形线体端口中随机选取P
k+i 赋给X1
2
，从托盘出环形线
体端口中随机选取Q
k+i 赋给Y1
2
，直到形成合格的染体
为止。
2.3.3 适应度函数
适应度函数是判断种中个体好坏的标准，根据以上分析可得到相应的目标函数：
堵塞次数最少：
(5)
为了解决目标问题，将适应度函数定义为在一个周期内到问题。本章将把问题用一个适应度函数表示：
(6)
其实把问题简化为了到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号出口送出托
盘，故不会堵塞。可以得到当Y i
k+1≥Y i
k
时，会使托盘拥
堵一次。
通过上面的分析，此次堵塞次数为7次，适应度函数F=∑14
c=1
B c(q)=7。
2.3.4 遗传算子设计
本文选择算子采用混合选择的方法，即采用保留优秀个体和赌法结合。具体操作如下：
第一步随机生成染体，将适应度大于平均适应度的个体去除，保留下适应度小于平均适应度的个体。保留下来的个体进入下一代；
组合式桥架
第二步利用赌法将去除的个体进行选择，与第一步中保留下来的个体组成下一代种。
得到的种在利用基因重组的方法进行单点换位算子，对每代染体个体中进行m次单点换位，计算模型如下：
(7)
式(7)中ceil是向上取整，f
min
是种中个体的最小适
应度，f
avg
是种的平均适应度，f
i
是要单点换位的个体的适应度，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代左右收敛最佳。
50
100
150
200
250
300
350
400
450
500
代数
24
6
8最优解
单亲遗传算法迭代过程
堵塞次数
图6 最优解随进化代数的变化趋势
050100150200250300350400450500
代数
4
6
8
均值
单亲遗传算法迭代过程
堵塞次数
图7 平均堵塞次数随进化代数的变化趋势
利用上述方法将得到第二次周期，第三次周期的变化趋势，进行比较，如表1所示。
表1 优化前后堵塞次数
第一周期
优化前
堵塞次数为7
优化后堵塞次数为2第二周期
优化前
堵塞次数为8优化后
堵塞次数为3第三周期
优化前
堵塞次数为7优化后
间硝基苯甲酸
堵塞次数为2由表1可以根据仿真优化前后得出环形线经过本文设计的遗传算法模型，减少一个周期内的堵塞次数，提升输送线系统效率。
4 结语
本文提出了一种基于遗传算法规划环形输送线系统的方法，并针对环形输送线系统的瓶颈进行分析。通过对系统进行分析，得出适应度函数，从而设计出改良单亲遗传算法。通过仿真验证遗传算法运用在该系统的优越性，提高了物流效率。
现代化的物流系统还有许多其他的环节，例如RGV 系统、AGV 系统等。这些系统的货物调度程序均可以用遗传算法进行优化。
参考文献：
[1] 贺道坤，刘国臣，尹欢.环形输送分拣装置的设计与实现[J].信息
化研究,2020,46(05):63-67,73.
[2] 王鹏，余亮.纸箱输送装置设计[J].南方农机,2020,51(07):23. [3] 刘焕牢，周磊磊，王宇林，等.电饭煲铝盖冲压自动输送线设计[J].
机电工程技术,2020,49(03):41-43.
[4] 慕晶晶.基于遗传算法的服装退货回收车辆路径优化问题研究
[J].物流工程与管理,2021,43(03):123-125.
[5] 向旺，吴双，张可义，等.基于排队论的环形穿梭车系统运行参数
分析[J].制造业自动化,2018,40(06):151-153.
