AGV路径规划设计.doc

安徽工业大学管理科学与工程学院
安徽工业大学

毕业设计(论文)任务书

课题名称
面向AGVs的物流运输系统自动化研究

学 院
管理科学与工程学院
专业班级
工业工程111班
姓 名
金辉
学 号
119094008
毕业设计(论文)的主要内容及要求：
1、调研资料收集：AGV的历史与技术以及国内外应用与发展趋势，AGVs路径规划问题国内外研究现状和优化方法等，其它需要收集的相关资料和数据。
2、查阅文献资料，明确研究方向，运用运筹学的相关理论和方法对AGV系统路径优化问题进行分析和研究，构建图论系统模型和路径规划优化方法。
3、根据路径规划研究方法，进行编程实现路径规划算法，对比路径规划后的实施效果并进行相应的实证研究。
4、基于CAD绘图软件，绘制不少于相当于1张A2工作量的CAD图。
5、开题报告：包括工作任务分析、调研报告、文献综述或现场实习、方案拟定与分析以及实施计划等，开题报告须单独装订。
6、论文说明书的篇幅一般为2.5万字左右。论文撰写按学校《本科生毕业设计撰写规范细则》。中文摘要在300字以内及相应的外文摘要。
7、参考文献不少于20篇，其中外文资料不少于2篇。

指导教师签字：

第III页
摘要
随着生产物流自动化程度的提高，柔性制造系统和自动化立体化仓库等的发展，AGVs(Automated Guided Vehicle system)作为物流系统和柔性制造系统中的关键子系统，得到越来越多的应用。路径规划问题是AGV系统应用中的基本问题之一，对路径规划问题的研究有重要的理论和实践意义。
本文首先介绍AGV的结构组成及其系统组成，了解AGVs的工作模式，对AGVs的工作流程进行分析；其次对单台AGV路径规划优化技术进行研究，在建立电子地图的基础之上，对 Dijkstra 算法进行改进和优化，从而实现单AGV 路径规划；然后针对多台AGVs的无碰撞路径规划问题，采用与时间窗原理相结合的路径规划算法，并提出缓冲时间窗的概念，减少各种因素对算法的影响，使算法在运行过程中具有很好的稳定性和持续性，从而实现多台AGV的无碰撞路径规划；最后编写了C语言代码，实现了实验室单AGV路径规划Dijkstra算法运行程序。
关键词：AGV；路径规划；Dijkstra 算法；时间窗方法；缓冲时间窗

Research on logistics transportation system automation based on AGVs
Abstract
With the improvement of the degree of production logistics automation and the development of flexible manufacturing systems and three-dimensional warehouse automation, AGVs (Automated Guided Vehicle system) have been widely put into use as one of the key subsystems of logistics system and flexible manufacturing systems. Path planning problem is one of the basic problems among the application of AGVs and is of great theoretical and practical importance to the research of path planning problem.
This paper first introduces the structure and system composition of AGV, comprehends the operating mode and analyzes the working process of the AGVs. Secondly, based on the construction of electronic map, the paper studies the path planning optimization technology of single AGV and improves the Dijkstra algorithm, so as to realize single AGV path planning. Then aimed at the collision less path planning problem of more than one AGV, the paper adopts path planning algorithm combined with time window theory, puts forward the concept of buffer time window and reduces the influence of various factors upon the algorithm in order to keep the stability and continuity of the algorithm during the operation process, as thus realize the collision less path planning of more than one AGV. Finally, the C programming language code was written and the Dijkstra algorithm operational procedure of single AGV path planning in lab was realized.
Keywords: AGV；path planning；Dijkstra algorithm；Time window method；Buffer time window

目录
摘要 I
Abstract II
1.绪论 1
1.1 引言 1
1.2 AGV的历史与技术 2
1.2.1 AGV的发展历史 2
1.2.2 现代AGV的技术特点 4
1.3 AGVs在国内应用与发展趋势 5
1.4 AGVs路径规划历史和现状 6
1.5 论文的研究内容和意义 7
1.5.1 研究内容 7
1.5.2 研究的目的及意义 8
2.AGV与AGV系统 9
2.1 AGV的种类与结构 9
2.1.1 AGV的种类 9
2.1.2 AGV的结构 10
2.2 AGVs的总体结构 13
2.2.1 AGVs的组成 13
2.2.2 地面控制系统 13
2.2.3 通讯系统 14
2.2.4 车载控制系统 14
2.2.5 车载导航系统 15
2.2.6 移载系统 15
2.2.7 充电系统 15
2.3 AGV系统的工作模式 16
2.3.1 AGVs的工作特点 16
2.3.2 AGVs的运行模式 16
2.3.3 AGVs的工作流程 17
3.单AGV系统的路径规划 19
3.1 AGVs的路径规划概述 19
3.1.1 全局路径规划 19
3.1.2 局部路径规划 20
3.2 电子地图建模方法 20
3.2.1 可视图法 20
3.2.2 栅格地图法 21
3.2.3 拓扑地图法 22
3.3 基于图论的路径规划 22
3.3.1 图的定义 23
3.3.2 基于图论法的路径规划算法 23
3.3.3 物流综合实验室建模 24
3.3.4 基于Dijkstra算法的路径规划 26
3.3.5 路径分析和算法改进 28
4. 多AGV系统路径规划 29
4.1 多AGV系统的路径规划问题 29
4.1.1 问题的由来 29
4.1.2 冲突的类型 29
4.1.3 AGV冲突解决方法 30
4.2 校图书馆某科室环境建模 31
4.2.1 校图书馆某科室 31
4.2.2 AGV系统模型设定 32
4.3 基于时间窗方法的多AGVs路径规划 33
4.3.1 时间窗方法 33
4.3.2 算法步骤 34
4.3.3 算法实践与路径方案 36
4.3.4 算法不足与改进 38
5. 单AGV路径规划C语言模拟 39
总结与展望 41
致谢 42
主要参考文献 43
附录：单AGV路径规划Dijkstra算法代码 45

1.绪论
1.1 引言
随着工厂生产和物流自动化的显著提高，传统制造业的生产和物料运输方式发生了天翻地覆的变化，从20世纪末，现代制造业就已经迈入自动化、智能化和个性化的崭新时代。柔性制造系统（FMS，Flexible Manufacture System）和立体化智能仓库（SW：Stereoscopic Warehouse）等先进的科学技术在生产制造产业中得到越来越多的广泛应用[1]。我们都知道，生产物流系统技术是先进制造技术中的重要组成部分，随着计算机科学和自动化技术的广泛应用，它已从原来简单的物料搬运发展到现代物流自动化系统，物流管理系统也从原来的简单方式迅速向自动化管理演变，使得物流系统自动化水平得到显著提高。
根据相关文献显示：在整个生产制造过程中，仅仅有20％的成本时间是用于加工和制造，剩余的大部分的80％都用于储存、装卸、等待加工和输送[2]。我国的大多数制造企业属于劳动密集型，也就是主要依靠劳动力来生产制造，然而现在中国劳动力成本在持续增长，中国廉价劳动力的优势已不复存在。因此现在多数企业对于自动化的要求也是越来越高。在这种情况下，AGVs（Automated Guided Vehicle system）作为货物搬运输送系统，能够满足柔性制造系统和立体仓库的要求，是整个物流自动化和生产自动化最关键的部件之一。
AGV（Automated Guided Vehicle）一般被称为自动导引小车[3]，是为了更好地解决物流活动中的智能化、自动化和合理化等问题，从而实现物流系统的时间和空间效益。AGV作为一种智能化移动机器人，拥有着包含环境感知、动态决策与规划、行为控制与执行等多功能于一体的综合系统。AGV集中了传感器技术、机械工程、电子工程、计算机工程、自动化控制工程以及人工智能等多学科的研究成果，代表机电一体化的最高成就，是目前科学技术发展最活跃的领域之一。而且AGVs以其快速、准确的运输、便于计算机管理与调度、能够自主导航、自动规划路径和执行任务和更有利于劳动安全保障的实施等优点已被广泛应用于制造业、农业和服务业等各个领域。因此AGVs是整个物流自动化和生产自动化最关键的部件之一[3]。
随着现代AGV性能不断地提高，其应用范围不断扩展，不仅将在工业、农业、国防、医疗、服务等行业中得到广泛的应用，而且将在排险、搜捕、救援、强辐射等危险环境下得到很好的应用，几乎适合于仓储、制造、邮政、图书馆、港口、机场、烟草、医药、食品、化工等各种场合。因此，AGV技术已经得到世界各国的普遍认可。

1.2 AGV的历史与技术
1.2.1 AGV的发展历史
根据美国物流协会的定义，AGV是指装备有电磁或光学自动导引装置，能够沿规定的导引路径行驶的运输小车，同时还具有小车编程与停车选择装置、安全保护装置以及各种移载功能[3]。AGV是现代物流系统的关键设备之一，与其他物料配送运输设备相比，AGV具有其独特的先进性和优越性，由计算机控制进行自主导航，可以自动规划路径和完成任务等无人化、自动化先进技术；也可完成不适合工作人员进入的某些工作场合去完成工作；对那些劳动强度大或者要求工作精度高的工作环境，AGVs可以较为完美的完成这些任务。
1913年，美国福特汽车公司首次将有轨导引的AGV用于汽车制造生产中的底盘装配生产线上。这是AGV第一次出现在制造业的舞台上。随着科学技术的进一步发展，到1953年，世界上真正意义上的第一台AGV是由美国Barrett电子公司开发成功的，它是一种牵引式小车系统，可十分方便地与其他物流系统自动连接，显著地提高劳动生产率，极大地提高了装卸搬运的自动化程度。1954年英国最早研制了电磁感应导向的AGV，基本的导引技术是靠感应埋在地下的导线产生的电磁频率。通过一个叫做“地面控制器”的设备打开或关闭导线中的频率，从而指引AGV沿着预定的路径行驶。由于它的显著特点，迅速得到了应用和推广。
从20世纪50年代末到60年代初期，计算机技术开始应用到自动化生产线上，出现了最初的计算机控制系统。这一时期就有多种类型的AGV用于工厂和仓库，1960年欧洲就安装了各种形式、不同水平的AGVs220套，使用AGV1300多台。20世纪70年代，由于欧洲的公司对托盘的尺寸和结构进行的标准化，促进了AGV的进一步发展。70年代中期，由于微处理器技术和计算机技术的相结合发展，伺服驱动技术的成功促进了复杂控制系统的改进，并设计出更为灵活的AGV。1973年，瑞典的VOLVO汽车公司和Schindler-Dighton公司就联合研发了多种AGV，并在KALMAR轿车厂的装配线上大量采用了AGV进行计算机控制装配作业，扩大了AGV的使用范围。70年代末，欧洲约装备了520个AGV系统，共有4800台小车。其应用领域分布为：汽车工业（57%），柔性制造系统FMS(8%)和柔性装配系统FAS(44%)。当时，欧洲的AGV的发展很快，已经成为AGV技术研发与运用的中心，为各大企业带来了巨大的经济效益。
20世纪80年代初，欧洲的技术就开始向美国转移，此时美国的AGV生产厂商从1983年的23家剧增至1985年的74家。美国各公司在欧洲技术的基础上，将AGV发展到更加先进的水平。这一时期，无线导引技术也开始引入到AGV系统中，而且系统也可以在线自动充电，24小时不间断运行，充分表现出AGV系统较好的灵活性、准确性和可靠性。1984年，美国通用汽车公司完成了它的第一个柔性装配系统(FAS),从此该公司就成为当时AGV的最大用户。1986年已达1407台，1987年又新增加1662台。到目前为止,全世界已拥有AGV系统15000多组，约100000辆AGV。AGV的发展主要依赖于经济的发展和科技的进步。AGV是替代高吊的人力劳动的高科技产物。
AGV技术被引入亚洲是日本于1963年，其第一家AGV工厂于1966年由一家运输设备供应厂商与美国的Webb公司合资建成。1976年后，日本对AGV的发展给予了高度重视，每年增加数十套AGV系统，有神钢电机、平田电机、住友重机等27个主要生产厂商生产几十种不同类型的AGV。1981年，日本的AGV总产值为60亿日元，1985年已上升到200亿日元，平均每年以20%的速度递增，1986年，日本累计安装了2312个AGVs，拥有5032台AGV，到1990年日本拥有AGV约一万台。到1988年，日本AGV制造厂已达47家，如大福、Fanuc公司、Murata(村田)公司等，广泛应用于汽车制造、机械、电子、钢铁、化工、医药、印刷、仓储、运输业和商业上。
我国AGV的研制和应用起步比较晚，原因是人力资源成本低和工厂自动化程度低两个主要因素导致了国内的AGV研究和应用起步以及其发展均较为缓慢。不过其发展历程虽短，但一直以来不断加大在这一领域的投入，以改变我国AGV长期依赖进口的局面。1976年，北京起重机械研究所研制出第一台AGV，建成第一套AGV滚珠加工演示系统，随后又研制出单向运行载重500公斤的AGV，双向运行载重500kg、1000kg、2000kg的AGV，开发研制了几套较简单的AGV应用系统。1988年，原邮电部北京邮政科学技术研究所研制了邮政枢纽AGV。1989年，北京机械工业自动化研究所为二汽研制了应用在立体化仓库中的AGV。90年代，清华大学国家CIMS工程中心将从国外引进的AGV成功的应用于EIMS的实验研究。1991年起，中科院沈阳自动化研究所和新松机器人自动化股份研究公司为沈阳金杯汽车厂研制生产了客车6台AGV用于汽车装配线中，可以说这是我国汽车工业中用得比较成功的例子，并于1996年获国家科学技术进步三等奖。1992年，天津理工学院研制了核电站用光学导引AGV。1995年，我国的AGV技术出口韩国，标志着我国自主研发的机器人技术第一次走向了国际市场。1998年，昆明船舶设备集团公司在红河卷烟厂研制了多模式激光导引无人自动车22辆。红河项目于2002年获国家科学技术进步二等奖。在国内AGV的技术来源有两种模式：一种是引进技术；一种是自有知识产权的技术。两种模式目前都涵盖AGV的所有技术，技术水平并无多大差别。引进技术主要是瑞典NDC的AGV控制系统技术。
20世纪末到21世纪初，随着电子技术和计算机技术等高科技的迅速发展，AGV的硬件设备和智能化程度都上了一个新的台阶。微控制器技术已经广泛应用于AGV的各个功能模块，因此AGV正在往智能化、自动化的方向发展。一些新的控制方法正在逐渐应用到实际生活中，各种机器人控制领域的新方法和新策略正在开始逐步应用到AGV系统中。AGV发展到今天，已经深入到社会生产生活的各个领域，广泛应用于汽车制造、机械、电子、钢铁、化工、医药、印刷、仓储、运输业和商业上。

1.2.2 现代AGV的技术特点
AGV作为联系和调节物流运输管理系统使其作业智能化的必要的搬运装卸手段，其应用范围和技术水平得到了迅猛的发展。在最近的十几年里，各种新型AGV被广泛应用于工业生产的各个领域中。
现代AGV技术的最显著特征是其智能化得到了明显的提高。由于车载计算机的硬软件功能日益强大，使AGV具有从网络、无线或红外信号接受装置接收调度中心或客户的指令、自动导引、自主行驶、优化路线、自动作业、运行管理、车辆调度、安全避碰、自动充电和自动诊断等功能，实现了AGV的智能化、信息化、数字化、网络化、柔性化、敏捷化、节能化、绿色化。现代AGV是可以24小时不停工作的智能化车辆(只要给与其充足的能源)，就能主动、自序、有节拍的按最短和最安全的路线去完成任务。智能化和动力强劲等特点，将使AGV具有日益广泛的用途。
现代AGV设计的显著进步是其动力源装置的设计。由于动力源的功率大小直接影响AGV的运行功能，而动力源的体积大小将直接影响整车的体积及外观造型[4]。传统的AGV采用铅酸电池，能量密度小，体积大。近年来，随着电池能源技术的快速发展，电池由原来的高能酸性电池，改用现在的高能碱性电池，以提高电池的环保性能。现代AGV的快速充电技术使充电时间：放电时间由原来的1：1提高到1：12，大幅缩短了AGV的待机充电的时间。动力电池性能的改进与快速充电技术的使用，使得现代AGV的动力性能普遍提高，运载能力与行驶特性得到了进一步的优化。
由于智能机器人技术的引进，AGV的机器人化就成为了现代AGV研究的热点话题[5]。实际上，在智能机器人的整个发展历史过程中，其许多相关技术都先后应用于AGV技术发展过程中。如智能移动机器人技术涉及到的机器人导航与定位、路径规划、运动控制等，均在AGV中得到了体现，使得现代AGV无论是专项技术，还是综合性能，均得到了普遍提高，并仍将继续提高。由于AGV的智能化，现代AGV已不仅仅只是沿固定铺设轨道行驶的物流运输工具，几乎可以适合于各种物流环境中。
现代AGV的还有个显著特点是无人驾驶。它可以保障系统在不需要人工导航的情况下自动行驶和自动搬运，柔性好、自动化和智能化水平高。AGV可以根据仓库货位要求和生产工艺流程等做出改变，并且改变铺设轨道的成本与传统的输送带或传送带相比非常低廉。如果配有移载装置，AGV还可以与其他物流设备自动接口，实现制造生产和物流运输全过程自动化。此外，现代AGV还具有清洁生产的特点，AGV依靠自带的蓄电池提供动力，运行过程噪声极低、无污染，可以应用在许多要求工作环境清洁的场所。
由于现代AGV系统在应用上的灵活性和准确性得到很大地提高，许多先进的导引方式的引入，使得AGV小车的导引方式更加多样化从而形成了一个新的产业，主要可以概括为两种发展模式：第一种是全自动AGV技术，这类技术追求AGV的自动化，几乎完全不需要人工的干预，其路径规划和生产流程复杂多变，基本能够运用在所有的物流领域，在欧美国家应用广泛。这些AGV的功能完善、技术先进，采用模块化设计，已经形成了一套生产标准，但是此类AGV价格昂贵，降低了它的市场占有率；第二种是简易型AGV,该技术可以实现AGVs的最佳性价比，让用户可以在较短的时间内收回成本，日本在这方面技术处于世界领先水平，因此这类AGV在日本企业得到了广泛使用。

图1-1 简易型自动导引小车（AGV） 图1-2 电磁式自动导引小车（AGV）

图1-3 汽车制造现场的AGV 图1-4 仓库运输系统的AGV
1.3 AGVs在国内应用与发展趋势
在中国, 随着计算机硬件技术、并行分析与处理技术、自动控制技术、传感器技术以及软件开发环境等先进技术的不断发展, 为AGVs的研究与应用提供了必要的技术基础。近年来，随着工厂物流自动化、计算机集成制造系统技术的逐步发展，以及柔性制造系统和自动化立体仓库的广泛应用，对生产线运行、物流系统的柔性要求越来越高。在这种良好的背景环境下，AGVs将会在国内得到一个很好的发展机会。
近年来，随着国内人力资源成本的不断上涨，全国各地制造产业都出现了严重的用工荒现象，生产自动化和物流运输自动化的需求日益迫切。2013年6月18日，广东省召开了全国首届“中国AGV应用与产业发展论坛”。2014年4月3日广州市政府常务会议审议通过了《广州市推动工业机器人及智能装备产业发展的实施意见》，将大力推动广州市工业AGV产业发展，促进产业转型升级，所以AGV行业将迎来一轮快速发展的黄金时期。
中国对AGVs的研究主要集中在电机驱动技术、电池能源技术、车辆制造技术、导引导航技术、自动控制技术、通讯技术和移载技术等方面，如表1-1,给出了上述技术在中国的研究成熟度，表1-2给出了各种导引导航技术在中国的研究的成熟度、专利、应用现状和发展前景。
表1-1 AGV技术在中国的研究成熟度
技术名称
成熟度
技术名称
成熟度
电机驱动技术
成熟
自动控制技术
相对成熟
电池能源技术
相对成熟
通讯技术
相对成熟
车辆制造技术
成熟
移载技术
成熟
导引导航技术
相对成熟

表1-2 各种导引导航技术的比较
技术名称
成熟度
技术难度
成本
专利
应用现状
先进性
应用前景
电磁导引
成熟
中
低
无
较广
一般
较好
激光导引
较成熟
高
高
有
广
较先进
好
超声导引
较成熟
高
高
未知
少
一般
一般
视觉导引
不成熟
高
高
有
少
较先进
很好
惯性导引
成熟
中
低
无
广
一般
好
GPS导引
较成熟
高
高
无
少
一般
一般
AGV系统大大减轻了劳动强度和危险性，提高了工作效率，在制造、家电、钢铁、化工、纺织、卷烟等行业都已经发挥重要作用。国内AGV应用需求现已不仅仅局限于传统制造行业，在医药、港口、服务业等行业的需求也在日益扩大。尤其是在要求高度自动化的民航、邮政等行业，要求高度清洁的医药、食品加工等行业，还有核材料、感光材料等特种行业都有着广阔的应用前景[6]。
1.4 AGVs路径规划历史和现状
路径规划是指，在具有障碍物的环境中，按照一定的评价标准，机器人寻找一条从起始状态到目标状态的最优或次优路径。AGV的路径规划就是根据给定的起点和终点选择一条最佳的行走路径[6]。
国内外许多学者都对路径规划有过深入研究并在这一领域取得了很大的成就。根据对现场环境建模方式的不同，传统的全局路径规划方法主要有：自由空间法、图搜索法、栅格法、人工势场法等。LING QIU和WEN-JING HSU综述了AGV的路径规划和调度的算法,对于全局环境相关信息完全已知的全局路径规划的研究一般分为两个研究方向，即传统路径规划方法和人工智能规划方法。
AGV与移动机器人在运行方式上有极大相似之处，所以可以认为对移动机器人路径规划算法和对AGV的路径规划算法是相同的。随着国内外学者对人工智能的研究，逐渐提出了多种智能规划方法，其中应用较为广泛的主要有：蚁群算法、A*算法、Dijkstra算法、神经网络算法和模糊控制方法[7]。
周明等提出了利用遗传算法对在连续空间中运行的AGV进行路径规划的方法，该方法首先需要建立环境模型，调用算法搜索从起始点到目标点的多条路径，在此基础之上利用遗传算法对已搜索到的路径逐步优化、不断比较从而得到最优路径[8]。庄晓东等提出一种基于模糊概念的动态环境模型，在此模型的基础上通过构造二维隶属度函数，对路径进行模糊评价从而得到最优路径，此算法主要应用在动态路径规划环境中[9]。
目前国内外学者在多AGVs的路径规划和整体调度方面也做了很多研究，使用的路径规划方法主要包括优先级法、交通规则法、速度调整法和几何路径调整法等。速度调节法是通过改变AGV的运行速度来实现多个AGV之间的协调以避免发生碰撞；几何路径调整法是当路径规划发生冲突的时候通过重新搜索路径避免AGV之间发生碰撞。
刘国栋对多AGV调度系统提出了一种两阶段动态路径规划策略[10]。Kim和Tanchoco提出一种基于Dijkstra的最短路径算法。FISHER提出拉格朗日松弛启发式算法来解决基于时间窗的路径规划问题。Bennexitz等通过动态调节优先级顺序方法优化得到行驶路径[11]。
1.5 论文的研究内容和意义
1.5.1 研究内容
本论文根据学校物流综合实验室和图书馆某科室的布局提出AGVs的路径规划问题。从而解决AGVs路径规划问题中可能出现的问题，进行路径规划算法和优化方法的研究。本文主要研究内容如下：
（1）介绍AGV与AGVs的整体结构和组成系统，了解AGVs的工作模式和工作流程，从而体现出AGVs路径规划问题在整个物流运输系统的重要性。
（2）针对物流综合实验室和图书馆某科室的工作环境和布局，基于图论法创建与现实环境对应的电子地图。根据电子地图作出AGVs运行路径图。
（3）分析学校物流综合实验室的物流特性，利用研发式搜索算法和Dijkstra算法进行单AGV路径规划，再考虑实际情况和其他因素，对Dijkstra算法进行改进，得出优化后的AGV的行走路径图和解决方法。
（4）对于多AGV系统的路径规划问题，我们主要研究的是如何解决系统中冲突和死锁等问题。根据图书馆某科室借还书物流系统运用AGV系统实现物流自动化，基于时间窗方法和Dijkstra算法相结合的方法，来进行多AGV的路径规划。
（5）编写了C语言代码，实现了实验室单AGV路径规划Dijkstra算法运行程序。进一步验证了算法的可行性。

技术路线方案如下：
和意义
确定研究方向、目的

图书馆借阅书籍，购买书籍
学习相关理论知识
收集相关文献资料

访问数据库收集相关文献资料

请教导师

AGVs的材料
整理有关AGV与
AGV

AGVs
优化路径图
Dijkstra算法，作出
对比两种算法，选择

物流综合实验室建模
作物流路径图

学习路径规划需要
A*算法和Dijkstra算法

化路径运行图
作出单AGV优

对Dijkstra算法进行改进
得出最终的物流路径优化方案
考虑综合因素

Dijkstra算法
提出多AGV问题

时间窗方法
寻找解决方案
图书馆某科室建模
作物流路径图

总结分析
提出不足

提出解决方法
得出最终路径规划方法
多AGV路径规划方法
作出路径规划图

图1-5 论文技术路线图
1.5.2 研究的目的及意义
本文研究的目的是基于国内企业物流运输系统改革与国内AGV技术的兴起这一背景，在国内外学者研究的基础上，以学校的物流综合实验室和图书馆某科室为例，对AGV系统路径搜索及其优化进行研究，从而研究出AGVs路径规划问题中寻找最优或次优路径的办法，使其运用到实际应用当中去，实现智能化仓库AGV系统智能化和自动化。

2.AGV与AGV系统
2.1 AGV的种类与结构
2.1.1 AGV的种类
AGV从发明至今已经有60多年的历史，在这漫长的历史长河之中，随着其应用领域的不断扩大，其种类和形式也变得多种多样。按不同的分类标准，可以有不同的分类方法。主要有以下几种分类方式：
根据小车运行时有无固定轨道划分，可以分为有轨式AGV和无轨 式AGV。有轨式AGV是需要运行的线路上铺设轨道，AGV小车只能沿着固定的轨道运行，导引技术较为简单，但铺设轨道与更改轨道的工作量大，使得AGV系统灵活性差，是早期经常采用的一种技术，但现在不少对技术要求较低的工作环境还在普遍使用；无轨式AGV没有轨道，将显示环境中的路径通过坐标或拓扑的形式存储到电子计算机中，通过坐标数据交换的方式得到AGV在现实环境中的位置并与虚拟路径进行对应，所以系统具有良好的柔性。因此近年来无轨式AGV的应用越来越广泛。但受技术限制，无轨式AGV仍存在诸多技术问题。
根据小车运行时智能程度划分，可以分为智能型AGV和普通型AGV两种：智能型AGV是将全部运行路线和线路信息存储在每台AGV的车载控制系统中，当小车得到指令确定了起始点和目标点后就可以自动搜索并选择最优路径到达指定目标点完成指定的运输或装卸任务，对于由50台以内AGV构成的系统多数采用这种控制方式工作。随着系统中AGV的数量增加，交通管理和发生碰撞的策略就会越来越困难；普通型AGV小车的车载控制系统一般比较简单，仅仅通过传感器收集小车的位置和姿态信息，控制小车的运行速度和方向，各AGV之间不相互通讯，只是每隔一段时间与地面控制系统交换数据。其本身的所有功能路线规划和区段控制都由地面控制系统进行控制，其地面控制系统结构比较复杂，包括地图建模、路径规划、车辆管理、实时监控等一系列功能。此类AGV一般用来组成最多大约200台小车的AGVs。
根据小车运行时导引方式划分，AGV可以分为惯性导引、电磁导引、光/化学/磁感应式导引、红外线导引、激光导引、直接坐标导引、信标导引、视觉导引等方式。下面介绍主要的几种导引式AGV：
（1）电磁感应导引式AGV
电磁感应导引式AGV一般都会在地面下沿预先设定的行驶路线埋设电线，当高频电流流经电线时，电线周围就会产生电磁场，小车上左右对称安装了两个电磁感应器，它们所接收的电磁信号的强度差异就可以改变AGV偏离路径的程度。AGV的导航导引系统根据这种信号来控制车辆的转向，连续的动态闭环控制可以保证AGV对预定路径的稳定自动跟踪。这种电磁感应导引式方法在目前绝大多数商业化的AGVs上都有使用，尤其是大中型的AGV系统。
（2）激光导引式AGV
激光导引技术是上个世纪90年代开始采用的，该种AGV的车身上安装有可旋转的激光扫描器，在小车运行路径的墙壁或支柱上都安装有具有高反光性的激光定位装置，AGV利用激光扫描器发射激光束，然后通过由四周定位装置反射回来的激光束，车载控制系统就能计算出小车当前所处的位置，通过和系统内的数字地图进行对比来路径规划，从而实现自主导航、自动行驶。目前，该种导引方式的应用越来越普遍，并且依据同样的导引原理，可将激光导引式AGV变成红外线导引式AGV和超声波导引式AGV。
（3）视觉导引式AGV
视觉导引式AGV是正在快速发展和成熟的AGV，该种AGV上装有CCD摄像机和传感器，在车载计算机中设置有AGV行驶路径周围环境图像数据库[12]。AGV运行过程中，摄像机动态获取小车周围环境图像信息并与地面控制系统进行比较，从而确定AGV所处位置并对下一步行驶做出规划。这种导引方式由于不需要人为设置任何物理路径，因此在理论上具有最佳的导引柔性。随着计算机图像采集、储存和处理技术的快速发展，该种导引方式的实用性越来越强。
2.1.2 AGV的结构
AGV主要是由机械系统、动力系统、车载控制系统和通讯系统组成。其中机械系统由车身、车轮、驱动转向系统、安全防护装置、移载系统等构成，保证了小车的承载能力和运行性能；动力系统由驱动电机、转向电机、移载电机、蓄电池和充电装置等装置构成，为AGV的正常运转提供动力来源；车载控制系统由人机界面、信息传输及处理系统、导航定位系统等构成，确保了小车的正确安全智能地按照预定路径正确运行；通讯系统就是负责AGV与主控机之间进行双向传输信息的系统。

机械系统

A
G
V

动力系统

车载控制系统

通讯系统

图 2-1 AGV的结构

（一）机械系统
（1）车身
车身主要为钢材结构,是AGV最基础的部分，是整个AGV的“脊柱”。车身一般由底盘架和结构架两个部分构成，其中底盘架为立体型框架结构，用于安装驱动转向系统、移载系统、机械防撞装置、各种电机、蓄电池等；而结构架则用于安装各种控制设备和通讯设备。为了便于安装和维修，通常底盘架和结构架之间采用可拆卸的方式联接。
（2）车轮
车轮是整个AGV的“脚”，外层一般使用树脂橡胶材料做成，具有强度高、耐磨损、稳定性高、拥有一定的弹性等优点，适合于AGV系统的使用。
（3）驱动转向系统
AGV的驱动转向系统包括行进系统和转向系统，是整个AGV的“四肢”。他的性能直接影响到AGV的运动性能，并在一定程度上影响到自动导航系统的动态调节性能。根据不同需求AGV可采用双轮驱动差速转向和双轮驱动独立转向方式，我们需要根据实际需求选择合适的驱动方式。AGV的驱动转向系统结构简图如下：

1-连接板；2-螺栓；3-驱动电机；4-转向减速电机；5-转向齿轮副；6-减速直齿轮副；
7-减速（转向）锥齿轮副；8-减速箱箱体；9-行星齿轮副；10-行走轮。
图2-2 驱动转向系统结构简图
（4）安全防护装置
AGV作为自动化机器人的一种，安全措施至关重要。车身上必须安装障碍物接近报警装置，是为了避免AGV小车碰撞，确保整个运行过程中的人身安全和财产安全。同时也必须安装障碍物接触式缓冲器，这种装置一般同时安装在AGV车身的前后方，缓冲器的材质具有一定的柔软性，保证发生故障时不会造成太大的损失。
（5）移载系统
将货物自动装到AGV载货台上或从AGV载货台上取下货物并放置到指定位置的过程叫做移载。根据不同的工作环境，AGV可以装备不同的移载装置，如：叉车式、牵引式、辊道式等。

（二）动力系统
（1）电机
电机是给AGV运行过程中提供动力的，AGV主要需要驱动电机、转向电机和移载电机。目前比较常用的AGV驱动系统有：直流电机驱动系统、感应电机交流驱动系统和永磁同步电机交流驱动系统。其中由于直流电机驱动