基于改进Dijkstra算法的泊车系统路径规划研究

摘要

In order to solve the path planning problem of AGV accessing cars in intelligent garage,and overcome the defect of traditional Dijkstra algorithm,which includes higher time complexity,larger search scope and lower search efficiency etc,the path planning method of parking system based on the bi-directional Dijkstra algorithm was proposed.In this paper,firstly,the weighted undirected graph of the target parking spot was created on the basis of the distribution of free parking spot at a certain time in intelligent garage.Secondly,the traditional Dijkstra algorithm was optimized and improved through altering the data storage structure and introducing the bidirectional search strategy.Finally,the shortest path length was used as evaluation index,the traditional Dijkstra algorithm and improved Dijkstra algorithm used as search strategy,the path planning process of AGV accessing cars was simulated with MATLAB software.The simulation results show improved Dijkstra algorithm is correct,feasible and effective.Moreover,compared with traditional Dijkstra algorithm,improved Dijkstra algorithm can effectively reduce data store space and improve search efficiency,and can meet the requirement of AGV accessing cars in path planning.%为了解决智能车库中自动导引运输车(Automated Guided Vehicle,AGV)存取车路径规划问题和克服传统Dijkstra算法时间复杂度高、搜索范围大及搜索效率低等缺陷,提出了一种基于改进Dijkstra算法的泊车系统路径规划方法.首先以智能车库某时刻空闲泊车位的分布情况为背景,创建该时刻目标泊车位的带权无向图;其次,通过更改数据存储结构和引入双向搜索策略对传统Dijkstra算法进行改进;最后,以距离最短为评价指标,以传统Dijkstra算法和改进Dijkstra算法为路径寻优方法,在MATLAB环境下对AGV存取车路径规划过程进行仿真测试.结果表明:改进Dijkstra算法正确、可行及有效,与传统Dijkstra算法相比,能有效节省数据存储空间,减少搜索时间,提高搜索效率,可以满足AGV存取车路径规划要求.