物流中心多AGV无碰撞路径规划

杨 洁，田 钊，刘国宁

（1.郑州大学机械与动力工程学院，河南 郑州 450001；2.郑州大学软件学院，河南 郑州 450002）

1 引言

近年来随着企业对仓储物流中心自动化水平的需求的不断提高，AGV已经成为了决定物流中心工作效率的主要运输工具，主要负责物流中心、车间等区域的包裹或物料运输。因此，AGV的运输效率和协调能力也就成为了决定仓储物流自动化水平高低的主要因素之一。

目前，AGV 的路径优化已经成为国内外于仓储物流中的主要研究问题之一，为了规划出无死锁无冲突的路径，学者们采用了不同的算法对AGV进行路径规划［1］。文献［2］将A*算法和D*Lite算法相结合完成了对路径规划问题的解决。 文献［3］采用混合启发式算法对带有时间窗的车辆进行路径规划，使得行驶的路径最短。文献［4］使用改进的A*算法生成候选路径，提出了两种启发式时间窗搜索算法以搜索每条候选路径上的空闲时间窗组合进而完成了对物流中心AGV路径进行规划。文献［5］通过增加AGV共享路径的惩罚值来改进A*算法并完成了对智能仓储中AGV的无碰撞路径规划。文献［6］将传统的人工蜂群算法和粒子群算法思想相结合提出了混合蚁群粒子群的方法，通过此方法完成了对智能仓库中AGV搬运货物的路径优化。文献［7］采用改进的Dijkstra算法和时间窗相结合的方法对碰撞进行分类，并基于碰撞类型实现了自动化仓库系统中多AGV的路径规划。文献［8］通过对A*算法进行改进减少了AGV的运输路径长度，实现了对AGV路径的规划并提高了AGV的运行效率。

目前针对采用遗传算法求解多AGV路径的研究相对较少。本研究专注于对多路径、多节点的复杂场景中的多AGV作业路径进行优化，提出了基于遗传算法和时间推理相结合的多AGV路径规划的两种模型，然后设计实验并将两种模型的实验结果进行了分析和对比。本研究对复杂条件下多AGV路径规划问题的解决具有参考意义。

2 问题描述

2.1 场景描述

这里以典型仓储物流中心分拣库区为应用背景进行研究。整体按照功能布局，分为货架区，运输区以及工作台区。货架区和工作区之间为AGV运输区。如图1所示，货架1区和货架2区分别由2行5列共10个货架组成，中间区域为AGV运输区，右侧工作台区由3个工作台组成。分拣库区的作业过程为AGV将目标货架运送到相应的工作台，随后员工完成拣选、扫码以及装箱等业务。AGV越多，越有利于提高效率，但也大大增加AGV之间的碰撞概率。为了避免碰撞现象的产生，此研究从多AGV路径规划方面着手进行研究；为了给AGV规划路径和计算路径的长度以及完成任务花费的时间，此研究采用拓扑建模法对物流分拣场景进行数学建模并采用邻接矩阵的方法对有向图G(V，E)进行表示。

图1 拓扑建模法构建的地图Fig.1 Topological Model of the Logistics Center

在有向图G(V，E)中，V代表图中的顶点集合，E代表连接相邻两顶点的边的集合，每条边用两个顶点的有序元素对(Vi，Vj)进行表示［9］，并且每条边都有对应的权重W(Vi，Vj)。这里用一个|V|×|V|阶的邻接矩阵A来存储各边的权重并把每条边的长度d(Vi，Vj)作为此边权重W(Vi，Vj)。若节点Vi和Vj之间有边线存在，则这条边的边的实际长度d(Vi，Vj)为这条边的权重W(Vi，Vj)，否则，此边的权重为∞，当用矩阵A进行存储此边时先用一个正数除以0得到一个正无穷大，再通过Double的POSITIVE_INFINITY进行表示，最后进行存储。本研究采用顶点的有序集合来代表路径［10］，顶点的排列顺序代表路径经过各个顶点的顺序，依次找出相邻两个顶点间的边进行连接就可以表示出这条路径。

基于应用场景，这里提出以下规定：

（1）每辆AGV在任意一条边均为双向行驶，每个顶点仅允许一辆AGV占用。

（2）每辆AGV 运行过程中速度保持不变且所有AGV 速度相同。

（3）每辆AGV在顶点处90度拐弯时需要0.5s。

（4）图中单一路径长度均为3m，每辆AGV 的车身长度约为1.2m，顶点为圆形且直径与车长相同。

（5）所有货架的规格均相同且货架长度与AGV长度相同。

（6）物料运输终点的工作台节点不作为AGV通过节点。

（7）此场景未考虑避障问题。

2.2 冲突类型描述

运输过程中AGV之间可能出现的冲突类型有：

2.2.1 节点冲突

类型一：如图2（a）所示，AGV1由西向东行驶，AGV2由南向北行驶，两辆AGV同时到达顶点就会发生冲突，这类冲突为节点冲突的第一种类型。

类型二：如图2（b）所示，AGV1由西向东行驶，AGV2先由南向北行驶到达顶点处拐弯由西向东行驶，两辆AGV同时到达顶点就会发生冲突，这类冲突为节点冲突的第二种类型。

类型三：如图2（c）所示，AGV1先由西向东行驶然后在顶点处拐弯由南向北行驶，AGV2先由南向北行驶到达顶点处拐弯由西向东行驶，两辆AGV同时到达顶点就会发生冲突，这类冲突为节点冲突的第三种类型。

类型四：如图2（d）所示，AGV1先由西向东行驶然后在顶点处拐弯由南向北行驶，AGV2由南向北行驶，两辆AGV同时到达顶点就会发生冲突，这类冲突为节点冲突的第四种类型。

图2 节点冲突Fig.2 Node Conflict

2.2.2 线路冲突

AGV1 由西向东行驶，AGV2 由东向西行驶，两辆AGV 相向行驶就会发生冲突，这种冲突为线路冲突，如图3所示。

图3 线路冲突Fig.3 Line Conflict

2.3 路径规划模型一

2.3.1 模型一符号说明

以图1为例进行研究，研究中要计算每辆AGV 行驶的路径长度、到达路径中每个顶点的时间，以及从每个顶点出发的时间。下述以kn为例给出相应的计算方法，其中，kn表示序号为n的AGV。

（1）kn从起点Ps到终点Gs路径Jn=(Vs1，Vs2，Vs3，…，Vsm)的总长度［8］Ln：

（2）kn在行驶过程中到达第L个顶点附近的时间TnL：

（3）kn开始进入第L个顶点的时间：

（4）kn在行驶过程中从第L个顶点出发的时间TnLf：

式中：Tn(L-1)f—kn在第(L- 1 )个顶点处出发的时间；v—kn的速度；l—圆形节点的直径；tnL—kn在第L个顶点附近等待的时间；ts—kn的出发时间，即给kn发放任务的时间；tc—在第L个顶点的转弯时间。

假设K{k1，k2，…，kn} 为所有AGV 的集合，R{r1，r2，r3…，rt}为所有任务的集合，P{p1，p2，p3，…，pt} 为所有任务起点的集合，G{g1，g2，g3，…，gt} 为所有任务终点的集合，这里则用r s={s，ts，ps，gs，kn} 表示用kn去完成出发时间为ts，起点为ps终点为gs的任务，其中，s∈{1 ，2，3，…，t}ps∈Pgs∈Gkn∈K，kn从起点ps到终点gs的行驶路径表示为Jn=(Vs1，Vs2，Vs3，…，Vsm)；到达路径中各个顶点附近的时间为Mn =(Tn1，Tn2，Tn3，…，Tnm)；开始进入各个顶点的时间为从各个节点出发的时间Mnf=(Tn1f，Tn2f，Tn3f，…，Tnmf)；kn与ki在行驶过程中经过相同点的序列为Dni=(VP1，VP2，VP3，…，VPe)。

2.3.2 第一类模型建立

本模型中含t个任务，n辆AGV，且t≤n，所有AGV的出发点均为它们携带的任务的起点。

（1）车辆的优先级规则

在取货区AGV无优先级排序；在运输区AGV的优先级由kn的序号决定，序号n越小优先级越高。当优先级高的AGV和优先级低的AGV预计同一时刻到达某一顶点，优先级高的AGV可以直接通行，优先级低的AGV必须在此顶点附近进行等待。

（2）冲突判断方法

①节点冲突判断方法

如果第i和b个AGV，即ki与kb，都经过顶点VPm且i＜b，顶点VPm为ki的路径中第r个顶点，为kb的路径中第w个顶点。

当满足式（6）或式（8）时会发生类型一的节点冲突；当满足式（7）或式（8）时会发生类型二的节点冲突；当满足式（7）或式（9）时会发生类型三的节点冲突；当满足式（6）或式（9）时会发生类型一的节点冲突。

当节点冲突为类型一或者类型二时，kb需等待k i的车尾完全驶离顶点后才可以通行，则在第w个顶点附近等待的时间t如式（10）所示。

当节点冲突为类型三或者类型四时，kb需等到k i准备从节点出发然后和k i同时开始运行，则在第w个顶点附近等待的时间t，如式（11）所示。

②线路冲突判断方法

由下述分发任务的方法可知，k i领取的任务为任务i，kb领取的任务为任务b，且i＜b。k i路径中第r个顶点为Vir，第(r+ 1 )个顶点为Vi(r+1)；kb路径中第w个顶点为Vbw，第(w+ 1 )个顶点为Vb(w+1)，则：

若式（12）、式（13）和式（14）同时满足则k i与kb会发生相向冲突。

（3）派车方法

首先从K{k1，k2，…，kn} 中按照车辆优先级由高到低选取m辆AGV 并按照任务顺序为他们各自发放一个任务r s={s，ts，ps，gs，ks} ，然后采用路径规划方法为所有AGV规划路径，最后为所有AGV发送指令，让所有AGV同时开始执行任务。

（4）路径规划方法

第一步：当kn接收到发放任务r n={n，tn，pn，gn，kn} 后运用遗传算法为其生成一条尽可能最优路径Jn=(Vn1，Vn2，Vn3，…，Vnm)，然后计算出kn在行驶过程中到达路径中各个顶点附近的时间Mn=(Tn1，Tn2，Tn3，…，Tnm)、开始进入各个顶点的时间以及从各顶点出发的时间Mnf=(Tn1f，Tn2f，Tn3f，…，Tnmf)。

第二步：按照优先级高低顺序依次找出所有比kn优先级高AGV并存储与集合K1。

第三步：第一类模型路径规划流程，如图4所示。

图4 第一类模型路径规划流程图Fig.4 AGV Routing Method for Model I

第四步：重复上述步骤二、三、四、五为所有AGV生成路径并计算这些AGV达到各个顶点的时间和开始进入各个顶点的时间以及从各个顶点出发的时间。

第五步：总体判断各个AGV是否仍然存在冲突，如果存在，解决冲突，直至没有任何冲突。

2.4 路径规划模型二

2.4.1 模型二符号说明

以图1为例，研究中要计算每辆AGV行驶的路径长度、到达路径中每个顶点的时间，以及从每个顶点出发的时间。下述以kn为例给出相应的计算方法，其中，kn表示序号为n的AGV。时间计算方法如下所示：

（1）kn从起点Ps到终点Gs路径的总长度计算公式，如式（1）所示。kn在行驶过程中到达第L个顶点附近的时间计算公式，如式（2）所示。

（2）kn进入第L个顶点的时间：

（3）kn在行驶过程中到达第L个顶点的时间：

（4）kn在行驶过程中从第L个顶点出发的时间：

此处符号与模型一中的符号除tnL意义不同外均相同，式（18）中：tnL为kn在第L个顶点上等待的时间。

此模型中的假设与模型一中的假设基本相同，不同之处在于此模型中假设添加了

2.4.2 第二类模型建立

本模型中含t个任务，n辆AGV，t≤n，所有AGV的出发点均为它们携带的任务的起点。

（1）车辆的优先级规则：

在取货区AGV无优先级排序；在运输区AGV的优先级由kn的序号决定，序号n越小优先级越高。当优先级高的AGV和优先级低的AGV预计同时到达某一顶点，优先级高的AGV可以直接通行，优先级低的AGV必须在前一点进行等待直到优先级高的AGV准备从冲突节点出发时也从前一顶点准备出发。

（2）冲突判断方法

①节点冲突判断方法

此处节点冲突的判断方法与模型一中的节点冲突判断方法相同。只是此模型中无论发生什么类型的节点冲突，kb的等待时间t的计算方法均相同，为：

②线路冲突判断方法

线路冲突判断方法与模型一中线路冲突判断方法相同。

（3）派车方法：

派车方法与模型一的派车方法相同。

（4）路径规划方法：

除去步骤一和步骤三外，其他步骤与模型一中对应步骤相同。

第一步：当kn接收到的发放的任务r n={n，tn，pn，gn，kn} 后这里运用遗传的算法为其生成一条尽可能最优的路径Jn=(Vn1，Vn2，Vn3，…，Vnm)，然后计算出kn在行驶过程中开始进入各个顶点的时间到达各个顶点的时间以及从各顶点出发的时间

第三步：第二类模型路径规划流程。此路径规划流程与第一类模型中路径规划流程不同之处在于对节点冲突的解决方法不同。第二类模型中的路径规划流程中如果存在节点冲突，kn在发生节点冲突顶点的前一顶点处等待t秒，与此同时，将Marr和Min发生节点冲突的顶点及其后所有顶点对应的时间均增Mnf加t秒，将中kb进行等待时所在顶点及其后所有顶点对应的时间也依次增加t秒。

3 基于遗传算法的路径求解

3.1 编码

采用二进制编码和排列编码相结合的方法进行编码，编码后每条染色体代表一条路径。对于一个给定的图形，染色体的总长度为图上顶点的总数目的2倍，假设图中顶点的总数目为n，染色体总长度即为2n。染色体上的第1位到第n位上的基因用二进制编码且第1位和第n位的基因值均为1，其他基因位上的基因值为0或为1由计算机随机产生一个0到1之间的一个小数然后进行四舍五入后决定；染色体上第(n+ 1 )位到第( 2n)位上的基因值为图上各顶点的序号。第(n+ 1 )位放置需要求解的路径的起始顶点的序号，第( 2n)位上放置结束顶点的序号，然后将除去顶点和终点的其他顶点随机排列组合并依次放置在染色体上第(n+ 2 )位到第( 2n- 1 )位上，其中染色体上第(n+ 1 )位到第( 2n)位的顶点序号不可重复。一条长度为10，出发点为顶点3，结束点为顶点5的染色体编码示意图，如图5所示。

图5 染色体编码示意图Fig.5 Coding Method for AGV Routing Path

3.2 解码

当产生一条染色体后，依次找出这条染色体上第1位到第n位的基因序列中基因值为1的基因所处的基因位的序号I，并将染色体上第(I+n)位上的基因值按顺序取出放置于集合D，D中基因值为路径中经过的顶点［9］，D中的排列顺序则为这个AGV在行驶过程中经过顶点的先后顺序。一条长度为10，出发点为顶点3，然后经过顶点4到达结束点顶点5的染色体解码示意图，如图6所示。

图6 染色体解码示意图Fig.6 Decoding Method for AGV Routing Path

3.3 适应度函数

对于给定的图形，先用邻接矩阵表示出各个顶点之间的连接关系及每条边的权重。因为这里要求解最短路径且根据下文可知这里应用的是轮盘赌进行选择，所以综合考虑，用（1∕路径总长度）作为适应度，适应度函数为：

3.4 选择

采用的选择方法为轮盘赌选择法，运用这种选择方法完成对父代P1的选择，直接选取前代种群中适应度值最好的个体作为母代P2。

3.5 交叉

采用单点交叉的方法进行交叉。首先产生一个（0～1）之间的随机数与交叉概率进行比较，当交叉概率大于随机数且满足个体不是精英时进行交叉。交叉步骤：首先在染色体的第1位到第n位基因组中随机选择一个位置。然后将父代染色体此位置之前的基因（包括此位置的基因）和母类染色体的此位置之后的基因进行组合产生子代染色体。当交叉后的染色体的适应度大于P2适应度，保留交叉后的个体在种群中，否则保留原染色体。两条长度为10的染色体交叉示意图，如图7所示。

图7 染色体交叉示意图Fig.7 Chromosome Crossing Diagram

3.6 变异

随机产生一个0到1之间的数，当随机数大于变异概率且满足个体不是精英时进行变异。变异步骤：（1）在染色体的第2位到第(n- 1 )位采用位翻转变异方法进行变异，根据染色体位的初始值，将它的第2位到第(n- 1 )位中的某几位从1反转为0或从0翻转为1；（2）在染色体的第( 2 +n)位到第( 2n- 1 )位置中随机选择两个不同的位置s位和d位并将这两个位置的基因交换，与此同时，将染色体的第(s-n)位和第(d-n)位两个位置上的基因也交换；重复数次步骤2。当变异后的染色体的适应度大于变异种群中适应度最好的个体的适应度，保留变异后的个体在种群中，否则保留原个体。长度为10的染色体的变异示意图，如图8所示。

图8 染色体变异示意图Fig.8 Schematic Diagram of Chromosome Variation

4 案例分析

4.1 实验环境

在Myeslipe平台上采用Java语言进行编程完成实验仿真并得出实验结果；在MATLAB平台上实现对实验结果中的路径展示。

4.2 实验前提

实验前提：（1）每辆AGV的速度均为36m∕min；（2）这里采用了4辆AGV进行实验验证；（3）为所有AGV发送指令的时间设置为第0s。（4）这里默认在两种模型求解的路径均为最短且路径相同的情况下，完成任务花费总时间越短模型越优。

4.3 实验设置

（1）首先随机为4辆AGV分别生成4个任务请求：

任务1：r1={1 ，0，p4，30，k1} ；

任务2：r2={2 ，0，p11，50，k2} ；

任务3：r3={3 ，0，p19，10，k3} ；

任务4：r4={4 ，0，p1，30，k4} ；

（2）运用遗传算法为4辆AGV生成路径，其中遗传算法中交叉概率Pc= 0.99，变异概率Pm= 0.0005，精英数elitismCount= 2，种群数N= 1000，终止代数generations= 300。

（3）实验方法：分别采用模型一和模型二为所有AGV规划路径并分析实验结果。

4.4 实验结果

实验结果，如表1～表3、图9～图11所示。

图9 第一组多AGV路径规划图Fig.9 The First Set of multi-AGV Path Planning Diagram

图11 第三组多AGV路径规划图Fig.11 The Third Set of Multi-AGV Path Planning Diagram

表1 多AGV路径中转弯顶点及转弯花费时间汇总Tab.1 Simulation Results for Time on AGV Turning at Turning Points along the Path

表3 采用模型二的多AGV路径规划结果Tab.3 Multi-AGV Path Planning Results Using Model 2

表1统计了多AGV在行驶过程中进行转弯的顶点及转弯花费的时间。

表2 统计了采用模型一完成任务时所有AGV 的行驶路径、AGV 在行驶中到达各个节点附近的时间、进入各个节点的时间和从各个节点出发的时间以及完成所有任务所花费的总时间

表2 采用模型一的多AGV路径规划结果Tab.2 Multi-AGV Path Planning Results for Model One

表3 统计了采用模型二完成任务时所有AGV 的行驶路径、AGV在行驶过程中到达每个顶点的时间和从各顶点出发的时间以及完成所有任务所花费的总时间。

由图9和表2以及图9表1和表3中的第一组实验结果可以清晰地看出采用两种模型进行求解时4辆AGV之间均没有发生冲突，因此使用两种模型的实验结果相同，花费总时间均为252.5s。由图10和表2中第二组实验结果可以看出采用模型一时k3和k2为了避免在顶点28发生冲突，k3在顶点28附近等待了3.5s直至k2的车尾驶离顶点才开始进入顶点，避免了和k2的碰撞，花费总时间为255.5s；由图10和表1、表3中的第二组实验结果可以看出采用模型二时k3为了避免和k2在顶点28发生碰撞，在顶点28的前一顶点33等待了4.5s直至k2开始从顶点28出发才开始从顶点33出发，顺利地避免了冲突，花费总时间为256.5s。通过比较可以知晓采用模型一完成任务比采用模型二完成任务花费时间少1s。

图10 第二组实验多AGV路径规划图Fig.10 The Second Set of Multi-AGV Path Planning Diagram

将图11和表2中的第三组实验结果可以看出采用模型一时k2在顶点26附近等待了3s直到k1开始从顶点26出发才开始驶进顶点；k3在顶点27附近等待了4.5s直至k1的车尾驶出顶点才开始驶进顶点；同理，k4在顶点17附近等待了3s直至k3的车尾驶出顶点才开始驶进顶点。采用模型一完成任务花费总时间为263.5s；将图11、表1 和表3 中的第三组实验结果可以看出采用模型二时k2在顶点26的前一顶点25等待了6s直到k1开始从顶点26 出发时才开始从顶点25 出发；k3在顶点32 等待了5.5s 直到k1开始从顶点27出发时才开始从顶点32出发；k4为了避免和k3在节点17 发生冲突，在顶点16 等了5s 直到k3开始从顶点17出发才开始从顶点16 出发。采用模型二花费总时间为269.5s。通过比较可以知晓采用模型一完成任务比采用模型二完成任务花费时间少3s。由实验结果可知采用模型一和模型二均可以有效避免AGV之间碰撞使所有AGV可以顺利地完成任务，在没有冲突时，采用模型一和模型二花费时间相同。但存在冲突且规划路径相同时，使用模型一比使用模型二可能花费时间更短，因此综合考虑采用模型一规划路径更合理。

5 总结

这里针对物流中心多AGV的路径规划问题，采用拓扑建模法对仓储物流中心分拣库区进行建模，并针对提出的两种路径规划模型，利用基因遗传算法，对多AGV的运行路径，所需时间，等待时间，冲突节点和等待节点等进行了实验仿真。研究结果表明，对两种模型而言，利用这里提出的编码方法和算法，均可实现多AGV的无碰撞路径规划，但在规划路径相同且存在冲突的情况下采用模型一完成任务花费时间更短。另外，这里研究方法也适用于物流中心多批次多AGV的派车、路径规划和路径优化，对提升仓储物流分拣区的效率具有意义。