柔性制造車(chē)間多載具AGV 任務(wù)分組算法研究*

張博暉，武照云，程洋洋，代爭(zhēng)爭(zhēng)，高夢(mèng)媛

（河南工業(yè)大學(xué) 機(jī)電工程學(xué)院，河南 鄭州 450001）

引言

自動(dòng)導(dǎo)引運(yùn)輸車(chē)（automated guided vehicle，AGV）是柔性制造車(chē)間中不可或缺的運(yùn)輸工具，但隨著對(duì)柔性制造車(chē)間生產(chǎn)效率的要求不斷提高，多載具AGV 在柔性制造車(chē)間中的應(yīng)用也越來(lái)越多，即每輛AGV 上有多個(gè)可裝載工位，如何對(duì)任務(wù)與多載具AGV 進(jìn)行匹配是當(dāng)前急需解決的問(wèn)題，一種合理的任務(wù)調(diào)度策略可以有效提高多載具AGV 系統(tǒng)整體運(yùn)行效率[1]。

本文提出一種基于取貨點(diǎn)距離的多載具AGV 任務(wù)分組算法，即在已知多載具AGV 搬運(yùn)能力和任務(wù)的情況下，對(duì)任務(wù)進(jìn)行聚類(lèi)分組，從而最大化的利用多載具AGV 的搬運(yùn)效率，提高車(chē)間工作效率。

1 任務(wù)組合問(wèn)題描述與建模

柔性制造車(chē)間多載具AGV 系統(tǒng)的任務(wù)序列中通常存在多個(gè)運(yùn)輸任務(wù)，由于每個(gè)任務(wù)的位置信息不同，所以要考慮多載具AGV 與多個(gè)任務(wù)如何匹配的問(wèn)題，即每輛多載具AGV 選擇哪些貨物進(jìn)行搬運(yùn)的問(wèn)題[2]。因此多載具AGV 任務(wù)調(diào)度要求AGV 控制系統(tǒng)對(duì)任務(wù)進(jìn)行合理分配，協(xié)調(diào)所有任務(wù)有序執(zhí)行，從而保證柔性制造車(chē)間能夠高效運(yùn)轉(zhuǎn)。

1.1 車(chē)間環(huán)境建模

在制造車(chē)間環(huán)境中開(kāi)展AGV 任務(wù)調(diào)度研究，首先要建立車(chē)間環(huán)境地圖。關(guān)于車(chē)間環(huán)境表達(dá)存在許多方法，例如：可視圖法、柵格地圖法、拓?fù)涞貓D法等，其中拓?fù)涞貓D法是一種高效的電子地圖建模方法，尤其適用于車(chē)輛路網(wǎng)確定的情形[3，4]。相應(yīng)地，實(shí)際的AGV 可行行使路徑可抽象為拓?fù)鋱D中的線段或者是弧線，AGV 路徑的交叉點(diǎn)、停車(chē)點(diǎn)、充電樁等特殊意義的位置可以抽象為節(jié)點(diǎn)，進(jìn)而這些節(jié)點(diǎn)和連接線組合成為車(chē)間環(huán)境的拓?fù)浣Y(jié)構(gòu)圖。

具體地，拓?fù)鋱D G=（V，E）中 V={v1，v2，…，vi，…，vz}是圖G 中z 個(gè)頂點(diǎn)的集合，vi可代表路徑交叉點(diǎn)和工作臺(tái)等具有獨(dú)特意義的位置，i∈[1，z]；E={e1，e2，…，ek，…，em}是圖G 中數(shù)量為m 的邊集合，ek代表車(chē)間運(yùn)輸?shù)缆罚琸∈[1，m]。

1.2 任務(wù)分組函數(shù)建模

柔性制造車(chē)間中多載具AGV 的任務(wù)調(diào)度問(wèn)題首先要明確哪輛多載具AGV 搬運(yùn)哪些工件，這是一種經(jīng)典的NP-hard 問(wèn)題。本文將多個(gè)任務(wù)與多個(gè)多載具AGV 的匹配問(wèn)題轉(zhuǎn)化為多個(gè)任務(wù)組與多個(gè)多載具AGV 的匹配問(wèn)題，即將任務(wù)序列中的任務(wù)基于取貨點(diǎn)聚類(lèi)為多個(gè)任務(wù)組，再將這些任務(wù)組分配給每輛多載具AGV[5]。

為了描述模型，現(xiàn)定義以下變量和常量。

表1 模型參數(shù)和決策變量定義表

假設(shè)制造車(chē)間環(huán)境待執(zhí)行任務(wù)信息已知，為建立基于取貨點(diǎn)距離的任務(wù)分組模型，以模型構(gòu)建的現(xiàn)實(shí)性和易處理性為原則且不失一般性，提出以下建模假設(shè)：

（1）所有多載具AGV 零時(shí)刻可用。

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

（3）一道工序任務(wù)只能被分配到一個(gè)任務(wù)組中。

基于建模假設(shè)，多載具AGV 任務(wù)分組算法以組內(nèi)取貨點(diǎn)距離max（Czi-CGj）2為優(yōu)化目標(biāo)，具體可表示為：

約束條件為：

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

2 問(wèn)題求解

柔性制造車(chē)間多載具AGV 調(diào)度系統(tǒng)檢測(cè)到任務(wù)到來(lái)后，首先讀取所有待執(zhí)行任務(wù)的信息，然后根據(jù)所提任務(wù)分組算法對(duì)所有任務(wù)進(jìn)行聚類(lèi)分組，直至所有任務(wù)都被分組?；谌∝淈c(diǎn)距離的任務(wù)分組算法流程如下：

步驟一：讀取任務(wù)序列信息，提取各任務(wù)的取貨點(diǎn)坐標(biāo)，隨機(jī)選擇一個(gè)任務(wù)點(diǎn)作為一個(gè)初始組心；

步驟二：計(jì)算每個(gè)樣本點(diǎn)與當(dāng)前已有聚類(lèi)中心之間的最短距離，用D（x）表示，然后計(jì)算每個(gè)樣本點(diǎn)被選為下一個(gè)聚類(lèi)中心的概率按輪盤(pán)法選出下一個(gè)聚類(lèi)中心，D（x）越大被選為聚類(lèi)中心的概率越大；

步驟三：重復(fù)步驟二，直至選出r 個(gè)組心；

步驟四：計(jì)算任務(wù)序列中其他各任務(wù)點(diǎn)到r 個(gè)組心之間的距離，并將其分配到距離最小的組心所對(duì)應(yīng)的組中；

步驟五：重新計(jì)算r 個(gè)組的質(zhì)心，并作為新的組心；

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

步驟七：每個(gè)組心依次選擇距離自身最近的任務(wù)點(diǎn)，直至所有任務(wù)都被分配到任務(wù)組中；

基于取貨點(diǎn)距離的任務(wù)分組算法流程如圖1 所示。

圖1 基于取貨點(diǎn)距離的任務(wù)分組算法流程圖

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

以某柔性制造車(chē)間為例，所建立的車(chē)間拓?fù)涞貓D如圖2 所示，共有38 個(gè)節(jié)點(diǎn)，61 條邊，定義車(chē)間中1 點(diǎn)為坐標(biāo)原點(diǎn)，車(chē)間中有多輛三工位的多載具AGV，即每輛AGV 可最多同時(shí)搬運(yùn)三個(gè)工件，當(dāng)前待執(zhí)行任務(wù)序列Xn如表2 所示。

圖2 車(chē)間拓?fù)涞貓D

首先采用任務(wù)分組算法對(duì)任務(wù)進(jìn)行聚類(lèi)分組，然后使用Dijkstra 算法計(jì)算多載具AGV 完成所有任務(wù)所需的運(yùn)輸距離[6]。本實(shí)驗(yàn)以matlab2018 版為實(shí)驗(yàn)平臺(tái)，通過(guò)所提算法求解可將任務(wù)序列分為6 組，算法結(jié)果圖示意圖如圖3 所示，基于取貨點(diǎn)距離的任務(wù)分組結(jié)果及組內(nèi)各成員信息如表3 所示，經(jīng)計(jì)算完成所有任務(wù)后，多載具AGV 總的運(yùn)輸距離為307.5m。

表2 柔性制造車(chē)間待執(zhí)行任務(wù)序列

圖3 任務(wù)分組算法結(jié)果示意圖

表3 基于取貨點(diǎn)距離的任務(wù)分組結(jié)果及組內(nèi)各成員信息

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

表4 基于順序分組的任務(wù)分組結(jié)果及組內(nèi)各成員信息

通過(guò)對(duì)比兩種方法下多負(fù)載AGV 執(zhí)行任務(wù)所需的運(yùn)輸距離可知，在多載具AGV 任務(wù)已知的情況下，基于取貨點(diǎn)距離的任務(wù)分組算法既能在充分利用多載具AGV 最大運(yùn)輸能力的情況下對(duì)任務(wù)進(jìn)行分組，又可以有效減少AGV 執(zhí)行任務(wù)所需的運(yùn)輸距離，共減少了155.5m 的運(yùn)輸路徑，有效的提高了車(chē)間的運(yùn)行效率。

4 結(jié)論

（1）根據(jù)柔性制造車(chē)間中現(xiàn)有的任務(wù)信息，設(shè)計(jì)提出了一種基于取貨點(diǎn)距離的多載具AGV 任務(wù)分組算法。

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