基于智能计算方法的AGV制造车间调度问题研究现状*

2021-09-26王亚东蔡国旗夏琴香程秀全

机电工程技术 2021年8期

马骏，王亚东，蔡国旗，夏琴香，程秀全

（1. 珠海格力精密模具有限公司，广东珠海 519070； 2. 华南理工大学机械与汽车工程学院，广州 510641；3. 广州民航职业技术学院，广州 510403）

0 引言

AGV 是由计算机控制并配备不同导航系统以实现物料水平移动的无人驾驶的车辆[1]。AGV 非常适合物料从/到多个目的地的长距离水平移动。它们也适用于重复/可预测的材料运输和/或危险任务[2]。AGV 的运行控制可以集成到计算机控制系统中，也可以自身集成导航与控制为一体来进行工作，多AGV组成的系统一般都由远端计算机进行中央控制。AGV到目前为止已经广泛应用于制造、物流等领域。在柔性制造系统（Flexible Manufacturing System，FMS）中，AGV 能同机床共同协作，在不同机床间传递物料，一般运输盛放物料/货物的托盘；自升式AGV可以应用在自动化集装箱码头等转运系统上，而无需其他设备将负载转移到车辆上[3]。在仓储中，AGV 不仅能够将物料从仓储位置运送到所有工作中心，也能够在各工作站点间来回传送。

高效的调度对于AGV应用至关重要，不仅仅能够减少能耗，而且能够减少系统中机器的待机时间，提高整个系统的工作效率。术语 “调度” 是指将AGV分配给任务的过程，考虑到完成操作成本和所需时间[4]。考虑到调度问题的目标、局限性和考虑因素的多样性，不断改进的AGV调度以获得在真实环境的效果仍然是当前研究热点。大型AGV系统需要建立新的分析和仿真模型，以克服计算量大、NP 完全性、拥塞、系统死锁和延迟以及有限的规划时间[5]，AGV调度准则大概有6 个：（1）完工时间；（2）总完工时间；（3）平均流动时间；（4）平均等待时间；（5）延迟时间；（6）拖期。到目前为止，大多数AGV调度的文献很少考虑特别的约束场景，如运输作业过程中单个AGV负载大小约束、制造车间与其他设备相配合调度形式以及待机过程时停靠的最优位置，这些约束在大型AGV系统的实际应用中变得越来越重要。

智能计算（Intellectual Computing，IC）是人们面对生物进化后逐步适应现实世界的规律进行模仿设计的算法。解决AGV 调度问题需要合适的数学优化算法，智能计算方法为解决AGV 调度问题提供了众多优秀的算法，主要包含遗传算法、粒子群算法、蚁群算法、人工神经网络等。本文主要通过群智能计算、遗传算法、人工神经网络等主流算法开展对AGV 调度研究，主要涉及车间柔性制造系统研究进展及前景的探讨。

1 群智能计算

群智能（Swarm Intelligence， SI），也称仿生网络（Bio-inspired networking，BIN），是由一组自由个体（individ⁃ual/agent）遵循简单行为规则、通过个体间的局部通信以及个体与环境间的交互作用而涌现出来的集体智能行为的自组织特性，是对现实世界中的群居性生物或人工群体所呈现出的有序群行为（Swarm behavior）的抽象[6]，群智能计算是指利用群集优势在没有集中控制、不提供全局模型的前提下，可由大量简单个体组成的群体分布式协作寻找复杂问题最优解。

群智能计算方法属于启发式计算方法，其涉及模型通常具有生物激励的特性，主要包括蚁群算法、粒子群优化、人工免疫系统、智能水滴算法、分组搜索优化、鱼群搜索算法、细菌趋药算法、萤群算法、蜜蜂交配优化、跳蛙算法、入侵性杂草优化、蝙蝠算法[7-13]等。

1.1 粒子群优化

粒子群优化（Particle Swarm Optimization，PSO）最初是用来研究模拟鸟群寻找食物的集体行为，其基本原理是种群中每个成员作为独立粒子在每次迭代中以一定的速度和加速度向更好的位置移动，图1 所示为每代任意粒子迭代过程[17]，最终求得最佳位置得到问题的解。粒子群优化算法运算高效、结构简单，是近些年来研究FMS 调度问题，特别是具体到车间AGV系统调度研究热点。

图1 粒子迭代框架

FMS 中的调度问题能很好地用PSO 方法解决，比如在对于车间与AGV 同步调度研究上，Murata 等[18]采用二元粒子群优化算法(Binary Particle Swarm Optimization，BPSO)用最大完工时间最小化的函数对多台机床与AGV调度进行了优化。通过与时间窗（Time Windows Approach，TWA）方法[19]、遗传算法（Genetic Algorithm coding by Ulusoy）[20]、遗传算法（Ge⁃netic Algorithm coding by Abdelmaguid）[21]进行对比，BPSO 在应对机床与AGV同步调度中总体性能表现更好。Zhang等[22]针对多品种、小批量生产订单驱动的AGV服务制造系统的优化问题进行了研究，以机床与AGV 的利用率为综合评价函数，建立了一种集成机床与AGV的调度模型，并提出了一种改进的粒子群算法（Improved Particle Swarm Optimization，IPSO），算法具有主粒子与嵌套粒子的特点。通过实验与PSO 和遗传算法（Genetic Algorithm，GA）相比，嵌套粒子群算法收敛和求解效率方面具有更大优势，能够为AGV服务制造系统的柔性调整提供有益借鉴。

PSO 与其他算法相结合较为容易，学界已经有基于PSO的混合算法来研究AGV 调度问题。Mousavi 等[23]将PSO 与GA相结合研究了在FMS 的多目标AGV 调度问题，特别考虑了AGV电池损耗的影响，通过最小化AGV的最大完工时间和数量建立了多目标数学模型，通过对单一算法（PSO/GA）与所提算法进行试验，3种算法都具有对问题解决的适用性，混合GA-PSO算法在平均AGVs运算效率具有更高的效率。在考虑FMS的工作中心处理最小行程和等待时间上，Chawla等[24]提出了多负载AGV 和任务的同步调度思想，将PSO 与因模算法（MA）相结合，提出了一种改进文化基因粒子群算法（Modi⁃fied Memetic Particle Swarm Optimization，MMPSO），试验结果表明，与PSO算法相比，MMPSO在多负载AGV的实施动态调度具有更好的效果，能够有效生成多负载AGV调度问题的最优初始解。

1.2 蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是Dorigo 于1995年通过模拟自然界中蚂蚁觅食行为的集体寻径行为而提出的一种基于种群的仿生进化算法。与粒子群算法一样，自20世纪90年代诞生以来，两者在智能算法领域引起了研究者们巨大兴趣。相比较于其他算法，ACO 最显著的特点是采用了正反馈的机制，单个个体只能够感知局部信息，不能直接利用全局信息。

ACO 每一次迭代中，都会考虑一些人工蚂蚁，其中的单个个体都通过在假定的路径图从一个点走到另一个点来构建一个解决方案，并且限制不访问其在行走中已经访问过的任何顶点。在解构造的每一步，蚂蚁都会根据信息素偏向的随机机制选择要访问的下一个顶点：在顶点i中，下一个顶点是在先前未访问的顶点中随机选择的，如图2所示[25]。

图2 城市中的蚂蚁通过一个随机机制选择下一个要访问的城市

在过去10年间，有学者对ACO能否为制造业中AGV小车提供更多智能理念进行了探索[26]，研究针对ACO在AGV系统设计与控制中应用是否具有可行性，但研究未见在具体到调度方面。对于车间AGV调度问题学界利用该算法也进行了探索。针对AGV的无冲突路由问题（CFRP）和最基本的车间作业调度问题（JSSP），Saidi-Mehrabad 等[27]研究了AGV 的车间作业调度问题（Job-Shop Scheduling Problem，JSSP）和无冲突路由问题（Conficlt-Free Routing Problem，CFRP）的集成模型，提出了一种混合整数线性规划模型，并采用两阶段蚁群算法进行求解。该项工作意义在于通过建立混合整数数学模型来同时考虑JSSP 和CFRP 的问题，最后通过采用ACA 进行求解。结果表明，与Exact算法相比，在时间上ACA能够更有效率地得出结果。

有学者对ACO 结合其他算法进行对调度问题进行了研究，Deng 等[28]提出了一种基于多种群策略、协同进化机制、信息素更新策略和信息素扩散机制的改进蚁群算法（Im⁃proved Ant Colony Optimization，ICMPACO），平衡了收敛速度和解的多样性，提高了求解大规模优化问题的优化性能，能够很好解决经典的旅行商问题和门分配问题，在未来势必将会为AGV调度研究中能够利用ACO提供理论参考。

1.3 人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）是模仿蜂群提出的一种优化方法，其主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各个个体间的协作来寻找最优解的算法。迄今为止，利用ABC 对现实世界的研究最为广泛[29]。

由承办部门将合同相关的签约依据、相对人资质、合同文本等资料分类上传至合同管理信息系统并送审。合同承办部门应对所提交资料的真实性、合同草本中标的金额的准确性、一致性等负责。

虽然ABC 研究领域众多，但是在调度问题上目前研究较少，至于车间中AGV调度问题，近年来才逐渐引起研究者们兴趣。Baradaran 等[30]提出了一个二元人工蜂群算法（Binary Artificial Bee Colony，BABC）去研究了伴有多个硬性优先时间窗口和一个异构车辆的路径问题。Zou等[31]针对线型制造车间的物料搬运中AGV 调度问题，以最小化单元等待时间和AGV 总行驶距离两者的标准差最小化为目标，提出了一个有效的离散人工蜂群算法（Discrete Artificial Bee Colony，DABC），包含了基于启发式的初始化、六邻域结构和新的旁观者蜂群进化策略。

1.4 其他群智能算法

除了以上较为热门的群智能算法外，还有一些优秀的群智能算法已经被用来研究制造系统中AGV 调度问题，如：Gnanavelbabu 等[32]利用人工免疫算法（Artificial Immune Sys⁃tem，AIS）研究了FMS 中生产任务、AGV、自动存储与检索系统的多目标调度。随着群智能算法研究不断发展以及计算能力的日益提高，势必将对车间AGV复杂调度问题提供更好研究支持。Nabovati等[33]研究一种新的机床与AGV同时调度模型，提出了两种元启发式算法：模糊多目标入侵杂草优化算法（Fuzzy Multi-Objective Invasive Weed Optimization， FMI⁃WO）、模糊多目标布谷鸟搜索算法（Fuzzy Multi-Objective Cuckoo Search Algorithm）。计算结果表明，FMIWO 在求解问题方面具有最好的性能。

目前还有一些已发掘的群智能算法尚未应用研究到AGV调度问题中，伴随着智能制造未来实施推进，某些群智能算法适合于解决特定场合的AGV调度问题将会被研究发掘。特别当应对AGV群规模比较大的调度问题时，群智能算法将会发挥其独特地能够解决大型优化问题的特性。

2 遗传算法

遗传算法(Genetic Algorithm，GA)是由John H于1975年用来被理解为一个基于基因和自然进化机制的优化复杂方程过程，基本算法模型如图3所示。2001年，Ponnambalam等[34]指出GA 是最流行的进化算法类型。遗传算法所取得的良好效果，使许多研究者开始将其应用于求解AGV调度问题，包括FMS 环境中涉及到有关AGV 配置[19-20,34-42]，以及仓储[43]、自动化集装箱码头[44-45]等领域。

图3 遗传算法模型

21世纪初，Ulusoy[35]应用遗传算法研究了在FMS中机床与AGV 同步调度的问题，分析了算法对应包含有6 个加工中心和2 个AGV 的3 种不同FMS 布局配置下算法的性能，性能研究结果验证算法的优越性，也验证了该算法非常适合解决此类问题。Sankar[36]对新到生产任务、机床和AGV 的同步调度进行了探索，利用1 台AGV 和4 台机床组成的FMS 进行了遗传算法优化及计算机仿真的思想，通过与其他算法（Kangaro算法）进行对比验证了算法的有效性和优越性。Taghavifard等[37]利用调度规则和遗传算法以最小化制造周期来研究机床与AGV 的同步调度问题，将实验结果与其他文献的最优值进行比较，并强调了该方法在效率与求解质量方面的有力性能。

近几年来，遗传算法应用不断发展，大多以改进形式研究应用在众多行业，尤其在制造领域[38-41]。Ren 等[39]根据协同制造系统特点，提出了一种改进的遗传算法来求解协同制造系统的生产效率问题，改进算法不仅优化了基因序列，而且优化了作业操作序列和AGV运动序列。仿真结果表明了该改进算法有效性，与标准遗传算法相比更加有效率。针对以往研究采用固定数量AGV或不考虑路由和运输时间的问题，Lyu等[40]通过考虑AGV 的最优数量、最短运输时间、路径规划问题、无冲突路由问题，提出了一种结合基于时间窗和Dijkstra算法的遗传算法。通过两组实验表明，算法在求解调度问题上与基准方法同样有效，同时也适用于FMS 中集成调度问题。Chen 等[41]研究了基于空间约束AGV 的预制浴室单元（PBU）制造系统的调度问题。为了防止死锁情况，必须控制PBU 的生产启动时间，提出的遗传算法能够确定每个工作站操作，并为每个PBU 选择一个启动时间。通过实际的工业项目数据的实验验证了该算法的有效性。Liu等[42]将两种自适应遗传算法（Adaptive Genetic Algorithm, AGA）和一种多目标遗传算法（Multi-adaptive Genetic Algorithm，MAGA）相结合，建立了AGV的多目标数学模型，并将其应用于AGV任务调度中，还考虑了AGV的充电任务和速度变化，最小化了AGV最大完工时间、使用数量、电量损耗。实验证明MAGA 在3 种算法表现最好，优化前后目标值变化30%，验证了模型和MAGA算法的有效性。

已有学者基于GA 结合其他智能算法也开展了FMS 的AGV调度研究[18,46]。Umar[46]提出一种基于遗传算法的FMS环境下作业和AGV的集成调度且无冲突路由选择的算法。该算法在考虑优化最大完工时间、AGV 的旅行商问题和由于冲突而导致作业延误和延迟的因素的同时，生成一个完整的调度和详细的路由路径。采用模糊专家系统对遗传算子进行控制，提高了前两代群体的群体性能。该算法特点是考虑了AGV调度、作业调度、路由选择各因素，保证了各集成要素可行性和有效性，通过计算实验验证了算法的有效性。

遗传算法目前仍是最重要的优化方法之一，在工业界的建模设计、优化、控制等等方面发挥着巨大的作用，随着AGV 智能化程度和车间等应用场景复杂度提高，将来应用遗传算法进行AGV调度研究将会继续发展下去。

3 人工神经网络

人工神经网络（Artificial Nueral Network，ANN）又简称为神经网络，是一种模仿生物神经网络（动物的中枢神经系统，特别是大脑）的结构和功能的数学模型或计算模型，用于对函数进行估计或近似，它是一种重要的智能计算方法，也是当今受到火热研究的机器学习的基础。从简单的单层神经网络（图4）发展到现在已经产生两层、多层类型网络，如BP、 Pre-training、 Drop⁃out 等，并广泛地延伸到各个学科领域，其中也包含了对于AGV 调度应用研究[47]。

图4 单层神经网络

Li等[47]针对AGV系统中死锁问题提出了一种基于ANN的AGV 调度算法，该方法充分利用了传统调度算法和深度学习（Deep Learning，DL）的优点，前者防止了死锁和冲突，后者提高了效率。Hegera[48]以简单性和小计算时间用于排序操作、路由作业和调度AGV为优先规则，训练人工神经网络，学习排序、调度、路由等不同规则组合对系统性能的影响。在训练网络的基础上，对规则的组合进行了优化，降低了系统性能变化时作业的平均延误。

随着人工智能在近几年爆发，以DL为代表的神经网络技术对智能算法被研究在AGV 中，其中Xue 等[49]采用了强化学习方法研究了多AGV 流水作业调度问题，通过定义状态特征、行为空间和报酬函数，将调度问题归结为马尔科夫问题，提出了一种强化学习的调度方法。仿真结果表明，该方法在动态环境下学习了以往的最优或近似最优解，比多智能体调度方法具有更好的性能。Hu 等[50]针对车间环境的高动态性、复杂性和不确定性的问题，以最小化车间的完工时间和延迟率为问题的目标，提出了一种基于混合规则的自适应深度强化学习AGVs 实施调度方法。根据训练过程和对比实验，该方法能够有效地基于柔性车间的场景来选择合适的调度规则和AGV。

随着大数据、5G、云计算技术兴起，基于ANN的智能算法思想正不断演化到研究于高技术产业中，对于AGV调度问题研究也正在不断被探索与应用中，本文认为虽然目前人工神经网络在AGV调度中应用较少，但是随着人工智能技术发展，未来利用人工神经网络为基础的智能学习算法的AGV调度研究势必将会成为新的AGV领域研究热点。