Abstract:

Auto Store, a new compact and dense storage system, has many characteristics, such as more short-distance relocation operations, more AGV conflicts at the top level, and more structural corners of shelves, therefore, an offline online two-stage AGV scheduling method is proposed. In the off-line path planning stage, an improved two-level A* algorithm is given. On the basis of topological graph modeling and dividing the search area, the upper layer seeks the feasible region by considering the conflict heuristic function and the cost function considering turning, and the lower level searches the optimal path based on this area. In the operation phase of online AGV, the backoff strategy and route replanning strategy are extended for the conflict between two AGVs; for multiple AGV conflicts, a regional collision avoidance decision strategy based on greedy algorithm is proposed to control the scale of the problem. Finally, Flexsim simulation is used to verify the results. The results show that compared with the standard A* algorithm, the improved A* algorithm can obtain the initial path scheme with less conflicts while ensuring the search efficiency; compared with the priority strategy, the regional collision avoidance strategy can reduce the waiting time of AGV; the combination of the two can shorten the overall job completion time, and with the increase of the number of AGVs and tasks, the advantages of the improved A* algorithm are better obviously.

Key words: Auto Store, AGV path planning, AGV conflict, improved A* algorithm, storage system

摘要：

针对新兴紧致密集仓储系统Auto Store具有短途挪库作业多、顶层AGV冲突多、货架结构性角落多等特点，提出一种离线-在线两阶段AGV优化调度方法。离线路径规划阶段，给出改进双层A*算法，在拓扑图建模划分搜索区域基础上，上层通过考虑冲突的启发式函数和考虑转弯的代价函数寻求可行区域，下层在此区域基础上搜索最优路径。在线AGV运行阶段，针对两AGV冲突，扩充了回退策略和路线重规划策略；针对多AGV冲突，提出一种基于贪心算法的区域避碰决策策略，以控制问题规模。最后利用Flexsim仿真进行了验证，结果表明，较于标准A*算法，改进A*算法能在保证搜索效率的同时获得冲突较少的初始路径方案；较于优先级策略，区域避碰策略能减少AGV等待时间；将二者相结合，能缩短整体作业完成时间，且随着AGV数量和作业任务增多，优势越明显。

关键词: Auto Store, AGV路径规划, AGV冲突, 改进A*算法, 仓储系统