□ 梅 前,董寶力

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

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

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

1.2 模型建立

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

圖2 配送中心建模

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

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

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

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

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

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

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

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

(g)針對同一批次訂單，每個貨架只能被AGV 搬運一次。

參數(shù)如下：

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

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

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

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

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

⑥Xkp為決策變量，表示第k臺AGV是否執(zhí)行第p個搬運貨架任務(wù)。當(dāng)Xkp=1，則由第k臺AGV執(zhí)行第p個貨架搬運任務(wù)，當(dāng)Xkp=0，則第k臺AGV不執(zhí)行p貨架搬運任務(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完成搬運任務(wù)的總距離；式(2)表示第k臺AGV執(zhí)行q任務(wù)到達(dá)貨架i的距離；式(3)表示AGV搬運貨架前往分揀站臺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)表示一個搬運貨架任務(wù)只能由一個AGV執(zhí)行；式(6)和(7)表示一個AGV一次只能執(zhí)行一個任務(wù)。

2 混合蟻群遺傳算法

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

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

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

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

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

(8)

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

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

(9)

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

2.2 遺傳算法階段

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

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

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

圖3 染色體編碼方式

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

(10)

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

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

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

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

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

3 實例驗證

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

表1 訂單分批后的貨架序號及位置

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

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

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

遺傳算法求解3臺AGV的任務(wù)分配結(jié)果見表2，仿真結(jié)果如圖6所示；混合蟻群遺傳算法的分配結(jié)果見表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ù)分配效益表

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

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

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

4 總結(jié)

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