面向矩阵式制造车间AGV调度的改进模拟退火算法
2024-11-04曾俊海廉胤东彭雄峰余锦伟
摘要:随着客制化和大规模生产需求的不断增长,矩阵制造车间的重要性日益凸显。同时,多台自动导引车(AGV)的有效调度可提高矩阵制造车间的运行效率。以矩阵制造车间内的AGV运输过程为研究对象,提出一种改进的模拟退火(ISA)算法,旨在找到降低运输成本的最佳调度方案。ISA算法通过Metropolis准则来提高算法跳出局部最优解的能力;利用顺序交叉算子和前置交叉算子更新种群,以提高ISA算法寻找全局最优解的收敛速度和精度;提出一种种群重生机制,避免ISA算法陷入局部最优解。为了评估ISA算法的有效性,在某工厂100个真实实例的数据集上进行了仿真测试,并与FCFS算法、HFOA、IHS算法进行对比实验。实验结果表明,ISA算法更适合解决矩阵制造车间的AGV调度问题。
关键词:矩阵式制造车间;自动导引车;模拟退火算法;调度问题
中图分类号:TP242.6 文献标志码:A 文章编号:1674-2605(2024)05-0005-08
DOI:10.3969/j.issn.1674-2605.2024.05.005 开放获取
Improved Simulated Annealing Algorithm for AGV Scheduling
in Matrix Manufacturing Workshops
ZENG Junhai1 LIAN Yindong2 PENG Xiongfeng1 YU Jinwei3
(1.School of Automation Science and Engineering, South China University of Technology, Guangzhou 510641, China 2.Southern Power Grid Supply Chain Technology (Guangdong) Co., Ltd., Guangzhou 510630, China
3.Guangdong Research Institute of China Telecom Corporation Limited, Guangzhou 510660, China)
Abstract: With the increasing demand for customization and large-scale production, the importance of matrix manufacturing workshops is becoming increasingly prominent. Meanwhile, the effective scheduling of multiple Automated Guided Vehicle (AGV) can improve the operating efficiency of matrix manufacturing workshops. Taking the AGV transportation process in the matrix manufacturing workshop as the research object, an improved simulated annealing (ISA) algorithm is proposed to find the optimal scheduling scheme to reduce transportation costs. The ISA algorithm improves its ability to escape from local optima through the Metropolis criterion; Using sequential crossover operators and pre crossover operators to update the population, in order to improve the convergence speed and accuracy of the ISA algorithm in finding the global optimal solution; Propose a population regeneration mechanism to prevent the ISA algorithm from getting stuck in local optima. In order to evaluate the effectiveness of the ISA algorithm, simulation tests were conducted on a dataset of 100 real instances in a certain factory, and comparative experiments were conducted with the FCFS algorithm, HFOA, and IHS algorithm. The experimental results indicate that the ISA algorithm is more suitable for solving AGV scheduling problems in matrix manufacturing workshops.
Keywords: matrix manufacturing workshops; automated guided vehicle; simulated annealing algorithm; scheduling problem
0 引言
自动导引车(automated guided vehicle, AGV)能够自主导航,执行多种物料的搬运和分配任务,广泛应用于工厂和仓库等场合[1-2],已成为众多制造企业提高效率和降低成本不可或缺的工具。AGV调度问题(AGV scheduling problem, AGVSP)是当前制造业备受关注的一项挑战[3-4],其高效地规划和管理AGV的任务和路径,确保物料和产品在按时、按需运输的同时,最大限度地减少等待时间和资源浪费[5]。AGVSP包括AGV分配问题(合理分配任务给AGV,以设定每台AGV的任务服务顺序)和AGV路径规划问题(为给定的任务服务顺序寻找最佳路径)。AGVSP的复杂性源于生产设备状态、任务优先级、工厂布局、车辆容量等因素。有效的AGV调度可以提升生产线效率和灵活性、减小误差、降低能源消耗,从而增强制造企业的竞争力[6-7]。
矩阵制造车间是现代制造企业广泛采用的智能车间之一[8],通常被划分为多个生产区域,每个生产区域负责不同产品或零部件的制造。每台AGV配备多个隔间,每个隔间仅能装载一种物料或工具,且有装载量限制。矩阵制造车间的AGVSP可以看作是车辆路径问题的一个复杂变种,但因其具有多个隔间、可变需求和多个约束等特征,更为复杂。车辆路径问题是NP-hard问题,这意味着AGVSP也是NP-hard问题。针对这种问题,精确的求解方法在有限的时间内难以获得较优的调度方案。因此,通常采用基于规则的启发式算法或智能优化算法来求解[9]。迄今为止,矩阵制造车间的AGVSP只吸引了少数研究者的关注。ZOU等[8]提出了矩阵制造车间的AGVSP,其基于离散人工蜂群算法结合多种启发式策略实现了AGV的有效调度。ZHANG等[10]引入一种改进的迭代贪婪算法,采用AGV路线合并和车间分区及修复策略,防止算法收敛到局部最优解,最大限度地降低AGV的运输成本。ZOU等[11]提出一种迭代贪婪算法,通过解构和重构过程的迭代来增强AGVSP的解决方案;引入加速定理来提高解评估的效率;采用Metropolis准则来选择解;最后通过真实案例的比较实验,证明了所提算法生成的解优于现有算法。LI等[12]在矩阵制造车间AGVSP中引入离散入侵杂草优化算法,通过两个有效的邻域算子来提高算法性能;基于插入的局部搜索方法来增强局部搜索能力;最后通过综合仿真实验,验证了所提算法的有效性。尽管以上研究在矩阵制造车间的AGVSP上取得了一定进展,但所采用的方法仍可能陷入局部最优解,限制了调度方案的质量,且在大规模或复杂场景下,计算时间较长,无法满足实时调度的需求,影响了实际应用。因此,探索更高效的调度方案以应对矩阵制造车间AGVSP的复杂性,具有重要的研究意义。
本文构建了一个混合整数线性模型,并提出一种改进的模拟退火(improved simulated annealing, ISA)算法来解决矩阵制造车间的AGVSP。首先,将顺序交叉算子和前置交叉算子作为种群更新机制,提高ISA算法寻找全局最优解的收敛速度和精度;然后,基于Metropolis准则,以一定的概率接受较差解,使ISA算法在优化前期具有较广的搜索范围;接着,提出一种种群重生机制,以避免ISA算法在优化后期陷入局部最优解;最后,通过在100个真实实例的数据集上进行仿真测试,验证ISA算法解决AGVSP的有效性和可靠性。
1 矩阵制造车间AGVSP建模
1.1 环境描述
本文研究的矩阵制造车间AGVSP描述如下:在矩阵制造车间中,设有多台AGV、一个仓库和m个生产区域,其布局图如图1所示。
仓库用于储存各生产区域所需的物料。根据物料的数量,将矩阵制造车间划分为m个生产区域,每个生产区域拥有若干个工作站。每个工作站均设有缓冲区和数控机床。当缓冲区的物料数量低于设定的阈值时,叫料工作站向控制中心发出物料请求信号,要求AGV进行补给。为了避免AGV资源浪费和运输成本增加,将生产时间划分为若干个周期,每个周期包括规划阶段和调度阶段。在规划阶段,控制中心为AGV分配任务;在调度阶段,控制中心派遣AGV将物料运输到指定的工作站,并返回仓库。第x个生产周期内收到的物料请求将在第 个生产周期内处理。
假设所需物料都储存在仓库中;所有AGV的质量相同,匀速行驶,且不受装载量的影响;每台AGV拥有多个隔间,每个隔间用于存放特定的物料;隔间数量等于物料和刀具种类的总数;AGV在矩阵制造车间内独立行驶,不发生停机、故障或碰撞等事故;AGV从仓库出发,最终返回仓库;每条AGV路线只能由一台AGV执行;每个客户只能被服务一次;一条路线上所有客户的物料需求总量不超过AGV的总载重量;AGV在客户要求的时间窗口内提供服务。
2.3 种群重生机制
为了避免ISA算法陷入局部最优解,本文提出一种种群重生机制。当ISA算法在第 次迭代过程中仍然无法找到更优解时,则认为算法陷入局部最优解,此时采用种群重生机制重新生成个体并进一步探索解空间,从而摆脱局部最优解。种群重生机制的具体实现过程如下:
1) 选择解 中的一条路线 ,并从该条路线中随机选择 数量的客户放入到档案库 中;
2) 提取 中的第一个客户,插入到 剩余路线所有能够插入的位置,并选择最优位置作为该客户的最终位置;
3) 若 的剩余路线都无法插入该客户,则重新生成一条新路线。以此类推,直至 中的客户全部被插入为止。
3 实验与分析
本文采用ZOU等提供的100个矩阵制造车间的真实实例进行仿真测试[8]。该测试实例的客户数量包括10、20、30、40和50个,每个大小类别分别含有20个实例,并利用T10I1表示任务为10的第一个实例。为了进一步评估本文ISA算法求解矩阵制造车间AGVSP的有效性。将本文ISA算法与先来先服务(first come first serve, FCFS)算法、混合果蝇优化算法(hybrid fruit-fly optimization algorithm, HFOA)、改进的和谐搜索(improved harmony search, IHS)算法进行对比实验。设置最大迭代时间为5 s,种群数量为150个,其他参数设置如表1所示。4种算法均在Windows 10操作系统上MATLAB R2020a的.m文件实现,并在一台CPU主频为2.60 GHz、处理器内存为16 GB的计算机上运行。
为了更准确地量化ISA算法与最优调度方案之间的差异,采用相对百分比偏差(relative percentage deviation, RPD)来评估实验结果。RPD的计算公式为
(24)
式中: 为所用算法获得的运输成本, 为4种算法对同一实例获得的最优运输成本。
为确保对比实验的公平性,FCFS算法、HFOA、HIS算法和ISA算法先在所有测试实例中各自独立运行30次,再对平均RPD、最优RPD进行比较,结果如表2所示。
由表2可知:在客户数量为10个的实例中,ISA算法和IHS算法的性能不相上下;在客户数量为20和30个的实例中,ISA算法和IHS算法的性能也相差无几;在客户数量为40和50个的实例中,ISA算法不管是精确度还是鲁棒性,均优于FCFS算法、HFOA、IHS算法,证明了ISA算法求解AGVSP的优越性。
4 结论
针对矩阵制造车间的多隔间、可变需求和多约束AGVSP,本文提出一种ISA算法。该算法利用顺序交叉算子和前置交叉算子来更新种群个体,并通过Metropolis准则接受较差解,以保证算法的前期勘探能力,避免陷入局部最优解;通过种群重生机制,平衡算法后期的勘探能力和开发能力,不仅增强了算法跳出局部最优解的能力,还加强了算法进一步开发解的能力。最后,通过与FCFS算法、HFOA、IHS算法的对比实验,验证了ISA算法的有效性。未来研究可以考虑以下几个方面:1) 将ISA算法与其他智能优化算法相结合,以提高其在动态环境中的适应性和灵活性;2) 探索在更复杂的制造环境中引入多目标优化,以平衡成本、时间和资源利用效率;3) 集成机器学习技术,以提升算法的预测能力和响应速度;4) 通过对实际应用案例的深入分析,进一步验证ISA算法在不同制造场景中的有效性和可扩展性。
©The author(s) 2024. This is an open access article under the CC BY-NC-ND 4.0 License (https://creativecommons.org/licenses/ by-nc-nd/4.0/)
参考文献
[1] 李玉,苌道方,高银萍,等.基于数字孪生的自动化集装箱码头多AGV动态调度[J].计算机集成制造系统,2023,29(12):4175-4190.
[2] 马骏,王亚东,蔡国旗,等.基于智能计算方法的AGV制造车间调度问题研究现状[J].机电工程技术,2021,50(8):6-10;73.
[3] ABDERRAHIM M, BEKRAR A, TRENTESAUX D, et al. Manufacturing 4.0 operations scheduling with AGV battery management constraints[J]. Energies, 2020,13(18):4948.
[4] 钟建琳,刘忠和.制造系统中多智能体运输子系统的调度与监控[J].机床与液压,2011,39 (11):73-76;50.
[5] HU H, JIA X, HE Q, et al. Deep reinforcement learning based AGVs real-time scheduling with mixed rule for flexible shop floor in industry 4.0[J]. Computers & Industrial Engineering, 2020,149:106749.
[6] 彭丽文,沈吟东.多隔间车辆路径问题研究综述[J].物流科技,2021,44(2):72-77;87.
[7] 朱伟枝,谢娟烘,卢子荣.基于SLAM的校园配送AGV地图构建及路径规划研究[J].机电工程技术,2023,52(1):107-110; 160.
[8] ZOU W Q, PAN Q K, MENG T, et al. An effective discrete artificial bee colony algorithm for multi-AGVs dispatching problem in a matrix manufacturing workshop[J]. Expert Sys-tems with Applications, 2020,161:113675.
[9] 庞燕,罗华丽,邢立宁,等.车辆路径优化问题及求解方法研究综述[J].控制理论与应用,2019,36(10):1573-1584.
[10] ZHANG X, SANG H, LI J, et al. An effective multi-AGVs dispatching method applied to matrix manufacturing work-shop[J]. Computers & Industrial Engineering, 2022,163:107791.
[11] ZOU W Q, PAN Q K, TASGETIREN M F. An effective iterated greedy algorithm for solving a multi-compartment AGV sche-duling problem in a matrix manufacturing work-shop[J]. Applied Soft Computing, 2021,99:106945.
[12] LI Z K, SANG H Y, LI J Q, et al. Invasive weed optimization for multi-AGVs dispatching problem in a matrix manufactu-ring workshop[J]. Swarm and Evolutionary Computation, 2023,77:101227.
作者简介:
曾俊海,男,1996年生,博士研究生,主要研究方向:智能优化算法及机器人调度。E-mail: jhaizeng@163.com
廉胤东,男,1992年生,博士研究生,工程师,主要研究方向:数字供应链、机器人调度、信息物理系统。E-mail: 601292628@qq.com
彭雄峰,男,2000年生,硕士研究生,主要研究方向:移动机器人视觉伺服控制与协调规划。E-mail: 1241491625@qq.com
余锦伟,男,1995年生,博士研究生,工程师,主要研究方向:机器视觉、图像处理、人工智能。E-mail: yujw5@ chinatelecom.cn