基于CBS算法的物流分拣多AGV路径规划的研究

发布时间：2020-03-28 14:20

【摘要】：“互联网+”和“工业4.0”的提出带动了传统制造业往智能制造方面发展。各个物流企业纷纷引入自动引导车(Automated Guided Vehicle,AGV)来替代传统的“传送带+人工”,实现全自动智能分拣。用AGV来进行包裹的分拣,引发了多AGV路径规划问题,需要给场地中的所有AGV规划互不冲突的路径,并且尽可能地使分拣效率得到提升。这也就是本文所要研究的问题,针对该问题,本文主要完成了以下几方面的工作:依据应用特点,本文选用了已有的多Agent路径规划模型作为问题模型,并以最小化路径代价和为优化目标。在该模型下,本文提出了两种基于CBS算法改进的并行算法:PCBS与它的增强型EPCBS。并行算法理论上可以用任意多的线程来对问题进行求解,因此可以更好地利用实际环境提供的计算性能。通过登记正在扩展结点的代价值使得并行算法可以有条件选取待扩展结点,最终求得问题的近似最优解;利用随机化的冲突选择策略,让结点之间找到解的概率尽可能相互独立,使得并行算法带来实质上的效率提升。考虑到物流分拣场景的动态特性,本文提出了动态多Agent路径规划问题模型,在其中加入了对环境中执行任务的Agent数量变化的考虑。针对该问题,本文基于CBS设计了一种增量搜索算法LPCBS来求,并证明了其最优性。增量搜索通过复用CBS前一次搜索过程中产生的约束树实现了给“新到达”Agent规划路径的同时快速调整“在途中”Agent的路径。同时在LPCBS中我们给出了CBS中约束树的一种新的实现,该实现有效节省了搜索过程中所需要的内存。最后,本文在不同大小、不同Agent数量的场景下,将本文中设计的并行算法与改进前的串行算法在不同方面进行了对比。发现并行算法在应对Agent数量的增长上,搜索时间增长的幅度比串行算法更小,而且并行算法利用多个线程来搜索获得的效率提升明显。为了验证本文设计的增量搜索算法LPCBS,本文模拟了一个物流分拣的场景。通过模拟多个Agent在环境中进行任务分拣,实验结果从多方面解释了LPCBS在求解动态问题上比CBS效率要高,并且所求解的质量相对于典型的分布式求解器HCA*有着明显优势。
【图文】：

哈尔滨工业大学工学硕士学位论文，操作人员通过将快件身上的条码给 AGV 中央控制系统进行扫描，快件将要发往的位置；随后由系统给 AGV 规划路径，将路径传输给 A来，AGV 按照规划好的路径行走；最后到达目的点完成快件的投递，。因此，AGV 的路径好坏是影响分拣作业效率的关键，，本课题着手于背景之下，研究物流分拣作业中的多 AGV 路径规划。通过优化多个 径，使得分拣效率可以得到提升。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：F253;TP23

【相似文献】

相关期刊论文 前10条

1 黄建华,方毅,黄樟灿,吴方才;基于演化计算的广义路径规划问题[J];武汉理工大学学报(信息与管理工程版);2001年02期

2 朱光宇;;面向钻削路径规划问题的微粒群优化算法研究[J];信息与控制;2008年01期

3 李梅娟;陈雪波;张梅凤;;基于群集智能算法的路径规划问题[J];清华大学学报(自然科学版);2007年S2期

4 孙丽君;胡祥培;王征;;车辆路径规划问题及其求解方法研究进展[J];系统工程;2006年11期

5 陈刚,沈林成;复杂环境下路径规划问题的遗传路径规划方法[J];机器人;2001年01期

6 谭超;徐志鹏;牛可;;采煤机记忆切割路径规划问题研究[J];现代矿业;2009年12期

7 付春菊;吴成东;雷寒;刘彦辉;;基于遗传算法的车辆路径规划问题研究[J];科技广场;2008年10期

8 于锐;曹介南;朱培栋;;车辆运输路径规划问题研究[J];计算机技术与发展;2011年01期

9 曾纪钧;梁哲恒;;监督式强化学习在路径规划中的应用研究[J];计算机应用与软件;2018年10期

10 徐磊;陈璐;;道路养护中的带随机时间变量的弧路径规划问题[J];工业工程;2017年01期

相关会议论文 前10条

1 贾永基;张丽娜;王长军;;带充电设施的电动汽车路径规划问题研究[A];管理科学与工程学会2016年年会论文集[C];2016年

2 裴振奎;刘健;华夏;;求解随机车辆路径规划问题的混合微粒群算法[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

3 唐校辉;黎旭成;刘松灵;陈振武;王卓;;车辆路径规划问题主流求解框架对比分析[A];品质交通与协同共治——2019年中国城市交通规划年会论文集[C];2019年

4 马华伟;范奉伟;胡笑旋;;基于禁忌搜索算法的甩挂运输路径规划问题研究[A];第十八届中国管理科学学术年会论文集[C];2016年

5 刘宁琳;唐們;;基于最小绕行网络的城市与建筑复合功能空间路径生成方法研究[A];数字技术·建筑全生命周期——2018年全国建筑院系建筑数字技术教学与研究学术研讨会论文集[C];2018年

6 张炜;王原;何永明;邢立宁;;基于先排序后聚类原则下解决CARP问题的分割算法[A];第十七届中国管理科学学术年会论文集[C];2015年

7 马华伟;胡明明;胡笑旋;;基于模拟退火算法的甩挂运输路径规划[A];第十八届中国管理科学学术年会论文集[C];2016年

8 王哲;高峰;;基于地面分类的车辆行驶通过性及路径规划研究[A];中国宇航学会深空探测技术专业委员会第二届学术会议论文集[C];2005年

9 程小军;崔祜涛;崔平远;;深空探测器复杂约束姿态机动规划[A];中国宇航学会深空探测技术专业委员会第五届学术年会论文集[C];2008年

10 王壮;蔡杰进;;基于改进粒子群算法的辐射环境路径规划研究[A];中国核科学技术进展报告（第五卷）——中国核学会2017年学术年会论文集第5册（核材料分卷、辐射防护分卷）[C];2017年

相关博士学位论文 前10条

1 耿娜;考虑被困人员生命强度的机器人救援路径规划[D];中国矿业大学;2016年

2 孟令航;洲际航空编队飞行路径规划的理论方法研究[D];天津大学;2016年

3 王沛栋;改进蚁群算法及在路径规划问题的应用研究[D];中国海洋大学;2012年

4 曾麦脉;城市应急路网疏散规划的模型与算法研究[D];华中科技大学;2010年

5 朱剑;WSN中节点布局、定位及移动节点路径规划问题研究[D];东北大学;2010年

6 孙岩;基于运输情景的多式联运路径规划优化建模方法研究[D];北京交通大学;2017年

7 罗亚中;空间最优交会路径规划策略研究[D];国防科学技术大学;2007年

8 张兴;信使机制UAV/UGV多点动态集结的协同规划方法研究[D];北京理工大学;2015年

9 武心安;未知环境下自主式水下潜器路径规划问题研究[D];哈尔滨工程大学;2010年

10 杨鹏;基于自动分治的智能优化方法及其应用研究[D];中国科学技术大学;2017年

相关硕士学位论文 前10条

1 万千;基于CBS算法的物流分拣多AGV路径规划的研究[D];哈尔滨工业大学;2018年

2 杨欣潼;社区居家养老随机路径规划问题研究[D];广东工业大学;2019年

3 崔少华;移动充电服务的路径规划与设计问题研究[D];北京交通大学;2019年

4 资元星;区分任务紧急性的居家养老预约调度与路径规划问题研究[D];华南理工大学;2019年

5 张慧敏;任务均衡下的快递末端配送区域划分及路径优化研究[D];北京交通大学;2019年

6 叶馥榕;基于Spark的带三维装载与时间窗约束的车辆路径规划问题研究[D];厦门大学;2017年

7 杨彦明;基于模因算法的物流车辆路径规划问题求解及实现[D];深圳大学;2018年

8 李松林;AGV路径规划问题设计与研究[D];广东工业大学;2018年

9 刘致远;拥堵情形下的污染路径问题研究[D];中国科学技术大学;2018年

10 徐俊;带时间窗和送取货的车辆路径规划问题研究[D];暨南大学;2018年

本文编号：2604568