蔡帛良 魏長赟 張鵬鵬

（河海大學機電工程學院 常州 213022）

1 引言

貨物分揀與運輸是智能倉儲系統(tǒng)的重要環(huán)節(jié)，是未來社會物聯(lián)網系統(tǒng)的重要組成部分。對于未來智能倉儲系統(tǒng)，多機器人系統(tǒng)能夠通過協(xié)作，有效提高貨物分揀效率，降低包裹搬運時間。但是，多機器人系統(tǒng)在同一空間工作，容易產生任務干涉和沖突，從而導致死鎖等難題。因此，需要研究智能倉儲系統(tǒng)中多機器人的任務分配及調度問題。

多機器人系統(tǒng)在智能倉儲系統(tǒng)中的任務可以描述為服務器接收訂單信息，根據訂單信息生成貨物坐標圖，并通過算法為每個機器人分配任務及取貨順序，多個機器人從起點出發(fā)，按照系統(tǒng)分配取貨順序依次取貨并返回終點提交貨物。通?？梢詫⒋祟惾蝿辙D化為Multi-TSP（Multi-Traveling-salesman-problem）問題。

但由于現(xiàn)代多機器人系統(tǒng)任務分配算法都是以求解最小路程為總目標，這導致每個機器人的任務分配不均衡，最終導致分揀時發(fā)生有某幾個機器人長時間等待一個機器人返回的情況，實際分揀效率低下。針對此問題，本文提出以均衡各機器人路徑和最小總體路徑為目的的多目標Multi-TSP問題，即在解空間中尋找符合Pareto支配條件的解的問題，但該問題由于該類問題求解空間大，求解復雜，被歸類為NP-hard問題［1］。

圖1 多機器人的智能倉儲分揀系統(tǒng)

通常用于求解NP問題的啟發(fā)式算法有粒子群算法（PSO）、蟻群算法（ACO）、禁忌搜索算法（TS）、退火算法（SAA）和遺傳算法（GA），但由于多目標優(yōu)化問題在復雜問題下解空間龐大，以及傳統(tǒng)優(yōu)化算法的自身局限，使得各類優(yōu)化算法均很難獲得Pareto解，近年來，基于遺傳算法的多目標進化算法（MOEA）逐漸成為解決多目標優(yōu)化問題的重要方式［2］。

2 多機器人的任務分配模型

針對上述多目標Multi-TSP問題，可以歸納為：對于給定階為N的圖G={V，E}，安排m個機器人對節(jié)點集V進行遍歷，使得除出發(fā)點vn∈V以外的所有節(jié)點均有且僅有一個機器人通過，且路徑之和最小，各機器人路徑方差最小。

綜上所述，對于此多目標Multi-TSP問題，有如下優(yōu)化目標：

式中：S為所有機器人路徑總長度；Si為第i個機器人的路徑總長度；Savg為各機器人長度均值。

其中Si是根據機器人i的路徑Pi={Ui，Ei}并按照圖G的鄰接矩陣D（G）計算的路徑序列節(jié)點距離之和，即

且對Multi-TSP問題有：

所有機器人必須從指定起點出發(fā)，且對其他所有節(jié)點嚴格訪問一次后返回起點vn。即對于除出發(fā)點以外的點集U=V{vn}，有

且每組有效解必須包含m條平凡子路徑，即

上述各式中式（1）為本算法的優(yōu)化目標，式（2）～（4）構成了該問題的約束條件。

3 基于非支配排序的多目標遺傳算法

遺傳算法（Genetic Algorithm，GA）是模擬進化論中種群進化過程的計算模型，通過特定方式編碼種群個體的基因序列，并利用適應適應函數(shù)計算個體適應度，通過篩選種群獲得父代個體，產生下一代，并逐代向Pareto解靠近［2］。GA算法自20世紀60年代被提出到現(xiàn)在，被廣泛用于各類NP問題的求解中，引入了諸多附加機制以保證算法計算速度及收斂性，例如退火機制，精英策略等，已經在許多組合優(yōu)化問題上獲得顯著成果，Kim等提出了SPEA2+算法［3］，采用線性空間網格劃分的方法來維持子代種群的多樣性，以避免陷入局部最優(yōu)解；Deb等提出引入精英策略的NSGA-II算法［4］，通過改進的快速非支配排序算法和精英策略用來篩選較優(yōu)個體并保持種群多樣性，避免種群早熟的同時，保證種群快速收斂。

利用遺傳算法求解問題，需要對個體基因進行編碼，采用斷點標記法對基因進行編碼。步驟如下：

1）將集合V中的非起始點標記為1，2，…n-1，將起始點標記為n，并添加m-2個斷點并將其編號為n+1，n+2…n+m-2；

2）將斷點n+1，n+2…n+m-2與1，2，…n組合為基因序列，并在計算S時候將編號為n+1…n+m-2的節(jié)點指向起點O，從而將問題轉化為TSP問題進行求解；

3）為防止n+1…n+m-2前后相連，保證每條機器人路徑均為平凡子路徑，在G的鄰接矩陣D中應有dnn=∞，以保證進化過程中斷點相連的個體被淘汰。

通過GA算法求解單目標Multi-TSP問題可以得到較優(yōu)解，但在多目標Multi-TSP問題中，不同的適應度函數(shù)與子代的篩選策略對算法的收斂性具有較大影響。

3.1 帶有精英庫的種群重啟策略

針對遺傳算法無法避免陷入局部最優(yōu)值的缺點，本文提出了一種帶有精英庫的種群重啟策略，即對于每次計算，在種群達到收斂條件時，重新初始化種群，并將達到收斂條件的優(yōu)質解個體納入精英庫，達到使用精英庫進行進化的條件時，將精英庫作為新的種群繼續(xù)迭代，從而提高算法收斂到Pareto解的概率。其基本流程圖如圖2所示。

圖2 帶有精英庫的種群重啟策略下的遺傳算法流程圖

3.2 基于快速非支配排序子代選擇方法

基于快速非支配排序（Fastnon-Demined Sort）策略和精英策略的遺傳算法（NSGA-II）［1］是 由Kalyanmoy Deb針對多目標優(yōu)化問題提出的優(yōu)化算法，與傳統(tǒng)的單目標模型按照得分篩選優(yōu)質個體不同，NSGA-II對多目標優(yōu)化問題中的每個優(yōu)化特征進行綜合考察，引入了支配排序和擁擠度計算的概念，通過非支配排序策略獲得較優(yōu)個體，利用擁擠度策略保證種群多樣性，并將父代中的較優(yōu)個體直接引入子代，避免了種群較優(yōu)解的丟失，從而增加種群收斂到Pareto解的概率。

3.3 快速非支配排序算法的支配賦級策略

非支配排序是來對具有多個目標參量個體進行排序的策略，在NSGA-II中，每個個體都具有被支配集合Ni和支配解集合Si，其中Ni表示當前種群中支配個體i的個體集合，Si表示被個體i支配的個體集合。

算法1 支配賦級算法

3.4 快速非支配排序算法的擁擠度計算策略

為保正非支配排序策略選擇的父代種群具有多樣性，避免將種群中的優(yōu)化分量相近的個體納入父代，提高種群早熟并陷入局部Pareto解的概率，Kalyanmoy Deb提出了同支配等級間個體的擁擠度排序策略。其中個體i的擁擠度Ci被定義為距離個體i最近的兩個個體j，k的特征矢量(f1，f2)的差之和，即

其基本算法如下：

算法2 擁擠度排序算法

NSGA-II算法選取子代個體主要優(yōu)先通過支配序，同等支配序下優(yōu)先選擇擁擠度小的個體。

4 算法測試

4.1 算例描述

本文采用TSPLIB數(shù)據集的eil類（eil51）和Kro類（Kro_100、Kro_150、Kro_A200）作為測試數(shù)據集，分別在不同容量的數(shù)據集上進行不同機器人數(shù)目的橫向對比，并測試傳統(tǒng)Multi-TSP任務分配算法、將多目標優(yōu)化參量整合后的Multi-TSP算法（SFO）和本文所述非支配排序的多目標任務分配算法，并以最長距離和平均距離之差與總路徑的比值為評價標準進行評判。

4.2 計算結果

由于優(yōu)化目的為最小化多機器人系統(tǒng)總路程并減少多機器人系統(tǒng)的距離方差，選擇機器人各組最長距離和最大路徑偏差占比作為評判標準，以此作為衡量該算法對任務分配均衡性能和最長執(zhí)行時間的標準。

采用Python 3.6.5進行編程，在CPU為3.5GHz，內存為6GB的臺式機上進行測試，測試結果如圖3所示。

圖3 100節(jié)點下不同機器人最大子路徑

圖4 150節(jié)點下不同機器人最大子路徑

圖5 200節(jié)點下不同機器人最大子路徑

由圖2、圖3、圖4可知，隨著參與運輸機器人數(shù)目的增加，可以有效降低各運輸機器人運輸路徑長度，從而降低運輸時間，并有效減少各機器人的任務負載。

表3 各機器人最大路徑偏差占百分比

由表3統(tǒng)計結果，各機器人最大路徑和平均路徑的差值均小于平均路徑的2%，從而保證運動路徑較小機器人因為運動路徑較大的機器人工作時間過長而出現(xiàn)閑置的概率較低。

得到種群的計算收斂圖如下，從圖中可知種群共進行了5次重啟，并在最后的精英庫重啟中（680代后）獲得了新的最優(yōu)值。

圖6 每代最優(yōu)個體得分曲線

圖7 全局最優(yōu)解分數(shù)變化曲線

4.3 對比分析

為證明該任務分配算法的均衡性，本節(jié)采用eil51數(shù)據集，與傳統(tǒng)單目標Multi-TSP算法和SFO算法進行比較，并分別以平均路徑，總路程和最大子路徑為評價標準。

從上述各圖中可知，隨著機器人數(shù)目的增加，機器人組的總路徑長度增大，平均路徑均下降，但傳統(tǒng)Multi-TSP算法的最大路程時間遠高于本文提出的任務分配算法，而SFO算法的總路徑遠高于前兩者，最大子路徑和平均路徑數(shù)值性能劣于本文提出的改進的NSGA-II算法。

圖8 總路徑長度

圖9 平均路徑長度

圖10 最大子路徑

圖11 三種算法的目標特征散點圖

從圖11可以看出，SFO算法的劣勢在于在實際計算過程中，采用了犧牲路徑總長度，以獲取最小方差的算法，這導致了總路程過大。

表4 三種算法最大子路徑偏差

從表4可知，傳統(tǒng)Multi-TSP的計算結果中，最大子路徑偏（即最大子路徑和平均路徑之差）差明顯高于機器人平均路徑，這導致機器人組的工作負載極不平衡和效率低下，而SFO算法下機器人的路徑偏差極小，但這是通過提高較短路徑距離而實現(xiàn)的，從圖7可知，SFO算法的總路徑長度遠高于傳統(tǒng)Multi-TSP和NSGA-II算法，這導致了實際路徑的增大。而基于快速非支配排序的進化算法則可以平衡計算結果，保證機器人組負載平衡，保證智能倉儲物流系統(tǒng)的高效運行。

同時獲得了在eil51下的實驗結果的對比圖。

圖13 NormalMTSPwith 4 robots

圖14 NormalMTSPwith 6 robots

圖15 Improved NSGA-IIwith 2 robots

圖16 Improved NSGA-IIwith 4 robots

圖17 Improved NSGA-IIwith 6 robots

從上述各圖可以看出，較常規(guī)Multi-TSP問題，本文提出的改進的NSGA-II算法為多機器人系統(tǒng)提供有效的任務劃分，降低多機器人任務干涉和沖突的概率。

5 結語

基于快速非支配排序的多目標優(yōu)化遺傳算法較傳統(tǒng)Multi-tsp算法具有機器人利用率高，最大運行時間短的特點，可以提高智能倉儲系統(tǒng)的實際工作效率，本文為多目標智能倉儲機器人的路徑規(guī)劃構建對應的優(yōu)化目標函數(shù)組，并結合非支配排序算法和精英策略以及種群重啟和精英庫策略設計了遺傳算法。實驗結果表明，上述算法路徑尋優(yōu)性能，路徑均衡性能均優(yōu)于傳統(tǒng)Multi-TSP算法。

從本文研究結果可知，在遺傳算法中，種群達到早熟后，重置種群可以使種群繼續(xù)保持尋優(yōu)特性，并具有較大的概率獲得Pareto解，同時存儲歷代收斂種群的精英個體進行優(yōu)化可以更好地獲得Pareto解。

本文對多優(yōu)化目標的多機器人靜態(tài)任務分配問題進行了研究，但未對實際路徑網絡時變性問題進行研究，這是實際生產生活中更為常見的問題，因此需要針對這類問題進行進一步研究。