多AGV的多任务分配与路径规划研究

发布时间：2020-06-02 16:20

【摘要】：如今,自动导引车(Automated Guided Vehicles,AGVs)广泛用于制造业和仓储业等领域。例如,在自动化仓储系统中,占总成本最多的是AGV的运输成本,AGV以电能为能源,配合合理的调度策略和良好的AGV路径规划策略,能显著降低运输成本、提升运输效率。因此,本文构建了一种分布式多AGV系统,并针对多AGV的任务排序问题和路径规划问题提出了解决方案,主要的创新点如下:(1)在AGV任务排序问题中,对于具有N项任务的AGV,现有的基于2-opt局部搜索算符的解决方案需要O(N ~3)的复杂度来评估所有O(N ~2)种可能的2-opt移动,存在复杂度高、计算时间长等缺点。因此,本文引入一系列辅助数据结构将该方法的时间复杂度从O(N ~3)降低到O(N ~2)。实验证明,采用辅助数据结构的高效2-opt移动算符可以大大降低估算2-opt移动所需的复杂度,从而显著提高搜索效率。(2)为了解决AGV的动态多任务排序问题,本文提出一种动态蒙特卡罗树搜索算法,利用历史信息来加快排序过程,及时适应动态变化;其次,使用2-opt移动和3-opt移动构成的邻域交替搜索局部空间,优化动态蒙特卡罗树搜索算法生成的解决方案。实验证明,基于动态蒙特卡罗树搜索和变邻域局部搜索算法能显著提升AGV的运输效率,减少运输成本,从而提高企业的经济效益。(3)为了解决多AGV路径规划问题,本文提出了两阶段路径规划方法。首先,采用改进的A*算法为各个AGV规划一条从任务起点到任务终点且不与静态障碍物碰撞的路径。其次,若AGV沿着规划路径行驶时发生冲突,AGV通过携带的传感器提前感知其周围两个单位内的其它AGV的运行状态,然后采用基于博弈论的方法消解冲突,避免AGV之间的相互碰撞,更快速的完成任务。
【图文】：

京邮电大学专业学位硕士研究生学位论文 第一章 绪高运输效率。在运输一些特殊的物质（如有毒物质，放射性物质）时，使用 AGV 运输减少人与这些物质接触的机会，在保护工人安全方面具有传统运输无法比拟的优势。不将来，随着 AGV 技术的日益成熟，仓储 AGV 的应用将更加广泛，，市场上常见的仓储 A图 1.2 所示。

应用简单的 2-opt 局部搜索后的解决方案解决方案 S 的总距离，用 f(s)表示 Positive_Distance 和 Reversed_DistanceS 中任意两条能应用 2-opt 移动的弧 do使用 Efficient 方法估算对应于这两个弧的 2-opt 移动if 2-opt 移动后的距离小于 f(s) then％ 将相应的 2-opt 移动应用于 SS 2opt ( S)回到 line 1 继续迭代end ifd forurn S
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP242;O221

【相似文献】

相关期刊论文 前10条

1 李刚刚;鲁习文;;目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J];运筹学学报;2019年04期

2 苟燕;戴秦;张新功;;具有时间与位置相关的两类平行机排序问题[J];运筹学学报;2019年04期

3 冉金玉;张新功;;总加权误工损失的两个代理单机排序问题[J];湖北民族学院学报(自然科学版);2019年01期

4 韩飞;;高中数学一道数列典型题解法的探究[J];数学学习与研究;2016年23期

5 豆俊梅;孙彩贤;;单机排序问题的研究[J];数学学习与研究;2017年24期

6 胡觉亮;杨佳雯;苏晓彤;董建明;;机器带周期性维护时段的加工与运输协同排序问题[J];浙江理工大学学报(自然科学版);2016年06期

7 仲维亚;马晓茹;;带有运输且加工具有灵活性的无等待流水作业排序问题[J];运筹学学报;2016年04期

8 隋楠;罗成新;;具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J];沈阳航空航天大学学报;2016年06期

9 林浩;何程;;关于工期分配与加权误工数的双指标排序问题（英文）[J];工程数学学报;2017年01期

10 赵传立;张蕾;;带有交货期窗口和加工时间可控的排序问题[J];沈阳师范大学学报(自然科学版);2016年04期

相关会议论文 前10条

1 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

2 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 胡荣;吕绪华;;3TMF排序问题的计算复杂性及分支定界法[A];中国运筹学会第八届学术交流会论文集[C];2006年

8 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 吴翠连;;有尺寸的单机分批排序问题的近似算法[A];中国企业运筹学[2011（1）][C];2011年

相关重要报纸文章 前3条

1 杨文波;浅谈方位词“东、西、南、北”的词语排序问题[N];语言文字周报;2018年

2 山东 赵玉勇;小博士编程[N];电脑报;2004年

3 何靖;全国计算机应用技术证书考试（NIT）[N];中国电脑教育报;2003年

相关博士学位论文 前10条

1 李融奇;在线排序和批排序问题研究[D];浙江大学;2018年

2 沈佳煜;不确定情形下若干排序问题的研究[D];南京理工大学;2017年

3 高园;新型排序问题的计算复杂性研究[D];郑州大学;2018年

4 殷娜;依赖于资源分配的排序问题研究[D];上海大学;2015年

5 李好好;若干排序问题研究[D];浙江大学;2014年

6 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

7 罗润梓;平行机半在线排序问题[D];上海大学;2005年

8 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

9 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

10 李文华;关于分批排序问题的研究[D];郑州大学;2006年

相关硕士学位论文 前10条

1 李红;多AGV的多任务分配与路径规划研究[D];南京邮电大学;2019年

2 陈秋宏;与误工相关的双代理单机排序问题研究[D];重庆师范大学;2019年

3 马亚杰;工件具有相似加工时长的排序问题[D];湖南师范大学;2019年

4 丛稳;工件可拒绝的单机重新排序问题[D];郑州大学;2019年

5 曹移林;平行多阶段作业排序问题的研究[D];华东理工大学;2019年

6 康宇红;具有错位限制的重新排序问题研究[D];重庆师范大学;2019年

7 姜晓燕;MapReduce排序问题的若干算法研究[D];北京邮电大学;2019年

8 王亚男;具有退化维护和资源分配的单机排序问题[D];沈阳师范大学;2019年

9 李石;与资源相关加工时间可变的单机排序问题[D];沈阳师范大学;2019年

10 高焰红;平行批处理机上不相容族工件的在线排序问题[D];郑州大学;2019年

本文编号：2693437