自动导引车与机器集成调度问题研究现状_吴斌.pdf

2023，59（6）随着工业4.0以及中国制造2025的推进，多品种、小批量、短周期、个性化的生产模式已成为常态。自动导引车（automated guided vehicles，AGV）凭借其高效可靠、绿色节能、环境适应性强等优点，实现了车间物流自动化、柔性化配送，降低了生产成本，提升了生产效率，越来越多的生产制造车间使用 AGV 进行物料运输。AGV物料输送不同于传统的物料输送系统，需要AGV小车、机器设备、工件等资源之间的协同配合才能体现AGV的优势，一旦AGV出现拥堵、故障，会对整个制造任务的加工时间、调度规划、完工交货造成影响。因此，合理地分配运输搬运任务，规划AGV行驶路径，机器设备与AGV之间的协同配合，即AGV调度就成为柔性制造车间的关键环节。AGV 调度问题可以分为静态调度（又称离线调度）、动态调度（又称在线调度）和AGV集成调度。静态调度是针对已确定的加工工件进行AGV的运输任务排序和分配，动态调度则在此基础上考虑了任务插入/变更、设备故障、路径冲突等，更符合作业车间的不确定性。自动导引车与机器集成调度问题研究现状吴斌，丁钰超，ABLA Basri南京工业大学 经济与管理学院，南京 211816摘要：随着自动导引车（automated guided vehicles，AGV）的广泛应用，柔性制造车间中机器设备与AGV之间的协同配合日益受到重视。AGV与机器的集成调度主要研究机器分配、工序排序、搬运任务的AGV分配以及AGV路径规划。该问题是极为复杂的组合优化问题，对其研究具有重要的学术意义和应用价值。围绕问题特征，从模型与算法两个方面，对国内外最新的研究文献进行了梳理。对现有模型中的约束条件和优化目标进行了详细分类，从遗传算法、混合优化算法、仿真优化算法等五个方面综述了现有算法研究中的代表性成果。在此基础上，指出了现有研究中的不足，提出了未来的研究内容和方向。关键词：柔性制造车间；自动导引车；集成调度；智能优化；混合算法文献标志码：A中图分类号：TP183；TP391doi：10.3778/j.issn.1002-8331.2207-0427Research Status of AGV and Machine Integrated SchedulingWU Bin,DING Yuchao,ABLA BasriSchool of Economics&Management,Nanjing Tech University,Nanjing 211816,ChinaAbstract：With the wide application of automated guided vehicles（AGV）,the cooperation between machines and AGVsin flexible manufacturing system（FMS）is paid more and more attention.The research of AGV and machine integratedscheduling mainly includes machine allocation,process sequencing,AGV allocation of transport tasks and AGV path plan-ning.This problem is a very complex combinatorial optimization problem,which has important academic significanceand application value for its research.Based on the characteristics of the problem,the latest research literatures at homeand abroad are reviewed from two aspects of model and algorithm.The constraints and optimization objectives of the exist-ing models are classified in detail,and the representative results of the existing algorithms are summarized from five aspects：genetic algorithm,hybrid optimization algorithm and simulation optimization algorithm and so on.On this basis,the short-comings of existing research are pointed out,and the content and direction of future research are put forward.Key words：flexible manufacturing shop;automated guided vehicles;integrated scheduling;intelligent optimization;hybrid algorithm热点与综述基金项目：国家社科基金一般项目（20BGL025）；国家重点研发项目子课题（2020YFB1712102）。作者简介：吴斌（1979），男，工学博士，教授，硕士生导师，研究方向为智能优化算法、系统建模与优化等，E-mail：；丁钰超（1998），男，硕士研究生，研究方向为智能优化调度。收稿日期：2022-07-25修回日期：2022-11-04文章编号：1002-8331（2023）06-0001-12Computer Engineering and Applications计算机工程与应用1Computer Engineering and Applications计算机工程与应用2023，59（6）02468101214162010/20112012/20132014/20152016/20172018/20192020/20222010/20112012/20132014/20152016/20172018/20192020/2022年份1614121086420篇数1511970321131中文文献数量英文文献数量02468101214162010/20112012/20132014/20152016/20172018/20192020/202202468101214162010/20112012/20132014/20152016/20172018/20192020/2022图1各两年中英文文献数量Fig.1Quantity of Chinese and English literaturefor each two years上述两类AGV调度问题已取得较丰硕的研究成果1-3，国内也有相关综述文章4-5，本文不再赘述。AGV集成调度主要研究AGV与机床设备、工件等各类资源联合调度，更符合柔性智能制造车间的实际工况，对增强调度方案的可行性和合理性、保障生产任务的顺利执行具有重要意义。因此该问题越来越受到研究者的关注。AGV 集成调度的研究始于 20世纪。1993年土耳其学者Ulusoy等6首先提出将AGV和加工设备集成调度作为研究对象，应用遗传算法求解调度问题，并建立了标准算例库。之后，Lee等7-8提出了两种用于柔性制造系统集成调度模型，构造了基于Petri网的集中式和分布式AGV车辆系统。2004年，Sankar等9-10提出先到先服务（first come first serve，FCFS）和最短旅行时间（shortest travel time，STT）两种AGV调度规则，并分别基于遗传算法和散射搜索算法（scatter search，SS）进行优化求解。Tan等11考虑机器利用率最大化、利润最大化、AGV运行时间最短、AGV能量消耗最小等，建立了多目标的优化模型，提出了基于蚁群算法的优化求解方法。国内学者在2000年之后开始对此问题的研究，李岩等12采用自适应交叉和变异策略的遗传算法并结合启发式规则对机床和AGV联合调度问题进行了优化求解。柳赛男等13针对柔性作业车间中的机床与AGV双资源约束调度问题，利用遗传算法进行求解，仿真结果证明了算法的有效性。受限于当时AGV的普及程度，不管是在学术界还是在企业界，2010年之前该问题尚未引起重视，国内外对AGV集成调度的研究还不够深入。2010年之后，AGV的应用开始普及，AGV与加工设备集成调度越发受到关注，研究文章也随之增多，但关于该问题的综述文章目前还没有。本文主要分析整理2010年到2022年中的国内外相关文献，检索的数据库包括CNKI中国期刊全文数据库、Springer Link、Webof Science、Elsevier Science Direct和 IEEE Xplore等。将检索得到的类似文章进行阅读和划分，归纳统计得到国内外关于此问题的研究论文数量如图1所示。由图1可知，2017年以前AGV与机器集成调度问题在缓慢发展。2017年之后国内外学者对AGV集成调度的逐渐增多，相关文章开始爆发式增长。这种现象的出现与2017年之后越来越多的智能化车间引进AGV辅助生产密不可分。AGV与机器集成调度比传统的柔性车间调度问题更加复杂，其研究具有重要的学术意义和现实价值，必将成为智能制造领域的研究热点。本文在阐明集成调度问题概念的基础上，从模型和算法两方面，对近期的研究成果进行了综述，提出了进一步的研究方向和内容，有助于AGV与机器集成调度的研究发展。1AGV与机器集成调度问题描述传统的柔性制造车间使用人工或叉车搬运工件物料时，搬运时间不能精确控制。因此，传统车间调度问题往往忽略工件和物料的搬运时间，或者将搬运时间放在加工时间中考虑。AGV使搬运时间的控制更精准，并且使用AGV搬运时，许多应用场景中的运输时间占比高，搬运时间不能忽略，因此必须同时考虑加工工件的机器资源和运送工件的AGV资源，将二者集成调度，才能构造一个高度灵活且高效的智能化生产系统。AGV集成调度问题可以描述为：一个生产加工系统中有n个需要加工的工件，有m台机器和v辆可供搬运物料的AGV小车。每个工件Ni(i=1,2,n)包含一道或多道工序，Oij表示工件Ni的第j道工序，每一个操作Oij都可以由其可选机器组Mij中的任意一台机器加工，MijM1,M2,Mm。同一工件的同一工序在不同机器上的加工时间会有所差异。由于同一工件的不同工序通常在不同的机器上处理，因此需要在机器与机器之间、机器与装卸货站点之间运送工件。其示意图如图2所示。工件的运输依靠AGV完成，每台AGV可以在任意机器以及仓库之间运输工件，假设AGV的行驶速度恒定不变，运输时间只取决于运输距离及路径的拥堵状况。AGV的每一个运输任务可分为空载行程和负载行程，空载行程时AGV需要从当前位置行驶到目标工位取工件，负载行程则是AGV取得工件后从所在工位运送到加工机器所在位置。在制定调度方案时，需要为每道工序选择最合适的机器，为每道工序的运输任务选择最合适的AGV，确定每台机器上各道工序的最佳加工顺序及开工时间，确定每次运输任务的开始时间和站点，使整个系统的某些性能指标达到最优。这里 加工机器自动导引车AGV装载区卸载区AGV停靠点AGV主干道UULL图2柔性制造车间示意图Fig.2Schematic diagram of flexible manufacturing workshop22023，59（6）面其实包含了机器分配、工序排序、AGV分配以及AGV路径规划四个子问题，因此，AGV与机器集成调度问题是比柔性车间调度问题更复杂的NP难题14。AGV与机器集成调度比传统柔性车间调度问题更加得复杂，因此也更具备挑战性，以下三个方面是当前研究中的难点。（1）问题的约束条件更加复杂。由于AGV的物理属性，许多新的约束条件需要考虑，如电量约束、运载能力约束、AGV路径冲突等，使问题建模与求解都更加困难。所以，算法在编码和解码的处理上颇有难点，基于机床和工序的二段式编码的求解效率更快，但在解码时如何处理约束，降低计算难度是一个难题。基于工序、机床和AGV分配三段式编码解码时相对容易，但需要在算法的运行速度和求解效率上得到加强。因此，如何降低算法的时间和空间复杂度并提高可行域的搜索效率，更加有效迅速地求解大规模场景的调度问题，AGV与机器集成调度问题研究对算法设计提出了挑战。（2）优化目标更加多样。AGV与机器集成调度更加符合制造产业的现状，为了贴近实际生产的需求，除了传统的加工时间等优化目标，交货期、生产成本、节能减排等指标也是企业关注并亟待优化的重点。因此，机器设备能耗、AGV的利用率、搬运成本、延期成本、客户满意度等都是集成调度问题的优化目标，并且目标之间可能存在冲突。研究多目标下的调度方案更具现实意义但也给模型的合理构建带来了挑战。（3）问题的不确定性增强。由于集成调度问题包含机器调度与AGV调度两个问题，涉及机器、工件、工艺、路径等多种要素，并且这些要素之间耦合性较强。设备故障、路径冲突等突发情况的出现，都会使系统原有的调度方案发生改变。在制订调度方案时，需要考虑并处理好这些不确定因素来保证调度方案的鲁棒性。这使得问题变得极为复杂，求解难度也指数级提升，在当前的研究中往往会不考虑或被忽略，如果增加对这些不确定性的研究，具有极大的挑战性。2AGV与机器集成调度问题模型2.1集成调度问题的约束条件带AGV的柔性作业车间实际调度场景非常复杂，在建立AGV与机器集成调度模型时，往往会对真实环境进行简化或理想化，忽略一些次要因素，基于主要要素进行建模分析。本文归纳总结了现有文献中各类模型考虑的约束条件，并进行了分类标注，如图3所示。现有模型中考虑的约束条件主要分为三类：工序属性、机器属性和AGV的属性。其中工序属性和机器属性与传统的车间调度问题类似。区别之处在于机器属性中多了关于对 AGV 缓冲区的约束，目前通常假设AGV 缓冲区的容量无限大。AGV 的约束条件更加复杂，如一般都默认所有AGV开始时可用，不考虑AGV故障、变速行驶、多负载、异质等。但更多的实际约束条件也越来越被学者关注，如电量的约束、装载时间的约束、路径冲突等。图3中未标*号的是所搜集的大部分文献建模中包含的约束条件。标*的则是部分学者建模时考虑的特殊约束条件，如贺长征等15提到了装卸载时间，但将其放入了机器加工时间中。在考虑路径冲突方面，Lyu等16、贺长征等15、邹裕吉等17、邓希等18学者通过在模型中加入时间窗，实现了无冲突路径的集成调度。现有研究中考虑AGV续航能力的文献较少，只有基于工序属性集成调度作业环境基于机器属性基于AGV属性A1：各工件有相同的加工/搬运优先级A2：不同工件的工序没有加工顺序要求，相同工件的工序需要按照一定的顺序进行加工A3：一道工序加工开始，中间不能暂停和终止A4：只有在该工件的上一道工序加工完成并由机器人搬运到下一道工序的加工机床后，才能加工下一道工序A5：同一时刻一道工序只能被一个机器加工A6：同一时刻任一台机器只能加工一道工序*A7：机器的AGV缓冲区无限大A8：零时刻，所有机器都可用*A9：不考虑机器故障A10：零时刻，所有AGV都可用A11：不考虑AGV故障*A12：不考虑装卸载时间*A13：不考虑路径冲突、堵塞*A14：不考虑AGV电量A15：AGV单负载A16：不考虑AGV变速A17：AGV同质A18：AGV执行完当前运输任务后直接前往下一运输任务加工机器A19：AGV运输工件时不影响其他工件的加工A20：AGV在任意两台机器之间的运输路线固定，运输时间仅与机器之间的距离有关A21：一台AGV同一时间只能搬运一道工序A22：所有AGV小车起始位置为毛坯库/装载区图3AGV与机器集成调度模型中的环境条件Fig.3Environmental conditions in AGV and machineintegrated scheduling model吴斌，等：自动导引车与机器集成调度问题研究现状3Computer Engineering and Applications计算机工程与应用2023，59（6）李西兴等19、李峥峰等20的研究中考虑了充电因素对调度的影响。目前AGV集成调度的研究中，还未有学者在建模环境中考虑AGV多负载、异质等。但在AGV静态调度问题中，已有学者考虑AGV多负载环境，如刘畅等21、葛艳红等22、武星等23，能在一定程度上优化AGV的行驶路线、减少AGV运行路程。既能加快车间生产，又能节约能耗，这将会是未来集成调度建模需要考虑的。2.2集成调度问题的优化目标调度的目标是优化一个或多个与制造系统收益相关的性能指标，这是体现调度问题模型特征的一个重要方面24。集成调度问题的优化目标通常分为单目标和多目标。其中单目标优化模型的目标函数以最小化最大完工时间为主，即Minimum Makespan。此外单目标优化还有考虑最小工件平均延迟时间等。多目标AGV调度优化的目标函数包括能耗、成本与利润、资源利用率等。过去的研究以单目标居多，近年来随着计算机算力的提升以及调度模型的优化，针对多目标优化问题的研究开始增多。本文梳理了现有研究成果中目标函数的特征，将其分为五类：基于加工时间的优化目标、基于加工资源的优化目标、基于成本与利润的优化目标、基于能耗与环保的优化目标和基于交货期的优化目标。具体目标参数对应的目标类型如表1所示。其中基于加工时间的优化目标最多，多数学者都选择将最小化最大完工时间作为模型的优化目标。在此基础上，部分引入了其他优化目标，建立了多目标优化模型。其中，Umar等25在其优化模型中考虑了AGV的运行时间以及因避免冲突而导致的工作延误和延误而产生的惩罚成本。Heger等26将工件的平均流经时间和平均延迟时间加入到了优化模型中。He等27在模型中加入机器总空闲时间以及机器和AGV的总能耗的优化目标。此外，刘二辉等34考虑了AGV利用率；Barak等36考虑了由 AGV 运输成本和机器加工成本构成的总成本；Tan等42以总碳排放量最小为目标，包括AGV运输能耗、机床加工能耗和其他资源能耗；马千慧等28考虑了交货期限制，将最小化总延期时间作为优化目标之一。随着绿色制造的兴起，节能减排的理念逐渐深入，将能源消耗等目标引入模型的文献日益增多，目前约有1/4的文献，在模型中考虑了能耗目标，主要包括机器设备负荷17、机床加工能耗27、AGV运输能耗36等。3AGV与机器集成调度问题优化方法生产调度问题的优化算法主要有精确算法43-44、启发式算法、智能优化算法和仿真方法四类。由于AGV与机器集成调度问题的复杂性，目前的优化算法主要集中在后两者。其中智能优化算法包括遗传算法（geneticalgorithm，GA）、粒子群算法（particle swarm optimiza-tion，PSO）、差分进化算法（differential evolution algo-rithm，DE）以及新兴的花朵授粉算法（flower pollinationalgorithm，FPA）、鲸鱼算法（whale optimization algorithm，WOA）、灰狼算法（grey wolf optimizer，GWO）等。表2将本文所收集的文献，根据其优化目标、约束条件和优化算法等进行了汇总。目标类型基于加工时间17-18，25-34基于加工资源16，33-35基于成本与利润25，36*能源消耗与环保11，17，27-28，30-31，35-41基于交货期28目标参数最大完工时间MakespanAGV运行时间平均流经时间（工件平均花费时间）工件平均延迟时间机器空闲时间AGV利用率AGV数量机器/设备利用率生产利润AGV运输成本机器加工成本延误成本AGV运输能耗机器/设备总负荷各机器/设备负荷机床加工能耗其他资源能耗总碳排放延期时间客户满意度编号C1C2C3C4C5C6C7C8C9C10C11C12C13C14C15C16C17C18C19C20倾向于追求的函数值最小化最小化最小化最小化最小化最平均/最大化最合适/最小化最大化最大化最小化最小化最小化最小化最小化最平均最小化最小化最小化最小化最大化表1集成调度问题模型中的优化目标Table 1Optimization objectives in integrated scheduling problem model注：表中标*的为近年来的研究热点。42023，59（6）参考文献Babu（2010）45Chaudhry（2011）46Kumar（2011）47Erol（2012）48Lacomme（2013）49Nageswararao（2014）29Zheng（2014）50Umar（2015）25Nouri（2016）51Lin（2019）52Lyu（2019）16Xu（2019）35Zhu（2019）53Dai（2019）38Reddy（2019）54Reddy（2022）55Fontes（2019）43Heger（2019）26Heger（2019）32Homayouni（2020）56Ham（2020）44Yuan（2021）57Barak（2021）36Tan（2021）42Homayouni（2021）58Qu（2021）59Yan（2021）60Li（2021）30He（2022）27肖海宁（2013）37龙传泽（2015）61王雷（2017）62杨煜俊（2018）63徐云琴（2018）64徐云琴（2019）65刘二辉（2019）34陆远（2019）66李广博（2019）67贺长征（2019）15戴敏（2020a）40戴敏（2020b）41陈魁（2022）68郭沛佩（2021）33李峥峰（2021）20胡晓阳（2021）14马千慧（2021）28耿凯峰（2021）39邓希（2021）18李西兴（2021）19徐逸凡（2021）69伍乐（2021）70苑明海（2021）71邹裕吉（2021）17邹裕吉（2022）31目标编号C1C1C1C1C1C1，C4C1C1，C2，C12C1C1C1，C7C1，C7，C16C1C1，C13，C16，C17C1C1C1C1，C3，C4C4C1C1C1C10，C11，C13C1，C13，C16，C17，C18C1C1C1C1，C4，C13，C16，C17C1，C5，C13，C16C13、C14、C15C1C1C1C1C1C1，C6C1C1C1C1，C13，C16，C17C1，C13，C16，C17C1C1，C3，C6C1C1C1，C2，C13，C14，C19C1，C14，C16C1，C2C1C1C1C1C1，C2，C13，C14C1，C2，C13，C14环境条件编号A1A22A1A22A1A22A1A22A1A22A1A22A1A22A1A12，A14A22A1A22A1A22A1A11，A14A22A1A22A1A22A1A22A1A22A1A22A1A22A1A22A1A22A1A22A1A22A1A6，A8A22A1A22A1A22A1A22A1A22A1A22A1A22A1A6，A8A12，A14A22A1A22A1A22A1A22A1A22A1A22A1A22A2A22A1A22A1A11，A14A22A1A22A1A22A1A22A1A22A1A13，A15A22A1A22A1A22A1A22A1A12，A14A22A1A13，A15A22A1A22A1A22A1A22A1A11，A14A22A1A11，A14A22解决方法元启发式差分进化算法基于电子表格的遗传算法基于车辆分配/机器选择启发式算法的差分进化算法多智能系统动态调度引入扩展析取图的文化基因算法二进制粒子群车辆启发式算法基于禁忌搜索的启发式算法结合模糊逻辑控制器和局部搜索的混合遗传算法基于聚类多智能体模型的混合禁忌搜索-遗传算法基于仿真的优化算法（最优计算预算分配并结合局部搜索的遗传算法）基于时间窗的Dijkstra算法和遗传算法混合分段编码遗传算法与离散粒子群优化算法改进遗传算法（均匀分布初始染色体）改进遗传算法乌鸦搜索算法花授粉算法Gurobi数学规划优化器基于优先级规则组合的仿真方法基于优先级规则组合的神经网络仿真基于操作的多启动有偏随机密钥遗传算法基于warm-start机制的两阶段约束规划方法改进非支配排序遗传算法改进的多目标粒子群算法改进多目标粒子群优化算法基于延迟接受策略的爬山算法混合遗传算法改进遗传算法带反馈的帝国主义竞争算法基于反向学习策略的多目标进化算法小生境遗传算法和启发式调度算法引入启发式调整算法的混合遗传算法改进遗传算法混合蚁群算法改进粒子群算法改进鲸鱼算法改进花授粉算法结合六种调度策略的遗传算法改进变邻域遗传算法基于时间窗和Dijkstra算法的混合遗传算法融入模拟退火搜索策略的混合分布估计算法融入模拟退火搜索策略的混合分布估计算法混合离散粒子群优化算法离散事件建模仿真方法改进遗传算法融合贪心启发式规则的改进迭代局部搜索算法改进非支配遗传算法改进文化基因算法基于时间表和A*算法的混合遗传算法混合遗传鲸鱼优化算法改进灰狼算法混合变邻域搜索的改进离散差分进化算法基于模拟退火的混合遗传算法基于时间窗和Dijkstra算法的混合遗传算法基于时间窗和Dijkstra算法的混合遗传算法表22010年至2022年中AGV与机器集成调度文献总结Table 2Summary of AGV and machine integrated scheduling literature from 2010 to middle 2022吴斌，等：自动导引车与机器集成调度问题研究现状5Computer Engineering and Applications计算机工程与应用2023，59（6）3.1遗传算法Chaudhry等46基于遗传算法求解柔性制造系统中机器与车辆的同步调度问题，使用 Excel 电子表格和Evolver插件实现对遗传算法的序列优化。Lin等52提出了一种结合局部搜索的遗传算法，在算法中引入基于启发式规则的机器选择和随机插入的策略，有效提高算法的性能。Zhu等53提出了一种改进遗传算法，通过对机器的使用次数分析，对染色体进行均匀分布调整，从而生成更合理的染色体，使算法迭代过程更加高效，同时避免了陷入局部最优。Homayouni等56提出一种带多重启动的有偏随机密钥遗传算法（biased random keygenetic algorithm，BRKGA），结合贪婪启发式算法优化处理机器分配、机器排序、AGV分配和AGV任务排序四个相关联的组合问题，能够快速地寻找到高质量解。肖海宁等37提出在线调度求解机床选择和AGV调度，机床选择采用带邻域搜索的遗传算法，并基于海明距离的小生境方法保持种群多样性；AGV调度则采用了基于剩余容量的死锁避免规则启发式调度算法。王雷等62引入末端基因值编码方法，设计了基于调度知识的离散式交叉和变异算子，优化了柔性作业车间集成调度的最大完工时间。陆远等66在遗传算法中融入六种基于AGV小车的优先级策略对模型优化求解。李广博等67在遗传算法中，采用启发式与随机式结合的方式对初始编码进行改进，并通过自适应权重因子动态调整交叉和变异概率，在算法的执行过程中引入了基于移动和交换工序策略的变邻域搜索机制。此外，Yuan等57、Yan等60、李峥峰等20基于遗传算法框架解决单目标AGV与机器集成调度问题。在考虑设备负荷、车间能耗的多目标优化方面，Dai 等38提出了一种改进的遗传算法来求解最大完工时间与能耗之间的最优解，揭示了最大完工时间与能源消耗之间的矛盾关系，并指出AGV的能源消耗对总能源需求的影响不容忽视。He等27提出了一种有效的多目标进化算法（effective multi-objective evolutionary algo-rithm，EMOEA）求解总完工时间、总空闲时间和总能耗最小化的多目标优化问题。在EMOEA中，设计了一种新的AGV分配的交叉算子；并通过引入一种反向学习策略，平衡了EMOEA的探索和开发能力。马千慧等28建立以Makespan、最小化总延期、最小化设备总负荷为目标的多目标调度模型；设计基于工序的扩展染色体编码方式和基于AGV分配的贪婪式解码策略，提出基于Pareto级的去重精英保留策略的改进非支配排序遗传算法（elitist non-dominated sorting genetic algorithm，NSGA-II）。3.2粒子群算法和差分进化算法粒子群算法因其较强的全局搜索能力，也被学者用来解决AGV与机器集成调度问题。Nageswararao等29将最大完工时间的倒数定义为鲁棒因子函数，以鲁棒因子函数最大化和工件平均延迟时间最小化为优化目标，设计了启发式算法与二进制粒子群算法混合的方法，将粒子群算法用于机器调度问题，将启发式算法引入车辆分配问题中。Barak等36提出了一种改进的多目标粒子群算法优化AGV与机器集成车辆调度问题，模型涉及机器装卸、作业调度、机器设备分配及AGV调度。并与经典的多目标粒子群算法在运行时间等5个性能指标上进行了比较，证明了算法的高效。Tan等42提出了一种增强多目标粒子群优化算法求解碳排放和完工时间最小化的集成调度问题。在算法中嵌入了几种改进策略，包括高质量解的初始化方法、用于全局搜索的混沌位置更新和突变策略，以及基于问题知识的邻域搜索策略。徐云琴等64采用引入精英策略的粒子群算法，并基于遗传算法思想设计了新的位置更新公式，避免迭代过程中非法解的产生，提升算法的运行效率。Babu等45提出一种新的元启发式差分进化算法，以向量的形式表示给定的作业，将每个向量的Makespan值作为差分进化算法的代价函数，证明差分进化算法在求解集成调度问题方面的有效性。Kumar等47提出基于车辆分配和机器选择启发式算法的差分进化算法，通过两种不同的突变策略，取得了更好的运算结果。伍乐等70设计了一种基于变邻域搜索的改进离散差分进化算法求解AGV与机器集成调度问题，将每次迭代的最优解作为局部搜索的初始解，并引入了三种不同的邻域结构进行变邻域搜索，通过种群更新策略增加种群多样性。3.3其他智能优化算法Lacomme等49利用析取图对多AGV联合调度问题建模，并开发了一种基于机器和运输选择以及AGV运输工件序列生成的文化基因算法（memetic algorithm，MA），解决了柔性制造系统中的机器和AGV同步调度问题。耿凯峰等39提出改进文化基因算法求解带工序跳跃的绿色混流车间AGV与机器集成调度问题，运用完全随机和最早加工时间混合的初始化策略生成初始种群，引入两种基于问题的邻域搜索策略，平衡了算法的全局搜索和局部搜索能力。Zheng等50基于禁忌搜索（tabu search，TS）算法，提出了一种新的二维解表示方法，并在此基础上设计了两种相邻解生成方法，利用改进的下界计算方法处理大规模问题。除了上述算法，一些新兴的智能优化方法也应用于集成调度问题的求解。Reddy等55基于花朵授粉算法，对工序、机床、刀具和AGV组合编码，并设计了一个随机方案生成器生成初始种群。刘二辉等34提出改进的花朵授粉算法求解AGV与机器集成的调度问题，基于主成分分析法设计变异算子以增强局部搜索能力，引入模拟退火算法中的Metropolis准则，提高算法的全局搜索能力。Li等30为了同时优化最小化最大完工时间、总延误时间和总能耗等目标，提出一种结合了AGV运输和序列依赖准备时间的带反馈机制的帝国主义竞争算法（imperialist competitive algorithm with feedback，FICA），解决了高效节能柔性作业车间调度问题。徐逸62023，59（6）凡等69针对集成调度问题，构建了考虑AGV在装载站、机器、卸载站之间的有效负载时间和空载时间的数学模型。提出改进非线性收敛因子和关键参数设定的灰狼算法，并在算法中嵌入邻域搜索算子避免陷入局部最优。此外，迭代局部搜索算法14、乌鸦算法54、爬山算法58、鲸鱼算法65等方法在求解AGV集成调度方面，均取得了一定的成果。3.4混合优化算法算法的融合是提高算法求解质量的有效途径。混合优化算法往往比单一智能优化算法能取得更好的优化结果。Umar等25提出结合模糊逻辑控制器和局部搜索的混合遗传算法，并考虑AGV路径的冲突检测和避免，求解了以Makespan、AGV运行时间、任务拖期延迟惩罚成本为优化目标的多目标集成调度模型。Nouri等51提出聚类多智能体模型的混合禁忌搜索-遗传算法（hybrid genetic algorithm with tabu search based onclustered holonic multiagent model，GATS+HM）解决具有运输时间和多机器人的柔性作业车间调度问题。Xu等35针对FMS中的带有AGV的绿色调度问题，以Makespan、设备能耗和AGV数量最小为目标，设计了一种分段编码遗传算法与粒子群算法的混合优化方法，实现了多目标、多维度的优化调度。Qu等59针对多机器与多AGV复杂调度的最大完工时间优化问题，提出了一种嵌入车辆分配规则的混合遗传算法，避免了AGV在巨大的求解空间中完全随机分配组合的问题。龙传泽等61考虑AGV搬运序列矩阵，提出了结合启发式搬运矩阵调整的混合遗传算法求解多机器人制造单元作业车间调度问题。杨煜俊等63提出了一种基于机床选择策略和自适应伪随机比例规则的混合蚁群算法（hybrid ant colony optimization，HACO）求解AGV集成调度问题。戴敏等40-41针对绿色车间集成调度问题，考虑AGV、机床及其他车间资源的能耗，提出模拟退火算法与分布估计算法的混合优化算法求解，充分利用分布估计算法全局搜索能力快和模拟退火算法突跳性强的特点，提高算法的优化能力。陈魁等68在粒子群算法中融入了竞争学习机制和随机重启机制，并考虑AGV数量对完工时间的影响，发现AGV数量对完工时间的提升效率符合边际效应递减规律。邹裕吉等31提出基于时间窗和Dijkstra算法的多目标自适应聚类遗传算法，引入基于网格坐标的环境选择策略增加解集的多样性。苑明海等71建立了以Makespan最短为目标的柔性作业车间静态集成调度模型；提出模拟退火与遗传算法混合的优化方法，引入黄金分隔法，将算法迭代过程划分为三个阶段，并制定不同阶段的模拟退火算法融入规则，提高了算法的收敛速度，避免算法陷入局部最优。3.5仿真优化方法基于仿真的优化方法在AGV与机器集成调度也有应用。Erol等48建立了多智能体系统（multi-agent-basedsystems，MAS），用于制造系统中AGV和机器的动态同步调度，结果表明该方法能够实时生成与常用调度规则相近的调度结果。Heger等26，32分析了一种考虑自主导航车辆行程时间的柔性作业车间调度方法，分别进行了基于规则组合的仿真研究和神经网络仿真。郭沛佩等33基于离散事件建模仿真方法建立了柔性作业车间仿真模型，以最小化平均流动时间、完工时间、AGV平均利用率与完工数量为优化目标，采用 Plant Simulation软件，将不同路由规则与调度规则组合进行仿真实验，确定最佳的规则组合和AGV数量。3.6算法比较AGV与机器集成调度问题的求解算法虽多，但多数是针对特定问题或随机生成的算例进行优化，标准的测试实例库并不多，目前使用最广泛的是由Bilge等72提出。BILGE实例库包括10个作业集和4个车间布局形式，共82个实例。按机器间运输时间(t)和工序加工时间(p)的比值t/p的大小划分为t/p0.25和t/p0.25算例是把运输时间t增加了一倍或两倍，其他参数没有变化。多数算法都是对t/p0.25的 40 个实例进行的测试，因此，本文搜集整理了若干典型算法优化求解这40个实