柔性制造車間多載具AGV 任務分組算法研究*

張博暉，武照云，程洋洋，代爭爭，高夢媛

（河南工業大學 機電工程學院，河南 鄭州 450001）

引言

自動導引運輸車（automated guided vehicle，AGV）是柔性制造車間中不可或缺的運輸工具，但隨著對柔性制造車間生產效率的要求不斷提高，多載具AGV 在柔性制造車間中的應用也越來越多，即每輛AGV 上有多個可裝載工位，如何對任務與多載具AGV 進行匹配是當前急需解決的問題，一種合理的任務調度策略可以有效提高多載具AGV 系統整體運行效率[1]。

本文提出一種基于取貨點距離的多載具AGV 任務分組算法，即在已知多載具AGV 搬運能力和任務的情況下，對任務進行聚類分組，從而最大化的利用多載具AGV 的搬運效率，提高車間工作效率。

1 任務組合問題描述與建模

柔性制造車間多載具AGV 系統的任務序列中通常存在多個運輸任務，由于每個任務的位置信息不同，所以要考慮多載具AGV 與多個任務如何匹配的問題，即每輛多載具AGV 選擇哪些貨物進行搬運的問題[2]。因此多載具AGV 任務調度要求AGV 控制系統對任務進行合理分配，協調所有任務有序執行，從而保證柔性制造車間能夠高效運轉。

1.1 車間環境建模

在制造車間環境中開展AGV 任務調度研究，首先要建立車間環境地圖。關于車間環境表達存在許多方法，例如：可視圖法、柵格地圖法、拓撲地圖法等，其中拓撲地圖法是一種高效的電子地圖建模方法，尤其適用于車輛路網確定的情形[3，4]。相應地，實際的AGV 可行行使路徑可抽象為拓撲圖中的線段或者是弧線，AGV 路徑的交叉點、停車點、充電樁等特殊意義的位置可以抽象為節點，進而這些節點和連接線組合成為車間環境的拓撲結構圖。

具體地，拓撲圖 G=（V，E）中 V={v1，v2，…，vi，…，vz}是圖G 中z 個頂點的集合，vi可代表路徑交叉點和工作臺等具有獨特意義的位置，i∈[1，z]；E={e1，e2，…，ek，…，em}是圖G 中數量為m 的邊集合，ek代表車間運輸道路，k∈[1，m]。

1.2 任務分組函數建模

柔性制造車間中多載具AGV 的任務調度問題首先要明確哪輛多載具AGV 搬運哪些工件，這是一種經典的NP-hard 問題。本文將多個任務與多個多載具AGV 的匹配問題轉化為多個任務組與多個多載具AGV 的匹配問題，即將任務序列中的任務基于取貨點聚類為多個任務組，再將這些任務組分配給每輛多載具AGV[5]。

為了描述模型，現定義以下變量和常量。

表1 模型參數和決策變量定義表

假設制造車間環境待執行任務信息已知，為建立基于取貨點距離的任務分組模型，以模型構建的現實性和易處理性為原則且不失一般性，提出以下建模假設：

（1）所有多載具AGV 零時刻可用。

（2）不考慮工件的重量和體積。

（3）一道工序任務只能被分配到一個任務組中。

基于建模假設，多載具AGV 任務分組算法以組內取貨點距離max（Czi-CGj）2為優化目標，具體可表示為：

約束條件為：

式（2）保證每個任務都被分配；式（3）保證同一個任務只能被分配到一個組中。

2 問題求解

柔性制造車間多載具AGV 調度系統檢測到任務到來后，首先讀取所有待執行任務的信息，然后根據所提任務分組算法對所有任務進行聚類分組，直至所有任務都被分組?；谌∝淈c距離的任務分組算法流程如下：

步驟一：讀取任務序列信息，提取各任務的取貨點坐標，隨機選擇一個任務點作為一個初始組心；

步驟二：計算每個樣本點與當前已有聚類中心之間的最短距離，用D（x）表示，然后計算每個樣本點被選為下一個聚類中心的概率按輪盤法選出下一個聚類中心，D（x）越大被選為聚類中心的概率越大；

步驟三：重復步驟二，直至選出r 個組心；

步驟四：計算任務序列中其他各任務點到r 個組心之間的距離，并將其分配到距離最小的組心所對應的組中；

步驟五：重新計算r 個組的質心，并作為新的組心；

步驟六：重復步驟四、五直至組心不再變化；

步驟七：每個組心依次選擇距離自身最近的任務點，直至所有任務都被分配到任務組中；

基于取貨點距離的任務分組算法流程如圖1 所示。

圖1 基于取貨點距離的任務分組算法流程圖

3 實例驗證

以某柔性制造車間為例，所建立的車間拓撲地圖如圖2 所示，共有38 個節點，61 條邊，定義車間中1 點為坐標原點，車間中有多輛三工位的多載具AGV，即每輛AGV 可最多同時搬運三個工件，當前待執行任務序列Xn如表2 所示。

圖2 車間拓撲地圖

首先采用任務分組算法對任務進行聚類分組，然后使用Dijkstra 算法計算多載具AGV 完成所有任務所需的運輸距離[6]。本實驗以matlab2018 版為實驗平臺，通過所提算法求解可將任務序列分為6 組，算法結果圖示意圖如圖3 所示，基于取貨點距離的任務分組結果及組內各成員信息如表3 所示，經計算完成所有任務后，多載具AGV 總的運輸距離為307.5m。

表2 柔性制造車間待執行任務序列

圖3 任務分組算法結果示意圖

表3 基于取貨點距離的任務分組結果及組內各成員信息

然后，采用順序分組的方法進行分組，基于順序分組的結果如表4 所示，結合Dijkstra 算法求解，得出該方法下多載具AGV 完成所有任務的運輸距離為463m。

表4 基于順序分組的任務分組結果及組內各成員信息

通過對比兩種方法下多負載AGV 執行任務所需的運輸距離可知，在多載具AGV 任務已知的情況下，基于取貨點距離的任務分組算法既能在充分利用多載具AGV 最大運輸能力的情況下對任務進行分組，又可以有效減少AGV 執行任務所需的運輸距離，共減少了155.5m 的運輸路徑，有效的提高了車間的運行效率。

4 結論

（1）根據柔性制造車間中現有的任務信息，設計提出了一種基于取貨點距離的多載具AGV 任務分組算法。

（2）案例研究表明，在AGV 最大裝載能力確定的情況下，所提算法既可有效的將任務進行分組，又能減少多載具AGV 完成任務所需的運輸距離，進而證明了所提分組算法的可行性與有效性。