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

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

论文摘要

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

论文目录

  • 摘要
  • Abstract
  • 专用术语注释表
  • 第一章 绪论
  •   1.1 研究背景及意义
  •   1.2 国内外研究现状与分析
  •     1.2.1 AGV的导航方式
  •     1.2.2 多任务分配国内外发展现状
  •     1.2.3 多路径规划技术国内外发展现状
  •   1.3 本文的主要研究内容
  •   1.4 本文的组织结构
  • 第二章 多AGV控制系统关键技术与理论
  •   2.1 引言
  •   2.2 多AGV控制系统分类
  •     2.2.1 集中式控制系统
  •     2.2.2 分布式控制系统
  •   2.3 分布式多AGV系统结构与功能
  •   2.4 AGV控制系统的关键技术
  •     2.4.1 AGV运行环境建模
  •     2.4.2 AGV任务分配
  •     2.4.3 单AGV路径规划
  •   2.5 本章小结
  • 第三章 高效的2-opt算符处理AGV任务排序问题
  •   3.1 引言
  •   3.2 基于辅助数据结构的高效2-opt移动运算符
  •     3.2.1 2-opt局部搜索算符的基本原理
  •     3.2.2 高效的计算每个2-opt移动
  •     3.2.3 算法复杂度分析
  •   3.3 实验结果分析
  •   3.4 本章小结
  • 第四章 基于MCTS和变邻域LS的AGV动态多任务排序
  •   4.1 引言
  •   4.2 改进的动态蒙特卡罗树搜索和变邻域局部搜索算法
  •     4.2.1 算法框架
  •     4.2.2 改进的动态蒙特卡罗树搜索算法
  •     4.2.3 3-opt局部搜索算符的基本原理
  •     4.2.4 基于2-opt和3-opt的变邻域局部搜索
  •   4.3 实验结果分析
  •     4.3.1 实验方案
  •     4.3.2 实验结果
  •   4.4 本章小结
  • *算法与博弈论的多AGV路径规划'>第五章 基于改进A*算法与博弈论的多AGV路径规划
  •   5.1 引言
  •   5.2 问题描述
  • *算法的AGV路径规划'>  5.3 基于改进的A*算法的AGV路径规划
  • *算法的基本原理'>    5.3.1 A*算法的基本原理
  •     5.3.2 引入双向搜索机制和路径优化
  •     5.3.3 实验仿真分析
  •   5.4 基于博弈论的多AGV冲突消解
  •     5.4.1 博弈论的基本理论
  •     5.4.2 多AGV路径冲突分类
  •     5.4.3 多AGV冲突消解博弈模型
  •   5.5 实验结果分析
  •   5.6 本章小结
  • 第六章 总结与展望
  •   6.1 总结
  •   6.2 展望
  • 参考文献
  • 附录1 攻读硕士学位期间撰写的论文
  • 附录2 攻读硕士学位期间申请的专利
  • 致谢
  • 文章来源

    类型: 硕士论文

    作者: 李红

    导师: 罗杰

    关键词: 分布式系统,动态多任务排序,路径规划,冲突消解

    来源: 南京邮电大学

    年度: 2019

    分类: 基础科学,信息科技

    专业: 数学,自动化技术

    单位: 南京邮电大学

    分类号: TP242;O221

    DOI: 10.27251/d.cnki.gnjdc.2019.000897

    总页数: 66

    文件大小: 1970K

    下载量: 892

    相关论文文献

    • [1].目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报 2019(04)
    • [2].具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报 2019(04)
    • [3].基于Flexsim的零件加工排序仿真实现方法研究[J]. 新技术新工艺 2020(02)
    • [4].总加权误工损失的两个代理单机排序问题[J]. 湖北民族学院学报(自然科学版) 2019(01)
    • [5].机器带周期性维护时段的加工与运输协同排序问题[J]. 浙江理工大学学报(自然科学版) 2016(06)
    • [6].带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报 2016(04)
    • [7].具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J]. 沈阳航空航天大学学报 2016(06)
    • [8].关于工期分配与加权误工数的双指标排序问题(英文)[J]. 工程数学学报 2017(01)
    • [9].带有交货期窗口和加工时间可控的排序问题[J]. 沈阳师范大学学报(自然科学版) 2016(04)
    • [10].具有学习效应和遗忘效应的单机排序问题研究[J]. 枣庄学院学报 2017(02)
    • [11].资源定时投放的单机排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(02)
    • [12].有公共交货期的单机分批排序问题(英文)[J]. 重庆师范大学学报(自然科学版) 2017(02)
    • [13].在退化维修活动下具有多窗口及退化效应的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)
    • [14].一类资源费用可变的平行机排序问题[J]. 上海第二工业大学学报 2017(02)
    • [15].数学规划与约束规划整合下的多目标分组排序问题研究[J]. 运筹学学报 2016(01)
    • [16].具有学习效应的排序问题的某些新进展[J]. 沈阳师范大学学报(自然科学版) 2014(04)
    • [17].有界平行批处理机的在线排序问题[J]. 河南师范大学学报(自然科学版) 2015(05)
    • [18].集思[J]. 福建教育 2020(25)
    • [19].高中数学一道数列典型题解法的探究[J]. 数学学习与研究 2016(23)
    • [20].单机排序问题的研究[J]. 数学学习与研究 2017(24)
    • [21].一个排序问题的解决[J]. 中等数学 2009(07)
    • [22].具有多个制造商和分批配送的同类机排序问题[J]. 系统科学与数学 2019(09)
    • [23].工件具有加工位置上限最小化加权总误工量的单机排序问题(英文)[J]. 运筹学学报 2020(02)
    • [24].具有恶化效应与可控加工时间的工期指派排序问题研究[J]. 沈阳航空航天大学学报 2019(05)
    • [25].优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报 2016(04)
    • [26].具有公共流、退化效应与维护和资源分配的单机窗口排序问题[J]. 沈阳航空航天大学学报 2016(05)
    • [27].关于总误工损失的两个代理单机排序问题[J]. 运筹学学报 2017(01)
    • [28].具有不同生产时区费用的单机可拒绝排序问题[J]. 数学的实践与认识 2017(04)
    • [29].具有柔性维护周期的单机误工排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(03)
    • [30].带有多个工期窗口及退化维护的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)

    标签:;  ;  ;  ;  

    多AGV的多任务分配与路径规划研究
    下载Doc文档

    猜你喜欢