施剑烽　杨勇生

【摘 要】随着工业的发展，自动化码头已成为众多码头未来发展方向，而AGV作为自动化码头水平运输的重要手段，日益得到重视。研究AGV的相关技术意义重大，本文仅对AGV路径规划的Dijkstra算法进行研究，以期能应用于自动化码头。

【关键词】自动化码头；AGV；路径规划；Dijkstra算法

1 研究背景及意义

随着经济一体化、全球化趋势的发展，集装箱码头在全球航运中的地位愈加重要，集装箱码头之间的竞争也日趋激烈，提高码头的工作效率成为集装箱码头不断改进和完善的目标。因此许多发达国家提出建设自动化集装箱码头（简称“自动化码头”）的方案[1]。

自动化码头比传统码头更加安全、管控更加全面、极大降低人力成本等[2]。因此，国内外学者着手研究如何提高自动化码头水平运输环节效率，而自动化码头中的水平运输环节主要由AGV、岸桥、场桥组成。如图1所示，是衔接岸桥作业和场桥作业的中转区域。但随着技术的改进，岸桥、场桥装卸能力得到提升，因此AGV的运输效率将日益成为影响自动化码头作业效率重要因素，决定了码头的整体作业效率[3]。

因此必须研究恰当的路径规划算法使AGV能实时响应码头作业任务，并且尽可能的规划出一条或者几条最优路径，因此，本文对现有的各种算法进行归纳、总结，希望找到一种合适的算法以解决自动化码头AGV路径规划问题[4]。

2 路径规划技术

AGV路径规划是在地图中按照路径最短评价指标搜索出一条从起始节点到目标节点的最优或次优的路径，即f（n）=∑w。由于设定AGV速度不变，因此等价于考虑AGV最短路径的问题。目前常见的AGV 路径规划算法主要有人工势场法、Dijkstra算法、A*算法等[5]，本文仅对Dijkstra算法进行研究及改进，使之能应用于自动化码头。

3 Dijkstra算法

Dijkstra算法是图论G=（V，E）中的求解两点之间最短路径的算法[6]，其中V代表节点集合，E代表边的集合。它的搜索方式是从初始节点开始逐层向外搜索，直到所有节点都被搜索到，然后进行比较最终确定最短路径[7]。

Dijkstra算法的具体步骤为：

1）首先，集合S中只包含源节点S0，U包含除去S0之外的其他所有节点。

2）从U中选取与S0相邻连接的Sk，把Sk添加到S中，最短路径就是S0-Sk。

3）以Sk为新的中间节点，评估U中与Sk连接的节点。若从源点S0经过Sk再到U中节点Sk+1的距离比从源点S0不经过Sk再到U中节点Sk+1的距离短，则路径中的Sk的下一节点为Sk+1，把路径S0-Sk-Sk+1更新到集合E中。同时Sk+1加入集合S。

4）重复以上过程直至所有节点都加入集合S。最终由这些节点所连成的路径即为最短路径。

以图2中的节点图为模型，表1展示了从A点搜索到各点的最短路径的步骤。

通过以上算法过程，可以发现Dijkstra算法在搜索最短路径问题上表现良好，因此可以考虑应用在自动化码头。但明显发现Dijkstra算法搜索范围大，基本遍历所有路径，虽然能搜索到最优解，但搜索时间长、效率低。因此需要对Dijkstra算法进行改进。

4 算法改进及仿真验证

对于改进Dijkstra算法，以便能应用于自动化码头，本文以图3某自动化码头AGV作业区域模型为例，图中中每一条边都为80米，然后进行算法改进研究。

如下所示为使用Dijkstra算法在上图3所示电子地图中搜索节点V1到节点V10的路径结果。

Dijkstra算法一共生成6条可选路径，对于如果中间节点更多的情况下就搜索的可选路径更多，对系统的响应比较慢，因此有必要对Dijkstra算法进行改进。

由于AGV在行驶过程中，多次转弯会比直线行驶时间消耗、能源消耗都多，因此本文采用在之前的评价f（n）=∑w中添加转弯次数代价因素∑h，能源消耗代价因素∑p，路径通畅度∑q，即f（n）=∑w+∑h +∑p+∑q。每当AGV多转弯一次，整个系统的时间相应就越长，能源消耗越大，通过改进的Dijkstra算法重新对节点V1到节点V10进行路径规划，得出新的路径结果。

新的可选路径只有2条，减少了转弯次数，提高了算法的效率，增强了系统的响应能力。在MATLAB中分别对Dijkstra算法和改进的Dijkstra算法进行仿真，搜索从V1点到V18的AGV最优路径，比较这两种算法搜索的路径长度、转弯次数，数据如表2所示。

表2 算法仿真结果对比

可以看出Dijkstra算法搜索到11条备选最短路径，但存在多条备选路径时，所走的路径不尽相同。但是通过观察改进的Dijkstra算法搜索到的路径可以发现，改进的Dijkstra算法搜索到的路径的转弯次数最少，即只有1次转弯，轨迹明显优于其他备选路径，且提高了路径搜索效率。

5 结论

通过对Dijkstra算法的研究，发现Dijkstra算法可以应用于自动化码头AGV路径规划，但传统的Dijkstra算法不能满足转弯次数少、能源消耗最少等因素，因此需要对Dijkstra算法进行改进，通过对传统Dijkstra算法和改进后Dijkstra算法进行MATLAB仿真验证，验证了改进后的Dijkstra算法的有效性，因此，改进后的Dijkstra算法可以应用于自动化码头AGV路径规划。

【参考文献】

[1]田洪，吴富生.自动化码头的发展现状及趋势[C].物流工程三十年技术创新发展之道，中国铁道出版社，2010：232-236.

[2]郑见粹，李海波，谢文宁，等.自动化集装箱码头装卸工艺系统比较研究[J].水运科学研究，2011，2：26-33.

[3]Héctor J. Carloa，， Iris F.A. Visb ， Kees Jan Roodbergenb. Transport operations in container terminals： Literature overview， trends， research directions and classification scheme[J]. European Journal of Operational Research， 2014， 236： 1-13.

[4]李海波，马文杰，任良成.应用自动导引车的港口物流系统的分析与比较[J].水运科学研究，2010，2：23-27.

[5]冯海双.AGV自动运输系统调度及路径规划研究[D].哈尔滨工业大学，2013.

[6]孙奇.AGV系统路径规划技术研究[D].浙江大学，2012.

[7]贺丽娜.AGV系统运行路径优化技术研究[D].南京航空航天大学，2011.