制造车间自动导引车调度新进展

曹立佳，刘 洋

1.四川轻化工大学 计算机科学与工程学院，四川 宜宾644000

2.人工智能四川省重点实验室，四川 自贡643000

3.四川轻化工大学 自动化与信息工程学院，四川 宜宾644000

自动导引车（Automated Guided Vehicle，AGV）作为一种全自动或半自动的运载工具，服务于制造行业。其优点是载重能力强、运载起止地准确、运载时间可准确控制、无人化、节能、高效、绿色、工作环境适应性强等。自动导引车的应用帮助制造类企业节约了人力成本，实现了车间自动化中物料和工件运输这一关键步骤。自动导引车能够与各物料站点和机器工位之间形成协调配合的工作方式，让每一台机器都能尽最大可能发挥其工作效率，从而提高工作车间的整体生产效率。20世纪50年代，美国Basrrett Electric公司发明了第一台用于仓储货物运输的自动导引车以后，自动导引车随即开始服务于制造业[1]，乃至于当今的服务业、公共安全等领域。

AGV服务于制造企业，离不开其良好的调度系统，文献[2]主要对2018年及以后国内外AGV调度领域的文献进行了综述。本文主要针对文献[2]以后的最近三年制造车间AGV调度领域的文献进行了分析，对研究的问题、研究的方法进行了归纳总结，指出了现阶段存在的不足，对将来的研究方向提出了一些建议。

1 AGV调度问题描述

制造企业中AGV系统包括AGV小车、充电桩[3-4]、运行路径[5-8]、缓冲区[9]、作业工位以及其他协同配合的机器[10-11]等。AGV调度优化的目的是保证完成相应的生产搬运任务，同时保证某项或某些性能指标达到最优。

AGV调度的数学模型一般可表述如下：

公式中ai、bi、ci为常数，l、m、n为非负整数。公式（1）中f(x)为待优化的目标函数；公式（2）、（3）为不等式约束；公式（4）为等式约束。约束条件一般包括AGV与任务之间的分配关系，AGV与其他设备（如机器）的匹配关系，AGV和/或其他设备的处理过程持续不能中断，AGV和/或其他设备的作业顺序、开始/完成时间、故障和修复时间[12]，物料装卸顺序，AGV提前或延迟到达工位，AGV可承载的容量，解空间搜索区域，AGV运行方向，AGV电池余量等。

AGV调度优化的目标函数f(x)可以是单独一个优化目标，也可以是多个优化目标。当今制造车间的规模较大，且倡导节能减排的绿色生产政策，加之现如今计算机的算力进一步提升，AGV调度的目标函数是以两个或者更多优化目标为主。近三年的文献中大多数文献的研究工作均是以双目标和多目标优化模型展开研究的。

AGV调度的优化目标函数包括总完工时间、运输总成本、工件加工成本、周期时间、AGV数量、AGV空载运行时间、AGV电能消耗、AGV等待时间、AGV提前到达代价、AGV延迟到达代价、负载平衡等，多目标优化可表示为：

公式（5）中x为优化模型中考虑的变量；L为目标函数的个数；ωj为第j个目标函数的权重因子，并且满足用来调整第j个目标函数fj(x)的取值范围。

AGV调度优化的另一个关键问题是优化算法的选择和改进，以适应特定的优化需求和优化模型。现阶段最常用的优化算法是智能优化算法，尤其是遗传算法大量被用来求解调度模型。优化的结果可由表格呈现，也可以用甘特图（Gantt chart）绘制出更直观的优化结果。

2 AGV调度智能优化算法

AGV调度的优化方法主要有：传统分析方法、建模与软件仿真法、智能优化算法、混合优化方法等[2]。近三年，主要的研究方法是基于智能优化方法中的遗传算法为基本算法框架，并在其框架之上与其他智能优化方法的部分算子或者其他优化技术相结合的方法。

2.1 基于遗传算法框架的算法

遗传算法是模拟生物进化的一种智能优化方法，通过迭代进化找出可行域中的最优解或近优解。遗传算法相比于其他智能优化方法最大的优势在于能够跳出局部最优，实现广域搜索。为了实现更快的搜索速度，通常将其他智能优化方法的部分算子与遗传算法相结合，如文献中有：灰狼优化算法（Grey Wolf Optimization，GWO）、鲸鱼优化算法（Whale Optimization Algorithm，WOA）、差分进化算法（Differential algorithm，DE）、粒子群优化算法（Particle Swarm Optimization，PSO）、蚁群算法（Ant Colony Optimization，ACO）、迭代贪婪算法（Iterated Greedy Algorithm，IGA）；此外，也将其他优化技术与遗传算法相结合，如：局部搜索、精英保留策略、排队论、模糊、自适应交叉率和变异率、拍卖（Auction）等。相应的关键字索引见表1。

表1 基于遗传算法的方法中关键字索引Table 1 Keywords index in methods based on genetic algorithm

遗传算法在初始化阶段通过整数编码将待优化工序编码成为遗传算法中所使用的染色体。染色体在遗传算法迭代优化过程中可能出现不合理的情况，在每一次遗传操作后设置染色体合理性检查机制，对不合理的染色体进行重新生成或者进行修补。另外，在算法刚开始迭代的阶段，必须保证种群中染色体的多样性[7]，或者采用足够大的种群进行实验，以使算法能够尽可能大地搜索整个解空间，提高优化质量。

Wang等[13]根据AGV的电能消耗和完工时间建立调度模型，提出的改进遗传算法中增加了任务序列与AGV电池电量匹配，还增加了AGV充电判断。Chen等[14]研究空间受限场景下的AGV调度问题，采用遗传算法进行求解，算法中使用汉明距离评价种群多样性、使用灾难算子增加种群多样性，并且通过灵敏度分析，筛选出遗传算法的最佳参数值。Zhang等[15]提出了一种混合负荷AGV调度模型，分析了混合负荷AGV的优缺点，该模型根据不同物料的规格配置不同类型的AGV，采用遗传算法求解汽车装配站的最小总物流成本。Rahman等[16]建立物料运输的混合整数线性规划（Mixed integer Linear Programming，MILP）模型，提出遗传算法和迭代贪婪算法进行求解，以保证物料的顺畅流通。Lu等[17]采用遗传算法和基于时空图的蚁群算法相结合来优化混合模型装配线的效率。李峥峰等[18]用改进的遗传算法求解多AGV作业车间调度问题，并分析了运输时间、AGV数量和电量之间的相互影响关系。

为改善初始种群的质量的影响，李广博等[19]针对柔性制造车间的AGV调度，在遗传算法中设计了一种包含启发式与随机结合的初始解。Qu等[20]针对汽车装配系统中的AGV调度问题，提出了一种改进的遗传算法，根据物资需求点的时空距离对物资需求点进行聚类，生成初始种群。Rahman等[16]提出两种启发式算法来生产元启发式算法的初始解。

遗传算法中固定的变异率和交叉率致使算法求解时间长，学者们通过引入自适应交叉率和变异率来动态调整整个求解过程中的交叉率和变异率，以缩短求解时间，并提高解的质量。Mousavi等[3]和岳笑含等[4]讨论了柔性制造系统中的多目标AGV调度，分别提出一种模糊混合遗传算法粒子群优化（GA-PSO）算法，在考虑AGV电池充电的情况下，求解最小完工时间和最少AGV数量。其中遗传算法部分采用模糊逻辑调节交叉率和变异率。Umar等[8]提出了一种基于混合遗传算法的FMS环境下作业与AGV集成调度、分配与无冲突路径规划算法，算法中采用模糊逻辑控制技术自适应地控制交叉率和变异率。李广博等在文献[19]中采用线性调节的方法动态调整变异率。Liu等[21]建立仓库自动分拣系统AGV多目标调度模型，将两种自适应遗传算法和一种多自适应遗传算法相结合进行求解。

在AGV调度优化模型中单目标函数往往可以用一条染色体编码链进行表示，但是针对多目标函数的组合优化模型，使用单条染色体表示将增加交叉和变异算子设计的复杂性。因此，贺长征等[5]使用遗传算法求解柔性作业车间的AGV调度问题时，在算法中设计了三链式编码结构及AGV编码链的交叉、变异算子，同时在遗传算法的解码操作中将Dijkstra算法与时间窗原理相结合，规划出一条无碰撞无冲突的最短路径。Xiao等[6]建立了柔性作业车间中的单向路径网络AGV调度模型，分别用二进制染色体和整数编码染色体表示单向路径网络和任务序列。

遗传操作中突变算子使算法能够跳出局部最优，实现广度搜索。其局部搜索能力的提升除调节交叉率，还可以引入其他优化技术。正如遗传算法中的随机选择操作会破坏种群中的优良个体，为了避免这种逆优化现象，往往将精英保留策略加入到遗传算法中。王体春等[22]针对仓储生产环境中多AGV调度问题，建立了仓储多AGV调度的M/M/s/Ps排队模型，用排队论分析目标函数，采用融合精英保留策略的遗传算法进行求解。Xiao等[6]将小生境技术、领域搜索、精英保留策略等融入双种群协同进化遗传算法对单向路径网络AGV调度模型进行求解。Lee等[23]建立了基于组合拍卖（Combinatorial Auction，CA）的多AGV竞胜标确定问题（Winner Determination Problem，WDP）模型，提出了一种基于知识算子的遗传算法，来解决多AGV系统中的调度与路径规划整合的难题。Rahman等[16]提出一种两步局部搜索方法。詹逸鹏[24]采用基于文化算法框架的改进NSGA-III（Non-dominated Sorting Genetic Algorithm）算法，对多AGV调度的多目标优化模型进行求解。

遗传算法和其他智能优化方法组合的混合优化方法将各算法的优点组合在一起，可以获得优于其中任意一种优化算法的优化效果。熊晔等[9]建立了缓冲区有限的AGV调度模型，并提出一种混合灰狼遗传算法（HGWOGA）进行求解。该算法在遗传算法的选择操作步骤加入了灰狼社会等级制度和狼群狩猎机制，相比精英保留策略，提升了全局搜索能力。差分进化算法有较快的收敛速度，杨智飞等[25]提出一种引入差分进化的自适应多目标遗传差分进化算法（Adaptive Multi-Objective Genetic Algorithm with Differential Evolution，AMOGA-DE）求解制造车间多AGV调度问题。李西兴等[11]在鲸鱼优化算法中引入遗传算法的交叉、变异操作来提升全局搜索能力，并使用邻域结构和精英保留策略来提升局部搜索能力，提出了一种混合遗传鲸鱼算法来求解AGV和作业车间集成调度模型。Goli等[26]将AGV考虑进单元制造系统（Cellular Manufacturing System，CMS）模型中，建立了一个模糊MILP模型，并提出混合遗传算法和鲸鱼优化算法进行求解。在调度优化阶段引入路径规划算法，得到的优化结果可以保证路径可行性，有较高的工程实际价值。Lyu等[7]将基于时间窗的Dijkstra算法嵌入到遗传算法中，同时解决AGV的调度和路径规划问题。但是文中每一次算法迭代都需要进行路径规划，无疑大大增加了时间复杂度。Xu等[27]针对柔性制造系统（Flexible Manufacturing Systems，FMS）中AGV的多目标多维优化调度问题，提出了分段编码遗传算法（SE-GA）、分段编码离散粒子群优化算法（SEDPSO）和分段编码遗传算法与离散粒子群混合优化算法（H-SE-GA-DPSO），实验结果表明H-SE-GA-DPSO算法优于其他算法。利用物联网技术实时获得的请求信息，Xu等[28]提出了一种动态调度方法，从分配给AGV的任务序列和AGV分配两个维度对智能制造车间的物流调度过程进行考虑，结合双层混合遗传算法和蚁群优化算法（DLH-GA-ACO）进行求解。采用遗传算法求解AGV调度的还有Yao等[29]。

许多学者已经研究了AGV数量对优化目标的影响，通过减少AGV的数量可以节约很多建设成本，并且可以降低AGV路径冲突概率。不过，在建立AGV调度模型时，常常忽略了众多因素，如装卸时间、生产环境中的缓冲区容量、AGV突发故障以及AGV差异性等。在实际生产环境中存在AGV运行速度变化，发生突发故障，生产计划变更，AGV的充电时间和续航时间各不相同等因素需在建模时予以考虑。其次，绝大多数调度优化均是静态调度。另外，相比单载量AGV已经开展的工作，多载量AGV调度的研究还有许多方面未考虑到，比如电能消耗、提前到达和延迟到达代价、物料分配平滑性等。

2.2 其他智能优化方法

最近三年除了占主导地位的遗传算法，AGV调度中使用的其他智能优化方法还包括：鲸鱼算法、花授粉算法（Flower Pollinaton Algorithm，FPA）、蝙蝠算法（Bat Algorithm，BA）、差分进化算法、模拟退火算法（Simulated Annealing Algorithm，SAA）、入侵杂草优化算法（Invasive Weed Algorithm，IWA）、布谷鸟搜索算法（Cuckoo Search Algorithm，CSA）、和声搜索算法（Harmony Search Algorithm，HSA）、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）、蚁群算法、禁忌搜索算法（Tabu Search，TS）等，相应的关键字索引见表2。

表2 其他智能优化方法中关键字索引Table 2 Keywords index in other intelligent optimization methods

AGV调度是整数规划问题，需要对智能优化算法进行改进来适应待求解的模型。Barak等[30]将柔性制造系统中的AGV和机器都视为资源，建立了考虑AGV燃料消耗的多目标生产调度模型，提出了一种改进多目标粒子群优化算法（MMOPSO）来求解。Zou等[31]提出了一种新的迭代贪婪算法。

模拟座头鲸捕食猎物的方式，2016年提出了鲸鱼优化算法，该算法提高了优化求解速度，但是其易陷入局部最优值。徐云琴等[32]针对FMS中的AGV调度问题，建立了考虑学习效应和恶化效应的最短完工时间的调度模型，并提出一种具有混沌搜索策略的鲸鱼算法来防止陷入局部最优解。邹裕吉等[33]提出一种离散鲸鱼优化算法，采用三段式编码，设计一种结合混沌映射和对立学习的扩展GLR种群初始化方法和三种邻域结构，同时采用基于时间窗的Dijkstra算法进行无冲突路径规划。同样，为了避免蝙蝠算法早熟和陷入局部最优，魏永来等[34]建立了包含物料配送AGV的路径、时间和成本的多目标优化模型，提出一种混合禁忌蝙蝠算法来求解模型。该算法中采用ROV规则的编码，并且融合了禁忌表、藐视准则和几种局部搜索策略。伍乐等[35]建立一种机器和AGV双资源约束调度模型，提出一种改进离散差分进化算法进行求解，在算法中引入了模拟退火算法和变邻域结构来提升解的质量。刘二辉等[36]对机器和AGV集成调度问题，提出一种基于改进花授粉算法进行求解。为保证算法跳出局部最优和种群多样性，该算法中包含了基于染色体相似度矩阵的初始解、交叉算子和基于主成分分析法的变异算子。

入侵杂草优化算法模拟自然界中杂草的扩散、繁殖和竞争性生存的过程，迭代过程中根据个体适应度值确定产生种子数量，并且使用正态随机数和非线性调节因子进行局部搜索。同样，布谷鸟搜索算法模拟自然界中布谷鸟将鸟蛋下在寄生鸟巢中，由寄生鸟进行孵化并抚养，只有优质的鸟巢才能进入下一次迭代。Nabovati等[12，37]建立了机器和AGV的同时调度问题的双目标MILP模型，在模型中考虑了机器的故障时间和修复时间，提出了一种新的约束条件的染色体结构，并先后提出模糊多目标入侵杂草优化（Fuzzy Multi-objective Invasive Weeds Optimization，FMOIWO）算法和模糊多目标布谷鸟搜索（Fuzzy Multi-Objective Cuckoo Search，FMOCS）算法两种元启发式算法来求解该模型。其实验结果表明，改进的FMOIWO搜索算法在求解大、中、小规模问题时具有较好的性能。

和声搜索算法的迭代过程中，和声总是朝着越来越好的方向发展，为提升其全局搜索能力，需加入保持多样性的结构。Li等[38-39]建立了制造系统中AGV调度的双目标函数数学模型，提出了一种改进和声搜索算法进行求解，算法包括有效的和声离散编码方案、基于对立面学习策略的和声库初始化方法、动态记忆库取值概率以及局部搜索策略。

人工蜂群算法模拟自然界中蜜蜂寻找最佳蜜源，通过生成良好的初始解，并融入适当的局部搜索方法，可以提高算法的全局和局部搜索能力。Zou等[40-41]针对制造车间中AGV调度问题，提出了一种包括基于启发式的初始化方法、几个邻域操作算子和一种新的跟随蜂进化策略的离散人工蜂群算法，用于求解物料搬运过程中的AGV运行序列。

为满足特定的模型求解，也将智能优化算法和其他优化方法结合起来。Rahman等[10]研究以作业周期时间和总延误最小为目标的机器人装配线平衡和AGV调度问题，提出一种基于启发式和粒子群优化算法的分步优化算法。Zou等[42]建立了带提货和交货的AGV调度的多目标优化模型，并设计了一种引入了重启策略和双点交叉的高效多目标进化算法。

智能优化算法被用在AGV调度模型的求解中，但算法大多处于理论研究阶段，并未在生产环境中得到应用。与实际生产环境相比，调度模型还有许多影响因素需要考虑，如AGV冲突问题。多目标优化的研究要比单目标复杂得多，但是现阶段往往需要考虑多个优化目标。另外，智能优化算法都是单向迭代求解，没有信息反馈机制，在迭代过程中可能破坏最优解结构。

3 其他AGV调度优化方法

相比智能优化方法，采用其他的优化方法的文献数量要少得多，使用的方法有基于规则的调度优化方法和建模与软件仿真方法，较老的方法有拉格朗日松弛法（Lagrangian Relaxation，LR）和蒙特卡罗树搜索法（Monte Carlo Tree Search，MCTS）。另外，人工神经网络（Artificial Neural Network，ANN）、暴力枚举算法（Brute Force Enumeration Algorithm）、分布估计算法（Estimation of Distribution Algorithm，EDA）和基于网络概念的算法则很少被应用于AGV调度优化上。相应的关键字索引见表3。

表3 其他优化方法中关键字索引Table 3 Keywords index in other optimization methods

基于规则的方法能够保证实际生产环境中的AGV正常运行，但是其结果几乎不能达到最优调度要求。同时辅以软件仿真，能够直观看到AGV运行动态情况，有利于调整规则和规则中的参数。陈敏等[43]提出了7种多AGV调度规则，分别是FCFS规则、Random规则、SPT规则、ESD规则、Nearest规则、Farther规则和基于软时间窗的Window规则，采用Plant Simulation仿真软件对以上规则进行实验比较，结果表明基于软时间窗的AGV调度规则表现较好。Zhao等[44]针对车间多AGV调度问题，应用优先级规则进行调度，同时还使用A*算法进行路径规划。Fontes等[45]建立机器调度和AGV调度的新MILP模型，并用商业软件Gurobi进行求解。

有新的网络理论被用来优化AGV调度问题。Gyulai等[46]从物流网络模型出发，利用网络科学的概念和方法来发现AGV车队管理问题中的隐藏结构，将这种基于模块化的结构用于平衡车辆的预期负载和动态调度。

人工神经网络、蒙特卡罗树搜索、分布估计算法等算法被少数学者改进和适配后用来求解AGV调度问题，在一些模型上也取得了与智能优化方法相近的优化效果。Fazlollahtabar等[47]建立了一种能满足AGV无冲突路径的调度模型，并提出了一种面向路径网络的启发式搜索算法和求解方法。李红[48]采用动态蒙特卡罗树搜索和变邻域局部搜索对AGV运输任务顺序进行优化。戴敏等[49]建立了机器和AGV集成调度下的多目标能耗模型，并提出了一种改进分布估计算法进行求解，在算法中设计了良好的初始化、局部搜索机制和模拟退火择优。Fazlollahtabar[50]对AGV加工和等待时间与制造车间的路径进行了建模，提出了一种拉格朗日松弛法，并用次梯度法对搜索过程中的迭代次数进行更新，实验结果表明针对大规模问题该方法的求解速度较快。采用改进的A*算法进行路径规划，并采用博弈论的方法消除行驶过程中产生的冲突。Zeng等[51]提出了一种基于拍卖的启发式方法来解决机器和AGV的分配问题，并设计了一种改进的析取图模型，以优化基于拍卖的方法得到的可行解。Heger等[52]基于随机到达时间的离散事件仿真研究，训练人工神经网络，学习排序、调度、路径规划等不同规则组合之间的交互效应。基于训练好的网络，对物料搬运的AGV作业时间进行优化。Gutjahr等[53]优化FMS中AGV数量和完工时间，利用暴力枚举算法求解。Gao等[54]研究共轨双AGV的协同调度问题，建立双AGV调度模型，提出一种基于时间窗的订单动态调度方法。Chawla等[55]将自然启发算法和优先级混合调度规则应用于自动导引车辆（AGV）的同时调度和分配上。孙阳君等[56]提出了一种基于数字孪生的多AGV系统集中式调度方法，保证虚拟系统与物理系统一致性，并对物理系统中的变化及时响应调整。还有其他AGV调度的组合优化问题的求解方法，见文献[57]。

大规模调度问题和动态调度问题研究的不足，与智能优化算法相同。其中商业软件仿真法的求解速度受到软件自身的求解器极强的约束；人工神经网络的模型搭建、模型的超参数调整、现实生产现场数据集等都需要进一步完善。

4 总结及未来工作

制造车间AGV调度问题的研究，帮助指导制造车间完成生产任务的同时也为企业节约了不少成本和时间。另外，AGV调度问题的研究也为搬运系统的建设提供了参考建议。现阶段AGV调度仍然存在一些问题和不足：

（1）建模方面的不足。建立的数学模型作为一种对现实情况的抽象，并不能完全反应真实情况，并且需要在经济适用性和模型准确性之间做一个平衡。

（2）大规模场景的优化研究较少。绝大多是已有的研究均是基于静态调度和小规模场景开展的，而随着AGV的规模增大，求解时的计算量将呈激增态势，不能满足实际生产的要求。

在大数据，人工智能的盛行的当下，制造车间的AGV调度问题可以有以下几个值得开展的研究方向：

（1）多载量AGV调度。对于多种类小数量的物品输送搬运任务，若采用小型AGV运输，则场景中AGV数量巨大，导致调度困难且故障率增加；若采用大型AGV运输，还存在资源浪费的问题。因此采用一台AGV运输多种物品是一个值得研究的方向。与单载量AGV相比，多载量AGV[15]能够以较少数量的AGV完成相同的任务量，并且较大程度利用了AGV的运载能力，减少能源消耗。

（2）基于人工智能的突发状况识别和AGV作业预测。对于大规模的AGV场景中，AGV拥挤的运行区域更容易发生运行故障和降低AGV系统搬运效率，可以采用人工智能的方法对有碍于AGV运行的突发情况进行预测，并做出相应的决策以保障系统高效运作。尤其是针对大规模AGV场景，能够避免因少数AGV发生冲突和故障进而导致大量AGV发生冲突或故障损坏，造成的延误和损失。同时，利用人工智能的方法对生产制造环境下的不确定时间物料运输进行预测也可以起到提升企业生产效率的作用。

（3）动态调度。现阶段的AGV调度研究是以静态调度为主，对于动态情况下可能出现的差异性未做考虑，比如出现突发AGV故障或环境故障、生产计划变更[25]、AGV由于充电完成或故障恢复时进入、充电或故障发生时退出等，因此动态调度[28]可以作为一个研究方向。

（4）基于大数据的实时AGV调度与路径规划算法。随着传感器、物联网等技术的发展，工业大数据已经成为当今的热点。利用工业大数据来搭建AGV调度和路径规划的模型，巨大的数据量可以保证更多的实际运行情况被考虑进来，保障AGV的实时运行性能，提高搬运系统稳定性。尤其是针对大规模AGV场景，能够避免因建模困难、分布式计算造价高且系统复杂等困难。