陳 展，公建寧，劉媛媛，徐京邦

機(jī)械科學(xué)研究總院 機(jī)科發(fā)展科技股份有限公司，北京100044

自動(dòng)導(dǎo)引車（Automated Guided Vehicles，AGV）定義為配置導(dǎo)航定位功能的自動(dòng)導(dǎo)引裝置，能夠沿系統(tǒng)規(guī)劃的路徑行駛，具有安全保護(hù)且能完成各種裝卸作業(yè)的自動(dòng)設(shè)備[1]。在現(xiàn)代化輸送系統(tǒng)的自動(dòng)化和智能化中起著不可或缺的重要作用，日益廣泛應(yīng)用在制造業(yè)、航空航天、物流服務(wù)等行業(yè)。

多AGV 系統(tǒng)的路徑規(guī)劃技術(shù)包括作業(yè)任務(wù)的分派、最短路徑搜索和交通管理的相互配合，不僅需要保證作業(yè)的安全性，同時(shí)還要保持系統(tǒng)的高效運(yùn)轉(zhuǎn)。其中AGV 的路徑搜索需要在復(fù)雜的現(xiàn)場環(huán)境下，依據(jù)工藝地圖路線，按照作業(yè)時(shí)間最短、系統(tǒng)運(yùn)行成本最低和全局作業(yè)流暢的評(píng)價(jià)標(biāo)準(zhǔn)，規(guī)劃一條從起始點(diǎn)到目標(biāo)點(diǎn)的行駛路徑[2]。

多AGV 系統(tǒng)的路徑搜索是一個(gè)涉及約束條件、附加條件和現(xiàn)實(shí)條件的復(fù)雜非確定性多項(xiàng)式（Nondeterministic Polynomial，NP）問題。相比于傳統(tǒng)經(jīng)典算法，智能優(yōu)化算法能夠更有效地解決路徑規(guī)劃的多約束問題，通過將尋找最優(yōu)路徑轉(zhuǎn)化為尋找函數(shù)最優(yōu)值，從而實(shí)現(xiàn)多AGV 系統(tǒng)路徑規(guī)劃中的最短路徑搜索[3]。本文在保證合理任務(wù)分配機(jī)制和穩(wěn)定交通管理策略的前提下，對(duì)比經(jīng)典尋路算法，提出基于鄰域搜索的禁忌路徑搜索算法，通過仿真實(shí)驗(yàn)證明該方法的優(yōu)越性和必要性。

1 介紹

隨著AGV系統(tǒng)應(yīng)用的日益廣泛和作業(yè)任務(wù)的日益復(fù)雜，AGV集群之間的相互配合與協(xié)作，成為系統(tǒng)項(xiàng)目中不可避免的重要問題，而多AGV 的路徑規(guī)劃技術(shù)就是AGV 系統(tǒng)的核心技術(shù)之一，可分為環(huán)境信息完全已知的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃[4]。

在多AGV 系統(tǒng)的環(huán)境信息已知的全局路徑規(guī)劃中，任務(wù)調(diào)度算法、路徑搜索方法和交通管理的性能直接決定系統(tǒng)的整體效率。本文通過對(duì)路徑規(guī)劃技術(shù)中的路徑搜索算法在同等耦合條件任務(wù)分配和交通管理策略下進(jìn)行設(shè)計(jì)優(yōu)化，完成基于特定的環(huán)境模型，搜索出一條能耗低、用時(shí)少，盡量避免阻塞障礙的AGV作業(yè)路徑。

全局路徑規(guī)劃下的路徑搜索算法發(fā)展歷程如圖1所示，從傳統(tǒng)的Dijkstra 和啟發(fā)式的A*等經(jīng)典算法，經(jīng)過基于采樣和圖論的隨機(jī)路標(biāo)圖法（Probabilistic Road-Μaps，PRΜ）、快速搜索樹法（Rapid-exploration Random Tree，RRT）等，發(fā)展到日益成熟的智能仿生優(yōu)化算法和強(qiáng)化學(xué)習(xí)[5]。但實(shí)際應(yīng)用過程中的任何路徑搜索算法都存在局限性，在具體的應(yīng)用方向上，進(jìn)行針對(duì)性的優(yōu)化改善，或是融合優(yōu)化多種算法，可以快速有效提升算法性能[6]。

圖1 路徑搜索算法發(fā)展歷程

在多AGV 系統(tǒng)下的路徑規(guī)劃中，當(dāng)中央控制系統(tǒng)派發(fā)任務(wù)時(shí)，首先按照就近原則進(jìn)行約束排序，來選擇匹配一輛移動(dòng)機(jī)器人進(jìn)行任務(wù)分配。這樣的規(guī)劃方法在一定程度上利用多移動(dòng)機(jī)器人系統(tǒng)的優(yōu)勢(shì)，節(jié)約了AGV 電量和車體磨損等物流成本資源[7]。采用基于路徑資源分配機(jī)制以排除交通管理的調(diào)度策略對(duì)路徑規(guī)劃性能的影響，依此設(shè)計(jì)基于禁忌算法求解多AGV 系統(tǒng)的全局路徑搜索。

本文的主要內(nèi)容包括：

（1）構(gòu)建地圖模型拓?fù)浣Y(jié)構(gòu)生成XΜL 文件存儲(chǔ)包含信息。

（2）設(shè)計(jì)禁忌搜索算法原理步驟，基于目標(biāo)函數(shù)求解最優(yōu)路徑。

（3）進(jìn)行不同規(guī)模算例下的分組實(shí)驗(yàn)，驗(yàn)證禁忌搜索算法對(duì)路徑能耗屬性、時(shí)間屬性和路徑負(fù)載均衡目標(biāo)參數(shù)的優(yōu)化效果。

2 方法

為系統(tǒng)構(gòu)建環(huán)境模型是AGV路徑規(guī)劃過程的重要組成部分，是將實(shí)際工廠作業(yè)環(huán)境的物理空間抽象模擬為算法可處理的數(shù)據(jù)環(huán)境，具體實(shí)現(xiàn)物理空間和數(shù)據(jù)環(huán)境的相互映射。

環(huán)境信息已知的多AGV 路徑規(guī)劃，路徑規(guī)劃流程為上位機(jī)依據(jù)任務(wù)分配準(zhǔn)則匹配相對(duì)應(yīng)的AGV，分配準(zhǔn)則為固定的均衡任務(wù)分配順序，順序依據(jù)為先到先得，訂單就近原則匹配起始點(diǎn)最近的AGV，上位機(jī)調(diào)度系統(tǒng)進(jìn)行最短路徑搜索并逐段下發(fā)可行駛的路徑資源。之后AGV 再向調(diào)度系統(tǒng)申請(qǐng)下一路徑資源，調(diào)度系統(tǒng)對(duì)競爭路徑資源的AGV的集合進(jìn)行優(yōu)先級(jí)排序和判斷阻塞區(qū)域類型，進(jìn)行交通管理。通行方向相同的AGV或者是只允許單輛AGV通行該區(qū)域，將線段或是阻塞區(qū)域等路徑資源分配給優(yōu)先級(jí)最高的AGV，其他AGV 排隊(duì)等候。AGV 每駛離占用的路徑資源，便上行報(bào)告上位機(jī)，上位機(jī)調(diào)度系統(tǒng)釋放該資源。進(jìn)入循環(huán)流程，直到所有分配訂單的AGV完成作業(yè)，自動(dòng)泊車。

2.1 模型構(gòu)建

AGV任務(wù)的規(guī)劃決策建立在已知環(huán)境信息的基礎(chǔ)上，地圖的構(gòu)建就是對(duì)環(huán)境信息的描述過程，地圖建模方法直接決定著環(huán)境信息表達(dá)的精確性和復(fù)雜度，影響著路徑搜索的效果與效率。常用的方法有幾何建模法、柵格建模法和拓?fù)浣７ā缀谓７ň褪菍h(huán)境信息抽象為多點(diǎn)折線或圓弧等幾何特征對(duì)地圖進(jìn)行描述，從而簡化地圖的表示，適用于小尺度或靜態(tài)環(huán)境下的應(yīng)用；柵格建模法是將環(huán)境空間均勻地劃分為若干大小相等且固定不變的柵格，每個(gè)柵格具有唯一的位置信息，但信息分辨率較低，數(shù)據(jù)結(jié)構(gòu)復(fù)雜；拓?fù)浣７ㄊ菍㈥P(guān)鍵站位的狀態(tài)和位置信息抽象為節(jié)點(diǎn)形式，相鄰節(jié)點(diǎn)用有向線段連接，表征連通狀態(tài)，從而形成點(diǎn)線相連的關(guān)系網(wǎng)[8]。不同建模方式均存在各自的優(yōu)勢(shì)與不足，如表1所示，需根據(jù)具體應(yīng)用場景選擇適應(yīng)系統(tǒng)方案的建模方法。

表1 常用建模方法

針對(duì)倉儲(chǔ)環(huán)境站位密集布置的應(yīng)用場景，拓?fù)浣７▋?yōu)勢(shì)明顯，具有計(jì)算效率高、內(nèi)存空間小和構(gòu)造過程簡潔的特點(diǎn)，尤其適用于關(guān)鍵站點(diǎn)的多聯(lián)通狀態(tài)，地圖表達(dá)更加緊湊。同時(shí)考慮系統(tǒng)實(shí)現(xiàn)訂單規(guī)劃決策、AGV位姿監(jiān)控、可視化地圖管理等功能，采用拓?fù)涞貓D法進(jìn)行系統(tǒng)模型的構(gòu)建，將作業(yè)環(huán)境下的AGV 導(dǎo)航定位構(gòu)建的復(fù)雜電子地圖和現(xiàn)場物理空間抽象建立拓?fù)浣Y(jié)構(gòu)，拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)組成如表2 所示。拓?fù)涞貓D在搜索計(jì)算最短路徑時(shí)的復(fù)雜度取決于環(huán)境中可通行的節(jié)點(diǎn)的數(shù)量，系列節(jié)點(diǎn)和連接節(jié)點(diǎn)依次表示功能站點(diǎn)和行駛路徑節(jié)點(diǎn)，連線節(jié)點(diǎn)線段的權(quán)值表示具體的路徑代價(jià)。

表2 拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)

結(jié)合實(shí)際的生產(chǎn)車間環(huán)境，將作業(yè)環(huán)境下的AGV導(dǎo)航定位構(gòu)建的復(fù)雜電子地圖和現(xiàn)場物理空間抽象建立拓?fù)浣Y(jié)構(gòu)模型，繪制行駛節(jié)點(diǎn)和各個(gè)功能站點(diǎn)組成的強(qiáng)連通性的有向帶權(quán)圖。在構(gòu)建系統(tǒng)拓?fù)浣Y(jié)構(gòu)時(shí)，考慮AGV 轉(zhuǎn)彎角度限制，利用二次貝塞爾曲線函數(shù)對(duì)設(shè)計(jì)的曲線路徑做平滑處理，使得AGV 在規(guī)劃的可行路徑上平穩(wěn)自然運(yùn)動(dòng)。模型地圖信息存儲(chǔ)為xml文件，包含路徑搜索需要的節(jié)點(diǎn)、站點(diǎn)、路徑線段信息、阻塞信息，如圖2所示。

圖2 地圖存儲(chǔ)信息

拓?fù)淠Ｐ陀邢驇?quán)圖表示為F(xl)＜F(xbestl)，如圖3所示，其中P={1,2,…,n,n+1} 表示節(jié)點(diǎn)和站點(diǎn)集合，Point集合表示中繼、交叉的行駛路徑節(jié)點(diǎn)，節(jié)點(diǎn)坐標(biāo)為(x,y)；Location 集合表示工作站，站臺(tái)屬性為(x,y,m)，(x,y)表示該點(diǎn)在地圖中的空間位置坐標(biāo)，m 表示在該點(diǎn)AGV 所要完成取卸貨和充電的功能動(dòng)作；將路徑描述為有向帶權(quán)線段E，箭頭表示有向路徑的方向，路徑權(quán)值采用cost(Length,Maxvelocity)的形式，表示AGV行駛路徑線段的時(shí)間成本，其中Length 表示路徑節(jié)點(diǎn)間的實(shí)際距離，Maxvelocity 表示路徑設(shè)置的速度閾值。

多AGV系統(tǒng)的路徑優(yōu)化問題的基礎(chǔ)約束保證系統(tǒng)狀態(tài)正常及功能完備。容量約束為每一個(gè)作業(yè)訂單只對(duì)應(yīng)一輛AGV。工作時(shí)長約束為AGV 從起始點(diǎn)出發(fā)到完成作業(yè)訂單的時(shí)長不能超過設(shè)置閾值[9]。

2.2 禁忌搜索算法

2.2.1 算法介紹

傳統(tǒng)的經(jīng)典算法Dijkstra 算法于1959 年由荷蘭科學(xué)家Dijkstra提出，該算法是單源路徑算法，用來求解一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑問題，它以起始點(diǎn)為中心向外層層擴(kuò)展，直至擴(kuò)展到終點(diǎn)為止，計(jì)算得到最短路徑。Dijkstra 算法能夠簡潔有效地找到最優(yōu)解，但不足之處在于O(n2)的計(jì)算復(fù)雜度，當(dāng)數(shù)據(jù)節(jié)點(diǎn)龐大時(shí)所需的節(jié)點(diǎn)繁多，效率隨著數(shù)據(jù)節(jié)點(diǎn)的增加而下降，耗費(fèi)大量內(nèi)存空間與計(jì)算時(shí)間，并不能很好地滿足多AGV動(dòng)態(tài)路徑規(guī)劃的系統(tǒng)需求[10]。

傳統(tǒng)的啟發(fā)式的A*算法搜索速度快且效率高，能在一定程度上克服搜索過程中的早熟現(xiàn)象，在機(jī)器人路徑規(guī)劃中得到了廣泛應(yīng)用。但A*算法同樣存在限制，在路徑搜索過程中，隨著地圖面積的增大其搜索空間會(huì)產(chǎn)生多余的搜索節(jié)點(diǎn)，導(dǎo)致算法效率降低，耗費(fèi)大量內(nèi)存空間與計(jì)算時(shí)間。相對(duì)而言，智能優(yōu)化算法可以更為有效地解決路徑規(guī)劃的多約束問題，通過將搜索路徑轉(zhuǎn)化為尋找函數(shù)最優(yōu)值，從而實(shí)現(xiàn)多AGV 系統(tǒng)路徑規(guī)劃中的最短路徑搜索[11]。

圖3 地圖模型

1986年，禁忌搜索（Tabu Search，TS）算法由Glover教授正式提出。其通過引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和與之對(duì)應(yīng)的禁忌準(zhǔn)則，并通過藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，借此保證多樣化的有效搜索來實(shí)現(xiàn)最終的全局優(yōu)化[12]。其最主要的特點(diǎn)就是采用了禁忌技術(shù)和特赦規(guī)則，使得算法可以跳出局部最優(yōu)解，進(jìn)行有效的計(jì)算，最終實(shí)現(xiàn)全局的優(yōu)化。禁忌搜索算法的搜索結(jié)果依賴于初始解和鄰域的映射關(guān)系，計(jì)算靈活，收斂速度快，能夠有效提高搜索速度和解的質(zhì)量。尤其是在問題規(guī)模較為龐大、傳統(tǒng)搜索方法不能在較短時(shí)間內(nèi)求得問題的最優(yōu)解，禁忌搜索算法的優(yōu)勢(shì)更加明顯，是適應(yīng)求解多AGV系統(tǒng)路徑搜索的理想算法。

逐步尋優(yōu)的路徑搜索算法一般采用貪婪思想對(duì)當(dāng)前解的鄰域進(jìn)行搜索，這樣的搜索方式使得鄰域的結(jié)構(gòu)和初始解的選取決定了其搜索速度性能和解質(zhì)量的優(yōu)劣，且無法保證求解算法的全局最優(yōu)。在禁忌搜索算法中，將已經(jīng)實(shí)現(xiàn)過的局部最短方案保存至禁忌表，在后續(xù)檢索相似路徑時(shí)避過禁忌列表中的點(diǎn)，避免局部最短路徑作為最優(yōu)解出現(xiàn)，當(dāng)局部最短路徑成為全局最短路徑時(shí)，再特赦為算法最優(yōu)解[13]。

2.2.2 算法結(jié)構(gòu)設(shè)計(jì)

（1）構(gòu)造初始解

從起始頂點(diǎn)SID出發(fā)，依據(jù)地圖聯(lián)通信息，將各節(jié)點(diǎn)加入到路徑列表中，直到搜索終點(diǎn)DID加入，即得到SID到DID的初始解路徑。逐步尋優(yōu)的路徑搜索算法一般采用貪婪思想對(duì)當(dāng)前解的鄰域進(jìn)行搜索，這樣的搜索方式使得鄰域的結(jié)構(gòu)和初始解的選取決定了其搜索速度性能和解質(zhì)量的優(yōu)劣，且無法保證求解算法的全局最優(yōu)。在禁忌搜索算法中，將已經(jīng)實(shí)現(xiàn)過的局部最短方案保存至禁忌表，在后續(xù)檢索相似路徑時(shí)避過禁忌列表中的點(diǎn)，避免局部最短路徑作為最優(yōu)解出現(xiàn)，當(dāng)局部最短路徑成為全局最短路徑時(shí)，再特赦為算法最優(yōu)解。

（2）鄰域解迭代

基于當(dāng)前解在鄰域中迭代搜索，鄰域滿足拓?fù)浣Y(jié)構(gòu)聯(lián)通屬性，計(jì)算路徑搜索當(dāng)前解的邊屬性總權(quán)重，邊屬性權(quán)重為AGV 理想行駛時(shí)間，用拓?fù)涞貓D節(jié)點(diǎn)間邊長和最大速度閾值作商取值。隨著鄰域解的迭代，基于目標(biāo)函數(shù)評(píng)判所迭代鄰域解對(duì)求解路徑時(shí)間屬性、能耗屬性和系統(tǒng)運(yùn)行穩(wěn)定程度的積極性。

（3）目標(biāo)函數(shù)

定義節(jié)點(diǎn)集合P（point）和線段集合S（segment）的路徑邊屬性總權(quán)重值的時(shí)間評(píng)價(jià)函數(shù)d(m)為：

目標(biāo)函數(shù)表達(dá)式定義為：

目標(biāo)函數(shù)對(duì)于迭代鄰域解的評(píng)判基于求解路徑的時(shí)間屬性、能耗屬性和系統(tǒng)運(yùn)行穩(wěn)定程度。能耗屬性參考依據(jù)為AGV 作業(yè)所行駛的物理距離，求解出的行駛物理距離越大，AGV 車體和使用電量等能耗越高。計(jì)算求解的AGV 理想行駛時(shí)間越長，路徑邊屬性總權(quán)重值的評(píng)價(jià)函數(shù)d(x)越大，則對(duì)應(yīng)目標(biāo)函數(shù)值越大，積極性越小。路徑網(wǎng)絡(luò)負(fù)載分布集中程度的系數(shù)項(xiàng)中，隨著普通節(jié)點(diǎn)數(shù)量的減少和交叉節(jié)點(diǎn)的增多，反映系統(tǒng)對(duì)交叉節(jié)點(diǎn)資源的競爭使用程度，負(fù)載集中系數(shù)項(xiàng)越大，則AGV 作業(yè)路徑阻塞障礙更為普遍。綜上，系統(tǒng)的高效穩(wěn)定性能取決于目標(biāo)函數(shù)的各個(gè)組成，且最優(yōu)路徑將具有最小的目標(biāo)函數(shù)值。

（4）禁忌、終止和特赦規(guī)則

禁忌對(duì)象：基于連通性的搜索路徑作為禁忌對(duì)象，禁忌表中收納該局部最優(yōu)解。

禁忌規(guī)則：在候選解中選出適應(yīng)值最好的候選解，將其與當(dāng)前最優(yōu)解進(jìn)行比較，目標(biāo)函數(shù)如果優(yōu)于當(dāng)前最優(yōu)解，則更新替換，并且作為下一個(gè)迭代的當(dāng)前最優(yōu)解，然后將對(duì)應(yīng)的操作加入禁忌表；如果目標(biāo)函數(shù)不優(yōu)于當(dāng)前最優(yōu)解，就從所有候選解中選出不在禁忌狀態(tài)下的最好解作為新的當(dāng)前最優(yōu)解，并將對(duì)應(yīng)操作加入禁忌表。

禁忌長度：設(shè)置禁忌長度，限制被禁忌的對(duì)象需要進(jìn)行對(duì)比的步數(shù)，其值可以根據(jù)問題的規(guī)模大小，取常數(shù)。

候選集合的確定：將從當(dāng)前解的鄰域中選擇交換算子生成新搜索路徑作為候選集合。

終止準(zhǔn)則：最大迭代步數(shù)作為算法的終止準(zhǔn)則。

特赦規(guī)則：在算法迭代產(chǎn)生當(dāng)前最優(yōu)解的同時(shí)，記錄判斷該解的評(píng)價(jià)函數(shù)值，當(dāng)該解優(yōu)于當(dāng)前問題的最優(yōu)解時(shí)，將其從禁忌表中特赦。

2.2.3 算法步驟流程

算法流程圖如圖4所示。

圖4 算法流程圖

算法步驟如下：

（1）初始化模塊參數(shù)，禁忌列表List_T 置空，就近優(yōu)先逐節(jié)點(diǎn)加入路徑，生成最短路徑初始解xl；

（2）在xl的鄰域L(List_T,xl)中選出滿足禁忌要求的候選集Cand_L(xl)；

2.3 算法實(shí)現(xiàn)

本文用Java語言實(shí)現(xiàn)禁忌搜索算法，代碼結(jié)構(gòu)分為main（）、ReadIn_and_Initialization（）、Construction（）、Calculation（）、Tabu_Search（）、Check（）和Output（）函數(shù)模塊。其中main（）函數(shù)構(gòu)建算法的主體框架；ReadIn_and_Initialization（）的功能是讀取存儲(chǔ)xml 地圖文件并初始化所有變量；Construction（）、Calculation（）、Tabu_Search（）分別實(shí)現(xiàn)禁忌搜索算法中的初始解構(gòu)建、對(duì)應(yīng)解的適應(yīng)值計(jì)算和對(duì)定義鄰域進(jìn)行搜索并對(duì)應(yīng)標(biāo)準(zhǔn)選擇禁忌；Check（）函數(shù)的功能是用來檢驗(yàn)解是否滿足對(duì)應(yīng)的所有約束；Output（）函數(shù)輸出結(jié)果。

3 實(shí)驗(yàn)

本文將通過仿真實(shí)驗(yàn)對(duì)這幾種常用路徑規(guī)劃算法進(jìn)行比較，并且結(jié)合機(jī)器人實(shí)際運(yùn)行情況對(duì)幾種算法進(jìn)行分析。

運(yùn)輸訂單的生命周期如圖5所示。

圖5 訂單生命周期

創(chuàng)建運(yùn)輸訂單后，其初始狀態(tài)為RAW；設(shè)置運(yùn)輸訂單參數(shù)，激活狀態(tài)為ACTIVE；可匹配AGV 狀態(tài)轉(zhuǎn)換為DISPATCHABLE；UNROUTABLE 則不進(jìn)行任何處理；AGV執(zhí)行移動(dòng)指令任務(wù)訂單狀態(tài)為BEING_PROCESSED。AGV 的處理運(yùn)輸訂單失敗，則將其標(biāo)記為FAILED。如果AGV 成功處理了整個(gè)運(yùn)輸訂單，則將其標(biāo)記為FINISHED。AGV 總能耗用AGV 該批序列訂單完成過程中的總充電次數(shù)衡量定義。任務(wù)完成時(shí)間取決于最后一個(gè)任務(wù)的結(jié)束時(shí)間，用來衡量同批序列任務(wù)從生成到全部完成的總大時(shí)間開銷，任務(wù)完成時(shí)間越小則系統(tǒng)效率越高。

改變總節(jié)點(diǎn)個(gè)數(shù)、路徑邊數(shù)建立不同規(guī)模地圖模型，做分組實(shí)驗(yàn)驗(yàn)證禁忌搜索算法性能。實(shí)驗(yàn)仿真觸發(fā)200個(gè)任務(wù)訂單，跟蹤監(jiān)測(cè)系統(tǒng)總能耗、任務(wù)完成時(shí)間、死鎖情況出現(xiàn)概率和任務(wù)完成比率，來對(duì)標(biāo)路徑優(yōu)化算法在能耗屬性、時(shí)間屬性和系統(tǒng)運(yùn)行負(fù)載均衡屬性上的優(yōu)越性，測(cè)試用例執(zhí)行狀態(tài)跟蹤表如表3～表5所示。

表3 40節(jié)點(diǎn)地圖模型中路徑搜索算法對(duì)比

表4 100節(jié)點(diǎn)地圖模型中路徑搜索算法對(duì)比

禁忌搜索算法的核心是在循環(huán)中構(gòu)建一個(gè)禁忌循環(huán)列表，采用動(dòng)態(tài)更新的方法來實(shí)現(xiàn)短期循環(huán)記憶，以避免搜索出現(xiàn)相同的解。經(jīng)實(shí)驗(yàn)驗(yàn)證，在一般情況下，禁忌搜索算法在處理時(shí)間、系統(tǒng)能耗和任務(wù)完成比率上相差不大，但在項(xiàng)目規(guī)模較大的情況下，禁忌搜索算法相比于傳統(tǒng)經(jīng)典算法Dijkstra的計(jì)算時(shí)長優(yōu)越性顯著體現(xiàn)，相對(duì)于啟發(fā)式A*算法的系統(tǒng)運(yùn)行流暢度顯著提升。隨著系統(tǒng)規(guī)模的增大，求解路徑能耗更低，用時(shí)更少，可以有效地均衡全局路徑的資源使用，充分體現(xiàn)基于禁忌搜索的多AGV路徑優(yōu)化算法的必要性和優(yōu)越性。

表5 1 000節(jié)點(diǎn)地圖模型中路徑搜索算法對(duì)比

4 結(jié)束語

隨著5G時(shí)代和工業(yè)4.0的到來，企業(yè)智能制造的不斷改造升級(jí)，AGV移動(dòng)機(jī)器人扮演著相當(dāng)重要的角色，而對(duì)AGV路徑規(guī)劃技術(shù)的依賴要求也日益增高[14]。多AGV系統(tǒng)的路徑規(guī)劃，要求其按照一定的參數(shù)指標(biāo)，在任務(wù)區(qū)域求解出滿足要求的優(yōu)化可行路徑。禁忌搜索算法在一定程度上而言，算法方案較為復(fù)雜，解的要素偏多，運(yùn)算工作量較大，且智能優(yōu)化算法的收斂速度和收斂效果存在一定限制。

多AGV系統(tǒng)的路徑規(guī)劃問題屬于NP問題，約束條件復(fù)雜，問題規(guī)模和求解難度大，本研究有重要的學(xué)術(shù)意義，有助于Agent路徑問題及相關(guān)優(yōu)化問題的發(fā)展[15]。在未來的研究方向中，基于本文集中式AGV 控制系統(tǒng)模式的全局路徑規(guī)劃，結(jié)合分布式AGV 控制系統(tǒng)的局部路徑規(guī)劃，可以完善AGV的避障功能，提高系統(tǒng)的穩(wěn)定性和抗干擾性。