物流中心基于CROTPN的多AGV无冲突和无死锁路径规划的研究

发布时间：2020-06-06 13:20

【摘要】：自动引导小车(AGV)的有效路径规划对于智能仓库、无人码头和自动化工厂等工业场景具有重要意义。近年来,尤其随着电子商务的发展,网上购物越来越受欢迎。为了加速消费者的递送过程,物流中心需要智能地对包裹进行高效的分拣和运输,这需要使用智能的AGV而不是传统的人工和传送带来实现。由于物流分拣中心每天有成千上万件包裹需要分拣和运输,为了提升分拣效率,人们已经开始研究在给定的时间内多AGV运输尽可能多的包裹。然而,当两个或者多个AGV在相同时间通过相同区域时会造成死锁和冲突。本文研究物流中心多AGV自动分拣无冲突和死锁的路径规划及调度问题。针对实际场景的布局,本文的目标是使用尽可能少的AGV并且使得系统运行期间分拣吞吐量最大。为了解决物流中心多AGV无冲突和无死锁路径规划的问题,本文主要完成了以下几方面的工作:本文首先分析和总结了现有多AGV路径规划方法的优缺点,并在现有多AGV路径规划的研究基础上,对物流分拣中心场地布局的特征进行调研。基于图论模型将场地布局抽象成无向图,在无向图的理论上本文对多AGV自动分拣系统路径规划问题做了详细的描述。本文主要研究了以完工时间最小为目标函数的无冲突和无死锁多AGV的路径规划,其中完工时间是指所有AGV完成一次传送的最大时间。针对少量AGV无冲突路径规划的问题,本文提出了启发式搜索算法和协调算法,AGV通过启发式算法可以快速地估计最短路径的方向。当多个AGV搜索路径时会产生冲突,本文通过使用协调算法让AGV等待和转弯的策略来避免与其他AGV的路径冲突。针对大量AGV和场景复杂的无冲突路径规划问题,本文首先提出候选路径生成算法为每个AGV规划出多条路径,其次根据最优路径组合选择算法选出一组路径,此组路径组合使得冲突和死锁最少。然后本文将安排时间划分为时间片对动态改变的AGV路径构造出一个面向资源的着色时间Petri网(CROTPN)模型,并基于该模型对各种冲突和死锁进行了分析和求解,譬如节点冲突、圈、圈链、互动圈链和环等。通过时间片控制策略,各种冲突和死锁都可以被有效的避免。本文使用CPNtools工具进行仿真实验,实验结果显示基于CROTPN模型的方法可以实现使用更少的AGV完成更多的运输任务。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP23;O221

【相似文献】

相关期刊论文 前10条

1 常忠;126系统用户号死锁故障的探讨[J];天津通信技术;1994年03期

2 刘映雪;Ada任务死锁动态检测工具[J];计算机工程与设计;1988年04期

3 何炎祥;;分布式OS中处理死锁两种方法[J];计算机工程与应用;1988年10期

4 吴X;戴菡;周竞扬;陆桑璐;陈道蓄;谢立;;分布式死锁检测算法中伪死锁率的研究和改进[J];计算机科学;2005年06期

5 叶蓉,陈莘萌;k元n-立方体网络的死锁特征剖析[J];小型微型计算机系统;2002年02期

6 孟章荣;死锁的解法[J];计算机工程与设计;1990年01期

7 郝克刚,叶祖尧;分布式程序中固有死锁的检测[J];西北大学学报(自然科学版);1984年04期

8 鄢勇,刘键;一种新的分布式死锁探测与解除方法[J];华中理工大学学报;1990年01期

9 冯彦翔;陈泽宾;张为元;;基于变迁覆盖的柔性制造系统的鲁棒死锁控制策略[J];咸阳师范学院学报;2019年06期

10 舒英;网上多用户程序编制中死锁及死锁的处理[J];重庆邮电学院学报;1998年02期

相关会议论文 前7条

1 齐进;张家明;周伯鑫;徐南荣;;嵌套事务中不可补偿死锁的两种处理方法[A];数据库研究进展97——第十四届全国数据库学术会议论文集（上）[C];1997年

2 白哥乐;杨朝红;王雅文;;多线程死锁静态检测方法研究[A];第十四届全国容错计算学术会议(CFTC'2011)论文集[C];2011年

3 王商武;张长水;韩曾晋;;FMS运行中死锁的预测和避免[A];1993中国控制与决策学术年会论文集[C];1993年

4 卫朝阳;;关于加油站零售管理系统的建设[A];第二十届中国（天津）'2006IT、网络、信息技术、电子、仪器仪表创新学术会议论文集[C];2006年

5 彭成宝;吕新宇;张霞;;OpenBASE事务管理机制的设计与实现[A];第十五届全国数据库学术会议论文集[C];1998年

6 岳昊;;具有多资源需求和柔性加工路径的顺序资源分配系统Petri网模型的死锁结构特征[A];第二十九届中国控制会议论文集[C];2010年

7 罗鑫;肖卓明;李乔儒;;采编系统的性能调优[A];中国新闻技术工作者联合会2008年学术年会论文集（上）[C];2008年

相关重要报纸文章 前1条

1 人民银行吉林市中心支行科技处 刘志明;解决Sybase数据库死锁的方法[N];计算机世界;2001年

相关博士学位论文 前7条

1 黄忠华;自动制造系统中的无死锁调度与控制[D];上海交通大学;2007年

2 刘苗;柔性制造系统活性分析与死锁控制[D];西安电子科技大学;2015年

3 何善君;自动小车存取系统的建模及其若干关键技术研究[D];厦门大学;2008年

4 肖海宁;基于UGNL的AGV系统规划设计与控制方法研究[D];南京航空航天大学;2013年

5 胡文敏;基于二维Mesh网络的片上组播通信关键技术研究[D];国防科学技术大学;2012年

6 朱森;资源分配系统死锁控制及其应用研究[D];西安电子科技大学;2009年

7 莫太平;制造执行系统的建模与调度问题研究及应用[D];西安电子科技大学;2015年

相关硕士学位论文 前10条

1 向昭宇;基于颜色资源导向型佩特里网自动导航车调度系统防死锁方法研究[D];湖南工业大学;2019年

2 孙三魁;物流中心基于CROTPN的多AGV无冲突和无死锁路径规划的研究[D];哈尔滨工业大学;2018年

3 王升升;基于Petri网对含有不可控/不可观事件的自动制造系统的死锁控制研究[D];西安电子科技大学;2019年

4 何文龙;基于Petri网分解技术的死锁分析与控制[D];西安电子科技大学;2018年

5 贺勤勤;面向资源的有色Petri网模型控制研究[D];西安电子科技大学;2018年

6 齐鹏;基于未来锁集的死锁规避技术研究[D];哈尔滨工业大学;2015年

7 汪胜;并发程序中的潜在死锁检测与调试[D];华中科技大学;2016年

8 夏海斌;一类柔性制造系统的死锁研究与分析[D];西安电子科技大学;2005年

9 翁东良;基于二型模糊逻辑的死锁与数据竞争检测方法研究[D];苏州大学;2012年

10 臧丽娜;基于死锁的并发类单元测试用例自动生成研究[D];北京化工大学;2017年

，

本文编号：2699736