摘" 要： 針對(duì)自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)中多AGV的批量任務(wù)分配問題，以總?cè)蝿?wù)等待時(shí)間、AGV負(fù)載均衡指數(shù)、總AGV能耗為目標(biāo)，以AGV和任務(wù)的匹配關(guān)系為決策變量構(gòu)建多目標(biāo)優(yōu)化數(shù)學(xué)模型，加入電量約束條件。為克服傳統(tǒng)NSGA?Ⅱ算法存在的收斂速度慢、種群多樣性維護(hù)差等不足，提出三種改進(jìn)策略：改進(jìn)交叉和變異算子，采用順序交叉算子、逆序和單點(diǎn)相結(jié)合的混合變異算子；改進(jìn)擁擠度計(jì)算公式，提出非線性平均絕對(duì)差的擁擠度計(jì)算方法；提出從局部和全局雙角度調(diào)整的動(dòng)態(tài)參數(shù)自適應(yīng)調(diào)整策略。最后，設(shè)計(jì)多AGV多任務(wù)分配的仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的NSGA?Ⅱ算法有效解決了多AGV多任務(wù)分配問題，同時(shí)，所提出的改進(jìn)策略有效提高了算法的收斂速度、穩(wěn)定性和魯棒性。

關(guān)鍵詞： 自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)； 多AGV； 任務(wù)分配； 多目標(biāo)優(yōu)化； 電量約束； 動(dòng)態(tài)參數(shù)； NSGA?Ⅱ算法

中圖分類號(hào)： TN911?34； TP242""""""""""""""""""" 文獻(xiàn)標(biāo)識(shí)碼： A"""""""""""""""nbsp;"""" 文章編號(hào)： 1004?373X（2024）09?0157?07

0" 引" 言

隨著生產(chǎn)規(guī)模的擴(kuò)大和柔性制造系統(tǒng)的發(fā)展，多AGV（Automated Guided Vehicle）以其靈活性、容錯(cuò)性和可擴(kuò)展性強(qiáng)的顯著優(yōu)勢(shì)成為新的發(fā)展趨勢(shì)，與之匹配的多AGV調(diào)度系統(tǒng)也得到了迅速發(fā)展。多AGV調(diào)度系統(tǒng)的五大核心任務(wù)有任務(wù)分配、車輛定位、路徑規(guī)劃、運(yùn)動(dòng)規(guī)劃、車輛管理[1]。其中，任務(wù)分配作為最基礎(chǔ)的任務(wù)之一，得到了國(guó)內(nèi)外學(xué)者的廣泛研究。

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

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

1" 問題描述與模型建立

1.1" 環(huán)境建模

自動(dòng)倉(cāng)儲(chǔ)系統(tǒng)作為一種自動(dòng)化、智能化的物流系統(tǒng)，具有貨物存儲(chǔ)、檢索、處理等核心功能，被廣泛應(yīng)用于電子商務(wù)、制造業(yè)領(lǐng)域，大幅提高了運(yùn)營(yíng)操作效率。本文利用柵格法對(duì)自動(dòng)倉(cāng)儲(chǔ)環(huán)境進(jìn)行地圖建模，將環(huán)境抽象成一個(gè)平面二維地圖，如圖1所示。將工位點(diǎn)、存儲(chǔ)點(diǎn)等重要節(jié)點(diǎn)抽象成50×50的柵格數(shù)據(jù)點(diǎn)，其坐標(biāo)表示為[（x，y）]的形式。整個(gè)地圖被劃分成五個(gè)不同區(qū)域：存儲(chǔ)區(qū)、入庫(kù)區(qū)、出庫(kù)區(qū)、充電區(qū)、行駛區(qū)。

1.2" 問題描述

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

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

式中：[ymn]為0/1變量，任務(wù)[am]由AGV [vn]執(zhí)行時(shí)，[ymn]為1，否則，[ymn]為0。

1.3" 條件假設(shè)及參數(shù)定義

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

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

2） AGV保持勻速行駛，不考慮負(fù)載和轉(zhuǎn)彎對(duì)速度的影響，但考慮負(fù)載對(duì)AGV能耗的影響；

3） 任務(wù)分配階段不考慮AGV調(diào)度的沖突問題；

4） AGV始終在無故障狀態(tài)下運(yùn)行；

5） AGV為單負(fù)載，即同一時(shí)刻只執(zhí)行一個(gè)任務(wù)，且每個(gè)任務(wù)僅由一臺(tái)AGV去執(zhí)行，任務(wù)數(shù)量大于AGV數(shù)量。

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

1.4" 模型建立

1.4.1" 任務(wù)等待時(shí)間成本

在多AGV批量任務(wù)分配問題中，任務(wù)等待時(shí)間是指從任務(wù)發(fā)布到任務(wù)開始執(zhí)行時(shí)的時(shí)間間隔。由于每臺(tái)AGV可能會(huì)被一次性分配多個(gè)任務(wù)，AGV會(huì)維護(hù)一個(gè)任務(wù)隊(duì)列，任務(wù)隊(duì)列的長(zhǎng)度直接影響靠近隊(duì)列末尾的任務(wù)等待時(shí)間?？?cè)蝿?wù)等待時(shí)間[f1]作為一個(gè)綜合指標(biāo)，對(duì)系統(tǒng)任務(wù)執(zhí)行效率和全局任務(wù)調(diào)度結(jié)果起著關(guān)鍵作用，其計(jì)算公式如下：

[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]為總?cè)蝿?wù)等待時(shí)間；[w]為任務(wù)隊(duì)列位置序號(hào)；[twaitk]為第[k]個(gè)任務(wù)[ak]的任務(wù)等待時(shí)間，由任務(wù)所在任務(wù)隊(duì)列[Qi]的位置所決定。式中距離用哈曼頓距離來計(jì)算，如式（4）、式（5）所示。當(dāng)[k]=1時(shí)，[vci]=（[xci]，[yci]），否則[vci]=（[xgk-1]，[ygk-1]）。AGV [vi]執(zhí)行任務(wù)[aj]的完整過程可分為兩個(gè)有序過程：空載過程（當(dāng)前位置至任務(wù)起始點(diǎn)）和負(fù)載過程（任務(wù)起始點(diǎn)至任務(wù)目標(biāo)點(diǎn)）?？蛰d和負(fù)載各需要一個(gè)單位的[tc]來完成裝載和卸載貨物。

1.4.2" AGV負(fù)載均衡指數(shù)

所有AGV構(gòu)成一個(gè)整體的運(yùn)輸系統(tǒng)，在任務(wù)分配過程中，如果一部分AGV長(zhǎng)時(shí)間處于忙碌狀態(tài)，而另一部分處于空閑狀態(tài)，這將導(dǎo)致AGV工作負(fù)荷分布極不均勻。負(fù)載均衡[f2]旨在最大程度地均衡每臺(tái)AGV的工作負(fù)荷，變異系數(shù)克服了標(biāo)準(zhǔn)差和方差在數(shù)據(jù)分布不均勻時(shí)誤差較大、最大最小差對(duì)極值敏感的不足，能更好地反映數(shù)據(jù)的離散程度。其計(jì)算公式如下：

[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）

本文以每臺(tái)AGV的能耗作為工作負(fù)荷的度量標(biāo)準(zhǔn)。由式（6）～式（9）可知，變異系數(shù)cv的取值在[0，1]之間，其值越接近于0，說明每臺(tái)AGV的工作量越均衡。

1.4.3" AGV能耗成本

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

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

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

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

[pij=1，""" AGV vi執(zhí)行任務(wù)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）保證所有任務(wù)都被分配完；式（13）保證每個(gè)任務(wù)只能由一臺(tái)AGV去執(zhí)行；式（14）保證AGV [vi]的電量可用性；式（15）保證AGV [vi]按照任務(wù)隊(duì)列[Qi]依次執(zhí)行任務(wù)，[card]（[Qi]）為任務(wù)隊(duì)列的任務(wù)數(shù)量。

2" NSGA?Ⅱ算法及其改進(jìn)

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

2.1" 改進(jìn)交叉與變異算子

本文中，任務(wù)分配數(shù)學(xué)模型的決策變量[pij]為離散的0/1變量，考慮使用整數(shù)編碼的形式來表達(dá)解。染色體的長(zhǎng)度等于任務(wù)數(shù)量，每個(gè)基因位的值為AGV編號(hào)。假設(shè)存在20臺(tái)AGV任務(wù)和5臺(tái)AGV，染色體表達(dá)形式如圖2所示。例如第10個(gè)基因位的值為3，表示第10個(gè)任務(wù)由第3臺(tái)AGV執(zhí)行。

針對(duì)該問題的特點(diǎn)，本文對(duì)傳統(tǒng)的交叉和變異操作進(jìn)行改進(jìn)。在交叉操作方面，由于AGV按照任務(wù)隊(duì)列的前后順序執(zhí)行任務(wù)，將單點(diǎn)交叉改為順序交叉，以增加種群多樣性、保留優(yōu)秀染色體的部分有序性，如圖3a）所示。在變異操作方面，由于AGV執(zhí)行任務(wù)的順序?qū)?yōu)化目標(biāo)的值有一定影響，采用逆序變異和單點(diǎn)變異相結(jié)合的方式可有效改變?nèi)旧w結(jié)構(gòu)，增加種群的多樣性，如圖3b）所示。

2.2" 改進(jìn)擁擠度計(jì)算方法

傳統(tǒng)的擁擠度計(jì)算是線性的，這種方法只考慮相鄰個(gè)體之間的距離，當(dāng)解的分布非常不均勻時(shí)，難以反映解的密度差異，使種群的多樣性降低，還可能導(dǎo)致算法過早收斂。因此提出使用平均絕對(duì)差距離來計(jì)算擁擠度，以綜合考慮解的密度分布。擁擠度計(jì)算方法由式（16）變?yōu)槭剑?7）：

[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]為目標(biāo)函數(shù)的個(gè)數(shù)；front為帕累托層；[R]為該帕累托前沿中解的個(gè)數(shù)。

2.3" 自適應(yīng)動(dòng)態(tài)參數(shù)調(diào)整

傳統(tǒng)的靜態(tài)參數(shù)無法充分利用算法迭代的動(dòng)態(tài)特性，缺乏靈活性。因此，提出從局部和全局雙角度進(jìn)行調(diào)整的自適應(yīng)動(dòng)態(tài)參數(shù)策略。在NSGA?Ⅱ算法多目標(biāo)優(yōu)化問題中，前沿非支配個(gè)體的覆蓋率是描述種群質(zhì)量的重要指標(biāo)，如式（18）所示：

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

依據(jù)該指標(biāo)，動(dòng)態(tài)調(diào)整交叉概率和變異概率，如式（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]為當(dāng)前迭代次數(shù)；[N]為種群大?。籟pgc]為第[g]代的交叉概率；[pgm]為第[g]代的變異概率；[Δpc]為交叉概率的變化步長(zhǎng)，[Δpm]為變異概率的變化步長(zhǎng)，二者從局部角度進(jìn)行參數(shù)的調(diào)整；[k1]為交叉概率動(dòng)態(tài)變化的強(qiáng)度系數(shù)，[k2]為變異概率動(dòng)態(tài)變化的強(qiáng)度系數(shù)，二者從全局角度進(jìn)行參數(shù)的調(diào)整。同時(shí)，需要設(shè)置參數(shù)極值以防止參數(shù)越界。

改進(jìn)的NSGA?Ⅱ算法的計(jì)算流程如圖4所示。

3" 仿真實(shí)驗(yàn)

為驗(yàn)證本文研究?jī)?nèi)容的有效性、魯棒性等性能，設(shè)計(jì)多AGV多任務(wù)分配問題的仿真實(shí)驗(yàn)。設(shè)置參數(shù)：任務(wù)數(shù)量為50個(gè)，AGV數(shù)量為10臺(tái)，AGV初始電量為1 000個(gè)單位電量，[eunload]=1，[eload]=1.5，[eth]=100?？紤]問題規(guī)模，設(shè)置NSGA?Ⅱ算法的參數(shù)為：種群規(guī)模[N]=200，最大迭代次數(shù)Gen=500，交叉概率[Pc]=0.9，變異概率[Pm]= 0.05，交叉概率變化步長(zhǎng)[Δpc]=0.01，變異概率變化步長(zhǎng)[Δpm]=0.005，交叉概率強(qiáng)度變化系數(shù)[k1]=0.5，變異概率強(qiáng)度變化系數(shù)[k2]=0.2，交叉概率極值為[0.5，1]，變異概率極值為[0.01，0.3]。

隨機(jī)初始化50個(gè)任務(wù)和10臺(tái)AGV初始位置，算法迭代完畢后，初始種群的分布和最終種群的分布如圖5a）所示，不同目標(biāo)函數(shù)維度下的種群映射分布如圖5b）～圖5d）所示。

由圖5可分析出：首先，與初始種群相比，兩種算法在種群質(zhì)量方面都有顯著提升。這體現(xiàn)在三個(gè)目標(biāo)函數(shù)的值都明顯變小，且種群分布更加均勻。其次，相對(duì)于傳統(tǒng)NSGA?Ⅱ算法，改進(jìn)的NSGA?Ⅱ算法在三個(gè)目標(biāo)函數(shù)上表現(xiàn)更優(yōu)，一方面體現(xiàn)在帕累托解的位置更具競(jìng)爭(zhēng)力，另一方面體現(xiàn)在帕累托解的分布均勻性更佳，避免了斷層現(xiàn)象的出現(xiàn)。最后，總?cè)蝿?wù)等待時(shí)間與負(fù)載均衡指數(shù)呈正比關(guān)系，因?yàn)檩^低的負(fù)載均衡指數(shù)表示任務(wù)分配更加均勻，因此任務(wù)等待時(shí)間更短；同時(shí)，負(fù)載均衡指數(shù)與總AGV能耗呈反比關(guān)系，因?yàn)楫?dāng)AGV執(zhí)行完一個(gè)任務(wù)后，可就近執(zhí)行另一個(gè)任務(wù)以節(jié)省能耗，但由于負(fù)載均衡的限制，另一個(gè)任務(wù)需由其他AGV去執(zhí)行，最終導(dǎo)致能耗上升。這種關(guān)系凸顯出問題的復(fù)雜性和目標(biāo)之間的互斥性。

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

算法迭代完畢后，使用線性加權(quán)法從帕累托前沿中確定最優(yōu)解，每個(gè)解的評(píng)估值由式（21）計(jì)算：

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

式中：[i=1，2，…，N]，[N]為解的個(gè)數(shù)；[j=1，2，…，K]，[K]為目標(biāo)函數(shù)的個(gè)數(shù)；[eij]為第[i]個(gè)解的第[j]個(gè)目標(biāo)函數(shù)的歸一化值，如式（22）所示：

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

本文中，結(jié)合場(chǎng)景需求，[f1]、[f2]、[f3]三個(gè)目標(biāo)函數(shù)的權(quán)重分別設(shè)為[w1]=0.4、[w2]=0.2、[w3]=0.4。改進(jìn)的NSGA?Ⅱ算法最終種群的評(píng)估值如圖7所示。

帕累托解集的最優(yōu)評(píng)估值為0.648，其三個(gè)目標(biāo)函數(shù)值分別為：1 301.89、0.04、3 299.11。

為評(píng)估算法的魯棒性，通過設(shè)置不同的任務(wù)規(guī)模進(jìn)行壓力測(cè)試。在進(jìn)行種群評(píng)估選擇最優(yōu)解時(shí)，[fminj]=min{[fminj1]，[fminj2]}、[fmaxj]=max{[fmaxj1]，[fmaxj2]}，其中[fj1]和[fj2]分別為NSGA?Ⅱ算法和改進(jìn)NSGA?Ⅱ算法的第[j]個(gè)目標(biāo)函數(shù)。在每個(gè)任務(wù)規(guī)模下，最優(yōu)個(gè)體的歸一化評(píng)估值如圖8所示。

由圖8可知，在每個(gè)任務(wù)規(guī)模下，改進(jìn)的NSGA?Ⅱ算法的表現(xiàn)都優(yōu)于傳統(tǒng)NSGA?Ⅱ算法，并且隨著任務(wù)規(guī)模的增加，即隨著問題規(guī)模的擴(kuò)大，兩者的評(píng)估值之差逐漸增大，表明改進(jìn)的NSGA?Ⅱ算法具有較強(qiáng)的魯棒性。

4" 結(jié)" 語

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

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

參考文獻(xiàn)

[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調(diào)度研究[J].現(xiàn)代電子技術(shù)，2021，44（9）：105?109.

[3] 李緣.多AGV路徑規(guī)劃算法與任務(wù)分配調(diào)度策略研究[D].杭州：浙江大學(xué)，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] 馮開團(tuán)，袁杰.在離散車間下的AGV任務(wù)分配規(guī)劃研究[J].現(xiàn)代電子技術(shù)，2022，45（18）：69?74.

[7] 丁一，袁浩，方懷瑾，等.考慮沖突規(guī)避的自動(dòng)化集裝箱碼頭AGV優(yōu)化調(diào)度方法[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] 楊瑋，李然，張堃.基于變鄰域模擬退火算法的多自動(dòng)導(dǎo)引車任務(wù)分配優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2021，41（10）：3056?3062.

[10] 楊智飛，蘇春，胡祥濤，等.面向智能生產(chǎn)車間的多AGV系統(tǒng)多目標(biāo)調(diào)度優(yōu)化[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，49（6）：1033?1040.

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

[12] 楊俊，詹軍，佘勇.基于多目標(biāo)優(yōu)化模型的港口多載AGV調(diào)度方法[J].中國(guó)航海，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

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

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

基金項(xiàng)目：浙江省公益性技術(shù)應(yīng)用研究（分析測(cè)試）計(jì)劃項(xiàng)目

（LGC21F030001）

王凡通，等：基于改進(jìn)NSGA?Ⅱ算法的多AGV多任務(wù)分配研究

王凡通，等：基于改進(jìn)NSGA?Ⅱ算法的多AGV多任務(wù)分配研究

作者簡(jiǎn)介：王凡通（1998—），男，山東泰安人，碩士研究生，研究方向?yàn)槎鄼C(jī)器人調(diào)度。

王" 凌（1980—），男，浙江義烏人，博士，副教授，研究方向?yàn)闄C(jī)器人性能測(cè)試、故障診斷及其應(yīng)用技術(shù)。

王凡通，等：基于改進(jìn)NSGA?Ⅱ算法的多AGV多任務(wù)分配研究