基于混合蟻群遺傳算法的多AGV任務(wù)分配*

□ 梅 前,董寶力

(浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(xué)院,浙江 杭州 310018)

消費(fèi)者需求不斷趨于多樣化和個(gè)性化，訂單結(jié)構(gòu)呈現(xiàn)多品種、多批次、小批量的特點(diǎn)，因而對(duì)揀選作業(yè)的速度和準(zhǔn)確性提出了更高的要求。在此背景下，揀選模式已由傳統(tǒng)“人到貨”逐漸向“貨到人”模式轉(zhuǎn)變，對(duì)揀選效率也提出了更高要求，而多AGV的任務(wù)調(diào)度是關(guān)系到揀選效率的核心問(wèn)題。

目前，不同學(xué)者采用多種算法對(duì)任務(wù)分配問(wèn)題進(jìn)行研究。朱良恒等在考慮安全能量約束下，針對(duì)多AGV任務(wù)分配中存在的能量消耗不均衡問(wèn)題，提出基于能量懲罰策略的遺傳算法優(yōu)化任務(wù)序列[1]。秦新立等在復(fù)雜約束環(huán)境下，引入局部?jī)?yōu)化算子和改進(jìn)模擬退火算法求解多AGV任務(wù)分配問(wèn)題[2]。李明等在基于Agent能力模型的基礎(chǔ)上改進(jìn)合同網(wǎng)的招標(biāo)階段和投標(biāo)階段，提出一種改進(jìn)的合同網(wǎng)協(xié)議的多Agent動(dòng)態(tài)任務(wù)分配方法[3]。張子迎等提出基于啟發(fā)式深度Q學(xué)習(xí)多AGV任務(wù)分配算法解決環(huán)境復(fù)雜性增加時(shí)出現(xiàn)的維度災(zāi)難問(wèn)題[4]。陳明智等采用Q-Learning算法求解綜合時(shí)間代價(jià)、路徑代價(jià)和協(xié)同度代價(jià)的多智能體分配算法[5]。Elango等提出利用拍賣(mài)機(jī)制和 K-means聚類算法求解雙目標(biāo)任務(wù)分配模型[6]。王曉軍等采用改進(jìn)交叉變異的方式的多種群遺傳算法求解多作業(yè)模式下多AGV任務(wù)分配問(wèn)題[7]。熊昕霞針對(duì)多AGV任務(wù)搬運(yùn)問(wèn)題，提出一種分布式協(xié)同任務(wù)分配策略，并采用k-means算法和改進(jìn)遺傳算法進(jìn)行求解[8]。

本文在基于貨架相似度的訂單分批基礎(chǔ)上,提出混合蟻群遺傳算法求解任務(wù)分配問(wèn)題，通過(guò)引入蟻群算法改進(jìn)遺傳算法尋優(yōu)能力的不足并利用蟻群算法產(chǎn)生的最優(yōu)解作為遺傳算法的初始種群,以加快遺傳算法的全局搜索能力和收斂速度。針對(duì)蟻群算法易陷入局部最優(yōu)解這一問(wèn)題，提出帶懲罰機(jī)制的動(dòng)態(tài)信息素更新策略，在遺傳算法中采用實(shí)數(shù)編碼,形象地表示搬運(yùn)貨架任務(wù)和AGV的對(duì)應(yīng)關(guān)系，在選擇方面采用輪盤(pán)賭和精英保留策略，對(duì)選擇算子進(jìn)行改進(jìn)從而使最優(yōu)個(gè)體能夠直接遺傳到下一代。仿真結(jié)果表明，在本文提出的混合蟻群遺傳算法較使用遺傳算法求解，能夠更明顯地發(fā)揮遺傳算法全局搜索能力強(qiáng)的特點(diǎn)且算法性能穩(wěn)定。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

本文研究某配送中心在“貨到人”揀選模式下多AGV任務(wù)分配的問(wèn)題。多AGV的任務(wù)分配問(wèn)題可以描述為:當(dāng)控制中心接受一個(gè)時(shí)間段訂單，按照邊播邊揀的模式將訂單合并同時(shí)基于貨架相似度[9]進(jìn)行分批處理，系統(tǒng)確認(rèn)每個(gè)訂單中貨物所在貨架的位置并調(diào)度系統(tǒng)中一定數(shù)量的AGV完成貨架的搬運(yùn)工作。當(dāng)訂單任務(wù)已經(jīng)確定后，由于揀選人員所需揀選的訂單品項(xiàng)是固定的，所有品項(xiàng)在貨架的貨位固定，即貨架的位置是固定的。通過(guò)將多個(gè)貨架搬運(yùn)任務(wù)分配給多個(gè)AGV進(jìn)行搬運(yùn)，對(duì)AGV貨架搬運(yùn)任務(wù)順序進(jìn)行調(diào)整，可以減少AGV總行駛距離，提升系統(tǒng)的揀選效率。AGV任務(wù)分配問(wèn)題屬于NP-C問(wèn)題，分配的目標(biāo)是將訂單任務(wù)合理均勻分配給不同的AGV并考慮任務(wù)之間的搬運(yùn)順序，加快整體的出庫(kù)效率。

在AGV完成任務(wù)的過(guò)程中，AGV首先從初始位置移動(dòng)到貨架所在位置并將貨架搬運(yùn)至分揀站臺(tái)，揀選人員根據(jù)訂單的信息揀選貨物并進(jìn)行打包裝箱工作，揀選完成后AGV將貨架搬運(yùn)到該貨架的原來(lái)位置，在此位置進(jìn)行下一次任務(wù)的分配[10]。邊揀邊播模式如圖1所示。

在以上背景下，針對(duì)多AGV任務(wù)分配問(wèn)題進(jìn)行研究，建立最小化所有AGV任務(wù)距離最短的數(shù)學(xué)模型，通過(guò)引入蟻群算法改進(jìn)了遺傳算法，提高遺傳算法局部搜索的能力，并對(duì)模型進(jìn)行求解。

1.2 模型建立

本文選擇柵格建模法對(duì)配送中心進(jìn)行建模[11]，這種建模方法直觀性強(qiáng)、適用性高且相對(duì)比較簡(jiǎn)單。配送中心環(huán)境如下：系統(tǒng)中有多個(gè)AGV、貨架以及分揀站臺(tái)，配送中心整體相當(dāng)于一個(gè)二維平面。建立直角坐標(biāo)系，以左下角為坐標(biāo)原點(diǎn)O，橫向建立X軸，縱向建立Y軸，將平面劃分成一個(gè)個(gè)柵格，如圖2所示。定義坐標(biāo)原點(diǎn)O的坐標(biāo)為(0,0)，每一個(gè)柵格都有確定的坐標(biāo)(x,y)。

圖2 配送中心建模

配送中心的整體布局采用I型布局，其中，貨架區(qū)域由多排貨架組成，每排貨架之間留有AGV行走的通道，每個(gè)貨架有多個(gè)貨位，每個(gè)貨位只有一種商品。AGV規(guī)定可以從通道內(nèi)行駛，亦可從貨架下方行駛。

本文對(duì)系統(tǒng)做出以下假設(shè)：

(a) 每個(gè)AGV從初始位置O出發(fā)；

(b) AGV在進(jìn)行轉(zhuǎn)彎作業(yè)時(shí)間設(shè)定為0；

(c) 所有貨架和分揀站臺(tái)的位置已知；

(d) 已分批訂單所需揀選的品項(xiàng)存儲(chǔ)在唯一貨架上且位置固定；

(e)任務(wù)的數(shù)量遠(yuǎn)大于AGV的數(shù)量；

(f)不考慮AGV在貨架等待和擁堵等情況；

(g)針對(duì)同一批次訂單，每個(gè)貨架只能被AGV 搬運(yùn)一次。

參數(shù)如下：

①C為待揀選貨架的數(shù)量，R為可調(diào)度AGV的數(shù)量，M為分揀站臺(tái)的數(shù)量；O為AGV初始位置；

②i為第i個(gè)貨架，i∈[1,C]；j為第j個(gè)分揀站臺(tái)，j∈[1,M]；k為第k臺(tái)AGV，k∈[1,R]；N為第k臺(tái)AGV分配的搬運(yùn)貨架的任務(wù)數(shù)量，p∈[1,N]；

③(xi,yi)是貨架i的坐標(biāo)位置，(xj,yj)是分揀站臺(tái)j的坐標(biāo)位置，(xk,yk)表示第k臺(tái)AGV在第i個(gè)貨架坐標(biāo)位置；

④Dkp0表示第k臺(tái)AGV從初始位置到達(dá)任務(wù)p所在貨架i所行駛的距離；Dkp1表示第k臺(tái)AGV從貨架i到分揀站臺(tái)j行走的距離；Dkp2表示第k臺(tái)AGV從分揀站臺(tái)j回到貨架i所行駛的距離；

⑤Sk(0,p)表示第k輛AGV執(zhí)行p任務(wù)從初始位置出發(fā)將貨架i搬運(yùn)到分揀站臺(tái)j并返回貨架位置的距離；Sk(p,p+1)表示第k輛AGV將貨架i搬運(yùn)回原位置后，前往第p+1個(gè)任務(wù)搬運(yùn)貨架i+1并完成貨架搬運(yùn)任務(wù)的距離，Sk(p,N)表示第k輛AGV完成最后搬運(yùn)任務(wù)后返回起始點(diǎn)的距離；

⑥Xkp為決策變量，表示第k臺(tái)AGV是否執(zhí)行第p個(gè)搬運(yùn)貨架任務(wù)。當(dāng)Xkp=1，則由第k臺(tái)AGV執(zhí)行第p個(gè)貨架搬運(yùn)任務(wù)，當(dāng)Xkp=0，則第k臺(tái)AGV不執(zhí)行p貨架搬運(yùn)任務(wù)。

基于AGV的任務(wù)分配目標(biāo)函數(shù)表示為最小化所有AGV的總行駛距離，數(shù)學(xué)表達(dá)式如下:

(1)

(2)

Dkp1=|xki-xkj|+|yki-ykj|

(3)

Dkp2=|xki-xkj|+|yki-ykj|

(4)

式(1)表示最小化所有AGV完成搬運(yùn)任務(wù)的總距離；式(2)表示第k臺(tái)AGV執(zhí)行q任務(wù)到達(dá)貨架i的距離；式(3)表示AGV搬運(yùn)貨架前往分揀站臺(tái)j的距離；式(4)表示AGV返回貨架原位置的距離。

約束條件：

∑kxkp=1，p∈[1,N]

(5)

∑pxkpq=xkq，q∈[1,N]，k∈[1,R]

(6)

∑qxkpq=xkp，p∈[1,N]，k∈[1,R]

(7)

式(5)表示一個(gè)搬運(yùn)貨架任務(wù)只能由一個(gè)AGV執(zhí)行；式(6)和(7)表示一個(gè)AGV一次只能執(zhí)行一個(gè)任務(wù)。

2 混合蟻群遺傳算法

遺傳算法(Genetic Algorithm，GA)是一種隨機(jī)化搜索方法，遺傳算法實(shí)現(xiàn)簡(jiǎn)單，通用性強(qiáng)，但也存在過(guò)早收斂、局部搜索能力弱等問(wèn)題。針對(duì)遺傳算法的上述不足，本文在遺傳算法的基礎(chǔ)上，引入蟻群算法來(lái)改進(jìn)遺傳算法的局部搜索能力。

2.1 蟻群算法求解任務(wù)分配問(wèn)題

本文求解的最小化所有AGV行駛總距離可轉(zhuǎn)化為MTSP問(wèn)題即將貨架類比城市，AGV類比旅行商，通過(guò)改變AGV任務(wù)執(zhí)行順序使得總路徑最短。

蟻群算法求解 MTSP 問(wèn)題主要是將 MTSP 問(wèn)題轉(zhuǎn)化為T(mén)SP 問(wèn)題，即在保持貨架和AGV數(shù)目不變的情況下，通過(guò)建立(m-1)個(gè)虛擬坐標(biāo)的單AGV問(wèn)題。給每只螞蟻隨機(jī)分配一個(gè)初始任務(wù),待初始任務(wù)完成將其加入禁忌表uk,然后從未完成的任務(wù)中選擇一個(gè)任務(wù)。當(dāng)?shù)趉輛AGV完成的任務(wù)數(shù)達(dá)到最大任務(wù)數(shù)時(shí),螞蟻選擇下一個(gè)AGV執(zhí)行其余任務(wù),直到所有任務(wù)完成為止。

①設(shè)置蟻群算法的初始參數(shù)，其中最大迭代次數(shù)Nmax，螞蟻的編號(hào)為k=1。

(8)

③當(dāng)某一貨架搬運(yùn)任務(wù)被完成后，將其加入設(shè)置的禁忌表uk中，記錄當(dāng)前的最優(yōu)解。

④判斷螞蟻是否完成對(duì)所有貨架的訪問(wèn)任務(wù)，如果完成則對(duì)信息素濃度進(jìn)行更新。蟻群算法在迭代產(chǎn)生最差的解會(huì)對(duì)后續(xù)螞蟻選擇路徑的行為產(chǎn)生誤導(dǎo)，因此，提出一種帶懲罰機(jī)制的動(dòng)態(tài)信息素更新策略，其更新方法如式(9)所示。

(9)

⑤判斷算法是否達(dá)到最大迭代次數(shù)，即是否滿足N>Nmax，是則輸出蟻群算法的最優(yōu)解，否則轉(zhuǎn)入步驟②。

2.2 遺傳算法階段

①生成初始種群。首先本文在蟻群算法產(chǎn)生的最優(yōu)解中選擇路徑最短的G/2個(gè)路徑，再?gòu)碾S機(jī)產(chǎn)生的G/2個(gè)路徑中確定初始種群的數(shù)量G，染色體長(zhǎng)度為N，最大迭代次數(shù)為gmax，交叉概率為Pc和變異概率為Pm。

②編碼。本文采用實(shí)數(shù)編碼方式生成染色體，其中染色體的長(zhǎng)度為一個(gè)批次中的總?cè)蝿?wù)數(shù)；每個(gè)基因位代表一個(gè)貨架搬運(yùn)任務(wù)；基因位上對(duì)應(yīng)的值表示該序號(hào)的AGV完成該位置的任務(wù)。

以圖3染色體編碼為例，AGV編碼數(shù)字表示執(zhí)行該任務(wù)的AGV編號(hào)，任務(wù)號(hào)數(shù)字表示一個(gè)批次的任務(wù)順序。在種群初始化中，AGV編碼按照均衡分配編碼進(jìn)行初始化。

圖3 染色體編碼方式

③適應(yīng)度函數(shù)設(shè)計(jì)。取各染色體的目標(biāo)函數(shù)值的倒數(shù)，即染色體中所有AGV完成全部任務(wù)行駛距離的倒數(shù)作為該染色體的適應(yīng)度值，適應(yīng)度函數(shù)如式10所示。

(10)

④采用精英策略和輪盤(pán)賭選擇。先根據(jù)輪盤(pán)賭規(guī)則選擇一定比例的個(gè)體，再通過(guò)精英策略選擇最佳個(gè)體復(fù)制到下一代。

⑤交叉。交叉操作隨機(jī)選擇染色體中的父代染色體的兩段基因片段，然后將兩個(gè)基因片段進(jìn)行交叉互換，生成兩個(gè)子代染色體。

⑥變異。在任務(wù)總數(shù)范圍內(nèi)，隨機(jī)選擇一個(gè)基因位，并將該基因按照Pc進(jìn)行變異，將發(fā)生變異的基因位的值與其他AGV編號(hào)進(jìn)行替換。

⑦解碼。設(shè)置最大迭代次數(shù)，當(dāng)達(dá)到最大迭代時(shí)，終止迭代，輸出最初結(jié)果。

圖4 混合蟻群遺傳算法流程

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

假設(shè)仿真實(shí)驗(yàn)在50×50m配送中心中進(jìn)行，用柵格法進(jìn)行建模。配送中心中有3臺(tái)AGV，從初始位置出發(fā)，速度v為1 m/s。參數(shù)設(shè)置為α=1,β=4,Pm=0.1，Pc=0.6，最大迭代次數(shù)=100。當(dāng)一批訂單需求到達(dá)后，按照貨架相似度進(jìn)行分批并確定貨架的位置，分批后貨架序號(hào)和貨架位置見(jiàn)表1。

表1 訂單分批后的貨架序號(hào)及位置

通過(guò)上述參數(shù)對(duì)混合蟻群遺傳算法和遺傳算法的收斂速度和尋優(yōu)能力進(jìn)行仿真并進(jìn)行算法操作，如圖5所示。

圖5 小任務(wù)量下兩種算法的迭代圖

由圖5可知，兩種算法的求解過(guò)程中最優(yōu)值隨迭代次數(shù)不斷變化，與標(biāo)準(zhǔn)遺傳算法相比，混合蟻群遺傳算法迭代最小化目標(biāo)函數(shù)值快速下降，證明了混合蟻群遺傳算法具有更高的求解效率。由于混合蟻群遺傳算法在迭代開(kāi)始時(shí)就有較為優(yōu)秀的種群,因而在迭代過(guò)程中可以快速跳出局部最優(yōu),收斂性比較強(qiáng)。

遺傳算法求解3臺(tái)AGV的任務(wù)分配結(jié)果見(jiàn)表2，仿真結(jié)果如圖6所示；混合蟻群遺傳算法的分配結(jié)果見(jiàn)表3，仿真結(jié)果如圖7所示。

圖6 遺傳算法仿真結(jié)果

表3 混合蟻群遺傳算法任務(wù)分配結(jié)果

圖7 混合蟻群遺傳算法仿真結(jié)果

由表2和表3可知， 在混合蟻群遺傳算法下的所有AGV總行駛距離為1637m，在遺傳算法下所有AGV總行駛距離為1756m。

由表4可知，相較于傳統(tǒng)的遺傳算法，本混合蟻群遺傳的算法的減少行駛距離比例達(dá)到 6.7%，且在仿真范圍內(nèi)能更大程度縮短 AGV總行駛距離，得到更加理想的全局最優(yōu)解。

表4 兩種算法下任務(wù)分配效益表

通過(guò)改變 AGV 數(shù)目對(duì)混合算法尋優(yōu)能力做進(jìn)一步驗(yàn)證。本文設(shè)置任務(wù)數(shù)量為200，AGV數(shù)量分別為8、12、16、20、24、28，終止迭代次數(shù)為1000 次，使得各算法中個(gè)體充分迭代，迭代結(jié)果如圖8所示。

圖8 不同AGV任務(wù)完成總行駛距離

由圖8可知，在不同AGV數(shù)量下，AGV 總行駛距離呈現(xiàn)波動(dòng)狀態(tài)，當(dāng)AGV數(shù)量過(guò)少時(shí)，AGV分配任務(wù)較多且負(fù)載較大，總行駛距離增大，這是因?yàn)閷?duì)任務(wù)執(zhí)行順序進(jìn)行分配時(shí)可能會(huì)減少行駛距離，但會(huì)增加 AGV從初始位置前往貨架的移動(dòng)距離以及返回初始位置的距離。當(dāng)AGV數(shù)量過(guò)多時(shí),AGV在搬運(yùn)過(guò)程中會(huì)造成不同程度的擁擠并且導(dǎo)致每個(gè)AGV分配的任務(wù)數(shù)過(guò)少,造成資源浪費(fèi)。

4 總結(jié)

在“貨到人”揀選系統(tǒng)中，配送中心的揀選效率是關(guān)鍵問(wèn)題。本文在考慮訂單分批前提下，從AGV任務(wù)分配角度進(jìn)行優(yōu)化，建立最小化AGV總行駛距離的數(shù)學(xué)模型，并設(shè)計(jì)了混合蟻群遺傳算法優(yōu)化AGV搬運(yùn)貨架的順序?？紤]到遺傳算法局部搜索能力不足的問(wèn)題，引入帶懲罰機(jī)制的動(dòng)態(tài)信息素更新的蟻群算法的最優(yōu)解作為遺傳算法的初始種群來(lái)提高算法性能。仿真實(shí)驗(yàn)表明，混合蟻群遺傳算法能有效提升算法的尋優(yōu)能力，不會(huì)陷入局部最優(yōu)的快速下降陷阱，能更好地解決多AGV任務(wù)分配問(wèn)題。