汽车保有量的急剧增加，致使城市交通拥挤、停 车困难等社会问题不断涌现，严重影响了市民的居 住环境，因此，停车难已成为社会亟待解决的难题． 而基于自动导引小车（AGV）的平面移动式智能停 车库凭借占地面积少、有效停车数量多以及智能化 程度高等优点而备受社会各界广泛关注．研究平面 移动式智能停车库的核心，就是要解决 AGV 存取 车路径规划问题．车库路径规划的主要目的是让 AGV运行在有障碍物的未知环境中，根据某些评 价标准（如最短时间、最短距离或最少转弯次数），寻 找一条从预存停车位到目标停车位的最优无碰路 径，确保车辆在最短时间内完成存取，提高停车位利 用率，减少存取车等待时间，实现停车设备自动化管 理．针对路径规划问题，国内外学者已对其进行了深 入研究，并相继提出了多种算法，主要有可视图法、 图搜索法以及人工势场法等．随着智能算法的不断 发展， Dijkstra算法、 A*算法、遗传算法、粒子群算法 以及蚁群算法等也被广泛用于解决各领域路径规划 问题 [1 －2］．
Dijkstra算法是一种典型的单源最短路径算 法，因其采用遍历搜索方式求解最短路径，故得到的 最短路径往往具有可靠性高、鲁棒性好的特点，但也 存在时间复杂度高、搜索效率低、占用内存大等缺 陷 [3］．蚁群算法是一种新型的仿生算法，该算法凭借 并行性、强鲁棒性、全局最优以及易与其他启发式算 法相结合等优点，被广泛用于解决ＴＳＰ问题、路由 问题、二次分配问题以及车间调度问题等，并取得了 不错的效果 [4 －9］．Ｊｏｈｎｓｏｎ等 [2］研究了蚁群算法中信 息素对车辆路径选择的影响，仿真结果显示在允许 时间范围内，蚁群算法可有效解决逆向物流车辆路 径规划问题；康冰等 [4］将折返蚂蚁策略应用到蚁群 算法中，极大地提高了算法的收敛速度；黄震等 [8］将 蚁群算法和遗传算法进行了有效融合，通过将时间 窗因素引入蚁群算法来产生初始种群，然后由遗传 算法对其进行交叉和变异操作，得到了更优路径； Ｃｈａａｒｉ等 [9］针对机器人在静态环境中的路径规划问 题，提出将蚁群算法与遗传算法进行有效结合，并通 过仿真实验验证了算法的可行性和有效性；王美珍 等 [1０］将粒子群算法和蚁群算法进行了有效融合，极 大地提高了算法的搜索效率，缩短了路径长度；何少 佳等 [11］利用 Dijkstra算法的优点对蚁群算法进行 了改进，解决了逃生路径规划问题．
针对 AGV 存取车路径规划问题，将 Dijkstra 算法和蚁群算法的优点结合起来，提出一种基于Dijkstra －蚁群（ACO）的混合算法．利用链接可视图 法建立环境模型，采用 Dijkstra算法规划出 AGV 的初始路径，通过节点随机选择机制及信息素局部 更新和全局更新相结合的方式对基本蚁群算法进行 优化改进，然后选用改进的蚁群算法对初始路径进 行优化，并通过仿真测试验证混合算法的可行性和 有效性．
1 问题描述及环境建模
1.1 问题描述
为实现算法在 AGV 路径规划中的应用，须对 运行环境作如下假设 [12］： 1）假设 AGV运行环境为 二维有限空间； 2）假设图中障碍物已知，位置确定， 以不规则多边形表示，且忽略其高度方向； 3）假设 AGV在运行环境中匀速行驶，忽略 AGV 的启动、 转向、制动以及液压系统举升操作等因素； 4）以 AGV实际尺寸为基准，适当扩大障碍范围，为便于 仿真，将 AGV视为质点．
1.2 环境建模
利用 AGV自带的摄像头、雷达传感器及红外 传感器等采集AGV运行环境信息，其包括AGV的 起始车位、目标车位、障碍物以及 AGV待充电位置 等，根据上述信息通过链接可视图法创建 AGV 运行环境模型．图1 所示为采用链接可视图法在 MATLAB环境下创建的环境模型，模型规格为250ｍ×250ｍ，模型用6个黑色凸多边形表示障碍物区 域．图中各障碍物区域以及边界区域顶点之间的虚 线为自由链接线，黑色实线为 AGV的可行路径，以V开头的序列数代表各链接线的中点， S和T为AGV的起点和终点位置．
图1 agv二维工作环境模型
暂无评论内容