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

0 引言

近年来，随着汽车工业的飞速发展和人们生活质量的不断提高，拥有私家车对多数家庭来说已不再是一种奢想。汽车保有量急剧增加，致使城市交通拥挤和停车困难等社会难题不断涌现，为缓解城市交通拥挤和解决停车难问题，目前市场上出现了多种类型的停车设备，如传统地下停车库、机械式立体停车库、磁悬浮式立体停车库以及基于 AGV 的智能立体停车库等。基于 AGV 的智能立体停车库与其他三种类型停车设备相比，具有占用空间面积小、有效停车数量多、自动化程度高、性价比及安全可靠性高等特点［1-2］，因此，该智能车库一经出现，便受到社会各界广泛关注。在基于 AGV 的智能立体停车库中，如何使 AGV 在最短时间内顺利完成车辆存取停放任务，这涉及到 AGV最优路径规划问题。
目前，用于解决路径规划问题的方法主要有 Dijkstra 算法［3］、A* 算法［4］、蚁群算法［5］及遗传算法［6］。在上述算法中，Dijkstra 算法技术最成熟，具有算法简单、易于实现、规划的路径具有鲁棒性强，以及可靠性高的特点，因此，该算法一经提出，便受到相关学者的广泛关注与研究。如 Wang Shuxi［7］提出了一种改进Dijkstra 算法，改进算法不仅可以有效实现无向图和有向图的最短路径求解功能，还可避免死循环出现;Deng Yong 等人［8］提出采用一种模糊 Dijkstra 算法解决不确定环境下的最短路径问题，改进算法以 Dijkstra算法为核心，通过模糊评级集合解决了两边之和及不同路径之间的长度比较问题，实现了不确定环境下的最短路径寻优; Huang Yizhen 等人［9］通过引入自适应权值约束函数，设计了一种基于搜索策略的改进 Dijkstra 算法，并将其运用到电子地图路径搜索中，有效地减少了路径节点搜索数量和程序运行时间; ZhengYicheng 等人［10］通过选用二进制描述路径权重和修剪路网重复节点对传统 Dijkstra 算法进行了改进，并将改进 Dijkstra 算法运用到动态路网的消防救援路径规划中，测试结果表明，改进算法可行、有效且具有较高的搜索效率; Wang Ｒui 等人［11］针对传统 Dijkstra 算法在多节点搜索过程中存在的高时间复杂度和低搜索效率缺陷，提出采用双向搜索策略对 Dijkstra 算法进行优化改进，有效地提高了节点搜索效率; Gayathri N等人［12］鉴于路径运行时间的多变性，提出以路径交通密度作为参数，以运行时间为评价指标，选用改进 Dijkstra 算法求解最优路径运行时间，并通过实验验证了改进算法的可行性和有效性; 彭红星等人［13］根据大型停车场交通路网实际情况，通过将车位节点与路口节点分开和引入双层搜索策略对传统 Dijkstra 算法进行了改进，有效地减少了节点搜索数量，提高了算法的搜索效率。

针对智能车库中 AGV 存取车路径规划问题，结合传统 Dijkstra 算法的特点，笔者提出了一种基于改进Dijkstra 算法的泊车系统路径规划方法。该方法是通过更改数据存储结构和引入双向搜索策略对原蚁群算法进行改进实现的。为验证改进算法的正确性和有效性，最后通过 MATLAB 软件对改进 Dijkstra 算法进行了测试。

1 问题描述及环境建模

1． 1 问题描述

研究智能停车库路径规划方法的目的在于: 系统通过各种检测装置实时获取车库中各泊车位和行车道的占用情况，并根据 AGV 状态信息，快速地为 AGV搜寻到一条从起点到目标点的无碰最优路径，确保AGV 在较短时间内顺利完成车辆存取、停放任务，以便提高车库泊车位利用率和降低社会人员存取车等待时间。Dijkstra 算法是一种基于权值来解决图论中单源节点到其他节点最短路径问题的启发式智能优化算法，若想将 Dijkstra 算法用于解决智能车库中AGV 存取车路径规划问题，需对智能车库和 AGV 做如下处理: 1) 泊车位要尽可能对称密集布局，但各泊车位间要留有足够间距，避免 AGV 在存取车过程中出现车辆刮碰; 2) 行车道宽度须根据车道类型设定，在满足 AGV 最大转弯半径和避免 AGV 在存取车过程中出现车辆刮碰的同时，要尽可能减小行车道宽度; 3)车库环境模型需按照智能车库中泊车位和行车道的实际布局情况创建; 4) 车库环境模型需转换为带权无向图路网结构; 5) 假定 AGV 匀速运行，忽略其驻停、存取车等待时间及液压系统举升操作等因素; 6) 忽略AGV 实际尺寸，视 AGV 为一个质点。

1． 2 环境模型创建

图 1 所示为采用 CAD 创建的某时刻智能停车库泊车位布局示意图，图1 中，黑色圆格表示该泊车位已被占用; 白色圆格表示空闲泊车位; P0和 Pu ( 与交叉口C2通道重合，此处未标出) 分别表示智能停车库的出口和入口; P1 ～ P15为空闲泊车位，表示该部分泊车位可用于存放车辆; C1 ～ C6表示车道交叉路口，AGV 在此处可完成转向及切换车道操作。