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

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

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

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

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

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

1.1 問(wèn)題描述

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

圖1 自動(dòng)化倉(cāng)儲(chǔ)模型Fig.1 Automated warehousing model

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

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

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

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

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

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

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

2 混合遺傳禁忌搜索算法

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

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

2.1 遺傳算法階段

（1）編碼。文中采用實(shí)數(shù)編碼生成染色體，實(shí)數(shù)代表的數(shù)值就是任務(wù)編號(hào)。首先初始化染色體的長(zhǎng)度N，再按機(jī)器人的數(shù)量M，把染色體分段，每臺(tái)機(jī)器人都對(duì)應(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）計(jì)算適應(yīng)值。取染色體中所有機(jī)器人完成全部任務(wù)的總成本的倒數(shù)作為適應(yīng)度值，適應(yīng)度函數(shù)定義為

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

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

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

2.2 禁忌搜索算法階段

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

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

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

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

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

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

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

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

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

為驗(yàn)證所提算法的性能，本文在Windows10 操作系統(tǒng)上，使用Matlab2021b 軟件對(duì)改進(jìn)前后的算法進(jìn)行仿真。假設(shè)仿真實(shí)驗(yàn)在100 m×100 m 的倉(cāng)儲(chǔ)環(huán)境中進(jìn)行，用柵格法進(jìn)行建模。倉(cāng)儲(chǔ)中有3 臺(tái)機(jī)器人，30 個(gè)待分配任務(wù)，機(jī)器人的起始點(diǎn)互不相同，速度v 為1 m/s，每個(gè)機(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

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

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

基于GATS 算法的多機(jī)器人任務(wù)分配仿真結(jié)果如圖6 所示，任務(wù)分配優(yōu)化結(jié)果如表2 所示，每個(gè)機(jī)器人都執(zhí)行10 個(gè)任務(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à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)解。通過(guò)將每個(gè)實(shí)例在相同環(huán)境下分別運(yùn)行10 次，記錄10次運(yùn)行結(jié)果中的平均值。表3 所示為各算法運(yùn)行結(jié)果，從表3 中可以看出，本文所提算法的優(yōu)化結(jié)果更接近最優(yōu)解。

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

4 結(jié)語(yǔ)

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