摘 要

现代工业系统随着生产规模的扩大、生产自动化水平的提高，立体仓库的规模越来越大，多AGV小车的运用越来越广泛。在本文所研究的直达式立体仓库中，AGV小车运输货物时无需经过堆垛起重机等设备的上下料，AGV小车能够直接实现装载、卸货与运输的功能，节省大量的占地空间。在立体仓库中运用多AGV小车作业的目的正是提高生产系统整体的工作效率，而AGV小车的调度是其中的重要一环。

本文运用将实时任务调度的问题转换为比较简单的一系列离散的静态任务调度优化问题，使AGV小车动态调度得以实现。对于批量静态调度问题，本文采用遗传算法进行任务序列的优化。在理论分析之后使用Visual Studio 2013开发平台设计出交互式调度系统，能够根据用户输入的小车信息与任务信息输出一个相对最优的任务解序列。

关键词：多AGV；遗传算法；调度

Abstract

With the enlargement of production scale and the improvement of production automation level, the scale of three-dimensional warehouse is more and more large, and the use of multi-AGVs is more and more extensive. In the direct-type warehouse, which is researched in this paper, AGV can carry the function of loading, unloading and transporting without the upper and lower material of the stacker and cranes. This can save a lot of space of goods. The purpose of using multi-AGVs in stereoscopic warehouse is to improve the efficiency of production system as a whole. And the scheduling of multi-AGVs is an important part of it.

In this paper, the problem of real-time task scheduling is converted into a relatively simple series of discrete static task scheduling optimization problems, so that the dynamic scheduling of multi-AGVs can be realized. For static scheduling problem, genetic algorithm is used to optimize the task sequence. After theoretical analysis, this study uses Visual Studio 2013 development platform to design an interactive scheduling system. It can output a relatively optimal task solution sequence according to the information of AGVs and tasks.

Key words: multi-AGVs; genetic algorithm; scheduling

目 录

摘 要 I

Abstract II

1 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 2

1.3 论文研究的基本内容 2

2 多AGV调度过程分析与调度模型的建立 4

2.1 多AGV的调度过程 4

2.1.1 多AGV调度问题的提出 4

2.1.2 AGV作业执行过程 5

2.2 多AGV动态调度问题分析 5

2.3 调度模型的建立 6

3 基于遗传算法的多AGV动态调度优化算法设计 9

3.1 AGV调度算法的选择 9

3.2 遗传算法的核心思想 9

3.3 多AGV静态调度过程 10

3.3.1 立体仓库货位坐标的编码过程 10

3.3.2 高适应度个体的选择 11

3.3.3 父代个体基因的交叉过程 13

3.3.4 个体基因的变异过程 14

3.3.5 下一计算子代的竞争与产生过程 16

3.4 多AGV动态调度的实现 16

4 VS平台下基于C#的调度系统的实现过程 18

4.1 系统开发运行环境 18

4.2 系统实现过程 18

5 仿真结果与分析 20

6 经济性与环保性分析 23

7 总结与展望 24

7.1 课题研究的主要工作、结论 24

7.2 尚待研究解决的问题 24

致 谢 26

参考文献 27

附录A 28

附录B 30

附录C 33

1 绪论

1.1 研究背景及意义

我国实体经济的发展从高速发展阶段进入高质量发展阶段，物流中储运系统的更新对各大企业的发展具有重要意义，而物料储运系统中的立体仓库已经是全球发展的主要储货系统。立体仓库是货架自动化立体仓库的简称。立体仓库一般是几层或者十几层的货架储存单元，通过计算机精确定位与系统的程序分析，并使用相应的搬运设备进行出入货物操作作业的仓库^[1]。立体仓库一般都较高。其高度一般在5米以上，对于大型立体仓库，为了存储更多的货物，有时高度能够达到40米。

现如今，立体仓库的运用越来越广泛，涉及到的领域也越来越多，立体仓库的类型与其形式也呈多样性发展。而对于现在时间成本的提高与准确高效的需求，对于大货物大物流的立体仓库中人工已经完全无法实现对货物的装载与转运，必须依靠机械进行作业。因而AGV小车、堆垛机等自动搬运设备就不可避免的出现在货储仓库之中。AGV小车也称为自动导引运输车，是指以可充电的蓄电池为动力能源、装备有自动导引设备以保证精度、能够沿着规划好的路径行驶且无需驾驶员的搬运车^[2]。这不仅能节省大量的人工劳动力，而且能够避免人工在装载与转运货物时出现的意外伤亡情况。AGV小车在货储仓库中有诸多优势，它由计算机、电控设备、激光反射板等控制，自动化程度高，还可以实现自动充电功能，有方便、美观，占地面积少等特点。

直达式立体仓库是指AGV小车运输货物时无需经过堆垛起重机等设备的上下料，AGV小车能够直接实现装载、卸货与运输的功能。减少了相应的成本，也能够节省大量的仓库空间，使仓库能够存储更多的货物。小车空载时能够在货架下面自由行走，克服了导轨式、磁条导引式等AGV小车只能沿固定轨道行驶的缺点。实际制造生产过程中，在优化立体仓库布局，增加货位数量以减少相应成本的同时，对于物料的搬运过程也是整个生产中非常重要的一部分，该部分包括了生产所需的各种原材料的搬运，生产出来的成品的装卸与运输，会大大增加生产过程中的时间成本^[3]。这就需要改善物料成品等在装卸、搬运和存储过程中的管理及自动化程度，以提高整个生产效率，达到减少成本的目的。

纵观当前各个企业的规模，单AGV进行立体仓库的作业已经无法满足规模庞大的各种仓库，而且单AGV的研究也比较基础简单，已经无法成为研究课题，对于多AGV的研究则成为此领域的热潮。多AGV小车同时作业能够大幅度降低高度自动化的流水生产线中的时间成本，对于大批量任务的处理也会更加快速，将多辆AGV小车集成到一个系统中也能够提高生产过程中的管理水品。对于小型立体仓库来说，在物流分拣时，直达式立体仓库能够更加高效的达到转运装卸的目的，而且能够省去堆垛机的空间占用，扩大仓库的货位数量，能节约一定量的成本。控制调度时也只需要对AGV小车进行调度，方便快捷。具有一定的研究意义。

1.2 国内外研究现状

对于国内外AGV小车的发展，由于技术积累的问题，国外的AGV还是要优于国内的AGV小车的。调度的准确性、AGV运行时导航的精确度、行走时车体自身稳定性、可控性以及方案的思路都比国内要好。但是现在国内也越来越重视AGV小车的生产研发，市场占比也越来越大，此领域内的研究我国也在慢慢追赶。

基于触发机制，多AGV和多运货卡车的调度可以区分为静态调度和动态调度^[4]。对于AGV小车调度问题，Dkhil等在2013年研究了自动化集装箱码头中装卸装备的联合调度问题来使作业时需要的AGV数量最少^[5]。在最小化总延迟时间和AGV总行驶时间的方面，Kim和Bae在2004年提出了一种静态AGV调度的整数规划模型^[6]。现在国内对立体仓库中的AGV小车调度与路径规划也有很多的研究，但是在直达式的立体仓库方面却并没有多少文献。本文旨在丰富国内对直达式立体仓库中AGV调度问题的研究。

1.3 论文研究的基本内容

在立体仓储中，AGV小车是一种普遍采用的自动化的搬运工具。当仓库中需要多台AGV小车搬运时，会涉及到AGV小车路径规划和分配的问题，是最优化问题。在没有堆垛机转运的直达式立体仓库中，AGV小车可以直接将货物送到分配的货位上去。而每台AGV小车应该执行哪些任务，以及每台AGV小车需要执行多个任务时各个任务的先后排序问题，是本次研究的基本内容。

本文主要研究的是直达式立体仓库中AGV小车的调度优化问题，研究的目标是开发一个基于C#的Windows窗体应用程序，使得对于给定的输入任务及AGV小车能够输出相对最有的任务序列。本次研究采用的是智能优化算法——遗传算法，来对AGV小车进行调度安排，并实现批量调度之后的实时调度。即根据AGV小车的数量及需要执行的任务数量，尽可能使总的AGV小车空载时间最短，尽可能保证每辆AGV小车的作业完成时间相差不大，综合考虑所有约束条件之后，通过遗传算法计算出相对最优的AGV小车执行的任务序列，即对任务的分配与排序。由于本文仅研究直达式立体仓库中AGV小车的调度问题，所以全文均以AGV小车的行程代替小车的运行时间。即目标函数变为尽可能使所有AGV小车的总空行程最短，尽可能保证每辆AGV小车的空行程相差不大。调度算法在对一批任务完成调度之后，还需要能够实现动态调度，以达到较高的效率。动态调度即为在上一批任务尚未完成之时，又需要执行一批新的任务。此时需要将上一批尚未完成的任务与当前出现的新一批任务结合起来使用遗传算法进行计算，达到使目标函数值最小的目的。

2 多AGV调度过程分析与调度模型的建立

2.1 多AGV的调度过程

2.1.1 多AGV调度问题的提出

立体仓库的出现，使得货架装载与取货的过程必须使用到AGV小车、堆垛起重机等设备。本文所研究的直达式立体仓库省去了堆垛起重机等设备，AGV小车自己能够完成装卸与搬运的作业。虽然普通立体仓库与直达式立体仓库有各种不同之处，但是二者都会用到AGV小车这一搬运设备。AGV小车是将所给对象从一个点搬运到另一个点的自动输运装置，可以通过编程对两驱动轮速度的控制来实现小车的向前行驶及转弯行驶，并配备有防碰撞报警设备、刹车设备及自动充电设备等其他辅助装置。每辆AGV小车应该执行哪些任务，对需要执行的任务的顺序是什么，这些是影响小车作业时间的重要因素。这就涉及到小车的调度问题。

直达式立体仓库平面简图如图2. 1所示，AGV小车在空载状态时可以在货架地下自由行走。初始状态下，AGV小车处于该车上一次任务完成之后的货架位置。由上位数据库给出需要进行装载与取货的货位点，根据直达式立体仓库中空闲AGV小车的数量，由所开发的AGV调度系统算出每辆AGV小车所需要执行的任务，以及每辆小车执行任务的顺序，以达到调度优化的目的，是最优化的问题。

空载小车： 负载小车：

货

架

巷

道

巷

道

巷

道

巷

道

图2. 1 直达式立体仓库平面简图

在当前批次任务尚未全部完成时，上位数据库可能会下发新的任务，若此时等待上一批任务全部完成，在上一批调度中，优先完成各自任务的AGV小车会等待调度中完成任务所需时间最长的那辆AGV小车，这样将会浪费大量的小车等待时间。所以，在一定量新的任务下发之后，需要将新给定的任务与上一批给定任务中尚未完成的任务一起重新计算，得到新的相对最优任务序列。这样才能保证总任务执行时间最短，减少时间成本，达到优化的目的。

2.1.2 AGV作业执行过程

AGV执行任务一般可以分为两个部分，即任务准备部分和任务执行部分^[7]。可以假设一辆AGV小车需要执行一项任务M，需要将货物从货位搬运到拣货台，然后再将货架搬运回其原来的位置，该AGV初始位置为驻点A。当AGV小车收到调度系统所给出的任务时，小车会从其初始位置驻点A，行驶到任务A的货位点。这就是作业过程的第一部分，可以看出该部分AGV小车处于空载状态，属于任务的准备部分，并未搬运货物，所花费的时间可以称为任务准备时间。在AGV小车到达任务初始点B处之后，小车将装有货物的货架装载在小车上，然后运送到指定目的地拣货台C处，在拣货完成之后再将货架运输到该货架的固定位置B处。可以看出该部分AGV小车均处于负载状态，属于任务的执行部分，全程搬运货物，所花费的时间可以称为任务执行时间。在完成该任务M之后，若后续还有任务需要执行，则可以把此时任务M的位置B作为小车下次执行任务的初始位置驻点A，然后将货物运送到指定的任务点。如此循环往复，直到分配给该AGV小车的所有任务执行完毕，由于直达式立体仓库的特性，AGV小车执行完任务之后小车可以停留在货位底下，等待下一次的任务调度。

2.2 多AGV动态调度问题分析

对于上述AGV执行任务的过程可知，在确定的直达式立体仓库的布局之后，只要上位数据库的任务下发，那么任务点到拣货台的距离就已经固定下来，不论调度系统所给出的调度方案如何改变，AGV小车的运行时间都是小车从任务的起点到该项任务的终点的时间，只要小车速度保持相对恒定，则该项时间仅与任务的起点和终点的距离成正比关系。即任务执行时间固定不变，调度改变的仅是任务准备时间。除开首次调度时AGV小车的初始位置在驻点处之外，AGV小车每执行一个任务，其当前初始位置为上一个任务的货位位置。因此，调度方案、任务执行顺序的不同，会使得AGV小车的任务准备时间发生变化。所以，每辆小车需要执行哪些任务，需要按什么顺序执行这些任务，都会对下发任务的执行效率产生非常大的影响。而这也正是AGV调度系统所需要完成的主要工作。对每辆AGV小车进行合理的任务分配与任务的排序来优化小车的作业过程，将能够有效提高直达式立体仓库的作业效率，大幅度减少生产过程中的时间成本。

一个完整的AGV系统会涉及到很多方面，综合考虑会非常复杂，而本文仅研究AGV小车的调度问题，诸多方面的因素都会影响到整个调度优化方案的性能及特性。为了简化模型，更好的研究问题的核心与求解思路，探讨调度问题的优化方案，可以认为下列陈述与假设同时成立：

（1）直达式立体仓库中AGV小车在执行完单项任务之后，不必像其他特定仓库那样必须回到驻点，而是停留在上一项任务的货位点，等待或者直接执行下一个任务。这样会节省大量小车空载行驶到初始驻点的时间。由于直达式立体仓库的特性，在小车完成其本身的任务序列之后，小车会停留在最后一个任务的货位点，直达式立体仓库的特性使得这样的安排并不会影响到其他小车的路径行驶。

（2）整个AGV调度系统会贯穿整个任务的执行过程，这种实际的不间断实时调度问题属于非常典型的动态实时调度，这种动态的调度往往涉及到各个方面，诸多因素的稍一变动就会影响到调度的优化。为了降低这种问题的影响，简化研究的分析量，可以认为一系列按时间顺序的任务先后进入调度系统，将这些任务按块分开进行调度优化，这些多块调度组成整个任务系统的调度全过程，这每个块调度中等待调度分配的任务数量是稳定不变的。这样就使得全动态的复杂调度问题，转化成了一系列的单独离散的区域块静态AGV小车调度优化的问题，同时还能保证整体还能有不错的优化任务序列。

（3）调度系统中最贴近实际情况的衡量任务执行代价的量就是时间，调度系统给出任务的最短时间序列最贴合生产中的作业效率的计算。但是由于AGV小车的运行路径无法在调度之前就预先知道，想要确定一次调度的具体或者大致的时间，这就涉及到专业的路径规划的优化问题，这已经超出了本文所要考虑的单纯AGV调度问题。因此在本文中假定所有AGV小车的运行路径都是稳定的，并且假定所有AGV小车的运行速度为设定好的已知值，小车所行走的时间仅与其所走的路径成正比关系^[8-9]。针对以上几点假设，为了简化模型的建立以及算法的设计，本文以小车所行走的路径长度作为度量其任务的执行代价。

（4）每辆小车一次仅能搬运一个货物，空载时能够在货架底下自由行走，且假定小车作业运行过程中不会发生碰撞。

2.3 调度模型的建立

假设系统中有辆AGV小车，需要执行个等待作业的任务。用表示第辆AGV小车，用表示个任务中分配给第辆小车的所有任务（若能够整除，则每辆小车分配的任务数量相同，若除以的商为，余数为且，则有辆小车执行个任务，有辆小车执行个任务），用表示第辆小车的第个任务。那么第辆小车在执行其第个任务的总行程为：

其中是第辆AGV小车在执行该小车本身的第个任务时，从第个任务的货位点运行到第个任务的货位点所行走的距离，对应的是任务的准备时间；而是第辆AGV小车在执行该小车本身的第个任务时，从第个任务的货位点把货物搬运到拣货台，再将货架搬运回其固定货位点所行走的距离，对应的是任务的执行时间。

在生产实际中，AGV小车总是在执行完一个任务之后，不间断的执行下一个任务。那么第辆AGV小车在执行分配给其自身的任务的总的作业时间（行程）为：

实际生产中，不可能仅是一台AGV小车执行任务，当有多台AGV小车同时执行整个下发任务时，台AGV小车完成整个下发任务的最终时间（行程）为：

由于整个作业任务最终完成时间为台AGV小车中执行任务所需时间最长的那辆小车完成任务所耗费的时间。所以，在一批量任务下发之后，为保证所有AGV小车总的等待时间最短，需要使得每辆AGV小车在执行分配给各自任务的时间尽可能地相差不大，用以控制所有小车的总等待时间，即所有小车的空载行程，虽然这样可能会使得所有AGV小车的总空行程增加，但是这样的控制所减少的等待时间足以弥补其所导致的总空形成增加量。

此次优化调度的目标，就是在满足各种约束条件下，找出一个相对最优的任务分配方案及任务执行顺序，使得每辆AGV小车的空行程相差不大，且使得所有AGV小车的空载行程最小。即有：

本文所研究的多AGV小车调度问题，在于搜索出一条小车所走过的最短路径，若是单AGV小车执行任务，则完全可以看作是一个限制其行走时间的旅行商问题。实际生产中的多AGV并行作业，相似的可以看作是一个多重旅行商问题。不论是TSP问题，还是多重TSP问题，都早已被证明是一个NP完全问题。对于NP完全问题，在大规模调度系统中，目前还没有一种算法能够在可接受的时间范围内搜索到一个最优解^[10-11]。对于辆AGV小车执行个任务，将任务分配给小车就有种方案，若是将辆小车分别分配到的任务，那么也将会产生种调度方案。只要任务规模及AGV小车数量稍一增多，这种调度方案的数量将会呈几何倍数激增。在如此庞大的方案基数之下，现阶段不可能采用穷举的方式将每种方案都计算一遍。这样无疑会花费巨大的时间，这种以大量时间作为代价以换取绝对的最有解是无法在实际情况中被接受的。因而对于这种问题，只能采用一些特定的算法，计算出一个无限接近最有解的近似解。这样在可接受的时间范围内，就能够得到一个比较优化的调度方案。

3 基于遗传算法的多AGV动态调度优化算法设计

3.1 AGV调度算法的选择

本次研究的多AGV调度问题所涉及目标函数为第2章中的式2. 4。对于具有限制每辆AGV小车均匀性的最短路径要求的问题，遗传算法中的适应度函数可以比较有效的表示出这两者之间的平衡目标。并且遗传算法并不依赖全局搜索中所需要的梯度信息，而是模拟进化过程得到近似最优解，具有非常多的特点：

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：