面向智能制造車間的自動導引車調度優化算法研究

崔占鵬，王永軍

（1.鄭州工商學院 信息工程學院，鄭州 451400；2.河南理工大學 計算機科學與技術學院，焦作 454000）

0 引言

制造業作為國民經濟的重要支柱，代表著一個國家的科學技術和產業力量。在激烈的市場競爭和不斷更新的情況下，現代制造面對著單件、小批量、個性化定制等多種生產形式，提出了敏捷制造、準時制造、智能制造等模式。自動導引車具有半自動化和全自動兩種運輸作業，它能使物料的搬運和裝卸實現自動化[1]。目前，自動導引車已被廣泛地用于自動化倉儲、物流搬運、智能制造車間等各個方面。為滿足智能制造車間的作業任務，對于自動導引車的調度優化研究成為了熱點問題。

李西興[2]等采用混合遺傳鯨魚優化算法，實現了柔性車間的自動引導車的融合調度。本文利用了基于工序排序和機械選取兩個問題的二次矢量化編碼方法，給出了以優先業務為基礎的自動引導車調度算法。提出了一種基于離散化改進鯨魚優化算法的群體初始化方法。采用了基于遺傳算法的交叉和變異運算，結合了基于局部搜索的方法，實現了融合調度模型求解。該方法的融合調度效果較好，但調度效率較低。蘇少春[3]等采用多目標狼群算法，研究了多模型自動導引車的路線優選問題。對自動導引車的航向規劃問題進行了分析，提出了多個最優解，并對自動導引車的兩級航跡進行了詳細的設計。將狼群算法應用于非支配狀態的狼群群體中，采用群體的數量來維持群體的差異，從而提高了多目標的性能，由此實現多模型自動導引車的路線優選。該方法能夠有效實現自動導引車運行路線規劃，但調度效果有待提高。針對上述問題，提出了面向智能制造車間的自動導引車調度優化算法。

1 智能制造車間自動導引車調度優化算法

1.1 自動導引車調度優化模型構建

為有效實現智能制造車間自動導引車調度優化，確保自動導引車行駛距離最短。首先，構建自動導引車調度優化模型。

假設存在一個任務指定位置集Q?W，W表示任務點集合，則將該任務指定位置集的總任務量描述為：

當自動導引車完成作業任務后，則返回作業起點，通過本文模型，獲取自動導引車行駛距離最短的路線。假設變量表示為自動導引車e從任務點i行駛至任務點j；變量表示為未行駛到任務點的情況。由此，可構建的自動導引車調度優化模型如下：

目標函數為：

式(2)中，R為自動導引車集合，wij為任務點i至任務點j的行駛消耗，其中包括行駛的時間和距離。

約束條件為：

1）自動引導車裝載數量的約束：

式(3)中，ti表示為任務點i的總任務量，P表示為自動導引車任務點具備數量。

2）每一個任務點只能進行一次訪問的約束：

3）從作業起點到任務點后，無自動導引車重新回到作業起點的約束：

4）路徑選擇的約束：

通過設置不同的參數，可以將自動導引車的優化模型轉化為組合優化問題。假定使用了某輛自動引導車，這個問題可以轉化為旅行商問題（TSP）模型。

若附加約束條件g0=GH，GH≤gi≤JH，其中，gi表示為自動導引車達到任務點的時間，[GH,JH]表示為實現每項任務的時間范圍。假設繼續附加約束其中，Tij為任務點i與任務點j之間的運輸時間，為自動導引車e行駛至任務點i的起始時間，則可獲取包含時間窗的自動導引車調度優化問題的數學模型。

1.2 自動導引車調度優化模型求解

在構建自動導引車調度優化模型后，采用遞歸神經網絡[4]對自動導引車調度優化模型進行求解。具體步驟如下：

1）相鄰矩陣構造：利用網絡節點，繪制了自動導引車起始點、經過路口和停車點，并用抽象的邊線將各點上的有向路徑相聯系，提出了一個有向圖表示為：

式(9)中，X為邊數，Z為節點數，C為節點數的矩陣。

根據上述自動導引車調度優化模型可知，需要最優目標是邊(i,j)的長度和時間，從而構造了距離和時間的相鄰矩陣。

2）約束處理：在此基礎上，提出了一種基于遞歸神經網絡的能量函數的自動導引車調度優化模型，并在各能量方程中加入了一條懲罰項完成約束處理，從而使得約束能量在網絡中的持續收斂得到了較好的穩定性。

設定pω為任務點所需量，ξ,ζ為運輸順序，運輸點為ω,?。

假定每一行和每一列只有1個，而且不包含0行，也就是說，當自動導引車經過一次任務點，并且必須經過一次時，返回作業起點的約束為：

假定0行中所有列的數值之和是B，也就是說，運輸的路徑數目是B，那么，有約束如下：

假定整個矩陣中的每一個單位的總和是V+B，作業起點的起始數目是τ，那么，有約束如下：

假定自動導引車的作業起點是一個物料任務點，那么，有約束如下：

假定自動導引車有負荷約束，并且每個自動導引車都有裝載極限D，當滿足極限條件時，將返回任務點，那么，有約束如下：

3）遞歸神經網絡計算：假定相鄰矩陣中的每個單元都對應于一個神經元，并設置了Vωξ是在(ω,ξ)點處的輸出數值。在此基礎上，首先求出了遞歸神經網絡的能量函數，并對其進行了能量分析，得到了神經元的傳輸和狀態轉換方程，并對其進行了連續的迭代，得到了網絡的收斂性。其能量函數表示為：

當得到能量函數后，由于該神經網絡是以梯度的形式實現，因此，需通過以下形式計算神經元的傳遞函數與狀態轉移方程表示為：

在獲得了能量函數之后，由于遞歸神經網絡采用了梯度結構，需要表達神經元的傳輸函數和狀態轉換，在(ω,ξ)點處的輸出數值表示為：

4）調度優化方案制定：通過對遞歸神經網絡的收斂性分析，可以形成以0和1為單位的移位陣列。在該陣列中，自動導引車通過的節點為1，將各節點之間的距離和運輸時間相加，可以得到最短的距離和時間。根據上述條件，可獲得面向智能制造車間的自動導引車調度優化方案。

1.3 自動導引車調度優化實現

在對自動導引車調度優化模型進行求解的基礎上，利用模擬退火算法[5]，實現自動導引車調度優化。基于模擬退火算法的自動導引車調度優化算法流程如圖1所示。

圖1 基于模擬退火算法的自動導引車調度優化算法流程

步驟1：對較高溫度T和自動導引車運輸路徑數目B進行初始化，設定溫度T的迭代次數為U；

步驟2：對初始自動導引車運輸路徑數目擾動產生新解ι;

步驟3：計算自動導引車運輸路徑長度的差為：

步驟4：如果Δ?＜0，接受新路線解ι，否則以為新解的接受概率。

步驟5：當迭代次數達到U時，新路線解ι沒有接受，則算法結束，輸出最優自動導引車調度路線；否則T減少，返回步驟2。通過上述步驟，由此實現自動導引車調度優化。

2 實驗分析

2.1 實驗環境設置

為了驗證面向智能制造車間的自動導引車調度優化算法的有效性。實驗在Intel(R) Core(TM) i5-4570 CPU @3.20GHz CPU的計算機上測得，在Windows 7系統環境下，將MATLAB仿真平臺作為實驗環境。以某智能制造車間的自動導引車作為研究對象，分別采用文獻[2]算法、文獻[3]算法和所提算法進行對比，對上述自動導引車調度優化模型的實現過程進行驗證。

2.2 自動導引車調度優化效果對比分析

為驗證所提算法的自動導引車調度優化效果，基于上述設置的實驗環境，選取2個任務點，得到不同算法從物料運輸點到達任務點的調度路線，對比分析結果如圖2所示。

分析圖2可知，不同算法從物料運輸點到達2個任務點的調度路線均有所不同。其中，文獻[2]算法從物料運輸點到達2個任務點的調度路線最遠，規劃后的路徑距離最遠，該調度路線呈現出曲線形狀。文獻[3]算法從物料運輸點到達2個任務點的調度路線明顯短于文獻[2]算法從物料運輸點到達2個任務點的調度路線，說明文獻[3]算法在從物料運輸點到達任務點的調度路線時，能夠有效縮短調度路徑。而相對于文獻[2]算法和文獻[3]算法，所提算法從物料運輸點到達2個任務點的調度路線最短，且均呈現出直線的形式。由此可知，所提算法的自動導引車調度優化效果較好。

圖2 不同算法從物料運輸點到達任務點的調度路線

2.3 自動導引車調度優化路徑長度對比分析

進一步驗證所提算法的自動導引車調度優化路徑長度，選取5個任務點進行自動導引車調度優化，得到不同算法的自動導引車調度優化路徑長度，對比分析結果如圖3所示。

圖3 不同算法的自動導引車調度優化路徑長度

分析圖3可知，隨著任務點的增加，不同算法的自動導引車調度優化路徑長度隨之增加。當任務點為5個時，文獻[2]算法的自動導引車調度優化路徑長度為3760m，文獻[3]算法的自動導引車調度優化路徑長度為5780m。而所提算法的自動導引車調度優化路徑長度僅為988m。由此可知，所提算法的自動導引車調度優化路徑長度較短。

2.4 自動導引車調度優化效率對比分析

在此基礎上，驗證所提算法的自動導引車調度優化效率，將自動導引車調度優化時間作為評價指標，其自動導引車調度優化時間越短，表明算法的自動導引車調度優化效率越高。得到不同算法的自動導引車調度優化時間，對比分析結果如表1所示。

表1 不同算法的自動導引車調度優化時間

根據表1可知，隨著任務點的增加，不同算法的自動導引車調度優化時間隨之增加。當任務點為10個時，文獻[2]算法的自動導引車調度優化時間為46.4s，文獻[3]算法的自動導引車調度優化時間為51.2s，而所提算法的自動導引車調度優化時間僅為38.4s。由此可知，所提算法的自動導引車調度優化時間較短，能夠有效提高自動導引車調度優化效率。

3 結語

針對智能制造車間存在的自動導引車調度優化路徑長、效果差和效率低下的問題，研究了面向智能制造車間的自動導引車調度優化算法。通過構建自動導引車調度優化模型，采用遞歸神經網絡，求解自動導引車調度優化模型。在此基礎上，利用模擬退火算法，實現自動導引車調度優化。所提算法的自動導引車調度優化效果較好，能夠有效提高調度優化效率，縮短自動導引車調度優化路徑長度。