Dijkstra算法在AGV调度系统中的应用

张 伟，张秋菊

(1. 江南大学机械工程学院，江苏 无锡 214122)

(2.江苏省食品先进制造装备技术重点实验室，江苏 无锡 214122)

Dijkstra算法在AGV调度系统中的应用

张 伟1,2，张秋菊1,2

(1. 江南大学机械工程学院，江苏 无锡 214122)

(2.江苏省食品先进制造装备技术重点实验室，江苏 无锡 214122)

目前仓储物流配货中，订单的周期短、批量少、批次多，传统的仓储物流模式已很难适应新的需求。随着自动化仓储物流的不断发展，基于AGV的仓储物流配货技术得到推广与使用。首先基于仓储物流形式，建立了一个有效仓储空间模型并制订了适于AGV的运行路网，然后根据配单任务需求，给出了AGV运行总距离最短的数学模型，对单任务调用AGV及多任务调用AGV进行分析，运用Dijkstra算法解决了仓储配货系统中AGV与任务的匹配问题。

任务；匹配；自动导引运输车/无人搬运车；Dijkstra算法

目前自动导引运输车/无人搬运车(Automated Guided Vehicle,AGV)在各种应用环境中发挥了越来越重要的作用，也逐渐显示出它的优越性，由于AGV具有可靠性好、对接方便等优点，又能实现生产和搬运功能，所以它在各行各业中得到广泛的应用。本文针对目前应用最广泛的单向固定导轨的潜伏式AGV运用于仓储物流配货系统中进行研究，仓储物流配货系统中AGV的主要作用是衔接配货车在整个配货阶段的自动运输。

仓储物流系统中AGV的调度问题，主要是任务与AGV的匹配问题以及无冲突的路径规划问题，目前大多数研究主要集中在路径规划问题上[1-6]，而对任务与AGV匹配问题的研究比较少。王文蕊等[7]研究了在规定的时间窗内满足约束条件的前提下，调整任务的执行顺序来实现与AGV的匹配。李军等[8]提出了通过将多任务相组合由同一辆AGV运输的组合运输策略，并为求解问题提出了3阶段求解算法的设计，即：1)任务分组；2)组内线路安排；3)组间线路连接。金芳、方凯等[9]研究了基于排队论方法解决自动化立体仓库中AGV的调度问题。

上述任务与AGV匹配问题的研究是通过将任务和AGV执行方法进行处理，包括任务组合、任务等待、AGV区域化、AGV绑定多任务等方法。由于上述处理方法会导致任务的累积，一些任务等待时间较长。在仓储物流配货系统中，每个配货车绑定的订单中有多个任务，需要系统及时对订单中的任务进行处理和释放。因此，本文对仓储物流配货系统中的任务与AGV匹配的有效性进行研究，在基于对仓储区域进行有效划分的前提下，以总路程最短为原则建立数学模型，利用Dijkstra算法进行求解，得到任务与AGV匹配的解，并结合实例进行验证。

1 仓储区域的有效划分

仓储区域整体结构包括存储区、缓冲区、搬运区等。主要考虑的是配货车的停放位置与搬运目标、AGV行走路径与方向等。

仓储区域整体结构中，存储区用于存放货物，其规模由货物子类、货物量确定；缓冲区用于人工配货，其规模大小由货物的出货量和进货量确定；搬运区主要作用是通过AGV托运配货车到指定的目标点，搬运区中包括货车的待配区与已配区、AGV运行路径区、充电区、停靠区等。

设某仓储区域中的搬运区的数目为M，AGV数量为Q。规定搬运区中的任务点编号为Mi(i=0,1,2,3,…)，AGV运行的地标点编号为Qj(j=1,2,3,…)。确定完成搬运区域中的任务点与AGV运行的地标点后，需要考虑区域中无AGV和AGV过载的情况，相对应的解决策略是通过调用邻近区域中的空闲AGV或释放当前区域中的AGV。

2 AGV在仓储物流配货系统中调度问题的描述与建模

仓储物流系统中AGV调度策略是，当任务到达时由调度系统寻找与其匹配的AGV执行任务。调度策略不仅要考虑当前AGV所在地标点到任务点的路径最短，也要考虑到系统中的总路径最短。针对上述调度策略，本文采用了单任务与AGV和多任务与AGV匹配的方法进行分析，通过分析单任务与AGV的匹配方法后，按照同样的分析原理，对多任务与AGV的匹配进行分析。建立数学模型前假设以下条件成立：

1)同一时间段任务的优先级相同。

2)每台AGV运行时的速度相同且不考虑启动和制动的过程。

3)AGV运行时不发生碰撞和死锁情况。

在上述约束条件成立的前提下，建立数学模型如下：

(1)

(2)

(3)

模型(1)表示单任务调度AGV到任务点的最小总路径(mind)，其中D表示AGV在完成某单一任务时所行走的最小路径值，x表示所调度的小车数，n表示总车数。模型(2)表示区域中多任务调度AGV小车到所有调度任务点的最小总路径，其中y表示区域中调度任务点数，N表示总任务点数。模型(3)表示所有搬运区域中的多任务调度AGV小车到所有调度任务点的最小总路径之和，其中h表示搬运区域数，H表示搬运区域总数。

3 任务与AGV的匹配问题求解

模型建立完成后，求解任务与AGV的匹配问题时需要将路径网以结构图的形式进行保存。在结构图中，任意两个区域之间都可能存在相应的关系，比线性表和树表要复杂。由于不存在前后顺序即相对应的关系是独立的，因而不能采用简单的数组来存储图。另一方面，如果采用链表，由于图中各区域的任务数不尽相同，可能差别很大，如果按最大的区域任务数来设计链表的指针域，则会浪费很多存储单元；反之，如果按照各个区域的任务数来设计不同的链表结点，则会使程序更加复杂且给操作带来更大的困难。

本文选用邻接矩阵存储路径网结构图。采用邻接矩阵存储，很容易判断图中区域中的任务与所调用的AGV是否相连，也容易求出各个区域的任务数。但是任何事物都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须遍历二维数组中的所有元素，时间复杂度为O(n2)，这对于区域很多而边较少的图(稀疏图)是不合算的。由于本文中的区域和路径相对比较多，所以并不受到上述问题的影响。

3.1任务与AGV的匹配问题

匹配问题换而言之即是任务点与AGV之间路径最短问题，所以将求最匹配问题转化为求最短路径。最短路径是实际应用中非常有用的方法，常见的2种最短路径是：1)从某源点到其余各顶点之间的最短路径。2)每一段顶点之间的最短路径。

本文研究中所指的最短路径为第1种，即从某一任务区域到各个AGV之间的最短路径。

3.2Dijkstra算法求最短路径

本文采用Dijkstra算法求解区域中任务点到各AGV的最短距离，通过总距离最短原则得到各相匹配的AGV,并将此AGV的编号反馈给调度系统。

Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点间的最短路径。算法建立一个顶点集合S，初始时该集合只有V0(任务点)，然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。

Dijkstra算法寻求区域中任务点到AGV的最短路径的基本过程如下：

设cost[i,j]=0 (cost[i,j]为邻接矩阵用于存储各条边的路径值)，S为已经求得最短路径的顶点集合，Vi表示AGV当前所在的位置点(i=1,2,…,n)。distance[i]用于存储当前状态下任务点V0到各AGV的最短路径。算法过程如下：

1)初始化，区域中任务工位点V0已在最短路径的顶点集合S中。

S={V0},distance[i]=cost[0,i]

2)选择各AGV当前所在的位置点Vj，满足：

distance[j]=min{distance[i]|Vi∈V-S}

3)把AGV当前所在的位置点Vj加入集合S中。

4)修改distance数组元素，修改方法为对于所有不在集合S中的顶点Vi,if(distance[j]+cost[i,j]

5)重复操作2)、3)、4)，直到全部的点加入到集合S中。

6)通过总距离最短原则得到相匹配的AGV，算法结束。算法的流程图如图1所示。

4 单任务与多任务调度模型的分析与验证

假设仓储区域中的AGV数量为Q(用实心圆形表示)、搬运区域中的任务数为H(用实心矩形表示)。当前搬运区域中的任务点为V01，搬运区域中的AGV所在的目标位置点为Vi。

4.1单任务调用AGV

分析单任务调用AGV的情况，选取H=1、Q=5，路段信息如图2(a)中的有向图所示，得到相应的邻接矩阵如图2(b)所示(当任务与AGV之间和AGV与AGV之间若不存在路径时取当前路径值为∞。)

由Dijkstra算法将区域中的任务点与各AGV的最短路径求出后得到距离最短的AGV，最后由调度系统将AGV与任务进行匹配，输出结果见表1。

输出结果为：任务区域V01选定的AGV编号为2，2号AGV距离任务区域V01的距离为300m。

4.2多任务调用AGV

由单任务调度模型的分析与验证可以得出多任务的调度模型。对多任务与AGV的情况进行分析，选取区域中任务点H=3，AGV数量Q=6，路段信息与对应有向图的邻接矩阵如图3所示。

同样由Dijkstra算法将区域中的多任务点与各AGV的最短路径进行分析比较，得到匹配结果，输出结果见表2。

输出结果为：任务区域V01选定的AGV编号为3，3号AGV距离任务区域V01的距离为300m。任务区域V02选定的AGV编号为4，4号AGV距离任务区域V02的距离为350m。任务区域V03选定的AGV编号为6，6号AGV距离任务区域V03的距离为300m。

结果表明,单任务、多任务匹配AGV时，Dijk-stra算法能够快速准确地搜索到与任务点最匹配的AGV完成任务，当不断有新的配货任务发出请求时，Dijkstra算法能够找到与任务相匹配的AGV，使得AGV运行的总路程最短，满足数学模型(2)。

验证结果说明，任务和AGV的匹配不是简单的求取两者之间的最短距离，而是在已知的最短距离中找到满足总路程最短要求的路径，从而得出相应的匹配关系。当多任务与同一AGV的距离相等且都为最短距离时，由Dijkstra算法先对其中一个任务点选取最近AGV，然后对另外的任务点依次选取距离次短的AGV，最终使得总距离最短。可见区域中任务数为H、AGV数为Q时，算法能够满足数学模型(3)要求。当系统中有多区域任务请求时，该算法同样满足数学模型(3)，使得总路程最短。

5 结束语

本文分析了仓储物流配货系统中AGV的调度机制，在基于仓储区域的有效划分和建立数学模型的基础上，从单任务与多任务匹配AGV方法出发，运用算法解决了调度系统中任务与AGV匹配的问题，结果表明该方法能够快速准确地将任务与AGV相匹配，保证了整个系统中的路径最短。因此该方法能够为实际的AGV调度系统提供参考。

[1] 李玉.自动导航小车的路径规划与控制研究[D].西安：西安科技大学,2008.

[2]LinLin，SeongWhanShinn，MitsuoGen，etal.NetworkmodelandeffectiveevolutionaryapproachforAGVdispatchinginmanufacturingsystem[J].JournalofIntelligentManufacturing, 2006, 17(4):465-477.

[3]ZengChengkuan，TangJiafu，YanChongjun.Schedulingofnobufferjobshopcellswithblockingconstraintsandautomatedguidedvehicles[J].AppliedSoftComputing,2014,24: 1033-1046.

[4]Smolic-RocakN,BogdanS,KovacicZ,etal.Timewindowsbaseddynamicroutinginmulti-AGVsystems.[J].IEEETransactionsonAutomationScienceandEngineering,2010, 7(1):151-155.

[5] 雷定猷, 张兰.AGV系统的调度优化模型[J]. 科学技术与工程, 2008 (1):66-69，79.

[6] 柳赛男, 柯映林. 一种解决有AGV小车约束的车间智能调度问题的算法[J].中国机械工程,2007(15):1810-1813.

[7] 王文蕊,吴耀华.自动导引车系统资源分配问题的建模及求解[J]. 计算机应用,2014(3):767-770,805.

[8] 李军, 郭强, 刘建新. 组合运输的优化调度[J]. 系统工程理论与实践, 2001, 21(2):117-121.

[9] 金芳,方凯,王京林.基于排队论的AGV调度研究[J].仪器仪表学报, 2004(增刊1):844-846，874.

The application of Dijkstra algorithm in the AGV dispatching system

ZHANG Wei1,2, ZHANG Qiuju1,2

(1.School of Mechanical Engineering, Jiangnan University, Jiangsu Wuxi, 214122, China)

(2.The key laboratory for advanced food manufacturing equipment technology of Jiangsu province, Jiangsu Wuxi, 214122, China)

It is difficult for traditional logistics mode to meet the market demand. It analyzes the requirement such as the short order cyclet, small batch and much batch times. Automated warehousing logistics has constantly get new development and application. Based on the AGV (automatic guided vehicle/AGV), it introduces the warehousing logistics distribution technology, designs the warehousing logistics form, establishes an effective storage space model and obtains a suitable road network for AGV run. Based on the single mission requirements, it builds the mathematical model of AGV running at the shortest total distance, analyzes from the methods of single task transfers AGV to multitasking transfers to AGV, applies Dijkstra algorithm to solve the warehousing distribution matching problem of AGV with tasks in the system.

task; AGV; Dijkstra algorithm; matches

10.3969/j.issn.2095-509X.2015.05.014

2015-04-23

张伟(1990—)，男，江苏海安人，江南大学硕士研究生 ，主要研究方向为机械电子工程。

TP391.9

A

2095-509X(2015)05-0061-04