AGV 调度系统设计

郑州大学毕业设计（论文）题目AGV 调度系统设计院系国际学院专业机械工程及其自动化年级学生姓名指导教师20XX 年X月X 日郑州大学学士学位论文AGV 调度系统设计摘要近年来，随着现代制造业的高速发展以及国内人力成本的不断提高，现代工厂对生产力、鲁棒性的要求不断提高，AGV 作为作为现代制造系统里的一个新兴的子系统，可以根据生产需要、工艺流程、仓储要求等突发情况随时对调度系统进行调整，极大地降低了生产车间对人力资源的需求量，实现了 AGV 小车与主系统之间物流联通的信息化，增强了整个制造系统的鲁棒性，没有局限性、效率低、货物破损率高等传统物流过程中经常出现的问题，有自动化程度高、安全可靠、人力需求很少、施工铺设轨道以及建立系统较为简单且维修方便、与传统的输送带和传送线相比运行过程中无噪音无污染运行成本低廉等优点，因而 AGV 被广泛地应用于汽车制造行业、烟草行业、工程机械制造行业、机场码头邮局等物资运输场所等在国内外的现代智能工厂改造中得到了越来越多的应用。本文针对 XXXX 智能工厂改造方案的子方案“AGV 小车调度系统设计”进行研究。了解 AGV 的定义、路径导引方式、控制以及通讯的基本原理，AGV 小车系统的历史背景、特点以及应用范围；研究 AGV 小车的调度原理和方法，结合实际情况在给出的车间草图基础上铺设 AGV 小车的路径；用 Visio 建立调度流程图对调度流程进行描述；了解以路径最短为原则求最优解的算法有哪些并结合实际情况选择 Dijkstra 算法作为研究内容；设立一些假设来简化课题并以路径最短为原则使用 Dijkstra 算法求最优解；熟悉 C 语言知识，针对已经完成的优化算法使用 C 语言编程进行描述。关键词：AGV、调度、Dijkstra 算法、C 语言AbstractIn recent years, with the rapid development of modern manufacturing industry and the continuous improvement of domestic labor costs, modern factory for the requirement of increasing the productivity, robustness, AGV as a modern I郑州大学学士学位论文AGV 调度系统设计manufacturing system, a new subsystem, can according to production needs, process, storage and other emergency at any time to adjust dispatching system, significantly reduced the demand for human resources in the workshop, with the main system for logistics information of unicom, enhanced the robustness of the manufacturing system, no limitations, low efficiency and high goods breakage problems that often appear in the process of traditional logistics, have a high degree of automation, safe and reliable, human needs few laying track, construction and building system is relatively simple and convenient maintenance, compared with the conventional conveyor belt and transmission line operation no noise pollution in the process of the advantages of low cost, thus AGV is widely used in automobile manufacturing industry, the tobacco industry, engineering machinery manufacturing industry, airport terminal post offices and other places of goods transportation at home and abroad, such as the reform of the modern intelligent factory got more and more applications.In the light of the son XXXX intelligent plant retrofit scheme plan AGV vehicle scheduling system design for research. Understand the definition of AGV, route guidance method, control and communications, the basic principle of the historical background of AGV car system, characteristics and application scope; Study of AGV car scheduling principle and method of combining actual situation on the basis of given workshop sketches laid the path of the AGV car; Description of scheduling process is established using Visio scheduling flow chart; Know the optimal solution based on principles of shortest path algorithm and combined with actual situation choice Dijkstra algorithm as the research content; Set up hypothesis and with the principle of the shortest path for the principle using the Dijkstra algorithm the optimal solution; Familiar with C language knowledge, in view of the completed optimization algorithm using C language programming is described.Key words: AGV, scheduling, Dijkstra algorithm, C languageII郑州大学学士学位论文AGV 调度系统设计目录摘要.IAbstract.I目录.III第一章绪论.11.1课题的背景.11.1.1AGV 概述.11.1.2AGV 的特点.11.1.3AGV 的应用.21.2选题的目的意义.51.3国内外研究概况.71.4本文研究内容.91.5本章小结.11第二章AGV 小车路径设计.122.1XXXX 裁剪车间智能化改造整体方案.122.1.1 集团目前生产流程分析.122.1.2总体示意图.122.1.3总体方案图.132.2模型简化.162.3AGV 小车轨道铺设.172.4本章小结.17第三章AGV 小车路径优化.193.1AGV 小车调度流程.193.2任务与 AGV 小车的匹配问题.213.3选择算法.223.4利用 Dijkstra 算法求解最短路径.253.5本章小结.32第四章优化算法编程.334.1C 语言.33III郑州大学学士学位论文AGV 调度系统设计4.1.1C 语言的历史背景.334.1.2C 语言的特点.344.2运行 C 程序的步骤与方法.354.2.1运行 C 程序的步骤.354.2.2上机运行 C 程序的方法.354.2.3用 C 语言描述 Dijkstra 算法.354.3仿真.404.4本章小结.41第五章总结.42致谢.43参考文献.44IV郑州大学学士学位论文AGV 调度系统设计第一章绪论1.1课题的背景1.1.1AGV 概述AGV（Automated Guided Vehicle）经常是指那些以电磁或光学为导引装置，按照规定的路径行驶，且同时具有安全保护和运载能力的的车辆，但由于其拥有可操控、智能化和即时信息交流等特点 AGV 属于轮式运动机器人 WMR（WheeledMobile Robot）的范围内。可以以充电蓄电池为动力，在人力成本高昂、高危环境等不利条件下不需要驾驶员的物流运输车辆。其控制以及调度通常通过电脑主系统收集信息分析判断后进行处理，行动方面有时也有沿着预先铺设好的电磁轨道(electromagneticpath-followingsystem)作为设定运行线路，AGV 小车通过电磁轨道所提供的信号进行移动。1.1.2AGV 的特点AGV 小车与传统的车间物流工具相比具有以下特点：1、降低劳力需求；2、拥有良好的鲁棒性和柔性；3、系统不会因少数 AGV 因突发情况无法工作而陷入瘫痪；4、提高了产品物流过程中的安全性和可靠性；5、空间占用率小；6、能耗少；7、易于安装维护；8、投入成本较高，回报期相对较长；9、自动化水平高与其它自动化系统相配合时会非常方便快捷；1郑州大学学士学位论文AGV 调度系统设计10、AGV 小车对比如强光、风沙、雨雪天气等恶劣的户外环境适应性不强，所以 AGV 小车一般只能在相对稳定的室内环境如车间中使用；11、采用磁导的 AGV 小车不能在金属材质的地面上通行。1.1.3AGV 的应用AGV 系统在制造业中有非常广泛的应用，重要用于仓储、加工制造、产品装配、物料分发等方面。1、仓储业AGV 系统最早得到应用的场所就是仓储业。目前世界上大约有两千多座大小仓库采用了 AGV 系统进行仓储运输，两万多台 AGV 小车在此过程中被使用。根据某研发组织所发布的消息，2000 年，海尔集团在其投资建设的智能立体仓库中使用了柔性 AGV 小车搬运系统，数台 AGV 小车每日可完成两万余次仓储运输任务。仓储企业在发展过程中采用传统的人工搬运作业方式通常情况下是适应不了其企业的规模发展，原因主要有两个方面：第一，随着货物搬运需求的快速增长，落后的人力搬运作业方法通常会伴随着较高的货物破损率和低下的效率；第二，传统的人工搬运作业方式会使仓储企业的自动化、信息化、智能化程度较低，对于大量的仓储任务不便于管理和信息反馈。2、制造业AGV 系统在制造业的流水生产线中得到了广泛应用。由多台 AGV 小车组成的柔性系统，在运输过程中 AGV 小车的路径铺设可根据实际的订单需求、生产工艺、订单紧急程度等各种突发情况随时进行调整，提高了系统的鲁棒性。随着企业的不断发展壮大，产品中科技含量的加成成为公司与公司之间较量的决定性因素，科技越是先进公司所能够获得的利润就越高，拥有了新兴技术的企业就如同在众多企业前进的道路上拥有了领跑地位，国内的一些汽车制造企业在汽车装试以及汽车零部件的生产加工等领域都加大了科技投入和技术创新以提高产能和生产效率，在近些年来在汽车的生产组织、信息管理和物流技术等各种方面取得了很多喜人的进步。据某汽车企业研发中心的一位权威人士发布的一则消息，称：未来的汽车制造业的前景趋势是智能化、信息化、灵活化、柔性化。而 AGV 小车的出现必将在未来的制造企业发展过程中得到更多的应用。2郑州大学学士学位论文AGV 调度系统设计3、装配美国通用汽车公司 90%的 AGV 用在汽车装配生产线中，欧洲各国整个 AGV 数量的 57%被应用于汽车装配生产线中。对于各加工台之间的元器件 FMS 要求很高的物流效率，而 AGV 柔性物流运输系统能提供拥有较好鲁棒性的方案，可以根据实际生产需求对 AGV 小车的轨道路径进行编程来改变路径来执行由主系统分配的运输任务，使整个运输系统能够更好地完成预期目标。如今，国内甚至出现了一些专门适应于汽车零部件装配流水生产线和发动机安装流水生产线的 AGV 系统，专用于汽车总装和发动机、变速箱等重要零部件的安装环节，取代了传统的输送机或输送带。AGV 系统还能通过改变调度方式、AGV 小车路径轨道等方式完成汽车装配过程中的混流作业以及执行特殊定制的生产方式等。在其它方面 AGV 系统也有被得到应用。在军事上，以 AGV 的自动驾驶为基础进行添加改造，使其能够执行一些高危任务比如放置高放射性材料、拆除爆炸物等；在胶片生产过程中，AGV 可以在黑暗环境中正常运输物料；邮政行业将邮件收入区的邮件运输到处理区以及从处理区到分发区的过程中也有使用 AGV 系统。3郑州大学学士学位论文AGV 调度系统设计4郑州大学学士学位论文AGV 调度系统设计图 1-1 AGV 的应用1.2 选题的目的意义随着现代中国人口老龄化问题的不断加剧，人力成本不断上升以及产业结构升级所带来的压力，此外一些行业因技术水平、工作环境等因素的不断变化造成的招工难现象，再加上随着现代制造业的高速发展现代工厂对生产力、鲁棒性的要求不断提高，当今社会对生产力的提高的需求不断增加。二零一五年二月根据IFR 发布的二零一四年世界机器人统计数据报告，预测二零一七年中国企业在加工制造以及装配车间等场所所使用的工业机器人的数量将由现有的十六点二万台增加到四十二点八万台。由此可以推测，到了二零一七年中国企业的工业机器人使用量将成为全世界第一，企业自动化程度也将由此进入世界领先水平。5郑州大学学士学位论文AGV 调度系统设计与此同时，根据统计我国制造业水平与发达国家还存在一定差距，比如在运输过程中车间物流效率偏低、成本比重偏高等。在这种情况下，AGV 作为作为现代制造系统里的一个新兴的子系统，可以根据生产需要、工艺流程、仓储要求等突发情况随时对调度系统进行调整，显著降低了车间的人力需求、实现了物流信息化、增强了制造过程中的鲁棒性、没有传统物流过程中常见的局限性等问题，有自动化程度高、安全可靠、人力需求很少、施工铺设轨道以及建立系统较为简单且维修方便、与传统的输送带和传送线相比运行过程中无噪音无污染运行成本低廉等优点，AGV 小车自动运输系统在我国的烟草、汽车组装、制造业等方面有广大的发展前景。根据美国物流协会的定义，AGV（Automated Guided Vehicle）是一种以电能驱动，以工控机作为逻辑核心，具备一台以上动力设备以及定位、寻径功能，能在预设的路径轨道中完成运输任务的物资输送装置。它的研究与发展涉及到计算机、自动化、信息传输、机械结构设计和软件编程等多个学科领域的知识，是集机电、光电、通信、自动化及计算机于一体的前沿运输技术。在车间进行 AGV 小车调度这一课题，当前国外的研究方向大多集中在 AGV 小车在行驶过程中所出现问题，对调度影响不大；国内针对 AGV 小车或类似的研究大多集中在在机器臂约束下的车间调度而机器臂仅进行物料在工作台以及仓库的上下料操作，与 AGV 小车系统调度的关系不大。使用 AGV 系统可以有效地提高企业生产线的生产效率以及自动化水平，而 AGV 的调度对 AGV 系统中各个 AGV 之间的协调工作有着至关重要的作用，因为生产车间内工件以及物料的运输任务是由 AGV 执行，所以 AGV 的调度是否合理得当将直接影响生产车间的工作效率和系统收益，所以 AGV 调度方案对整个 AGV 系统有着非常重要的作用。本文针对 XXXX 智能工厂改造的 AGV 小车调度问题，结合实际情况添加假设条件对车间制造系统中的 AGV 调度进行优化，对车间生产效率的提高有一定的价值。AGV 小车应用的意义有：1、AGV 小车的先进性：AGV 技术综合了当今科研发展的先进理论和前沿技术，集光、电、计算机、智能化等为一身。定位精细准确，自动化程度相对较高。6郑州大学学士学位论文AGV 调度系统设计2、AGV 小车的灵活性：AGV 系统能很便捷地与各种生产线、装配线、输送线、仓库、工作台以及 RS/AS/出入口等作业平台相配合。根据实际工作中各种不同的需要以不同的方式组合来实现预期的目的功能。以最大限度缩短物流周转周期、减低能源消耗、实现物料与加工物料与生产等的柔性对接，最大程度地提高生产效率。3、AGV 小车的可靠性：在 AGV 系统工作运行过程中，每时每刻 AGV 小车与主系统之间都进行着信息数据的交换，在后台庞大数据库支持的情况下能为 AGV 小车实际工作中遇到的各种突发情况进行分析判断并迅速做出适当反应，消除了人为因素的干扰充分保障了 AGV 小车作业过程中的可靠性、完成任务的及时性、数据信息的准确性。4、AGV 小车的独立性：在没有其它系统和配套设备支持的条件下，单独的 AGV 小车也能自成系统作为一个独立单元完成一些任务。5、AGV 小车兼容性：相比与单独工作，AGV 系统更多也更善长于与其它系统比如：调度系统、生产系统、管控系统等紧密结合起来一起运作，说明 AGV 系统具有优异的兼容性和适应性。6、AGV 小车的安全性：AGV 小车作为无人驾驶物流车辆能够在一些不适宜人类工作的恶劣环境比如高温、高辐射场合中正常运行。另外 AGV 小车具有智能化信息采集分辨判断处理的功能以及交通管理、紧急制动、安全规避、故障报告、多级警示等手段来保障 AGV 小车的安全性。7、AGV 小车示范性：作为先进技术的代表，AGV 系统是企业科技水平高端的象征。1.3国内外研究概况五十年代，美国 Barrett 公司开发出第一台自动导引小车，但随后在六十年代到七十年代期间 AGV 技术的发展和应用却主要在欧洲进行，直到八十年代 AGV技术的发展中心才又转移到美国。7郑州大学学士学位论文AGV 调度系统设计在国外，1985 年 Broadbent 首先提出了无冲突最短时间路径规划概论，并使用 dijkstra 最短路径算法生成矩阵来计算 AGV 小车的总路径最短解来描述系统最短用时。一九九一年 C.W.Kim 与 J.M.A.Tanchoco 在研究 AGV 小车双向轨道路径规划时提出无冲突最短时间路径规划 CFSTP 算法。后来 Samia 和 Pierre 对此算法进行改进，通过延迟某台 AGV 到达节点的时间，同时在考虑当前状态情况下重新使用 CFSTP 算法对系统中的每台 AGV 进行路径规划，但仍不能很好地处理复杂突发状况，实用性不强。在国内，从应用 AGV 技术的行业分析，包含有：汽车制造业、烟草行业、机械加工行业、仓库邮局机场等物流分配场所等。随着企业的不断发展和市场对产品科技附加值的需求增加，AGV 技术在国内有潜在的宽广市场，发展潜力巨大。2000 年，Sudha 等人针对防止多 AGV 小车在交点处碰撞的问题提出了博弈论模型，但将 AGV 防碰撞比作博弈必然会导致一方利益受损，可能影响整个系统的协同性。在国内，AGV 和自动化立体仓库及其配套系统智能的解决了人工运输与存储的枯燥繁琐工作，是现今无人化工厂的重要解决方案及组成部分，AGV 系统在各个领域各个行业都已经得到了广泛应用也拥有很多成熟的经验案例和极佳的用户反馈，由此可见业界对 AGV 系统是非常认可的，AGV 系统的应用推广前景大好。AGV 系统可以通过合理的路线设计和区域型交通管制以及主系统与 AGV 小车之间及时的信息交流的等途径完美地解决了死锁、追尾、相撞、交汇等 AGV 小车系统常见问题，减少了 AGV 小车处于无负载运动状态的时间，在停靠节点密集、 AGV 小车轨道路径分布复杂的区域依旧能够保持 AGV 小车运行起来平稳安全并且具有很高的效率。AGV 系统实现了信息化与自动化的完美结合的同时又具有安全性、可操作性和易于维护性。XX 智能工厂制药车间里的 AGV 系统是 XX 药业股份有限公司的立体智能化仓库项目中不可或缺的重要部分。该成功案例为我国企业进行智能工厂改造项目提供了示范作用，必将成为我国现代化药品生产产业结构调整提供了典型案列，在江中集团公司内部、整个物流行业乃至国际医药领域产生强烈反响。江中集团智能工厂层接待过如全国政协副主席张梅颖、国家中医药管理局局长王国强、卫生部副部长、江西省常务副省长凌成兴、副省长洪礼和等国内政要的视察，以及土库曼斯坦副总理萨帕尔杜尔8郑州大学学士学位论文AGV 调度系统设计德 托和肯尼亚共和国总理奥廷加等多位国外友人的参观，他们皆对 AGV 小车在高新技术方面的地位给出了高度评价和认可。1.4本文研究内容本设计主要内容包括：1、了解 AGV 的定义、路径导引方式、控制以及通讯的基本原理；2、AGV 小车系统的历史背景、特点以及应用范围；3、研究 AGV 小车的调度原理和方法；4、结合实际情况在给出的车间草图基础上铺设 AGV 小车的路径；5、用 Visio 建立调度流程图对调度流程进行描述；6、了解以路径最短为原则求最优解的算法并结合实际情况选择 Dijkstra 算法作为研究内容；7、建立一些假设对课题进行简化并以路径最短为原则利用 Dijkstra 算法求解路径最优解；8、熟悉 C 语言知识，针对已经完成的优化算法使用 C 语言编程进行描述。为了实现对整个系统中各个 AGV 小车的调度技术比如铺设 AGV 小车路径轨道、建立小车与主系统之间的通信联接、处理小车运动过程中碰到的各种冲突等问题的解决，主要有以下几个方式：1、规划最优路径路径规划指在既定 AGV 小车的任务起点以及终点后，在 AGV 小车的路径中按照一定的目标（比如时间最优、路径最优等等）进行规划，进而选择出相对适合的 AGV 行驶线路。2、任务调度所有任务的调度由主控系统完成。主系统根据生产车间的实际布局、生产需要以及即刻的工作环境进行判断，然后将任务分配给合适的 AGV 小车。在相对合9郑州大学学士学位论文AGV 调度系统设计理的调度方案下，可以对每个 AGV 的运行负载进行均衡来提高 AGV 小车的利用率并提高 AGV 系统完成物流的效率。3、处理冲突在实际的生产过程中，因为各种不可预见的因素会出现 AGV 小车之间的冲突，其常见情况有以下三种：（1）碰撞图 1-2 碰撞此类情况多是由于调度不当引发的，可引入限制条件如“道路单行”进行简化并避免此类冲突；（2）追尾图 1-3 追尾此类情况多是由于小车因拐弯、起步等因素造成的不同小车之间速度不同造成的，可以引入假设条件如“小车在运行过程中速率相同”进行简化并避免此类冲突；（3）交汇10郑州大学学士学位论文AGV 调度系统设计图 1-3 交汇此类情况在多 AGV 小车调度过程中很常见，在这里我们可以通过加入以下任意条件来进行优化：通过交汇节点的 AGV 小车必须遵循“先到先行”原则；直接采用单 AGV 小车调度来避免此类冲突。1.5本章小结本章主要介绍了本课题的应用领域、研究内容、背景情况以及研究意义，简要对 AGV 小车调度系统的特点、应用、发展状况及国内外研究过程及现状进行了介绍。11郑州大学学士学位论文AGV 调度系统设计第二章AGV 小车路径设计2.1XXXX 裁剪车间智能化改造整体方案2.1.1 集团目前生产流程分析根据导师们在加工车间现场考察时所了解到的加工工序，做出如下生产流程示意图2-1。图 2-1目前生产流程2.1.2 总体示意图结合生产流程图及文字描述可以看出，虽然在服装加工制造行业中 XXXX 公司的生产制造水平已经达到国内领先，但其生产车间对人力资源的需求依旧很高，能实现自动化的仍然只有单个机器所以自动化程度很低，依然是劳动密集型企业。结合对现有的生产工艺流程分析，对生产线更改如图 2-2 所示。12郑州大学学士学位论文AGV 调度系统设计图 2-2对生产线进行改造2.1.3 总体方案图根据改造的生产流程图可以看出搬运，输送，打号验片，扎布签的人工被机械臂、AGV 小车、计算机视觉系统分析系统所取代，使得整个生产车间所需要的人力资源大大减少。完成该改造方案后车间生产线基本上实现了自动化。具体流程如下图所示。13郑州大学学士学位论文AGV 调度系统设计图 2-3整体流程简图图 2-4流程简图 114郑州大学学士学位论文AGV 调度系统设计图 2-5流程简图 2图 2-6流程简图 315郑州大学学士学位论文AGV 调度系统设计图 2-7流程简图 42.2 模型简化结合上面所提到的实际情况，现在为简化方案建立如下假设：1、小车完成任务后就停在 AGV 小车待命区或当前工作台、仓库的临时停靠区（不影响轨道上的正常通行）；2、小车在运行状态下速率相同（不考虑起步和停止时的加速减速）；3、小车在执行一项任务时一次限载一批货物；4、一项任务只能由一辆小车执行；5、任务只能由空闲小车执行；6、小车在轨道上单向行驶；7、工作台和仓库的装卸载缓冲区足够大（装卸载无需等待）。16郑州大学学士学位论文AGV 调度系统设计2.3AGV 小车轨道铺设通常情况下，对 AGV 小车进行道路规划的先决条件是获取其系统环境信息，因为只有这样才能进一步确定可行路径、AGV 自身位置、目标位置来建立 AGV 小车路径，进而完成整个运输任务。但现在实际情况是无法找到 XXXX 智能工厂项目里的数据，所以在后面建立算法时会建立补充假设代入计算从而求解，这里暂且不讨论数据只根据已给信息设立 AGV 小车轨道铺设方案如下图。图 2-8铺设 AGV 轨道路径图其中 A、B、C、D 四个节点分别代表在 AGV 小车轨道上与工作台 1（裁布机）、工作台 2（打号打包机）、工作台 3（装订机）以及立体仓库的装卸载缓冲区相对应的 AGV 小车停靠节点，O 节点代表 AGV 小车待命区。2.4本章小结本章主要介绍了 XXXX 智能工厂改造项目方案的前后生产流程改动和需求，针对实际情况设立一些假设条件来简化方案，铺设一套与实际情况相符合的 AGV 小车的轨道路径图。17郑州大学学士学位论文AGV 调度系统设计18郑州大学学士学位论文AGV 调度系统设计第三章AGV 小车路径优化3.1AGV 小车调度流程要对 AGV 小车的任务路径进行调度优化必须要先对 AGV 小车的调度流程进行了解。AGV 小车在轨道上运行过程中常使用局域化原则，由线路及节点进行管理从而实现交通管制。具体如下：1、AGV 轨道单向通行通过设定线路类型来确定 AGV 走向。在这里由 2.2 中所建立的假设，采用单向环路的方法；2、车辆避让由 1.4 中所提到的另两种 AGV 小车运行过程中的常见冲突及 2.2 中所建立的假设，在 AGV 小车调度中采取先到先行原则、规定运行状态下 AGV 小车速率相同来解决。由此可设立 AGV 小车调度流程：1、开始工作；2、输入任务；3、将一项任务分配给工作台；4、判断此时是否有空闲的可工作 AGV 小车，如果是则继续进行下一步，如果否则停车并返回步骤 4；5、判定出最优 AGV 小车；6、将任务分配给此 AGV 小车；7、执行任务；8、判断该 AGV 小车是否是离下一个节