面向矩陣式制造車間AGV調度的改進模擬退火算法

摘要：隨著客制化和大規模生產需求的不斷增長，矩陣制造車間的重要性日益凸顯。同時，多臺自動導引車（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