抽象
本文研究了一种改进的多自动导向车辆（多AGV）路径规划遗传算法。创新体现在两个方面。首先，三交换交叉启发式运算符用于产生更优化的后代，以获得更多的信息，而不是传统的双交换启发式算子在改进的遗传算法中。第二，施加最小化所有AGV的总路径距离并最小化每个AGV的单路径距离的双路限制，获得最佳最短总路径距离。仿真结果表明，通过使用改进的遗传算法，缩短了所有AGV的总路径距离和最长的单个AGV路径距离。
介绍
多目标优化已经在许多领域得到应用，其中工程[ 15 ]，运输[ 6 – 10 ]和物流[ 11 – 15 ]。多目标问题是搜索满足冲突目标之间所有目标函数的解决方案。多目标优化的方法包括经典的优化算法（例如加权和的方法，ε -constraint方法，交互方法，帕累托为主的方法）[ 16 – 19 ]和智能优化方法（如基于演进算法和基于群算法）[ 20 – 24 ]。
以多目标为特征的多自动导向车（multi-AGV）在配送物流领域发挥越来越重要的作用，因为它们在工作站之间的物料搬运效率高。AGV系统的应用面临几个重要问题：AGV的数目确定[ 25 – 27]，路径规划[ 28 – 30 ]和约束施加[ 31 – 33 ]等。
确定车辆的最佳数量是AGV系统管理的根本问题。几种方法已经提出了为实现这一目标，他们的主要目标是准时参加所有任务与车辆[足够数量25 – 27，34 ]。例如，Vivaldini等人 提出了一个新的模块，通过集成任务分配和路由来估计用于执行一组任务的AGV的最优数量[ 27 ]。Ji和Xia为AGV系统建立了新的模型，并通过基于二叉搜索的近似分析方法研究了最小车辆数量[ 34]。Koo等人 研究了AGV车队大小模型，其中估计各种车辆调度规则的部分等待时间，以确定适当的AGV车队大小[ 26 ]。
多AGV路径规划对于确保在生产过程中材料的有效流动是最重要的。路径规划涉及到三个任务的调度，调度和路由问题。多AGV路径规划问题[ 35 – 37 ]与旅游推销员问题（TSP）[ 38 – 40 ]相似，在找到具有极大搜索空间的最短旅程/时间方面，难以解决。Smolic-Rocak等人 以矢量形式使用时间窗口来解决多AGV系统的最短路径问题[ 36 ]。Draganjac等人 实现了考虑多AGV系统的非完整车辆约束的最短可行路径规划算法[35 ]。王等人 提出了通过生产优秀个人的TSP的多代遗传算法[ 38]。王等人 研究一种新的模因算法，以保持总距离尽可能短的TSP [有竞争力的容量39 ]。姜和艳为TSP开发了离散果蝇优化算法[ 40 ]。
有存在于多AGV路径规划，例如各种约束无碰撞的约束[ 41 – 43 ]，时间窗约束[ 36，44 ]，和时间/距离的限制[ 35，45 ]。本文通过对所有AGV的总路径距离和每个AGV的单路径距离进行双路限制，以及通过选择三交换启发式运算符进行交叉运算，研究了改进的多AGV路径规划遗传算法。
传统的遗传算法通过双交换交叉算子为交叉操作，即，使用两个父代个体产生的后代的染色体[ 46- 48 ]。显然，与父母以外的两个父母的传统遗传算法将获得较少的父母信息，并减少后代表现的多样性。为了提高后代的多样性，我们提出了三交换交叉算子对交叉运算的思想，即使用三个亲本的个体来产生后代染色体。
本文的贡献在于：
-
与传统路径约束不同，仅对所有AGV的总路径距离施加影响，本文对所有AGV的总路径距离和每个AGV的单路径距离施加双路限制。该策略双重缩短了总/单个AGV路径距离，获得了最佳结果。
-
通过使用传统方法以外的三个亲本亲属与两个亲本的个体，产生后代染色体，该方法增加了后代染色体的产生信息，获得了继承父母优良特征的可能性，并加快了改进算法。
-
多AGV路径图的模拟和改进/传统遗传算法的迭代图验证了改进的遗传算法与所有AGV的总路径距离比传统遗传算法的距离更短。
本文的其余部分安排如下。第2节展示了设施布局的概况。第3节通过使用三交换交叉启发式算子来研究改进的具有双路限制的遗传算法。第4节通过仿真提供了算法的可行性。最后，总结性话题涉及第5节。
设施布局概述
设施布局
具有多个AGV的作业制造系统执行材料交付。有M个 AGV穿过N个工作站（N > M）。对于工作站分发，考虑以下假设来描述细节。
-
M AGV遍历N个工作站（N > M）。
-
只有一个AGV通过每个工作站（起点除外）。
-
每个AGV从相同的起点（工作站）开始，并返回起点。
-
每个AGV与预定义的路径和固定速度分开运行一条路线。
-
有两个限制：
-
所有AGV的总路径距离应最小化;
-
每个AGV路径距离应尽可能小。
-
原理图如图1所示。
数学表达
参考图1，我们在数学上提出了所提出的问题。索引，参数和变量如下。
-
索引i，j –对于弧的两端的两个工作站，i = 0,1,2 …，N，j = 0,1,2 …，N。k -Index表示AGV号，k = 1,2 …，M。l -Index对于工作站需要AGV进行传送，l = 1,2 …，L k，0 < L k < N。
-
参数R ij -Arc在两个工作站i和j之间。C ij -Path通过相应的弧段R ij。
-
变量
对于i = 0,1，…，N，j = 0,1，…，N，k = 1，…，M，定义
X我j k= { 10该第k个AGV通行证该弧[R我j否则，（1）ÿk 我= { 10该第k个AGV去至该第i个站否则，（2）žķ= Σi = 0大号ķΣj = 0大号ķC我jX我j k。（3） -
客观功能
Ĵ= m i n （Σk = 1中号žķ） ∩中号我Ñžķ（ķ = 1 ，2 ，。。。，ķ ），（4） -
要求
Σk = 1中号ÿk 我= { M，1 ，i = 0我= 1 ，。。。，Lķ，（5）Σi = 0大号ķX我j k= Yk j，Ĵ = 0 ，。。。，Lķ，ķ = 1 ，。。。，M，（6）Σj = 0大号ķX我j k= Yk 我，我= 0 ，。。。，Lķ，ķ = 1 ，。。。，M，（7）
哪里
要求（5）规定每个AGV从启动工作站0开始，所有工作站只能由AGV访问一次;
要求（6）表明任何电弧从启动工作站开始;
要求（7）意味着任何电弧都与起始工作站结束。
算法设计
将遗传算法应用于多AGV路径规划的关键问题是采用有效的编码和解码方法。遗传算法反复选择，交叉和突变群体，以产生比其父母更适应环境的新一代群体，直到满足期望的要求。
遗传算法的步骤包括：遗传编码，群体选择，适应度函数，选择动作，交叉操作和矩阵解码。提出的新遗传算法通过选择具有较大适应度值的个体来最小化所有AGV的总路径距离，并通过三交换启发式交叉算子方法最小化每个AGV路径距离。
遗传编码
符号0表示启动工作站（点）; 符号1，2，…，N表示需要AGV传送的N个工作站。我们添加M – 1个虚拟符号，表示M -1虚拟站点，标记为N + 1，…，N + M – 1。它们具有与起始站点相同的坐标，这意味着每次出现虚拟符号时，相应的AGV返回到起点。假设基因代表AGV行进的路径; 一条染色体包含所有基因，即所有AGV所有途径。为了避免频繁的子路径，我们假设从起始点0到起始点0的路径距离是无穷大的。
例如：有10个工作站，代码为0-9,5个AGV完成任务，随机染色体编码如图2所示。
五个AGV的路径如下：
0 – -6 – -2 – -0
0 – -7 – -0
0 – -1 – -8 – -0
0 -3 -3 -4 -4
0 – -5 – -9 – -0
在迭代过程中，可能出现两种死解决方案如下面的图Figs33和AND44。
-
虚拟符号位于染色体的一端五个AGV的路径如下：0 – -0 – -00 -2 -2 -6 -7 -70 – -1 – -8 – -00 -3 -3 -4 -40 – -5 – -9 – -00 – -0 – -0路径意味着距离是无穷大的，不能满足距离最小化约束，所以这个染色体将被消除。
-
虚拟符号在染色体中连续出现五个AGV的路径如下：0 – -6 – -2 – -00 – -7 – -8 – -1 – -00 – -0 – -00 -3 -3 -4 -40 – -5 – -9 – -0显然，该染色体上存在0-0-0-0路径，不能满足距离最小化约束，因此该染色体也将被消除。
人口选择
适当的人口规模对于遗传算法的收敛很重要。如果种群数量太小，则遗传算法很容易收敛到局部最优解; 相反，如果人口规模过大，遗传算法的计算速度就会降低。人口的大小与变量N有关，适当的群体规模应控制在4 N和6 N之间 [ 49 ]。
健身功能
在本文中，我们使用[ 50 ] 的指数适应度函数。这种转换方法的思想来自SA（模拟退火）过程[ 50]。由于幂等级变换的优点，参考[ 51 ]，我们选择具有指数变换的适应度函数为：
其中Z（= Z 1 + Z 2 + … + Z k）是父母之一; α和β是算术常数; α决定了复制的强制，值越小，具有最大适应度的个体的复制强度就越大。
选择操作
选择操作用于确定重组或交叉亲本个体以及由候选群体产生的后代个体的数量。如何选择一个运算符将直接影响遗传算法的结果。不合适的运算符将导致进化停止或使算法失去多样性，并产生过早的问题[ 52 ]。
在本文中，我们使用轮盘选择[ 53 ]选择父母个体，个体i的概率等于其适合度值和个体人群适应度的总和[ 54 ]，如下所示，
其中f i是个体i的适应度值。Q是所选择的染色体或种群数量。
交叉操作
传统上，交叉是指两条染色体以某种方式彼此交换一些基因以形成一个新个体的过程。交叉运营后，新一代产生，继承了父亲的基本特征。
三交换启发式交叉算子方法的思想是产生一个与三个父母个体的后代。与传统方法相比，提出的方法增加了后代染色体的产生信息。增加的母体染色体提高了继承父母优异特征的可能性，加快了算法的搜索速度。三重启发式交叉算子方法的解释如图5所示。
以10台工作站和5台AGV为例，详细介绍了三路启发式交叉算子方法的过程。十个工作站之间的距离如表1所示。
随机选择三个人作为三联启发式交叉算子：
A = 6 2 12 7 11 1 8 10 3 4 13 5 9
B = 3 2 12 7 9 11 1 4 13 5 10 6 8
C = 5 3 10 8 7 11 2 6 12 1 4 13 9
路线A的总距离为81，单个AGV路径的最大距离为27;
路线B的总距离为78，单个AGV路径的最大距离为24;
路线C的总距离为71，单个AGV路径的最大距离为22。
以染色体A为参照，点6为染色体A的第一位。从右到左循环移动染色体B和C中的基因，当第6点处于第一位置时停止，然后选择6作为后代S的第一个点，结果是
A = 6 2 12 7 11 1 8 10 3 4 13 5 9
B = 6 8 3 2 12 7 9 11 1 4 13 5 10
C = 6 12 1 4 13 9 5 3 10 8 7 11 2
S = 6 * * * * * * * * * * * * *
从表1可以看出，点6附近的距离如下，
所以我们得到
为了满足最小化单个AGV路径距离的约束，我们选择点2作为第二点，结果是
A = 6 2 12 7 11 1 8 10 3 4 13 5 9
B = 6 2 12 7 9 11 1 4 13 5 10 8 3
C = 6 2 12 1 4 13 9 5 3 10 8 7 11
同样，我们可以依次确定交叉后代S的其他基因。使用单个AGV路径距离最小化约束，第一个交叉步骤的交叉子代S是
S = 6 2 12 7 9 11 1 4 13 5 10 8 3
上述获得的后代染色体表明，所有AGV的总路径距离为65，单个AGV的最大路径距离为17.显然，所有AGV的总路径距离和获得的S的最大单个AGV路径距离较小比原来的甲，乙，和ç。
突变操作
突变是在同一染色体内交换基因，导致一个新的个体。突变可以确定遗传算法的局部搜索能力，保持群体的多样性，防止遗传算法的过早收敛[ 55 ]。
本文采用交换突变方法[ 56 ]。我们的想法是选择序数一，b，c ^（一 < b < Ç），然后插入中间路径一个和b（包括一个 b）之后Ç（ç是指与它相关的路径）。例如，如果序列号a = 2，b = 5和c = 10是随机生成的，则相应的单独变换如下：
A = 6 2 12 7 11 1 8 10 3 4 13 5 9
突变后：
A = 6 1 8 10 3 4 2 12 7 11 13 5 9
矩阵解码
设立10个工作站和5个AGV的生产场景。随机染色体如图6所示。
五个AGV的路径是：
0 – -6 – -2 – -0
0 – -7 – -0
0 – -1 – -8 – -0
0 -3 -3 -4 -4
0 – -5 – -9 – -0
根据表1建立10×10工作站矩阵D：
具体的解码步骤描述如下：
（1）获取AGV的可达矩阵
AGV1的行进路径为0 – -6 – -2 – -0，将路径与矩阵D进行比较，值1表示通过车站的AGV1，否则用值0表示。因此可以获得AGV1的可到达矩阵X 1：
类似地，我们可以得到其他AGV可达到的矩阵X 2，X 3，X 4，X 5。
（2）获取AGV的路径距离矩阵
将矩阵X k（k = 1,2，…，5）乘以D获得每个AGV 的路径距离矩阵D k（k = 1,2，…，5）。
例如，AGV1的路径距离矩阵为
（3）计算AGV的路径距离
AGV1的路径距离为
同样，
并且所有AGV的总路径距离为
模拟
在仿真中，我们建立了5个AGV和50个工作站的生产场景，满足第2节所列的要求和双路限制。设置群体大小为200，应用所提出的新遗传算法进行路径优化。
两个遗传算法的仿真结果示于图绘制Figs77 – 10。
图Figs77和AND88表明，在3000次迭代，总的路径距离是72为新的遗传算法，并且是用于传统的遗传算法86。
图9显示，在60次迭代中，传统遗传算法的单个AGV的最大距离为34，对于新遗传算法为32。
图10显示了使用条形图的两种算法之间的距离比较。
从仿真中我们可以得到：
（1）改进的遗传算法具有比传统遗传算法更短的总路径距离。
（2）改进遗传算法的收敛速度快于传统遗传算法。
结论
我们将多AGV路径规划问题重写为遗传算法框架，以研究多AGV路径优化的改进遗传算法。在改进的遗传算法中，通过使用具有比传统的双交换交叉启发式算子更多的信息的三交换交叉启发式算子，我们得到更优化的后代。通过施加最小化所有AGV的总路径距离并最小化每个AGV路径距离的双路限制，我们在AGV传送任务中获得最佳的最短总路径距离。仿真结果表明，使用改进的遗传算法可以缩短所有AGV路径距离和最长单个AGV路径距离。
程序下载：
AGV图和地图程序
单个AGV的最大距离程序
暂无评论内容