多AGV路径规划优化算法及调度系统的研究
发布时间：2021-09-30 18:48
当前,多AGV（Automated Guided Vehicle）智能仓库成为了物流行业大力发展的对象,同时基于智能仓库的AGV调度系统是国内外学者研究的热点。本文对基于智能仓库的AGV调度系统进行研究。首先,分析了基于智能仓库的AGV调度系统,并指出了影响AGV调度系统效率的两个关键环节是多AGV路径规划和任务调度环节。其次,采用拓扑-栅格法建立仓库环境的地图模型,并分析了A*算法。针对多AGV路径规划问题,在拓扑-栅格地图上加入时间维度构建时空地图模型,并提出了基于时空冲突约束A*算法的多AGV路径规划方法。该方法将冲突解决策略融入到节点扩展过程,并考虑了拐弯代价。最后在MATLAB上进行实验仿真,验证了该方法能够综合考虑AGV的行驶时间、等待时间和拐弯时间,为多AGV规划出无碰撞且时间花费最小的路径。再次,根据智能仓库中AGV的“单次多任务”作业模式,将任务调度问题分解为任务组合和派发问题。利用改进的蚁群算法对任务组合问题进行求解,并针对任务组的派发顺序问题,提出了基于任务组优先级的派发策略。最后在MATLAB上对任务调度算法进行了仿真,结果验证了改进后算法能够提升系统的整体效率...
【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校
【文章页数】：85 页
【学位级别】：硕士
【部分图文】：
京东
合肥工业大学硕士学位论文16栅格法最早由Howden提出，它采用多个离散的栅格表征真实环境。每一个栅格与真实地图中一小块区域对应，并且每一栅格都有一个属性值，常用BOOL量表示。0表示栅格为可行区域，1表示栅格为不可行区域。如图3.2所示，为一栅格地图，其中黑色区域表示障碍物，即不可行区域，白色表示可行区域。栅格地图具有易于创建和维护的优点，其对环境描述的精度取决于栅格数的设定。栅格数越多，环境描述越精确。但同时随着栅格数的增加，会使得存储空间极速上升，计算机处理速度变慢，无法满足实时性要求。栅格数太少又无法准确描述地图位置信息。因此，综合实际地图环境，选择合理的栅格数尤为重要。图3.2栅格地图Fig3.2Gridmap上述三种地图建模方法都有各自优缺点，为了综合每种方法的优点，越来越多人使用复合地图。如采用几何-拓扑混合地图建模方法能够在保证全局空间的连续性同时，兼顾局部空间的精确性。选择环境地图的构建方法时，不能仅从地图环境的角度来建模，而是要综合考虑AGV的定位、路径规划以及应用场合等多种因素。3.1.2AGV实际工作环境建模本文将栅格法与拓扑法相结合，首先利用栅格法对真实环境建模，构建栅格地图模型，然后在栅格地图上进行拓扑法建模，将特殊栅格（表征取货点、拣选台等）拓扑为节点，其他栅格拓扑为保持节点连接线的边，同时节点大小仍与栅格尺寸一致。如图3.3所示，将智能仓库看成一个二维平面，为其建立直角坐标系。该坐标系左下角为坐标原点(0,0)，横向和纵向分别为X轴和Y轴。圆点表示特殊栅格拓扑后的节点，连接线表示普通路径栅格拓扑后的边。同时设定每个栅格的边长为L，AGV的长、宽均小于L，仓库中每条道路的宽也为L。栅格地图X轴的坐标表示栅格的列,其最大值为maxX，Y轴的
第五章AGV调度系统软件平台与验证595.2.4路径规划模块路径规划模块主要负责AGV的路径规划，当系统为AGV分配任务后，根据任务的起始点和目标点以及任务的优先级为AGV规划一条无碰撞最优路径，使得AGV执行任务的成本最小化，进而降低系统的运输成本，提高系统运行效率。路径规划界面如图5.9所示，路径规划模块功能包括自动路径规划和手动路径规划。自动路径规划功能是路径规划模块的核心模块之一，其主要功能是对任务的起点和终点调用路径规划算法寻找一条最短路径。自动路径规划是针对于任务队列中的任务，在任务由等待执行状态转为正在执行状态时，调用路径规划算法为将要执行的任务的AGV指定行驶路径，并将路径信息下发至AGV。手动路径规划功能也是路径规划模块中必不可少的一部分。在实际使用过程中，有时候用户需要AGV沿着自己制定的路径或者经过自己指定的节点，这时自动路径规划便难以满足用户的需求。手动路径规划就是基于这个问题而开发的，用户可以指定AGV、指定所要经过的节点、指定路径，来完成用户所需求的搬运任务。图5.9路径规划界面Fig5.9Pathplanninginterface5.2.5状态监控模块状态监控模块负责对系统运行过程中的主要信息进行全局监控，只有实时掌握系统的运行信息，才能够快速响应系统的变化。如图5.10所示，为系统的主监控界面，在系统启动前，可以通过主监控界面左上角的“加载地图按钮”、“更新地图按钮”将设置好的地图导入主界面，为在线监控做准备。同时，可以通过主界面的右侧的界面切换按钮进入到“地图设计界面”、“通信设置界面”、“任务调度界面”、“路径规划界面”，进一步了解系统中详细的运行数据以及进行相关的参数设置。
【参考文献】：
期刊论文
[1]基于节约算法的港口集装箱运输路径优化研究[J]. 孙艺婕,彭勃. 特区经济. 2019(10)
[2]基于多重启动迭代扫描的需求可拆分车辆路径问题[J]. 闵嘉宁,金成,陆丽君. 制造业自动化. 2019(10)
[3]基于两阶段算法的快递企业末端配送网络优化研究[J]. 姬杨蓓蓓,储昊,成枫. 系统工程. 2019(02)
[4]带多软时间窗VRP及其禁忌搜索算法[J]. 谢九勇,符卓,邱萌,夏扬坤. 计算机工程与应用. 2019(06)
[5]智能仓库中的多机器人协同路径规划方法[J]. 张丹露,孙小勇,傅顺,郑彬. 计算机集成制造系统. 2018(02)
[6]多自动导引车路径规划的诱导蚁群粒子群算法[J]. 李军军,许波桅,杨勇生,吴华锋. 计算机集成制造系统. 2017(12)
[7]多AGV路径规划方法研究[J]. 泰应鹏,邢科新,林叶贵,张文安. 计算机科学. 2017(S2)
[8]中外快递企业分拣效果差距分析及启示——以UPS公司为例[J]. 柯晶琳,姜维军,王庆. 对外经贸实务. 2017(09)
[9]国内外快递公司外部分拣中心能力解析[J]. 刘诗洋. 中国邮政. 2017(06)
[10]基于动态规划算法的二阶段迭代模型任务分布方案的寻优[J]. 田启华,董群梅,杜义贤,汪巍巍,文小勇. 机械设计与研究. 2016(03)
博士论文
[1]大规模动态车辆路径问题优化方法研究[D]. 饶卫振.大连理工大学 2012
硕士论文
[1]多AGV系统的路径规划与调度算法的研究[D]. 王子意.北京邮电大学 2019
[2]智能仓库多移动机器人拣货路径规划研究[D]. 申栋栋.北京交通大学 2019
[3]基于视觉的工业机器人路径规划的研究[D]. 郝行猛.合肥工业大学 2018
[4]AGV系统路径规划与调度算法研究[D]. 梁建刚.北京邮电大学 2018
[5]基于嵌入式控制系统的AGV结构设计及控制方法研究[D]. 徐庆.南京航空航天大学 2018
[6]基于智能仓库的多机器人动态路径规划关键技术研究[D]. 张丹露.中国科学院大学(中国科学院重庆绿色智能技术研究院) 2017
[7]大型锻件多目立体视觉测量图像处理方法研究[D]. 王灵丽.大连理工大学 2016
[8]AGV系统作业调度策略研究[D]. 郝一名.山东大学 2016
[9]基于蚁群算法的车辆路径规划问题的研究[D]. 李建军.西安电子科技大学 2015
[10]AGV系统路径规划技术研究[D]. 孙奇.浙江大学 2012
本文编号：3416446
【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校
【文章页数】：85 页
【学位级别】：硕士
【部分图文】：
京东
合肥工业大学硕士学位论文16栅格法最早由Howden提出，它采用多个离散的栅格表征真实环境。每一个栅格与真实地图中一小块区域对应，并且每一栅格都有一个属性值，常用BOOL量表示。0表示栅格为可行区域，1表示栅格为不可行区域。如图3.2所示，为一栅格地图，其中黑色区域表示障碍物，即不可行区域，白色表示可行区域。栅格地图具有易于创建和维护的优点，其对环境描述的精度取决于栅格数的设定。栅格数越多，环境描述越精确。但同时随着栅格数的增加，会使得存储空间极速上升，计算机处理速度变慢，无法满足实时性要求。栅格数太少又无法准确描述地图位置信息。因此，综合实际地图环境，选择合理的栅格数尤为重要。图3.2栅格地图Fig3.2Gridmap上述三种地图建模方法都有各自优缺点，为了综合每种方法的优点，越来越多人使用复合地图。如采用几何-拓扑混合地图建模方法能够在保证全局空间的连续性同时，兼顾局部空间的精确性。选择环境地图的构建方法时，不能仅从地图环境的角度来建模，而是要综合考虑AGV的定位、路径规划以及应用场合等多种因素。3.1.2AGV实际工作环境建模本文将栅格法与拓扑法相结合，首先利用栅格法对真实环境建模，构建栅格地图模型，然后在栅格地图上进行拓扑法建模，将特殊栅格（表征取货点、拣选台等）拓扑为节点，其他栅格拓扑为保持节点连接线的边，同时节点大小仍与栅格尺寸一致。如图3.3所示，将智能仓库看成一个二维平面，为其建立直角坐标系。该坐标系左下角为坐标原点(0,0)，横向和纵向分别为X轴和Y轴。圆点表示特殊栅格拓扑后的节点，连接线表示普通路径栅格拓扑后的边。同时设定每个栅格的边长为L，AGV的长、宽均小于L，仓库中每条道路的宽也为L。栅格地图X轴的坐标表示栅格的列,其最大值为maxX，Y轴的
第五章AGV调度系统软件平台与验证595.2.4路径规划模块路径规划模块主要负责AGV的路径规划，当系统为AGV分配任务后，根据任务的起始点和目标点以及任务的优先级为AGV规划一条无碰撞最优路径，使得AGV执行任务的成本最小化，进而降低系统的运输成本，提高系统运行效率。路径规划界面如图5.9所示，路径规划模块功能包括自动路径规划和手动路径规划。自动路径规划功能是路径规划模块的核心模块之一，其主要功能是对任务的起点和终点调用路径规划算法寻找一条最短路径。自动路径规划是针对于任务队列中的任务，在任务由等待执行状态转为正在执行状态时，调用路径规划算法为将要执行的任务的AGV指定行驶路径，并将路径信息下发至AGV。手动路径规划功能也是路径规划模块中必不可少的一部分。在实际使用过程中，有时候用户需要AGV沿着自己制定的路径或者经过自己指定的节点，这时自动路径规划便难以满足用户的需求。手动路径规划就是基于这个问题而开发的，用户可以指定AGV、指定所要经过的节点、指定路径，来完成用户所需求的搬运任务。图5.9路径规划界面Fig5.9Pathplanninginterface5.2.5状态监控模块状态监控模块负责对系统运行过程中的主要信息进行全局监控，只有实时掌握系统的运行信息，才能够快速响应系统的变化。如图5.10所示，为系统的主监控界面，在系统启动前，可以通过主监控界面左上角的“加载地图按钮”、“更新地图按钮”将设置好的地图导入主界面，为在线监控做准备。同时，可以通过主界面的右侧的界面切换按钮进入到“地图设计界面”、“通信设置界面”、“任务调度界面”、“路径规划界面”，进一步了解系统中详细的运行数据以及进行相关的参数设置。
【参考文献】：
期刊论文
[1]基于节约算法的港口集装箱运输路径优化研究[J]. 孙艺婕,彭勃. 特区经济. 2019(10)
[2]基于多重启动迭代扫描的需求可拆分车辆路径问题[J]. 闵嘉宁,金成,陆丽君. 制造业自动化. 2019(10)
[3]基于两阶段算法的快递企业末端配送网络优化研究[J]. 姬杨蓓蓓,储昊,成枫. 系统工程. 2019(02)
[4]带多软时间窗VRP及其禁忌搜索算法[J]. 谢九勇,符卓,邱萌,夏扬坤. 计算机工程与应用. 2019(06)
[5]智能仓库中的多机器人协同路径规划方法[J]. 张丹露,孙小勇,傅顺,郑彬. 计算机集成制造系统. 2018(02)
[6]多自动导引车路径规划的诱导蚁群粒子群算法[J]. 李军军,许波桅,杨勇生,吴华锋. 计算机集成制造系统. 2017(12)
[7]多AGV路径规划方法研究[J]. 泰应鹏,邢科新,林叶贵,张文安. 计算机科学. 2017(S2)
[8]中外快递企业分拣效果差距分析及启示——以UPS公司为例[J]. 柯晶琳,姜维军,王庆. 对外经贸实务. 2017(09)
[9]国内外快递公司外部分拣中心能力解析[J]. 刘诗洋. 中国邮政. 2017(06)
[10]基于动态规划算法的二阶段迭代模型任务分布方案的寻优[J]. 田启华,董群梅,杜义贤,汪巍巍,文小勇. 机械设计与研究. 2016(03)
博士论文
[1]大规模动态车辆路径问题优化方法研究[D]. 饶卫振.大连理工大学 2012
硕士论文
[1]多AGV系统的路径规划与调度算法的研究[D]. 王子意.北京邮电大学 2019
[2]智能仓库多移动机器人拣货路径规划研究[D]. 申栋栋.北京交通大学 2019
[3]基于视觉的工业机器人路径规划的研究[D]. 郝行猛.合肥工业大学 2018
[4]AGV系统路径规划与调度算法研究[D]. 梁建刚.北京邮电大学 2018
[5]基于嵌入式控制系统的AGV结构设计及控制方法研究[D]. 徐庆.南京航空航天大学 2018
[6]基于智能仓库的多机器人动态路径规划关键技术研究[D]. 张丹露.中国科学院大学(中国科学院重庆绿色智能技术研究院) 2017
[7]大型锻件多目立体视觉测量图像处理方法研究[D]. 王灵丽.大连理工大学 2016
[8]AGV系统作业调度策略研究[D]. 郝一名.山东大学 2016
[9]基于蚁群算法的车辆路径规划问题的研究[D]. 李建军.西安电子科技大学 2015
[10]AGV系统路径规划技术研究[D]. 孙奇.浙江大学 2012
本文编号：3416446
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3416446.html
