龙源期刊网httpwwwqika
comc
AGV调度算法研究
作者：朱德龙高毅来源：《科学与财富》2016年第22期
摘要：AGV作为提供辅料运送链的关键设备，在物流自动化系统中具有重要的地位，对提高物流作业效率起到了巨大的作用，因此也逐渐得到了广泛的应用。本文通过对AGV系统的研究了提出了适用于单AGV和多AGV系统的调度算法。
关键词：AGV；AGV调度算法
1AGV系统地图建模
实际应用当中，AGV的工作路径随着不同工厂的环境条件和规划可能各不相同。
图11中AGV轨道模型，图中圆圈内的数字代表该位置的站点号，直有向线代表直线轨道，弯曲的有向线代表半圆轨道，线上的数值代表其长度或者半圆的半径。图11所示显然为一个有向赋权图，记为G（V，E），V为图中所有站点的集合，显然非空，E为任意站点Vi到另一站点Vj的边的集合。
2AGV调度问题研究
21单个AGV路径规划算法
单个AGV的调度问题可以简化为AGV的路径规划问题，即等价为求最短路径问题。
Dijkstra算法是一种用于计算有向图中一个节点到其他所有节点最短路径的典型图形搜索算法。其时间复杂度O（V2E）～O（VlgVE）取决于是否采用最小优先级队列。
实现的具体方法，即当不用队列而用数组实现时为O（V2），用二叉最小堆来实现时为：
O（（VE）lgV），用Fibo
acci堆来实现时为：
O（VlgVE）。采用Fibo
acci堆使算法的运行时间性能相比于O（V2）虽然有一些提高，但是编程时由于其常数较大，多数时候会发现其实际运行速度并没有明显的提高，并没有多大的效率优势。算法具体步骤为：
1）分组初始化，集合S中只有源节点v0，T由除V外的剩余节点组成。根据图的信息初始化各个节点的邻接关系和权值。
f龙源期刊网httpwwwqika
comc
2）从T中选取与v0有邻接关系且权值最小的顶点Tp，把Tp又加入到S中（v0到Tp的最短路径值即为其权值大小，最短路径为v0→Tp）。
3）以Tp为中间节点，考察T中与Tp邻接的节点。如果从源节点v0经过Tp到T中节点的距离比不经过Tp时距离短，则修改T中已比较过的顶点的路径值为经过Tp的路径。
4）判断T是否为空，或者源顶点到目的顶点的最短路径是否已经找到，若没有则
重新返回步骤2再次寻找。否则，推出循环，算法结束。
22多个AGV路径规划算法
协调各个AGV之间能够无碰撞地高效完成其工厂里的作业任务，是多AGV调度系统的主要任务。相向冲突、站点冲突、拐角冲突、赶超冲突是多AGV运行过程中常见的几种基本冲突。多AGV的任务调度问题的典型的有效方法有以下几种：
（1）基于时间窗r