基于混合遺傳禁忌搜索算法的多機(jī)器人任務(wù)分配

周 航，秦實宏，方?jīng)茇?/p>

（武漢工程大學(xué) 電氣信息學(xué)院，武漢 430205）

伴隨著電子商務(wù)在最近幾年的迅猛發(fā)展，以適應(yīng)倉儲物流行業(yè)發(fā)展的需要，建設(shè)更加智能化的自動化倉儲系統(tǒng)已經(jīng)成為當(dāng)前研究熱點(diǎn)。其中，以AGV（automated guided vehicle）為代表的智能搬運(yùn)機(jī)器人是自動化倉儲系統(tǒng)的關(guān)鍵組成部分，在降低物流成本、降低工人勞動強(qiáng)度、提高物流效率等方面起到了舉足輕重的作用。現(xiàn)代倉儲系統(tǒng)已經(jīng)逐步過渡到“貨到人”的運(yùn)作模式[1]，對于分揀效率、分揀精度等方面也都有較高的要求，而多機(jī)器人的任務(wù)分配是關(guān)系到倉儲運(yùn)作效率的核心問題。

目前，國內(nèi)外很多學(xué)者都采用不同算法對任務(wù)分配問題進(jìn)行了研究。文獻(xiàn)[2]引入局部最優(yōu)變異算子和融合改進(jìn)的模擬退火算法對蟻群算法進(jìn)行改進(jìn)，解決了多機(jī)器人的任務(wù)分配問題。文獻(xiàn)[3]采用時間窗法構(gòu)造了一個多AGV 調(diào)度系統(tǒng)，該系統(tǒng)能夠有效地解決AGV 之間的沖突和死鎖問題，具有較好的實時性和穩(wěn)定性。文獻(xiàn)[4]針對多AGV 的貨架任務(wù)分配問題，提出一種混合蟻群遺傳算法，該算法對遺傳算法的局部搜索能力有很好的改善作用。文獻(xiàn)[5]提出了在復(fù)雜環(huán)境下進(jìn)行多機(jī)器人任務(wù)指派時，將產(chǎn)生維度災(zāi)難，針對強(qiáng)化學(xué)習(xí)中災(zāi)難問題，提出了基于啟發(fā)式的深度Q 學(xué)習(xí)算法。文獻(xiàn)[6]提出了一種結(jié)合遺傳算法和滾動調(diào)度的多機(jī)器人任務(wù)分配算法，以解決大規(guī)模的包含任務(wù)優(yōu)先級約束的多機(jī)器人任務(wù)分配問題。文獻(xiàn)[7]在考慮多種倉儲作業(yè)模式的基礎(chǔ)上，提出一種改進(jìn)的多種群遺傳算法來求解總作業(yè)時間最小的多AGV 任務(wù)分配模型。

基于以上研究內(nèi)容，本文針對倉儲多機(jī)器人任務(wù)分配問題，提出了一種混合遺傳禁忌搜索算法。該算法利用禁忌搜索算法中的禁忌表和藐視準(zhǔn)則對遺傳算法每次迭代后的種群進(jìn)行優(yōu)化調(diào)整，既保留了遺傳算法強(qiáng)大的全局搜索能力，又加快了收斂速度，還避免其易陷入局部最優(yōu)的問題[8]。

1 問題描述與模型建立

1.1 問題描述

機(jī)器人任務(wù)分配是指將區(qū)域內(nèi)的任務(wù)點(diǎn)無重復(fù)地分配給各個機(jī)器人，并使機(jī)器人在滿足目標(biāo)約束的前提下達(dá)到最優(yōu)結(jié)果。本文以倉儲機(jī)器人為研究對象，以機(jī)器人配送成本最小為目標(biāo)建立數(shù)學(xué)模型，該模型可以轉(zhuǎn)化成VRP 模型進(jìn)行求解。假定倉儲環(huán)境是一個二維的空間，用柵格法建立環(huán)境模型，所述環(huán)境包括分揀臺、貨架、空載機(jī)器人、載貨機(jī)器人和充電樁。初始狀態(tài)時，機(jī)器人位于充電樁位置，可以接收任務(wù)訂單。一旦接收到任務(wù)，機(jī)器人會移動至對應(yīng)貨架位置，以及按指定的次序把貨物搬到分揀臺。機(jī)器人在電量不足或者完成全部工作時，機(jī)器人會重新回到充電樁。自動化倉儲模型如圖1所示。

圖1 自動化倉儲模型Fig.1 Automated warehousing model

為了方便對模型進(jìn)行求解，本文針對機(jī)器人在倉儲環(huán)境的任務(wù)調(diào)度過程做出以下假設(shè)：①起始點(diǎn)有多個，每臺機(jī)器人從起始點(diǎn)出發(fā)，完成任務(wù)后返回起始點(diǎn)；②針對同批任務(wù)，每項任務(wù)只允許被1臺機(jī)器人執(zhí)行；③機(jī)器人的行駛速度是固定的，暫不考慮沖突情況；④任務(wù)的數(shù)量要遠(yuǎn)大于機(jī)器人的數(shù)量。

1.2 數(shù)學(xué)模型的建立

則所有機(jī)器人的總行駛距離的數(shù)學(xué)表達(dá)式為

式中：Xki為決策變量，表示第i 臺機(jī)器人是否執(zhí)行第k 個搬運(yùn)任務(wù)。

式（5）表示所有配送任務(wù)將全部被分配，不存在某個任務(wù)不被執(zhí)行；式（6）表示1 個目標(biāo)點(diǎn)僅被1臺機(jī)器人配送；式（7）為任務(wù)載荷約束，表示每臺機(jī)器人可以執(zhí)行的任務(wù)數(shù)量，F(xiàn)i和ULi分別表示第i臺機(jī)器人的實際任務(wù)載荷和載荷上限；式（8）為電量約束，表示每臺機(jī)器人完成所有分配任務(wù)的剩余電量不能低于0，Ei為第i 臺機(jī)器人的電量情況為第i 臺機(jī)器人的單位距離電量消耗。

本文以機(jī)器人配送成本最小為目標(biāo)，目標(biāo)函數(shù)綜合考慮機(jī)器人的配送運(yùn)輸成本、電量消耗成本和罰函數(shù)部分：

式中：λi為第i 臺機(jī)器人單位距離運(yùn)輸成本；Pc為每臺機(jī)器人的單位電量消耗系數(shù)；α1和α2分別為機(jī)器人的配送運(yùn)輸成本和電量消耗成本的權(quán)重系數(shù)，并且α1+α2＝1；ω 為罰函數(shù)的權(quán)重系數(shù)；Pe為罰函數(shù)，罰函數(shù)的構(gòu)造思想是將有約束問題轉(zhuǎn)化為無約束問題[9]，數(shù)學(xué)表達(dá)式為

2 混合遺傳禁忌搜索算法

遺傳算法（genetic algorithm，GA）是一種模擬自然進(jìn)化過程的算法，該算法應(yīng)用廣泛，具備較強(qiáng)的全局擇優(yōu)能力，但也存在容易早熟、局部搜索能力較弱等缺點(diǎn)[10-11]。禁忌搜索算法（taboo search，TS）具有較好的局部搜索能力和記憶功能，但其搜索能力依賴于初始解的質(zhì)量[12]。本文基于這2 種算法的優(yōu)點(diǎn)，提出了混合遺傳禁忌搜索算法（GATS）來解決多機(jī)器人的任務(wù)分配問題。先用遺傳算法生成較優(yōu)初始解，然后將此解作為禁忌搜索算法初始種群迭代尋優(yōu)，這樣不僅保持遺傳算法全局尋優(yōu)能力，同時增強(qiáng)局部搜索能力。混合遺傳禁忌搜索算法流程如圖2 所示。

圖2 混合遺傳禁忌搜索算法流程Fig.2 Flow chart of hybrid genetic taboo search algorithm

2.1 遺傳算法階段

（1）編碼。文中采用實數(shù)編碼生成染色體，實數(shù)代表的數(shù)值就是任務(wù)編號。首先初始化染色體的長度N，再按機(jī)器人的數(shù)量M，把染色體分段，每臺機(jī)器人都對應(yīng)1 條染色體片段，再在相應(yīng)染色體片段最前端和最末端加設(shè)起點(diǎn)位置，染色體片段中含有機(jī)器人起點(diǎn)、待接入任務(wù)點(diǎn)和執(zhí)行順序，如圖3所示。

圖3 染色體編碼方式Fig.3 Chromosome encoding method

（2）產(chǎn)生初始種群。初始化種群，設(shè)定遺傳算法中各初始參數(shù)，如種群規(guī)模、最大迭代次數(shù)、交叉與變異概率。

（3）計算適應(yīng)值。取染色體中所有機(jī)器人完成全部任務(wù)的總成本的倒數(shù)作為適應(yīng)度值，適應(yīng)度函數(shù)定義為

（4）選擇操作。首先按照輪盤賭規(guī)則篩選出一定份額的個體，然后用精英策略為后續(xù)種群進(jìn)化挑選適應(yīng)度值較高的個體。

（5）交叉操作。首先在染色體長度上隨機(jī)選擇2個數(shù)，使2 個數(shù)間染色體片段各自向另一染色體最前端遷移，再按順序遍歷2 條染色體，去掉重復(fù)基因，從而獲得經(jīng)過交叉的1 條新個體。

（6）變異操作。在染色體中隨機(jī)抽取2 個位置基因，再在2 個基因間調(diào)換各基因位置次序，組成1個新個體。

2.2 禁忌搜索算法階段

為加強(qiáng)遺傳算法局部搜索能力，本文把禁忌搜索算法融合在遺傳算法變異操作之后，通過引入禁忌表來避免反復(fù)迂回搜索，從而實現(xiàn)全局優(yōu)化。主要步驟如下：

（1）獲取初始解及初始化參數(shù)，選取經(jīng)過遺傳算法變異階段的新種群，以適應(yīng)度值最大的個體為禁忌搜索算法初始解，初始化禁忌表并設(shè)置禁忌長度參數(shù)；

（2）判斷是否符合終止條件，如果符合條件則輸出最優(yōu)解并終止搜索，否則繼續(xù)循環(huán)；

（3）根據(jù)當(dāng)前解的領(lǐng)域映射模式，產(chǎn)生多個鄰域解，并從中選出多個候選解，并計算各個候選解的適應(yīng)值，保留較優(yōu)的候選解進(jìn)行后續(xù)判斷；

（4）判斷候選解是否符合藐視準(zhǔn)則，若符合，則將其解禁出來，并作為當(dāng)前最優(yōu)解，同時將該解放入禁忌表，并更新禁忌表狀態(tài)；若不符合，則篩選出候選解中未被禁忌的最優(yōu)解為當(dāng)前最優(yōu)解，并更新禁忌表狀態(tài)；

（5）當(dāng)滿足終止準(zhǔn)則時，則停止搜索，輸出最優(yōu)解。

禁忌搜索算法流程如圖4 所示。

圖4 禁忌搜索算法流程Fig.4 Flow chart of taboo search algorithm

3 仿真結(jié)果與分析

為驗證所提算法的性能，本文在Windows10 操作系統(tǒng)上，使用Matlab2021b 軟件對改進(jìn)前后的算法進(jìn)行仿真。假設(shè)仿真實驗在100 m×100 m 的倉儲環(huán)境中進(jìn)行，用柵格法進(jìn)行建模。倉儲中有3 臺機(jī)器人，30 個待分配任務(wù)，機(jī)器人的起始點(diǎn)互不相同，速度v 為1 m/s，每個機(jī)器人的任務(wù)載荷上限UL 為10。參數(shù)設(shè)置為Pc=0.5，權(quán)重系數(shù)α1＝0.6，α2＝0.4，ω＝100。將算法的種群規(guī)模定為100，迭代次數(shù)為500 次，交叉概率為0.9，變異概率為0.1。機(jī)器人部分性能參數(shù)如表1 所示。

表1 機(jī)器人性能參數(shù)Tab.1 Robot performance parameters

通過上述參數(shù)對GATS、GA 和TS 算法的收斂速度和尋優(yōu)能力進(jìn)行仿真，如圖5 所示。從圖中可以看出，相比GA 和TS 算法，GATS 算法的目標(biāo)函數(shù)值更低，表明GATS 算法在迭代過程中有利于跳出局部最優(yōu)解，且其收斂速度也比GA 算法更快，驗證了GATS 算法的有效性。

圖5 三種算法的迭代圖Fig.5 Iterative diagram of three algorithms

基于GATS 算法的多機(jī)器人任務(wù)分配仿真結(jié)果如圖6 所示，任務(wù)分配優(yōu)化結(jié)果如表2 所示，每個機(jī)器人都執(zhí)行10 個任務(wù)，符合任務(wù)載荷約束條件。

表2 任務(wù)分配優(yōu)化結(jié)果Tab.2 Optimization results of task allocation

圖6 多機(jī)器人任務(wù)分配優(yōu)化結(jié)果Fig.6 Optimization results of multi-robot task assignment

為了進(jìn)一步驗證混合算法的尋優(yōu)能力，本文設(shè)置機(jī)器人的數(shù)目分別為M=5，7，10，15，200，任務(wù)數(shù)量分別為N=50，70，100，150，200，終止迭代次數(shù)為2000 次，比較GATS、GA 和TS 算法的最優(yōu)解。通過將每個實例在相同環(huán)境下分別運(yùn)行10 次，記錄10次運(yùn)行結(jié)果中的平均值。表3 所示為各算法運(yùn)行結(jié)果，從表3 中可以看出，本文所提算法的優(yōu)化結(jié)果更接近最優(yōu)解。

表3 不同算法優(yōu)化結(jié)果對比Tab.3 Comparison of optimization results by different algorithms

4 結(jié)語

本文為解決倉儲多機(jī)器人任務(wù)分配問題，首先建立一種多機(jī)器人任務(wù)分配模型；然后針對遺傳算法易陷入局部最優(yōu)且收斂速度較慢的問題，提出了一種混合遺傳禁忌搜索算法；最后采用GATS 算法對不同規(guī)模的任務(wù)分配問題進(jìn)行了仿真實驗，并將其與GA 和TS 算法進(jìn)行對比。仿真結(jié)果表明，混合遺傳禁忌搜索算法能更好地解決多機(jī)器人任務(wù)分配問題。