王江华，楼佩煌，钱晓明

(南京航空航天大学机电学院，江苏南京　210016)



基于改进遗传算法的AGVS单双向混合路径规划

王江华，楼佩煌，钱晓明

(南京航空航天大学机电学院，江苏南京210016)

摘要:针对自动导引车系统路径规划问题，首先提出了一种新的路径网络模型，即单双向混合路径网络布局。然后在仔细分析该种路径布局的特征和优势的基础上，使用改进的遗传算法实现其路径网络的规划，并详细描述了算法步骤。最后，通过对两个自动搬运系统进行路径规划、系统建模、系统仿真和对比分析，验证了单双向混合路径网络布局的优越性和可行性。

关键词:自动导引车系统;单双向混合路径网络;单向路径网络;遗传算法

多台自动导引车(Automated Guided Vehicle，AGV)在控制系统的统一指挥下，组成的柔性化的自动搬运系统称为自动导引车系统(Automated Guided Vehicle System，AGVS)。AGVS路径设计问题是AGVS设计首先需要考虑的问题，其布局极大地影响系统的性能。常用的路径布局包括单向路径网络布局、双向路径网络布局、单循环路径布局和基于串联配置的路径布局等［1］，其中基于单向路径网络布局的AGVS由于控制简单可靠得到了普遍应用。单向路径网络的设计问题首先由Gaskins［2］等运用0－1整数规划方法来处理，之后分支定界法［3］、启发式算法［4］、禁忌搜索算法［5］、遗传算法［6］等也被逐渐应用于单向路径网络的规划，然而由于单向路径网络中每条路径只允许AGV单向运行，增加了AGV的绕行距离，降低了系统效率。基于双向路径网络布局的AGVS中每条路径都允许AGV双向行驶，大大减少了AGV的运行距离，因此双向路径网络在冲突和死锁很少发生且AGV数量较少的AGVS中可以发挥其优势。双向路径网络规划的难点在于死锁和冲突的解决，即规划一条从起始点到目标点的无死锁无冲突路径。为了实现该目标，学者们提出了时间窗［7］、petri网［8］等复杂的路径规划算法，同时也验证了此类算法对控制系统和硬件的高要求以及对AGVS规模的限制，因此双向路径网络在实际生产系统中未能广泛应用。为此，本文将双向路径的优势引入单向路径网络中，设计了单双向混合路径网络。

1　单双向混合路径网络的结构和交通管理

1.1路径结构

本文借用文献［9］所运用的路径模型来阐述本文中单双向混合路径网络的结构特点。图1(a)为该案例的无向路径网络，其有6个工作单元，每个工作单元配置一对装/卸站点。节点{ 2，4，9，11，12，14，19，20}表示路径交叉点。本文假设所有的装/卸站点都设置在路径段上，即不存在既表示装/卸站点又表示路径交叉点的节点。在该假设下，将每个度为2的节点所连接的两条路径合并为一条合成路径。合并之后，各路径段的两端节点都将是路径交叉点，如边{ (2，9)，(9，19)，(9，11) }。图1(b)和图1(c)分别表示了图1(a)中无向路径网络所对应的单向路径网络和单双向混合路径网络。经对比可以发现，该例中的单向路径网络和单双向混合路径网络除了各路径段所允许的AGV的运行方向不同之外，其他均相同，这就意味着将已存在的单向路径网络改造成单双向混合路径网络只需要重新设计路径方向，这个通过计算机就可以完成，不需要其他的改造费用。在图1(c)的路径网络中，路径段{ (2，4)，(9，11)，(14，20) }是双向路径，同时所有路径交叉点最多只有一条双向路径与之相连，这就是本文中单双向混合路径网络的最大特点，该特点使系统只需要采用简单的交通管理算法就可以实现系统无死锁运行。

1.2交通管理

单向AGVS中会发生节点冲突和循环死锁，双向AGVS中则还会发生相向冲突。为了避免相向冲突的发生，本文设计了每个路径交叉点最多只有一条双向路径与之相连的单双向路径网络布局，并为每条双向路径的两个路径方向各设置一个标志位，代表路径方向占有权。当一台AGV想要进入某双向路径时，需先询问该路径中与该AGV运行方向相反的标志位的值，若大于0，则表示该路径上至少有一台与该AGV运行方向相反的AGV占用了该路径，此时AGV停车等待，直到与该AGV运行方向相反的标志位的值等于0。当该AGV被允许进入某双向路径时，该双向路径中代表AGV的运行方向的标志位加1;离开该路径时，该路径中代表AGV的运行方向的标志位减1。

图1　某AGVS路径网络布局方案

2　单双向混合导引路径网络的设计方法

2.1问题描述

和单向路径网络规划问题类似，单双向混合路径网络规划问题可以表述为:给定无向路径网络和各工作单元之间的负载流量，确定AGV在路径网络各路径允许的运行方向，使得运行总路程最小。现以图1(a)所示的无向路径网络和表1所示的工作单元之间的负载流量为已知条件，确定AGV在各路径段上允许的运行方向。

表1　工作单元之间的负载流量

本文所涉及到的变量和符号定义如下:

i，j，μ，ω为路径交叉点或装、卸站点标号; m，n为工作单元标号; (i，j)为连接节点i和节点j的路径段，其中i＜j; Nw为工作单元的数量; NB为合成路径的数量; cij为路径段(i，j)的实际长度; dij为路径段(i，j)的更新长度; fmn为工作单元m到工作单元n的负载流量矩阵;为工作单元m到工作单元n的空载流量矩阵; lmn为AGV从工作单元m的装载站点到工作单元n的卸载站点的最短负载行驶距离矩阵;为AGV从工作单元m的卸载站点到工作单元n的装载站点的最短空载行驶距离矩阵; L为目标函数值，即AGV运行总路程;ε为双向导引路径的虚拟长度因子;如果路径段(i，j)允许AGV从节点i运行至节点j，Zij= 1，如果路径段(i，j)不允许AGV从节点i运行至节点j，Zij= 0;如果Zij+ Zji= 2，则Bij= 1，其他情况下Bij= 0。

本文的优化目标是使AGV的运行总路程最短，而AGV的运行总路程包括空载行程和负载行程两部分，即建立的目标函数如下:

约束条件为:

AGVS的运行总时间由负载和空载AGV的行驶时间、空闲AGV的运行时间、装卸物料时间、AGV阻塞时间4个部分组成。本文假设AGV完成当前搬运任务之后将立即获得一个新任务。在该假设下空闲AGV的运行时间将会被忽略。本文的目标是通过减少AGV行驶距离来减少负载和空载AGV的行驶时间，从而减少系统运行总时间，提高系统效率。然而，由于部分路径被设计成双向，AGV阻塞的可能性增加。如果双向路径导致的额外的等待时间比减少的AGV行驶时间长，系统运行总时间将不仅不会降低反而会增加，导致系统效率下降。因此必须考虑双向路径对系统效率的负面影响。双向路径造成的额外的等待时间很难估计，其与双向导引路径的长度和使用次数有关。本文用公式(2)更新双向路径的长度，其增加的路径长度(ε×cij)表示AGV在额外的等待时间内可以行使的路程的估计值，该长度称为双向路径的虚拟长度。其中ε的大小与系统中AGV数量有关，AGV数量越多，双向路径可能产生的阻塞时间越长，ε值越大。

目标函数中的fmn可以从表1查得，同时如果导引路径网络中各路径段的方向已知，lmn和lEmn可以通过最短路径算法获得。约束条件(3)和(4)是对每个装/卸站点的约束，即离开/进入每个装/卸站的AGV和进入/离开该站点的AGV数量相等。由式(3)和(4)以及各工作单元间的最短空载行驶距离矩阵，通过线性规划方法可以求得各工作单元之间的空载流量矩阵。另外式(5)保证了单双向混合路径网络中每个路径交叉点最多只与一条双向路径相连的结构特点。从定义可以看出，只有当路径段(i，j)是双向路径时，Bij值为1。式(6)确保每条双向路径都至少有一条能使AGV进入该路径的单向路径与之相连。式(7)确保每条双向路径都至少有一条能使AGV离开该路径的单向导引路径与之相连。式(8)确保每个路径交叉点都至少有一条能使AGV进入该路径交叉点的路径与之相连。式(9)确保每个路径交叉点都至少有一条能使AGV离开该路径交叉点的路径与之相连。满足约束条件(6)、(7)、(8)、(9)的路径网络有极大的可能性会是一个强联通的路径网络。为了进一步确保路径网络的强联通，可以使用n次Dijkstra算法或可达矩阵。

2.2基于改进遗传算法的单双向路径网络设计方法

遗传算法(genetic algotithm，GA)是一种用于搜索最优解或近似最优解的启发式搜索算法。为了避免过早收敛，本文将遗传算法和邻域搜索算法相结合来设计单双向混合路径网络。

2.2.1个体编码和解码

在遗传算法中，单双向混合路径网络可以用相应的字符串(染色体)来表示，该字符串中的字符(基因)是取值范围为［0，2］的正整数，代表了AGV在对应的路径段上允许的运行方向。因此染色体的长度等于路径段的数量NB。对于路径段(i，j) (i＜j)，如果对应的基因为“0”，则该路径段只允许AGV从节点i运行到节点j，如果是“1”，AGV只能从节点j前往节点i，除此之外如果该基因是“2”，该路径段是双向路径，允许AGV双向行驶，同时意味着该路径段的长度需要用式(2)来更新。以表2中的编码方案编码，图1(c)中的单双向混合路径网络对应的染色体为“1202010011211”。

解码过程是指根据路径网络的染色体获得AGV在各路径段上允许的运行方向，同时用式(6)、(7)、(8)、(9)和可达矩阵判断路径网络是否强连通。

2.2.2初始种群

本文中单双向混合路径网络中单向路径的数目明显多于双向路径，而单向路径的路径方向有两种可能。因此一条路径的编码情况“0”、“1”、“2”的可能性分别设置为“0.4”、“0.4”和“0.2”。随机生成初始种群，初始种群的规模NP= 0.5NB。为了保证个体的多样性，任意两个体之间的海明距离必须大于Hmin。在本文中，Hmin= 0.2NB。另外，个体i和j之间的海明距离定义见式(11)，其中代表个体i的第k位基因值。

表2　案例1的编码方案

2.2.3适应度函数计算

如果一个编码所对应的单双向混合路径网络强联通，则该编码可行，按照式(1)计算该编码目标函数值，并按式(12)计算适应度函数值。其中表示初始种群中所有个体的目标函数的平均值。

2.2.4选择操作

本文采用轮盘赌选择法来实现选择操作。

2.2.5交叉操作

本文采用两点交叉法实现交叉操作，交叉概率PC为1。

2.2.6变异操作

本文随机产生两个变异位置，这两个位置的基因值随机变换为其余两个基因值之一。变异操作由变异概率Pm决定是否进行，本文取Pm= 0.1。变异操作之后对染色体进行解码，如果对应路径网络强联通，计算该个体的适应度函数值。

2.2.7邻域搜索

邻域搜索(Neiborhood Search，NS)算法是一种最广泛使用的局部搜索算法之一，它通过邻域函数转移当前解的状态来完成优化过程。本文中邻域搜索安排在选择、交叉、变异操作之后。具体操作步骤如下。

步骤1:经选择、交叉、变异操作后获得一个可行解，即初始解X0。按照式(1)计算其目标函数值，并将X0设置为当前解。

步骤2:如果Xk是当前解(下标k代表第k个当前解，若当前解为X0，则k = 0)，则随机生成一个新的可行解Xk+1，具体操作为将当前解的某基因值(位置随机生成)随机变换为其余两个基因值之一，若该编码不可行，则重复该操作，直到获得一个可行解或连续重复Ns次仍无法获得可行解为止。如果获得可行解，计算该可行解的目标函数值。比较该邻域解与当前解，ΔL = L(Xk+1)－L(Xk)，若连续重复Ns次仍无法获得可行解，则终止邻域搜索。

步骤3:如果ΔL＜0，接受解Xk+1并以其替代当前解Xk成为新的当前解，且k←k + 1，转至步骤2。如果ΔL＞0，转至步骤4。

步骤4:如果有连续Ns个新个体不被接受，完成搜索。否则转至步骤2。本文中Ns=10。

重复选择、交叉、变异和邻域搜索，直到产生Np个可行的子染色体。将Np个父染色体和Np个子染色体合并，为了保持种群中个体之间的基因型差异，按照式(11)计算该2Np个个体中任意两个体之间的海明距离，如果两个体之间的海明距离小于Hmin，用式(13)更新该两个体中适应度函数值较小的个体的适应度函数值，其中η是惩罚因子(η＜1)，本文中，η= 0.8。本文将2Np个个体按适应度函数值优劣排序，取其中最优的Np个个体进入下一代。

2.2.8终止条件

如果连续Nr代种群中最佳个体相同，终止遗传算法。本文中Nr= 10。

3　计算机实验和仿真研究

为了评估单双向混合路径网络AGVS的性能，对其进行计算机实验和仿真研究，输入数据为无向路径网络和工作单元之间的负载流量。首先，运用改进遗传算法针对ε(ε= 0～1.0)设计单双向混合路径网络，同时将其运行总路程与用管贤平等［10］提出的算法优化的单向路径网络的运行总路程相比较。然后，将计算机实验得到的单双向混合路径网络的AGVS和单向路径网络的AGVS分别进行计算机仿真，仿真软件为生产系统仿真软件eM-Plant。最后，通过比较二者系统吞吐量和系统阻塞时间，验证单双向混合路径网络的AGVS的优越性，并评价双向路径对系统阻塞时间的影响。实验平台如下:台式机AMD速龙64位5000 +双核处理器，主频2.60GHz，2GB内存，Windows 7，32位操作系统，Visual C + +6.0编程环境。

3.1案例1

无向路径网络如图1(a)所示，工作单元之间的负载流量见表1。本案例中共有合成路径段13条。路径网络编码方案见表2。运用本文所提的改进遗传算法设计的单双向混合路径网络与用管贤平等所提的算法优化的单向路径网络见表3，文中设计的单双向混合路径网络所用的平均运行时间为21.67s。

表3　实验结果

本文用生产系统仿真软件eM-Plant对表3中的4种路径布局进行仿真实验，仿真时间为36 000s。AGV速度为1m/s，物料装/卸载时间为10s，系统中AGV的数量为2～14台。系统在每个参数下运行5次，仿真结果取平均值，见表4。从仿真结果可以看出当系统中只有少量AGV时，单双向混合路径网络(ε= 0)的AGVS吞吐量最高。当AGV数量逐渐增加，单双向混合路径网络(ε= 0.1～0.9)的AGVS逐渐表现其优越性。当AGV数量较多时(本例中14台)，单双向混合路径网络(ε= 1.0)的AGVS表现优于前二者。因此可以证明，虚拟长度因子ε的取值需要随着系统中AGV数量的增加而增大。图2显示了单双向混合AGVS相对于单向AGVS系统吞吐量增加的百分比，该图表明在以上仿真参数下，当ε= 0.1～0.9以及AGV数量为6台时单双向混合AGVS相较于单向AGVS系统吞吐量增加幅度最大，可达10.96%。

表4　案例1的系统吞吐量

在单向AGVS中，AGV会因以下原因停车造成系统效率下降:1)前方AGV停在路径上装卸货物时，后方AGV必须停车等待，直到前方车辆装卸完毕。2)前方路径或路径区域容量达到最高时，AGV必须停车等待，直到前方路段或区域有空间可以容纳该AGV。3)前方AGV由于以上原因停车时，其后的AGV也必须停车。因以上原因造成的停车时间归类为类型一。在单双向混合AGVS中，AGV除了类型一的停车外，还有因双向路径造成的额外停车，因双向路径造成的停车时间可归类为类型二。本文通过比较单双向混合AGVS与单向AGVS的停车时间来验证双向路径对系统效率的影响。图3显示了单向AGVS和单双向混合AGVS在系统仿真周期中所有AGV的总停车时间，从该图可以看出AGVS的总阻塞时间随AGV数量的增加而增长，且单双向混合AGVS中AGV阻塞时间增长速度比单向AGVS快。图4表明了单双向混合AGVS中AGV阻塞时间增长较快的主要原因是双向路径导致的阻塞时间随AGV数量增加而增长较快。

图3　AGV总阻塞时间

图4　单双向混合AGVS(ε=0.1～0.9)中两类阻塞时间的情况

3.2案例2

本文选用文献［10］中的自动制造中心来进一步证明单双向混合路径网络布局的优越性，其无向路径网络如图5所示，各加工单元之间的负载流量见表5。

图5　某自动制造中心的无向导引路径网络

本案例路径网络编码方案见表6。运用本文的遗传算法设计的单双向混合路径网络与用管贤平等所提的算法优化的单向路径网络见表7，其中用本文算法为案例2设计的单双向混合路径网络所用的平均运行时间为325.63s。对表7中5个路径网络方案进行仿真研究，物料装/卸载时间为10s，AGV运行速度为1m/s，系统中AGV的数量为2～20台，仿真结果见表8，该表再次证明了单双向混合路径网络相对于单向路径网络的优越性。

表5　案例2中各加工单元之间的负载流量表

表6　案例2的编码方案

表7　案例2的路径网络方案

表8　案例2的仿真结果

4　结束语

本文针对自动导引车系统路径设计问题提出的单双向混合路径网络由单向导引路径和双向导引路径网络组成，具有较高的系统效率，且不会提高系统交通管理的复杂度。然而，单双向混合路径网络设计过程中虚拟长度因子ε的取值对设计结果将会产生较大影响，其取值合适与否具有一定的随机性。如果能将系统仿真直接集成至路径网络设计中，必能更好地反映双向导引路径对系统阻塞时间的影响，从而设计出性能更佳的单双向混合路径网络布局。

参考文献:

［1］Le－Anh T，De Koster M B M.A review of design and control of automated guided vehicle systems［J］.European Journal of Operational Research，2006，171(1) :1－23.

［2］Gaskins R J，Tanchoco J M A.Flow path design for automated guided vehicle systems［J］.International Journal of Production Research，1987，25(5) :667－676.

［3］Goetz Jr W G，Egbelu P J.Guide path design and location of load pick－up/drop－off points for an automated guided vehicle system［J］.International Journal of Production Research，1990，28 (5) :927－941.

［4］Ko K C，Egbelu P J.Unidirectional AGV guidepath network design: a heuristic algorithm［J］.International Journal of Production Research，2003，41(10) :2325－2343.

［5］Seo Y，Lee C，Moon C.Tabu search algorithm for flexible flow path design of unidirectional automated－guided vehicle systems ［J］.OR Spectrum，2007，29(3) :471－487.

［6］肖海宁，楼佩煌，武星，等.基于混合遗传算法的单向路径网络设计方法［J］.计算机集成制造系统，2012，18(5) : 137－143.

［7］Krishnamurthy N N，Batta R，Karwan M H.Developing conflictfree routes for automated guided vehicles［J］.Operations Research，1993，41(6) :1077－1090.

［8］Wu N，Zhou M C.Modeling and deadlock control of automated guided vehicle systems［J］.Mechatronics IEEE/ASME Transactions on，2004，9(1) :50－57.

［9］Seo Y，Moon C，Moon Y，et al.Adapting genetic algorithm and tabu search approaches for unidirectional AGV flowpath design problems［C］/ /IEEE Congress on Evolutionary Computation.HongKong: IEEE，2008:3621－3625.

［10］管贤平，戴先中，李俊.基于变邻域小生境遗传算法的AGV路径网络设计方法［J］.中国机械工程，2009，20(21) :2581－2586.

Configuring mixed uni/bidirectional guide-path network for automated guided vehicle system based on improved genetic algorithm

WANG Jianghua，LOU Peihuang，QIAN Xiaoming
(College of Mechanical and Electrical Engineering，Nanjing University of Aeronautics and Astronautics，Jiangsu Nanjing，210016，China)

Abstract:To deal with the guide-path configuration problem for automated guided vehicle system，it presents a new guide-path model called mixed uni/bidirectional guide-path network，analyzes both structure and advantages of the guide-path network，proposes an improved genetic algorithm to configure the mixed uni/bidirectional guide path network.To verify the superiority and feasibility of mixed uni/bidirectional guide-path network，it illustrates two examples of automated handling system.This method configures the mixed networks，shows their performance and compares them with the corresponding unidirectional AGVS.

Key words:automated guided vehicle system; mixed uni/bidirectional guide-path network; unidirectional guidepath network; genetic algorithm

DOI:10.3969/j.issn.2095－509X.2015.06.006

作者简介:王江华(1989—)，女，江苏丹阳人，南京航空航天大学硕士研究生，主要研究方向为计算机集成及柔性制造。

基金项目:国家自然科学基金资助项目(61105114)

收稿日期:2015－03－20

中图分类号:TP128

文献标志码:A

文章编号:2095－509X(2015) 06－0020－07