本文是一篇工程硕士论文，本文针对智能仓储场景多AGV调度问题，将调度系统分解为各个功能模块展开研究，并以任务调度为主体，融合充电调度以及路径规划进行耦合计算。同时，结合任务链调度模型的特点，对遗传算法进行改进优化。
第1章 绪论
1.1研究背景及意义
1.1.1 研究背景
无人驾驶是近年来智能交通领域的研究热点之一，自动导引车（Automated Guided Vehicle, AGV）作为一种高度自动化和智能化的载运工具，其本质是无人驾驶技术的一种应用形式。在新冠疫情席卷全球，人力劳动成本不断上升的背景下，以AGV为代表的移动机器人在运输制造业，尤其是流水生产、港口运输、仓储管理和物流分配等领域，得到了广泛的应用。随着智能系统与智能控制研究的深入发展，AGV的应用场景也一直在被拓展。现代物流系统是智慧交通的重要组成部分，而其各细分场景，如自动化码头、智能仓储和快递分拣等的车辆调度与控制，则可以作为微观交通和无人驾驶研究的切入点。与复杂多变的道路交通环境比较，相对低速、封闭的AGV应用场景，也更为适合作为无人驾驶技术的先行落点。图1.1展示了AGV在一些主要物流场景的实际应用。
工程硕士论文怎么写
近年来互联网电商蓬勃发展，拉近了生产者与消费者之间的距离，市场也对更加先进的物流和仓储管理模式提出了新的需求。与传统的人工到各货架前拣选货物不同，自动化仓库采用“货到人”的模式，AGV将货架运输到拣选区进行集中拣选，这能够提高货物处理效率。仓储管理系统（Warehouse Management System, WMS）根据订单需求生成各类型任务，AGV调度系统根据任务池和各AGV的状态智能地调度相应AGV执行任务。在智能仓储系统中，AGV调度系统需要利用有限的设备物理性能，尽量提高系统整体的货物处理速度。
..............................
1.2国内外研究现状
1.2.1 AGV调度模型研究现状
（1）任务调度。AGV最初的应用场景是生产车间中的物料运输，国内外学者都对其任务调度做了大量研究。为了满足汽车装配作业需求，调度不同类型的AGV运输不同尺寸的物料，Zhang等[1]以最小化系统运行成本为目标提出了一种混合负载AGV调度模型，并采用遗传算法（Genetic Algorithm, GA）求解。Zheng等[2]提出了一种在分布式系统中基于激素调节的AGV实时调度方法，该方法实现了在实时环境下的任务调度，能够分配紧急任务并生成可行计划。随着AGV运行效率的提升和作业能力的丰富，具有环境相对封闭特点的自动化集装箱码头，开始引入AGV运输。针对高峰时段港口设备资源紧缺和集装箱码头拥堵等问题，马梦知等[3]构建了车辆预约与设备调度协同优化双层规划模型，设计了并行遗传算法（Parallel Genetic Algorithm, PGA）进行了求解。针对自动化集装箱码头复杂多变的环境，Angeloudis等[4]提出了一种基于滑动窗口的任务分配算法，该算法不断运行并即时将任务分配给AGV。Grunow等[5]研究了基于规则的港口集装箱码头AGV调度问题策略，并提出了更加高效的基于模式的离线启发式算法。针对仓储生产中的多AGV调度问题，王体春等[6]采用排队论建立了M/M/s/Ps 排队模型，考虑任务等待时间、AGV 数量和运行成本，得到了一种仓储 AGV 配置和调度的有效分析方法。Liu等[7]针对智能仓库系统中多机器人任务分配的动态性和实时性问题，首先使用动态任务池存储新增任务，将大规模连续任务分配问题拆分为小规模子问题，采用自适应控制策略调整任务总数，最后对任务池中任务进行派发。为研究仓库订单拣选中异构多机器人系统的协同任务规划问题，Zhuang等[8]建立了具有顺序关联和运输时间约束的任务调度混合整数线性规划模型，并引入启发式算法进行求解。
AGV调度的总体目标是提高系统的作业效率，因此任务分配和路径规划也需要考虑到避免拥堵、碰撞和死锁的发生。针对配送任务的多目标优化问题，楼振凯[9]基于双层规划思想，建立以车辆使用数最少、运输总里程最小以及客户不满意度最低的标量化多目标模型，并运用模拟退火（Simulated Annealing, SA）算法验证了模型的有效性。在多AGV在线协同调度问题的研究中，余娜娜等[10]设计了在动态环境下同时考虑多AGV任务指派和无冲突路径规划的一种在线协同调度算法。为缓解仓储环境下AGV拥堵问题，刘建胜等[11]提出了一种非传统的鱼骨型仓储布局模式，建立了多车协同拣选调度优化模型，并给出了一种混合粒子群优化（Particle Swarm optimization, PSO）算法进行求解。随着应用场景的多样化，AGV调度过程中需要考虑的目标和约束也越来越复杂。针对动态系统中的任务指派问题，Chawla等[12]提出了基于多种指派规则的多载AGV调度方法，并通过仿真实验对各种规则进行了对比研究。Luo 等[13]提出了一种分布式任务分配算法，优化的目标是最大化完成任务的收益。
......................
第2章 非耦合的仓储AGV调度系统研究
2.1仓储AGV调度系统介绍
2.1.1 智能仓储场景及业务
智能仓储一般采用立体库模式，主要涉及的运输设备有AGV、有轨穿梭小车（Rail Guided Vehicle, RGV）和提升机。AGV运行于第1层，用于搬运货物；提升机可以运输货物和RGV，其作用是连通各楼层；RGV运行于除第1层外的楼层，可以执行与AGV相同的货物搬运任务。图2.1为仓库第1层的基本布局示意图，其中绿色区域为货物存储区，蓝色为拣选区，红色和黄色分别为入库和出库缓存区，黑色为提升机作业区，紫色为AGV充电区，剩余空白区域为AGV的自由通行区。其它楼层只具有存储功能，因此其功能区只有存储区、提升机区、RGV通行及充电区。
仓储系统的基本业务包含与外界交互的出入库任务，以及内部清点整理的库内管理任务。具体如下：
（1）出入库任务，包括收货入库和备货出库。出入库作业具有整存零取的特点，每批到达的货物基本都是同一类型的产品，清点后即可入库，而要出库的货物往往品类分散，需要进行拣选。收货入库的作业流程是：通过叉车将外来货物卸至入库缓存区，在清点扫描完成后，WMS根据存储规则为货物分配相应库位并生成入库任务，AGV调度系统实时调度合适的设备进行最终的搬运和存放。备货出库的作业流程是：WMS生成出库任务后，调度系统调度AGV等设备先将货物运至拣选区，拣选完成后AGV或叉车将待出库的货物运输至出库缓存区，后续装车任务由叉车完成，当被拣选后的货架上有剩余货物时，系统还需调度相关设备将其运回存储区。
（2）库内管理任务，包括货物整理和货物合并。为提高出入库的响应速度，系统按照不同类型货物的订单频率和存储集中度，重新安排其库位，也会为出口近端预留空位，该类业务被称为货物整理。为提高库位利用率，系统需要将多个未装满的货架合并为满载货架，该类业务被称为货物合并。
........................
2.2 多AGV单任务调度
2.2.1 模型构建
对于仓储系统中多AGV与多任务之间的匹配问题，传统方案是基于贪心算法的单AGV单任务（Single AGV Single Task, SAST）调度模型。SAST调度指每次计算单个AGV，并为其分配（至多）一个任务。该调度策略依次计算当前空闲AGV，将其指派给期望最晚完成时间最早的任务中，起始点距该AGV最近的任务。该策略简单易行，但也存在突出问题：基于期望最晚完成时间的作业顺序缺乏灵活性，基于距离的贪心策略未有效利用全局信息，会导致AGV的总空载行驶距离较长，影响系统整体作业效率。
因此，需要在考虑任务与设备多维属性的基础上，建立多AGV单任务（Multiple AGV Single Task, MAST）调度模型。MAST调度指同时计算多辆AGV，并为每辆AGV分配（至多）一个任务。
模型假设： （1）AGV在空载运行状态下保持匀速行驶； （2）AGV每次转弯耗时固定； （3）碰撞与死锁避免机制能够完全消除两辆AGV间的碰撞与死锁； （4）忽略AGV规避碰撞和死锁的行为对行程时间的影响； （5）忽略三辆及以上AGV之间的循环死锁；
...........................
第3章 动态协同的多AGV调度系统研究 ........................... 25
3.1基于动态任务链的调度模型 ......................... 25
3.1.1 问题描述 ........................................ 25
3.1.2 模型假设 ................................... 26
第4章 任务调度优化算法研究 ............................. 45
4.1传统遗传算法 .................................. 45
4.2改进遗传算法 .................................... 47
第5章 仿真设计与实验分析 ................................. 61
5.1仿真系统搭建 .............................. 61
5.1.1 系统功能设计 ............................ 61
5.1.2 仿真参数设置 ....................................... 63
第5章 仿真设计与实验分析
5.1仿真系统搭建
5.1.1 系统功能设计
根据实际自动化仓库场景中的多AGV作业需求，基于Java编程语言以及SpringMVC框架开发AGV调度仿真系统。仿真系统主要包含调度模块、控制模块以及管理模块，如图5.1所示。各模块的具体功能如下：
工程硕士论文参考
（1）调度模块。与WMS对接，根据任务池中的作业需求，为AGV分配合适的作业任务，同时负责AGV系统的电量管理。调度模块的功能，是本文所研究调度模型和算法实现的载体。
（2）控制模块。与WCS交互，用于为AGV规划路径并对所有AGV进行运行和动作控制，保障各AGV顺利执行任务指令。通过将实时AGV状态信息反馈 至管理模块，实现模拟AGV的运动。
（3）管理模块。实现地图、车辆、任务等数据的管理，将基础数据存储于MySQL数据库，将动态数据存储于JVM缓存。根据立体仓库环境数据构建栅格化地图节点，通过HTML5绘图实现信息的可视化。
........................
第6章 总结与展望
6.1工作总结
本文针对智能仓储场景多AGV调度问题，将调度系统分解为各个功能模块展开研究，并以任务调度为主体，融合充电调度以及路径规划进行耦合计算。同时，结合任务链调度模型的特点，对遗传算法进行改进优化。本文工作的主要贡献如下：
（1）提出了一种基于DTC的多AGV多任务调度模型。该模型以优化系统时间和能量利用率为目标，通过降低AGV在任务衔接过程中的空载行驶时间，提高了运输作业的效率。该模型同时赋予系统未来状态预测的能力，为融合充电调度和路径规划等功能提供了基础。
（2）提出了一种基于动态差异化阈值的AGV充电策略，并将充电任务与运输任务进行了协同调度。改进充电策略利用全局AGV电量和充电桩状态信息，动态调整各AGV的充电阈值，通过及时调度AGV进行充电，减少了对充电桩的占用冲突。通过在任务调度计算中预估AGV电量状态，同时利用充电桩位置和任务终点位置信息，减少了AGV前往充电桩的空载行驶时间。
（3）提出了基于时空离散的系统拥挤度评价模型，并将AGV任务调度与拥挤度控制融合，缩短了多AGV系统的总行程时间。通过基于AGV独占运行区的运行控制策略，避免多车碰撞和减少死锁，提升了AGV的通行效率。通过为估价函数增加转弯次数和拥挤度代价，优化了A-STAR路径规划算法。
（4）提出了AGV预调度策略，以DTC调度模型为基础，通过预调度计算控制多AGV协同作业，解决了实际自动化仓库中的特殊作业约束问题。
参考文献（略）