基于改進NSGA?Ⅱ算法的多AGV多任務分配研究

摘" 要： 針對自動倉儲系統中多AGV的批量任務分配問題，以總任務等待時間、AGV負載均衡指數、總AGV能耗為目標，以AGV和任務的匹配關系為決策變量構建多目標優化數學模型，加入電量約束條件。為克服傳統NSGA?Ⅱ算法存在的收斂速度慢、種群多樣性維護差等不足，提出三種改進策略：改進交叉和變異算子，采用順序交叉算子、逆序和單點相結合的混合變異算子；改進擁擠度計算公式，提出非線性平均絕對差的擁擠度計算方法；提出從局部和全局雙角度調整的動態參數自適應調整策略。最后，設計多AGV多任務分配的仿真實驗。實驗結果表明：改進的NSGA?Ⅱ算法有效解決了多AGV多任務分配問題，同時，所提出的改進策略有效提高了算法的收斂速度、穩定性和魯棒性。

關鍵詞： 自動倉儲系統； 多AGV； 任務分配； 多目標優化； 電量約束； 動態參數； NSGA?Ⅱ算法

中圖分類號： TN911?34； TP242""""""""""""""""""" 文獻標識碼： A"""""""""""""""nbsp;"""" 文章編號： 1004?373X（2024）09?0157?07

0" 引" 言

隨著生產規模的擴大和柔性制造系統的發展，多AGV（Automated Guided Vehicle）以其靈活性、容錯性和可擴展性強的顯著優勢成為新的發展趨勢，與之匹配的多AGV調度系統也得到了迅速發展。多AGV調度系統的五大核心任務有任務分配、車輛定位、路徑規劃、運動規劃、車輛管理[1]。其中，任務分配作為最基礎的任務之一，得到了國內外學者的廣泛研究。

文獻[2]以最大完工時間最小化為目標建立了混合整數規劃模型，提出一種基于文化算法的改進遺傳算法求解模型。文獻[3]進一步考慮了周期任務的分配策略。文獻[4]重點研究了異構多AGV的任務分配問題，目標是最小化完工時間。文獻[5]提出一種基于任務綁定策略和改進粒子群算法的混合任務分配方法。上述研究集中在靜態任務分配問題上。文獻[6]針對離散車間中的實時動態任務分配，考慮AGV工作速率和運行成本因素建立模型，并用改進的注水算法進行了求解。文獻[7]考慮多載的特點，針對自動化集裝箱碼頭中的多AGV調度問題，考慮任務分配的時間成本和AGV數量建立模型，并用模擬退火算法進行求解。單目標優化考慮因素單一，難以貼合實際需求。文獻[8]考慮距離、時間等成本建立多目標優化數學模型，充分考慮了多負載和任務排序問題，并使用加權法轉換為單目標優化問題。文獻[9]同樣使用加權法實現了任務分配的協調優化。加權法具有一定的主觀性。文獻[10]以完工時間、AGV數量、懲罰成本為目標建立多目標優化模型，使用多目標遺傳?差分進化算法進行求解，取得了顯著效果。文獻[11]重點關注機器和AGV的集成調度問題，考慮最大完工時間、延期時間和設備負荷因素，建立了雙約束調度模型，然后使用NSGA?Ⅱ算法求解模型，得到了較優的帕累托解。文獻[12]建立了雙目標混合整數規劃模型，通過CPLEX和遺傳算法進行求解。分布式任務分配同樣得到了廣泛的研究，能夠實現高吞吐量任務分配[13]。

由前述分析可知，針對自動倉儲系統中多AGV多任務分配問題，現存研究主要集中在單目標優化問題上，多目標優化相關的研究較少，且優化目標或側面約束條件考慮尚不充分。本文引入電量約束，綜合考慮時間成本、負載均衡指數和能耗成本建立多目標優化數學模型。針對NSGA?Ⅱ算法在求解問題時的不足，提出了三種改進方法：采用順序交叉、逆序和單點相結合的混合變異操作；提出基于非線性平均絕對差距離的擁擠度計算方法；全局和局部雙角度調整的動態參數調整策略。最后，進行實例仿真實驗，對模型和算法進行驗證與分析。

1" 問題描述與模型建立

1.1" 環境建模

自動倉儲系統作為一種自動化、智能化的物流系統，具有貨物存儲、檢索、處理等核心功能，被廣泛應用于電子商務、制造業領域，大幅提高了運營操作效率。本文利用柵格法對自動倉儲環境進行地圖建模，將環境抽象成一個平面二維地圖，如圖1所示。將工位點、存儲點等重要節點抽象成50×50的柵格數據點，其坐標表示為[（x，y）]的形式。整個地圖被劃分成五個不同區域：存儲區、入庫區、出庫區、充電區、行駛區。

1.2" 問題描述

在自動倉儲系統中，任務分配問題描述為：在時刻[t]，系統生成一批任務集合[A={a1，a2，…，am}]，對于每個任務[aj（j=1，2，…，m）]都包含一個任務起始點[sj]=[（xsj，ysj）]和一個任務目標點[gj=（xgj，ygj）]，其中[x]為柵格點的橫坐標，[y]為柵格點的縱坐標。同時，系統有一批可用AGV集合[V={v1，v2，…，vn}]，對于每臺AGV [vi（i=1，2，…，n）]都包含AGV的起始點[vci=（xci，yci）]和電量[ei]信息。任務分配的目的是基于某種分配策略，將[m]個任務合理地分配給[n]臺AGV，保證所有任務被順利執行，并且滿足相關約束條件。任務分配結果[R]可表示為二維矩陣的形式，如式（1）所示：

[R=y11y12…y1ny21y22…y2n????ym1ym2…ymn] （1）

式中：[ymn]為0/1變量，任務[am]由AGV [vn]執行時，[ymn]為1，否則，[ymn]為0。

1.3" 條件假設及參數定義

為方便建模與分析，不失一般性地作如下假設：

1） AGV的裝載和卸載貨物時間為固定值；

2） AGV保持勻速行駛，不考慮負載和轉彎對速度的影響，但考慮負載對AGV能耗的影響；

3） 任務分配階段不考慮AGV調度的沖突問題；

4） AGV始終在無故障狀態下運行；

5） AGV為單負載，即同一時刻只執行一個任務，且每個任務僅由一臺AGV去執行，任務數量大于AGV數量。

模型參數及變量定義：[n]為AGV數量；[m]為任務數量；[tij]為AGV [vi]執行任務[aj]所需的時間；[tc]為AGV裝卸貨物時間；[di]為AGV [vi]的行駛路程；[dunloadij]為AGV [vi]執行任務[aj]的空載路程；[dloadij]為AGV [vi]執行任務[aj]的負載路程；[sj]=（[xsj]，[ysj]）為任務[aj]的起始點；[gj=（xjg，yjg）]為任務[aj]的目標點；[vci]=（[xci]，[yci]）為AGV [vi]的初始位置；[eij]為AGV [vi]執行任務[aj]所需要的電量；[eload]、[eunload]分別為AGV負載、空載時行駛單位路程的耗電量；[ei]為AGV [vi]的剩余電量；[eth]為AGV低電量閾值；[v]為AGV的運行速度；[pij]為0/1變量，AGV [vi]執行任務[aj]為1，否則為0。上述符號中，[i]的取值范圍為{[1≤i≤n，i∈Z]}，[j]的取值范圍為[{1≤j≤m， j∈Z}]。

1.4" 模型建立

1.4.1" 任務等待時間成本

在多AGV批量任務分配問題中，任務等待時間是指從任務發布到任務開始執行時的時間間隔。由于每臺AGV可能會被一次性分配多個任務，AGV會維護一個任務隊列，任務隊列的長度直接影響靠近隊列末尾的任務等待時間。總任務等待時間[f1]作為一個綜合指標，對系統任務執行效率和全局任務調度結果起著關鍵作用，其計算公式如下：

[min" T=j=1mk=1wtwaitk+tikv+2tc+dunloadijv] （2）

[tik=dunloadik+dloadikv] （3）

[dunloadij=xci-xsj-yci-ysj] （4）

[dloadik=xci-xsk-yci-ysk] （5）

式中：[T]為總任務等待時間；[w]為任務隊列位置序號；[twaitk]為第[k]個任務[ak]的任務等待時間，由任務所在任務隊列[Qi]的位置所決定。式中距離用哈曼頓距離來計算，如式（4）、式（5）所示。當[k]=1時，[vci]=（[xci]，[yci]），否則[vci]=（[xgk-1]，[ygk-1]）。AGV [vi]執行任務[aj]的完整過程可分為兩個有序過程：空載過程（當前位置至任務起始點）和負載過程（任務起始點至任務目標點）。空載和負載各需要一個單位的[tc]來完成裝載和卸載貨物。

1.4.2" AGV負載均衡指數

所有AGV構成一個整體的運輸系統，在任務分配過程中，如果一部分AGV長時間處于忙碌狀態，而另一部分處于空閑狀態，這將導致AGV工作負荷分布極不均勻。負載均衡[f2]旨在最大程度地均衡每臺AGV的工作負荷，變異系數克服了標準差和方差在數據分布不均勻時誤差較大、最大最小差對極值敏感的不足，能更好地反映數據的離散程度。其計算公式如下：

[min" cv=σE] （6）

[E=i=1nj=1m（dunloadij?eunload+dloadij?eload）n] （7）

[σ=i=1n（eij-E）n] （8）

[eij=j=1m（dunloadij+dloadij）] （9）

本文以每臺AGV的能耗作為工作負荷的度量標準。由式（6）～式（9）可知，變異系數cv的取值在[0，1]之間，其值越接近于0，說明每臺AGV的工作量越均衡。

1.4.3" AGV能耗成本

AGV主要依賴電池供電，且受到電量限制，目前大多數研究尚未充分考慮該約束。考慮能耗和電量約束的任務分配方法可減少AGV能耗，削減運營成本，促進低碳發展。AGV總能耗[f3]的計算公式如下：

[min" E=i=1nj=1m（dunloadij?eunload+dloadij?eload）] （10）

式中：[dunloadij]、[dloadij]的計算方法與[f1]相同。AGV的能耗可分為行駛能耗、加速和制動能耗、自然損耗等類型，其中行駛能耗為主要能耗，所以本文僅考慮行駛能耗。

綜上所述，決策變量及其取值如式（11）所示：

[pij=1，""" AGV vi執行任務aj0，""" 否則] （11）

滿足的約束條件如下：

[j=1mi=1npij=m] （12）

[i=1npij=1，""" ?j=1，2，…，m] （13）

[eth≤ei-k=1card（Qi）eik，"" ?Qi] （14）

[gk=sk+1，""" k=1，2，…，card（Qi）-1] （15）

上述約束中：式（12）保證所有任務都被分配完；式（13）保證每個任務只能由一臺AGV去執行；式（14）保證AGV [vi]的電量可用性；式（15）保證AGV [vi]按照任務隊列[Qi]依次執行任務，[card]（[Qi]）為任務隊列的任務數量。

2" NSGA?Ⅱ算法及其改進

由文獻[14]提出的基于支配關系的快速非支配遺傳算法（NSGA?Ⅱ）具有三大顯著優勢：基于支配關系的快速非支配排序、基于距離的擁擠度比較算子、父子代合并的精英策略。

2.1" 改進交叉與變異算子

本文中，任務分配數學模型的決策變量[pij]為離散的0/1變量，考慮使用整數編碼的形式來表達解。染色體的長度等于任務數量，每個基因位的值為AGV編號。假設存在20臺AGV任務和5臺AGV，染色體表達形式如圖2所示。例如第10個基因位的值為3，表示第10個任務由第3臺AGV執行。

針對該問題的特點，本文對傳統的交叉和變異操作進行改進。在交叉操作方面，由于AGV按照任務隊列的前后順序執行任務，將單點交叉改為順序交叉，以增加種群多樣性、保留優秀染色體的部分有序性，如圖3a）所示。在變異操作方面，由于AGV執行任務的順序對優化目標的值有一定影響，采用逆序變異和單點變異相結合的方式可有效改變染色體結構，增加種群的多樣性，如圖3b）所示。

2.2" 改進擁擠度計算方法

傳統的擁擠度計算是線性的，這種方法只考慮相鄰個體之間的距離，當解的分布非常不均勻時，難以反映解的密度差異，使種群的多樣性降低，還可能導致算法過早收斂。因此提出使用平均絕對差距離來計算擁擠度，以綜合考慮解的密度分布。擁擠度計算方法由式（16）變為式（17）：

[di=∞，""""""""""" i=1或i=card（front）1kl=1kfl（i-1）-fl（i+1）flmax-flmin，""" 否則] （16）

[di=∞，""""""""""" i=1或i=card（front）1kl=1k1Rw=1Rfl（i）-fl（w）fmaxl-fminl ，"" 否則] （17）

式中：[k]為目標函數的個數；front為帕累托層；[R]為該帕累托前沿中解的個數。

2.3" 自適應動態參數調整

傳統的靜態參數無法充分利用算法迭代的動態特性，缺乏靈活性。因此，提出從局部和全局雙角度進行調整的自適應動態參數策略。在NSGA?Ⅱ算法多目標優化問題中，前沿非支配個體的覆蓋率是描述種群質量的重要指標，如式（18）所示：

[Rg=card（front）N] （18）

依據該指標，動態調整交叉概率和變異概率，如式（19）、式（20）所示：

[pgc=（pg-1c+Δpc）?e-k1?gG，""" Rglt;Rg-1pg-1c，""" Rg=Rg-1（pg-1c-Δpc）?e-k1?gG，""" Rggt;Rg-1] （19）

[pgm=（pg-1m+Δpm）?e-k2?gG，""" Rglt;Rg-1pg-1m，""" Rg=Rg-1（pg-1m-Δpm）?e-k2?gG，""" Rggt;Rg-1] （20）

式中：[g]為當前迭代次數；[N]為種群大小；[pgc]為第[g]代的交叉概率；[pgm]為第[g]代的變異概率；[Δpc]為交叉概率的變化步長，[Δpm]為變異概率的變化步長，二者從局部角度進行參數的調整；[k1]為交叉概率動態變化的強度系數，[k2]為變異概率動態變化的強度系數，二者從全局角度進行參數的調整。同時，需要設置參數極值以防止參數越界。

改進的NSGA?Ⅱ算法的計算流程如圖4所示。

3" 仿真實驗

為驗證本文研究內容的有效性、魯棒性等性能，設計多AGV多任務分配問題的仿真實驗。設置參數：任務數量為50個，AGV數量為10臺，AGV初始電量為1 000個單位電量，[eunload]=1，[eload]=1.5，[eth]=100。考慮問題規模，設置NSGA?Ⅱ算法的參數為：種群規模[N]=200，最大迭代次數Gen=500，交叉概率[Pc]=0.9，變異概率[Pm]= 0.05，交叉概率變化步長[Δpc]=0.01，變異概率變化步長[Δpm]=0.005，交叉概率強度變化系數[k1]=0.5，變異概率強度變化系數[k2]=0.2，交叉概率極值為[0.5，1]，變異概率極值為[0.01，0.3]。

隨機初始化50個任務和10臺AGV初始位置，算法迭代完畢后，初始種群的分布和最終種群的分布如圖5a）所示，不同目標函數維度下的種群映射分布如圖5b）～圖5d）所示。

由圖5可分析出：首先，與初始種群相比，兩種算法在種群質量方面都有顯著提升。這體現在三個目標函數的值都明顯變小，且種群分布更加均勻。其次，相對于傳統NSGA?Ⅱ算法，改進的NSGA?Ⅱ算法在三個目標函數上表現更優，一方面體現在帕累托解的位置更具競爭力，另一方面體現在帕累托解的分布均勻性更佳，避免了斷層現象的出現。最后，總任務等待時間與負載均衡指數呈正比關系，因為較低的負載均衡指數表示任務分配更加均勻，因此任務等待時間更短；同時，負載均衡指數與總AGV能耗呈反比關系，因為當AGV執行完一個任務后，可就近執行另一個任務以節省能耗，但由于負載均衡的限制，另一個任務需由其他AGV去執行，最終導致能耗上升。這種關系凸顯出問題的復雜性和目標之間的互斥性。

非支配個體覆蓋率和函數目標值的收斂曲線如圖6所示。由圖6a）可知，改進的NSGA?Ⅱ算法的帕累托前沿覆蓋率最終穩定在1。然而，NSGA?Ⅱ算法最終穩定在約0.7，說明改進的NSGA?Ⅱ算法具有更快的收斂速度。此外，還可以看出，改進的NSGA?Ⅱ算法的覆蓋率波動整體較小，說明改進的NSGA?Ⅱ算法具有更好的穩定性。如圖6b）～圖6d）所示，與NSGA?Ⅱ算法相比，改進的NSGA?Ⅱ算法在總任務等待時間、負載均衡指數、總AGV能耗三個目標函數的平均值方面，相比于初始種群分別降低34.60%、78.83%、18.58%，而NSGA?Ⅱ算法分別降低23.30%、68.39%、7.68%。同時，改進的NSGA?Ⅱ算法的三個目標函數平均值分別在大約第120次、第100次、第110次迭代后趨于穩定，均低于NSGA?Ⅱ算法的相應數值，并且后者的穩定性較差。在三個目標函數的最小值方面，改進的NSGA?Ⅱ算法能更快探測到更低的值，說明其搜索能力更強、收斂性更好。

算法迭代完畢后，使用線性加權法從帕累托前沿中確定最優解，每個解的評估值由式（21）計算：

[Wi=j=1Kwj?eij] （21）

式中：[i=1，2，…，N]，[N]為解的個數；[j=1，2，…，K]，[K]為目標函數的個數；[eij]為第[i]個解的第[j]個目標函數的歸一化值，如式（22）所示：

[eij=fij-fminjfmaxj-fminj] （22）

本文中，結合場景需求，[f1]、[f2]、[f3]三個目標函數的權重分別設為[w1]=0.4、[w2]=0.2、[w3]=0.4。改進的NSGA?Ⅱ算法最終種群的評估值如圖7所示。

帕累托解集的最優評估值為0.648，其三個目標函數值分別為：1 301.89、0.04、3 299.11。

為評估算法的魯棒性，通過設置不同的任務規模進行壓力測試。在進行種群評估選擇最優解時，[fminj]=min{[fminj1]，[fminj2]}、[fmaxj]=max{[fmaxj1]，[fmaxj2]}，其中[fj1]和[fj2]分別為NSGA?Ⅱ算法和改進NSGA?Ⅱ算法的第[j]個目標函數。在每個任務規模下，最優個體的歸一化評估值如圖8所示。

由圖8可知，在每個任務規模下，改進的NSGA?Ⅱ算法的表現都優于傳統NSGA?Ⅱ算法，并且隨著任務規模的增加，即隨著問題規模的擴大，兩者的評估值之差逐漸增大，表明改進的NSGA?Ⅱ算法具有較強的魯棒性。

4" 結" 語

本文關注于多AGV多任務分配問題在自動倉儲系統中的優化問題。在通過柵格法建立環境模型的基礎上，考慮電量約束，以最小化總任務等待時間、AGV負載均衡指數、總AGV能耗為目標建立多目標優化數學模型，解決了現有研究中目標或側面約束考慮不全面的問題。為克服傳統NSGA?Ⅱ算法的不足，提出三種改進方法：采用順序交叉算子、逆序和單點相結合的混合變異算子，以增強種群的多樣性和均勻性；使用非線性平均絕對差距離來改進計算擁擠度方法，以提高擁擠度計算的科學性；為適應算法的動態特性，提出從局部和全局雙角度進行參數自適應調整的策略。最后基于上述研究內容，設計了多AGV多任務分配問題的實例仿真實驗和壓力測試實驗。實驗結果表明，改進的NSGA?Ⅱ算法能夠高效地解決多AGV多任務分配問題。與傳統NSGA?Ⅱ算法相比，本文提出的改進策略顯著提高了算法的收斂性和穩定性。

注：本文通訊作者為王凌。

參考文獻

[1] RYCK M D， VERSTEYHE M， DEBROUWERE F. Automated guided vehicle systems， state?of?the?art control algorithms and techniques [J]. Journal of manufacturing systems， 2020， 54（1）： 152?173.

[2] 曾亮，詹逸鵬，王粟.基于文化混合算法的多AGV調度研究[J].現代電子技術，2021，44（9）：105?109.

[3] 李緣.多AGV路徑規劃算法與任務分配調度策略研究[D].杭州：浙江大學，2022.

[4] WANG X， WU W， XING Z. Multi?decision points model to solve coupled?task scheduling problem with heterogeneous multi?AGV in manufacturing systems [J]. International journal of industrial engineering computations， 2023， 14（1）： 49?64.

[5] HU Y， WU X， ZHAI J， et al. Hybrid task allocation of an AGV system for task groups of an assembly line [J]. Applied sciences， 2022， 12（21）： 10956.

[6] 馮開團，袁杰.在離散車間下的AGV任務分配規劃研究[J].現代電子技術，2022，45（18）：69?74.

[7] 丁一，袁浩，方懷瑾，等.考慮沖突規避的自動化集裝箱碼頭AGV優化調度方法[J].交通信息與安全，2022，40（3）：96?107.

[8] LI G， LI X， GAO L， et al. Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm [J]. Journal of ambient intelligence and humanized computing， 2019， 10（11）： 4533?4546.

[9] 楊瑋，李然，張堃.基于變鄰域模擬退火算法的多自動導引車任務分配優化[J].計算機應用，2021，41（10）：3056?3062.

[10] 楊智飛，蘇春，胡祥濤，等.面向智能生產車間的多AGV系統多目標調度優化[J].東南大學學報（自然科學版），2019，49（6）：1033?1040.

[11] 馬千慧，梁曉磊，劉星雨，等.多AGV和機器集成的多目標柔性作業車間調度研究[J].計算機工程與應用，2023，59（1）：278?290.

[12] 楊俊，詹軍，佘勇.基于多目標優化模型的港口多載AGV調度方法[J].中國航海，2022，45（1）：66?72.

[13] DE R M， PISSOORT D， HOLVOET T， et al. Decentral task allocation for industrial AGV?systems with resource constraints [J]. Journal of manufacturing systems， 2021， 59： 310?319.

[14] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA?Ⅱ [J]. IEEE transactions on evolutionary computation， 2002， 6（2）： 182?197.

Research on multi?AGV multi?task allocation based on improved NSGA?Ⅱalgorithm

WANG Fantong， WANG Ling， GAO Yanfeng， CHEN Xiai， WANG Binrui

（College of Mechanical and Electrical Engineering， China Jiliang University， Hangzhou 310018， China）

Abstract： To address the batch task allocation problem for multi?AGVs （automated guided vehicles） in an automated warehousing system， a multi?objective optimization mathematical model is formulated with the objectives of minimizing total task waiting time， optimizing AGV load balance index， and reducing overall AGV energy consumption. The matching relationship between AGVs and tasks is established as decision variables， incorporating electrical constraints. In order to overcome the shortcomings of the traditional NSGA?Ⅱ （non?dominated sorting genetic algorithm Ⅱ） algorithm， for example， slow convergence speed and poor maintenance of population diversity， three improvement strategies are proposed， including improving crossover and mutation operators and adopting a hybrid mutation operator combining sequential crossover operator， reverse order and single?point mutations， improving the crowding degree calculation formula by introducing a non?linear average absolute deviation method， and introducing a dynamic parameter adaptive adjustment strategy in both global and local perspectives. Simulation experiments for multi?AGV multi?task allocation are designed. Experimental results demonstrate that the improved NSGA?Ⅱ algorithm can effectively address the batch task allocation problem for multi?AGVs， and enhance the convergence speed， stability and robustness.

Keywords： automated warehouse system; multi?AGV; task allocation; multi?objective optimization; electrical constraint; dynamic parameter; NSGA?Ⅱ algorithm

DOI：10.16652/j.issn.1004?373x.2024.09.028

引用格式：王凡通，王凌，高雁鳳，等.基于改進NSGA?Ⅱ算法的多AGV多任務分配研究[J].現代電子技術，2024，47（9）：157?163.

收稿日期：2023?12?09"""""""""" 修回日期：2024?01?05

基金項目：浙江省公益性技術應用研究（分析測試）計劃項目

（LGC21F030001）

王凡通，等：基于改進NSGA?Ⅱ算法的多AGV多任務分配研究

王凡通，等：基于改進NSGA?Ⅱ算法的多AGV多任務分配研究

作者簡介：王凡通（1998—），男，山東泰安人，碩士研究生，研究方向為多機器人調度。

王" 凌（1980—），男，浙江義烏人，博士，副教授，研究方向為機器人性能測試、故障診斷及其應用技術。

王凡通，等：基于改進NSGA?Ⅱ算法的多AGV多任務分配研究