摘要：隨著客制化和大規(guī)模生產(chǎn)需求的不斷增長(zhǎng)，矩陣制造車間的重要性日益凸顯。同時(shí)，多臺(tái)自動(dòng)導(dǎo)引車（AGV）的有效調(diào)度可提高矩陣制造車間的運(yùn)行效率。以矩陣制造車間內(nèi)的AGV運(yùn)輸過程為研究對(duì)象，提出一種改進(jìn)的模擬退火（ISA）算法，旨在找到降低運(yùn)輸成本的最佳調(diào)度方案。ISA算法通過Metropolis準(zhǔn)則來提高算法跳出局部最優(yōu)解的能力；利用順序交叉算子和前置交叉算子更新種群，以提高ISA算法尋找全局最優(yōu)解的收斂速度和精度；提出一種種群重生機(jī)制，避免ISA算法陷入局部最優(yōu)解。為了評(píng)估ISA算法的有效性，在某工廠100個(gè)真實(shí)實(shí)例的數(shù)據(jù)集上進(jìn)行了仿真測(cè)試，并與FCFS算法、HFOA、IHS算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，ISA算法更適合解決矩陣制造車間的AGV調(diào)度問題。

關(guān)鍵詞：矩陣式制造車間；自動(dòng)導(dǎo)引車；模擬退火算法；調(diào)度問題

中圖分類號(hào)：TP242.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

自動(dòng)導(dǎo)引車（automated guided vehicle， AGV）能夠自主導(dǎo)航，執(zhí)行多種物料的搬運(yùn)和分配任務(wù)，廣泛應(yīng)用于工廠和倉(cāng)庫(kù)等場(chǎng)合[1-2]，已成為眾多制造企業(yè)提高效率和降低成本不可或缺的工具。AGV調(diào)度問題（AGV scheduling problem， AGVSP）是當(dāng)前制造業(yè)備受關(guān)注的一項(xiàng)挑戰(zhàn)[3-4]，其高效地規(guī)劃和管理AGV的任務(wù)和路徑，確保物料和產(chǎn)品在按時(shí)、按需運(yùn)輸?shù)耐瑫r(shí)，最大限度地減少等待時(shí)間和資源浪費(fèi)[5]。AGVSP包括AGV分配問題（合理分配任務(wù)給AGV，以設(shè)定每臺(tái)AGV的任務(wù)服務(wù)順序）和AGV路徑規(guī)劃問題（為給定的任務(wù)服務(wù)順序?qū)ふ易罴崖窂剑?。AGVSP的復(fù)雜性源于生產(chǎn)設(shè)備狀態(tài)、任務(wù)優(yōu)先級(jí)、工廠布局、車輛容量等因素。有效的AGV調(diào)度可以提升生產(chǎn)線效率和靈活性、減小誤差、降低能源消耗，從而增強(qiáng)制造企業(yè)的競(jìng)爭(zhēng)力[6-7]。

矩陣制造車間是現(xiàn)代制造企業(yè)廣泛采用的智能車間之一[8]，通常被劃分為多個(gè)生產(chǎn)區(qū)域，每個(gè)生產(chǎn)區(qū)域負(fù)責(zé)不同產(chǎn)品或零部件的制造。每臺(tái)AGV配備多個(gè)隔間，每個(gè)隔間僅能裝載一種物料或工具，且有裝載量限制。矩陣制造車間的AGVSP可以看作是車輛路徑問題的一個(gè)復(fù)雜變種，但因其具有多個(gè)隔間、可變需求和多個(gè)約束等特征，更為復(fù)雜。車輛路徑問題是NP-hard問題，這意味著AGVSP也是NP-hard問題。針對(duì)這種問題，精確的求解方法在有限的時(shí)間內(nèi)難以獲得較優(yōu)的調(diào)度方案。因此，通常采用基于規(guī)則的啟發(fā)式算法或智能優(yōu)化算法來求解[9]。迄今為止，矩陣制造車間的AGVSP只吸引了少數(shù)研究者的關(guān)注。ZOU等[8]提出了矩陣制造車間的AGVSP，其基于離散人工蜂群算法結(jié)合多種啟發(fā)式策略實(shí)現(xiàn)了AGV的有效調(diào)度。ZHANG等[10]引入一種改進(jìn)的迭代貪婪算法，采用AGV路線合并和車間分區(qū)及修復(fù)策略，防止算法收斂到局部最優(yōu)解，最大限度地降低AGV的運(yùn)輸成本。ZOU等[11]提出一種迭代貪婪算法，通過解構(gòu)和重構(gòu)過程的迭代來增強(qiáng)AGVSP的解決方案；引入加速定理來提高解評(píng)估的效率；采用Metropolis準(zhǔn)則來選擇解；最后通過真實(shí)案例的比較實(shí)驗(yàn)，證明了所提算法生成的解優(yōu)于現(xiàn)有算法。LI等[12]在矩陣制造車間AGVSP中引入離散入侵雜草優(yōu)化算法，通過兩個(gè)有效的鄰域算子來提高算法性能；基于插入的局部搜索方法來增強(qiáng)局部搜索能力；最后通過綜合仿真實(shí)驗(yàn)，驗(yàn)證了所提算法的有效性。盡管以上研究在矩陣制造車間的AGVSP上取得了一定進(jìn)展，但所采用的方法仍可能陷入局部最優(yōu)解，限制了調(diào)度方案的質(zhì)量，且在大規(guī)模或復(fù)雜場(chǎng)景下，計(jì)算時(shí)間較長(zhǎng)，無法滿足實(shí)時(shí)調(diào)度的需求，影響了實(shí)際應(yīng)用。因此，探索更高效的調(diào)度方案以應(yīng)對(duì)矩陣制造車間AGVSP的復(fù)雜性，具有重要的研究意義。

本文構(gòu)建了一個(gè)混合整數(shù)線性模型，并提出一種改進(jìn)的模擬退火（improved simulated annealing， ISA）算法來解決矩陣制造車間的AGVSP。首先，將順序交叉算子和前置交叉算子作為種群更新機(jī)制，提高ISA算法尋找全局最優(yōu)解的收斂速度和精度；然后，基于Metropolis準(zhǔn)則，以一定的概率接受較差解，使ISA算法在優(yōu)化前期具有較廣的搜索范圍；接著，提出一種種群重生機(jī)制，以避免ISA算法在優(yōu)化后期陷入局部最優(yōu)解；最后，通過在100個(gè)真實(shí)實(shí)例的數(shù)據(jù)集上進(jìn)行仿真測(cè)試，驗(yàn)證ISA算法解決AGVSP的有效性和可靠性。

1 矩陣制造車間AGVSP建模

1.1 環(huán)境描述

本文研究的矩陣制造車間AGVSP描述如下：在矩陣制造車間中，設(shè)有多臺(tái)AGV、一個(gè)倉(cāng)庫(kù)和m個(gè)生產(chǎn)區(qū)域，其布局圖如圖1所示。

倉(cāng)庫(kù)用于儲(chǔ)存各生產(chǎn)區(qū)域所需的物料。根據(jù)物料的數(shù)量，將矩陣制造車間劃分為m個(gè)生產(chǎn)區(qū)域，每個(gè)生產(chǎn)區(qū)域擁有若干個(gè)工作站。每個(gè)工作站均設(shè)有緩沖區(qū)和數(shù)控機(jī)床。當(dāng)緩沖區(qū)的物料數(shù)量低于設(shè)定的閾值時(shí)，叫料工作站向控制中心發(fā)出物料請(qǐng)求信號(hào)，要求AGV進(jìn)行補(bǔ)給。為了避免AGV資源浪費(fèi)和運(yùn)輸成本增加，將生產(chǎn)時(shí)間劃分為若干個(gè)周期，每個(gè)周期包括規(guī)劃階段和調(diào)度階段。在規(guī)劃階段，控制中心為AGV分配任務(wù)；在調(diào)度階段，控制中心派遣AGV將物料運(yùn)輸?shù)街付ǖ墓ぷ髡?，并返回倉(cāng)庫(kù)。第x個(gè)生產(chǎn)周期內(nèi)收到的物料請(qǐng)求將在第 個(gè)生產(chǎn)周期內(nèi)處理。

假設(shè)所需物料都儲(chǔ)存在倉(cāng)庫(kù)中；所有AGV的質(zhì)量相同，勻速行駛，且不受裝載量的影響；每臺(tái)AGV擁有多個(gè)隔間，每個(gè)隔間用于存放特定的物料；隔間數(shù)量等于物料和刀具種類的總數(shù)；AGV在矩陣制造車間內(nèi)獨(dú)立行駛，不發(fā)生停機(jī)、故障或碰撞等事故；AGV從倉(cāng)庫(kù)出發(fā)，最終返回倉(cāng)庫(kù)；每條AGV路線只能由一臺(tái)AGV執(zhí)行；每個(gè)客戶只能被服務(wù)一次；一條路線上所有客戶的物料需求總量不超過AGV的總載重量；AGV在客戶要求的時(shí)間窗口內(nèi)提供服務(wù)。

2.3 種群重生機(jī)制

為了避免ISA算法陷入局部最優(yōu)解，本文提出一種種群重生機(jī)制。當(dāng)ISA算法在第 次迭代過程中仍然無法找到更優(yōu)解時(shí)，則認(rèn)為算法陷入局部最優(yōu)解，此時(shí)采用種群重生機(jī)制重新生成個(gè)體并進(jìn)一步探索解空間，從而擺脫局部最優(yōu)解。種群重生機(jī)制的具體實(shí)現(xiàn)過程如下：

1） 選擇解 中的一條路線 ，并從該條路線中隨機(jī)選擇 數(shù)量的客戶放入到檔案庫(kù) 中；

2） 提取 中的第一個(gè)客戶，插入到 剩余路線所有能夠插入的位置，并選擇最優(yōu)位置作為該客戶的最終位置；

3） 若 的剩余路線都無法插入該客戶，則重新生成一條新路線。以此類推，直至 中的客戶全部被插入為止。

3 實(shí)驗(yàn)與分析

本文采用ZOU等提供的100個(gè)矩陣制造車間的真實(shí)實(shí)例進(jìn)行仿真測(cè)試[8]。該測(cè)試實(shí)例的客戶數(shù)量包括10、20、30、40和50個(gè)，每個(gè)大小類別分別含有20個(gè)實(shí)例，并利用T10I1表示任務(wù)為10的第一個(gè)實(shí)例。為了進(jìn)一步評(píng)估本文ISA算法求解矩陣制造車間AGVSP的有效性。將本文ISA算法與先來先服務(wù)（first come first serve， FCFS）算法、混合果蠅優(yōu)化算法（hybrid fruit-fly optimization algorithm， HFOA）、改進(jìn)的和諧搜索（improved harmony search， IHS）算法進(jìn)行對(duì)比實(shí)驗(yàn)。設(shè)置最大迭代時(shí)間為5 s，種群數(shù)量為150個(gè)，其他參數(shù)設(shè)置如表1所示。4種算法均在Windows 10操作系統(tǒng)上MATLAB R2020a的.m文件實(shí)現(xiàn)，并在一臺(tái)CPU主頻為2.60 GHz、處理器內(nèi)存為16 GB的計(jì)算機(jī)上運(yùn)行。

為了更準(zhǔn)確地量化ISA算法與最優(yōu)調(diào)度方案之間的差異，采用相對(duì)百分比偏差（relative percentage deviation， RPD）來評(píng)估實(shí)驗(yàn)結(jié)果。RPD的計(jì)算公式為

（24）

式中： 為所用算法獲得的運(yùn)輸成本， 為4種算法對(duì)同一實(shí)例獲得的最優(yōu)運(yùn)輸成本。

為確保對(duì)比實(shí)驗(yàn)的公平性，F(xiàn)CFS算法、HFOA、HIS算法和ISA算法先在所有測(cè)試實(shí)例中各自獨(dú)立運(yùn)行30次，再對(duì)平均RPD、最優(yōu)RPD進(jìn)行比較，結(jié)果如表2所示。

由表2可知：在客戶數(shù)量為10個(gè)的實(shí)例中，ISA算法和IHS算法的性能不相上下；在客戶數(shù)量為20和30個(gè)的實(shí)例中，ISA算法和IHS算法的性能也相差無幾；在客戶數(shù)量為40和50個(gè)的實(shí)例中，ISA算法不管是精確度還是魯棒性，均優(yōu)于FCFS算法、HFOA、IHS算法，證明了ISA算法求解AGVSP的優(yōu)越性。

4 結(jié)論

針對(duì)矩陣制造車間的多隔間、可變需求和多約束AGVSP，本文提出一種ISA算法。該算法利用順序交叉算子和前置交叉算子來更新種群個(gè)體，并通過Metropolis準(zhǔn)則接受較差解，以保證算法的前期勘探能力，避免陷入局部最優(yōu)解；通過種群重生機(jī)制，平衡算法后期的勘探能力和開發(fā)能力，不僅增強(qiáng)了算法跳出局部最優(yōu)解的能力，還加強(qiáng)了算法進(jìn)一步開發(fā)解的能力。最后，通過與FCFS算法、HFOA、IHS算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了ISA算法的有效性。未來研究可以考慮以下幾個(gè)方面：1） 將ISA算法與其他智能優(yōu)化算法相結(jié)合，以提高其在動(dòng)態(tài)環(huán)境中的適應(yīng)性和靈活性；2） 探索在更復(fù)雜的制造環(huán)境中引入多目標(biāo)優(yōu)化，以平衡成本、時(shí)間和資源利用效率；3） 集成機(jī)器學(xué)習(xí)技術(shù)，以提升算法的預(yù)測(cè)能力和響應(yīng)速度；4） 通過對(duì)實(shí)際應(yīng)用案例的深入分析，進(jìn)一步驗(yàn)證ISA算法在不同制造場(chǎng)景中的有效性和可擴(kuò)展性。

?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/）

參考文獻(xiàn)

[1] 李玉，萇道方，高銀萍，等.基于數(shù)字孿生的自動(dòng)化集裝箱碼頭多AGV動(dòng)態(tài)調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2023，29（12）：4175-4190.

[2] 馬駿，王亞東，蔡國(guó)旗，等.基于智能計(jì)算方法的AGV制造車間調(diào)度問題研究現(xiàn)狀[J].機(jī)電工程技術(shù)，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] 鐘建琳，劉忠和.制造系統(tǒng)中多智能體運(yùn)輸子系統(tǒng)的調(diào)度與監(jiān)控[J].機(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地圖構(gòu)建及路徑規(guī)劃研究[J].機(jī)電工程技術(shù)，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] 龐燕，羅華麗，邢立寧，等.車輛路徑優(yōu)化問題及求解方法研究綜述[J].控制理論與應(yīng)用，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.

作者簡(jiǎn)介：

曾俊海，男，1996年生，博士研究生，主要研究方向：智能優(yōu)化算法及機(jī)器人調(diào)度。E-mail： jhaizeng@163.com

廉胤東，男，1992年生，博士研究生，工程師，主要研究方向：數(shù)字供應(yīng)鏈、機(jī)器人調(diào)度、信息物理系統(tǒng)。E-mail： 601292628@qq.com

彭雄峰，男，2000年生，碩士研究生，主要研究方向：移動(dòng)機(jī)器人視覺伺服控制與協(xié)調(diào)規(guī)劃。E-mail： 1241491625@qq.com

余錦偉，男，1995年生，博士研究生，工程師，主要研究方向：機(jī)器視覺、圖像處理、人工智能。E-mail： yujw5@ chinatelecom.cn