基于时间窗的自动导引车无碰撞路径规划

• 论文 •

基于时间窗的自动导引车无碰撞路径规划

贺丽娜，楼佩煌，钱晓明，刘冉

南京航空航天大学机电学院，江苏南京210016

出版日期:2010-12-15 发布日期:2010-12-25

Conflict-free automated guided vehicles routing based on time window

HE Li-na, LOU Pei-huang, QIAN Xiao-ming, LIU Ran

College of Mechanical & Electrical Engineering, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China

Online:2010-12-15 Published:2010-12-25

摘要/Abstract

摘要： 针对柔性制造系统中自动导引车的无碰撞路径规划问题，结合预先规划算法和实时规划算法的优点，提出基于先验决策的自动导引车无碰撞路径规划方法。将 Dijkstra算法和时间窗原理相结合，顺序规划各个自动导引车的路径。在已规划自动导引车路径的基础上，运用基于Dijkstra的算法继续规划下一自动导引车，实现自动导引车的无碰撞路径规划。该算法能有效避免死锁及碰撞，并保证最优化路径，能快速响应新的任务，在动态环境下具有较好的柔性。结合实例说明了该算法的实现过程，并证明了该方法具有较好的鲁棒性和柔性，同时能提高系统效率。

关键词: 自动导引车, 路径规划, 无碰撞, 时间窗, 柔性制造系统

Abstract: To solve conflict-free path planning problem for the Automated Guided Vehicles (AGV) in flexible manufacturing system, by combining advantages of pre-planning algorithm and real-time planning algorithm, a conflict-free AGV routing based on performance-based structural policy was proposed, in which Dijkstra algorithm and time window principle were combined. Every AGV path was scheduled in order. Based on the planned AGV paths, conflict-free routing was achieved by employing the Dijkstra algorithm in the next AGV routing. This algorithm effectively avoided deadlocks and guaranteed optimal path. It responded to new assignment rapidly with better flexibility in dynamic environment. Finally, the algorithm was performed with practical case, which proved to have better robustness, flexibility and efficiency.

Key words: automated guided vehicles, routing, conflict-free, time window, flexible manufacturing system

中图分类号:

TP24

贺丽娜，楼佩煌，钱晓明，刘冉. 基于时间窗的自动导引车无碰撞路径规划[J]. .

HE Li-na, LOU Pei-huang, QIAN Xiao-ming, LIU Ran. Conflict-free automated guided vehicles routing based on time window[J]. .

[1]	张海平,邓建新. 有决策时间窗匹配问题的决策优化支持模型[J]. 计算机集成制造系统, 2021, 27(6): 1728-1740.
[2]	鲁建厦,陈寿伍,易文超,汤洪涛. 跨层穿梭车仓储系统复合作业路径规划[J]. 计算机集成制造系统, 2021, 27(6): 1799-1808.
[3]	陈满意,张桥,张弓,梁济民,侯至丞,杨文林,徐征,王建. 多障碍环境下机械臂避障路径规划[J]. 计算机集成制造系统, 2021, 27(4): 990-998.
[4]	赵文政,刘银华,金隼. 面向多机器人协调运动规划的层级化任务分配方法[J]. 计算机集成制造系统, 2021, 27(4): 999-1007.
[5]	葛显龙,冉小芬. 基于时间窗指派的污染路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1178-1187.
[6]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[7]	吴铮,陈彦杰,何炳蔚,林立雄,王耀南. 基于方向选择的移动机器人路径规划方法[J]. 计算机集成制造系统, 2021, 27(3): 672-682.
[8]	邓建新,卫世丰,石先莲,陈星雨,韦婉冬. 基于数字孪生的配送管理系统研究[J]. 计算机集成制造系统, 2021, 27(2): 585-604.
[9]	李峥峰,刘阳阳. 考虑充电的多AGV的作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2872-2879.
[10]	陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.
[11]	翟敬梅,刘坤,徐晓. 室内移动机器人自主导航系统设计与方法[J]. 计算机集成制造系统, 2020, 26(第4): 890-899.
[12]	王闯,常丰田,高佳佳. 基于自动导引车单向导引路径网络的智能车间设备布局规划[J]. 计算机集成制造系统, 2020, 26(第4): 939-946.
[13]	鲁建厦,施贻贯,汤洪涛,詹燕. 考虑碳排放的子母穿梭车密集仓储系统复合作业三维路径规划[J]. 计算机集成制造系统, 2020, 26(第3): 795-805.
[14]	余娜娜,李铁克,王柏琳,袁帅鹏. 自动化分拣仓库中多AGV调度与路径规划算法[J]. 计算机集成制造系统, 2020, 26(第1): 171-180.
[15]	张硕,钱晓明,楼佩煌,武星,孙超. 基于改进粒子群算法的大规模自动导引车系统路径规划优化[J]. 计算机集成制造系统, 2020, 26(9): 2484-2496.