考慮負載量均衡的自動揀貨系統(tǒng)AGV任務分配優(yōu)化

摘 要：為提高AGV自動揀貨系統(tǒng)作業(yè)效率、降低作業(yè)成本，在剖析造成系統(tǒng)擁堵的關鍵影響因素基礎上，提出考慮負載量均衡的AGV任務分配雙層規(guī)劃模型，上層考慮總成本最小，下層通過構建多目標函數(shù)來最小化系統(tǒng)負載量標準差和AGV空閑率。針對傳統(tǒng)GA求解任務分配問題效率低、易陷入局部最優(yōu)等問題，提出了一種改進自適應遺傳算法（SAGA），引入sigmoid函數(shù)用于適應度值的轉(zhuǎn)換，并參與到自適應調(diào)整交叉變異算子的操作中，加入災變策略防止算法出現(xiàn)早熟的情況。最后將該算法對不同規(guī)模算例進行仿真，結果證明，相比遺傳算法、自適應遺傳算法、自適應災變遺傳算法、蟻群算法，該改進算法在不同規(guī)模算例實驗結果中均有明顯優(yōu)化，表明改進算法能更好地避免早熟、提升求解質(zhì)量與收斂穩(wěn)定性，有效地均衡了路網(wǎng)負載量，降低了作業(yè)總成本。

關鍵詞：任務分配； 負載量均衡； 自動揀貨系統(tǒng)； 雙層規(guī)劃； 遺傳算法

中圖分類號：TP391.9;TP11 文獻標志碼：A

文章編號：1001-3695（2024）08-017-2366-08

doi：10.19734/j.issn.1001-3695.2023.11.0576

Optimization of AGV task assignment considering load balancing in RMFS

Tian Shuaihui， Shen Yifan， Ou Liying， Fan Lue

（School of Modern Posts， Chongqing University of Posts & Telecommunications， Chongqing 400065， China）

Abstract：To enhance the efficiency of RMFS and reduce operating costs， this paper proposed a double-layer planning model for AGV task allocation considering load balancing， following an analysis of key factors causing congestion in RMFS. The upper layer sought to minimize the total cost， while the lower layer addressed the minimization of the system load standard deviation and AGV idle rate through a multi-objective function. It introduced a modified adaptive genetic algorithm（SAGA） to overcome the challenges of low efficiency and susceptibility to local optima in solving task allocation problems using traditional GA. It integrated the sigmoid function was to transform fitness values and participates in the adaptive adjustment of cross-mutation operators. Additionally， it incorporated catastrophic strategies to prevent premature convergence of the algorithm. Finally， it simulated the proposed algorithm on different scale cases， and the results demonstrate that， in comparison to the genetic algorithm， adaptive genetic algorithm， adaptive disaster genetic algorithm， and ant colony algorithm， the improved algorithm exhibits substantial optimization in the experimental results of various scale cases. This suggests that the enhanced algorithm effectively avoids premature convergence， enhances solution quality and convergence stability， actively balances road network load， and reduces total operating costs.

Key words：task allocation; load balancing; robotic mobile fulfillment systems（RMFS）; bi-level programming; genetic algorithm

0 引言

我國電子商務逆勢增長，訂單量不斷增加，客戶對訂單的配送時效性和服務質(zhì)量需求持續(xù)增高，這對電子商務倉庫揀貨作業(yè)效率及準確率提出更高要求。以AGV為代表的AGV自動揀貨系統(tǒng)（RMFS）應運而生，自動揀貨系統(tǒng)揀選效率是傳統(tǒng)揀貨系統(tǒng)的 2～3倍，相比較傳統(tǒng)倉庫的揀貨作業(yè)模式揀貨效率有了很大的提升。

基于每天數(shù)以萬計的大規(guī)模電子商務訂單，自動揀貨系統(tǒng)對高效率、低成本的揀貨解決方案需求大幅上升。然而，不斷增長的訂單業(yè)務，導致自動揀選系統(tǒng)擁堵問題日益嚴重，降低了揀選效率［1］。多臺AGV同時在同一地點進行作業(yè)，可能導致節(jié)點負載量（節(jié)點在當前AGV作業(yè)策略下的實際吞吐量）不均衡，進而引起系統(tǒng)擁堵［2］。系統(tǒng)節(jié)點在單位時間內(nèi)的累計負載超過一定閾值時，節(jié)點就會陷入擁堵狀態(tài)［3］。在這種狀態(tài)下，不同路段之間的負載不均衡問題會變得更加嚴重［4］。解決擁塞問題的關鍵，在于防止揀貨系統(tǒng)中每個節(jié)點的負載超過合理范圍。AGV任務分配直接影響多AGV作業(yè)中的擁堵情況以及任務完成的效率等，是自動揀貨系統(tǒng)降本增效的關鍵環(huán)節(jié)。

多AGV任務分配（multi-robot task allocation，MRTA）一直以來都是學者關注的熱點問題。任務分配的優(yōu)化目標在于將任務分配給適當?shù)腁GV，并確定作業(yè)順序。當多AGV同時完成訂單揀選任務時，研究如何在滿足多約束條件的前提下，尋求最優(yōu)任務分配方案使AGV能同時滿足多種目標，對提升揀貨系統(tǒng)的作業(yè)性能具有重要意義。

目前國內(nèi)外學者關于任務分配的研究主要是從模型構建到求解方法的探討。MRTA問題的模型主要有多旅行商問題、車輛路由問題和混合整數(shù)線性規(guī)劃模型等，其目標函數(shù)可以是單目標函數(shù)，也可以是多目標融合函數(shù)。大量學者集中于以作業(yè)成本、作業(yè)時間和行駛距離為研究目標來優(yōu)化MRTA問題。許麗麗等人［5］為解決四向穿梭車倉儲系統(tǒng)的任務分配問題，構建作業(yè)時間最短為目標的數(shù)學模型，并使用遺傳算法求解得到最優(yōu)任務分配方案；周航等人［6］研究了倉儲多機器人任務分配問題，以成本最小化為目標函數(shù)建立數(shù)學模型，使用混合遺傳禁忌搜索算法優(yōu)化任務分配結果；李騰等人［7］為提高移動機器人履約系統(tǒng)揀選效率，以作業(yè)成本最小為優(yōu)化目標，并建立了考慮移動機器人重載和空載成本差異的數(shù)學模型，得到協(xié)同優(yōu)化的任務分配和貨架儲位再指派策略；李緣［8］針對多AGV多任務分配問題，提出周期任務分配策略，考慮總成本最優(yōu)建立模型，使用改進粒子群遺傳算法求解，實現(xiàn)總成本最小化；于佳喬等人［9］以AGV完成任務行走總距離最短為優(yōu)化目標，采用雙層編碼的方式，解決AGV在多任務下的分配問題。也有部分學者優(yōu)化其他目標函數(shù)來研究MRTA問題，Zou等人［10］以能耗、AGV數(shù)量和客戶滿意度三個目標建立多目標優(yōu)化模型，并使用多目標貪婪算法解決了多AGV任務分配問題；王子意［11］將多AGV任務分配問題拆分為任務組合和任務派發(fā)兩個問題，構建以優(yōu)化剩余電量與AGV疲勞程度的任務分配模型，解決了任務分配存在的不均衡問題。

對于MRTA問題模型的求解方法，從較早期的匈牙利算法到拍賣算法、博弈論等，再到后來引入智能優(yōu)化算法，國內(nèi)外學者的相關研究都致力于探索如何提高MRTA問題的求解效率。孟憲福等人［12］考慮任務執(zhí)行時間、節(jié)點間的通信時間和任務調(diào)度費用等因素建立目標模型，使用了匈牙利算法求解任務分配問題。Zlot等人［13］基于動態(tài)變化的任務分配問題，提出了一種基于市場拍賣機制算法，結果表明該方法能克服環(huán)境信息的不確定性，有效優(yōu)化任務分配。Das等人［14］提出了一種基于分布式拍賣算法，用于解決多個異構自主機器人系統(tǒng)中的任務分配問題。Garapati等人［15］研究了博弈論算法在解決多機器人任務分配問題的有效性，尋找無人機之間的沖突平衡，再利用投票系統(tǒng)來確定最終的任務分配方案。對于求解任務分配的常用智能優(yōu)化算法有遺傳算法、蟻群算法、模擬退火算法和粒子群算法等。秦新立等人［16］將MRTA 問題轉(zhuǎn)換為 MTSP模型，改進了蟻群算法求解機器人任務分配問題，提升了收斂速度且避免陷入局部極小問題。Wei等人［17］改進了多目標粒子群優(yōu)化算法求解多機器人任務分配問題，在算法設計上提出了帕累托前沿細化策略和基于概率的領導者選擇策略，仿真結果驗證了算法的有效性。丁一等人［18］考慮AGV任務分配與路徑優(yōu)化問題，建立了兩階段模型，并設計改進的模擬退火算法求解第一階段模型。張子迎等人［19］提出了一種基于啟發(fā)式深度Q學習的多機器人多任務分配算法，解決多機器人任務分配方法在環(huán)境復雜性增加時出現(xiàn)的維度災難問題，證明了所改進算法的實用性和魯棒性。鄧輔秦等人［20］提出一種結合遺傳算法和滾動調(diào)度的MRTA算法，優(yōu)化現(xiàn)有算法在求解大規(guī)模多約束的MRTA問題時存在的不足。

基于以上研究內(nèi)容，將系統(tǒng)負載量作為任務分配優(yōu)化考慮因素的研究較為罕見，同時現(xiàn)有求解任務分配問題方法的效率仍有待提升。本文以移動AGV自動揀貨系統(tǒng)為研究對象，考慮造成系統(tǒng)擁堵的關鍵影響因素，將AGV任務分配與AGV數(shù)量配置結合建立雙層規(guī)劃模型，運用A*算法進行自動揀貨系統(tǒng)AGV路徑仿真實驗，針對傳統(tǒng)GA求解MRTA問題效率低、易陷入局部最優(yōu)等問題，提出了一種基于sigmoid改進的自適應遺傳算法，避免早熟問題的發(fā)生，增強了算法全局的搜索能力。

1 問題描述

多AGV自動揀貨系統(tǒng)采用分布式智能的思想，其作業(yè)順序為：系統(tǒng)根據(jù)任務訂單信息，調(diào)度AGV去揀取貨物貨架，AGV運至揀選臺取出貨物，再將空貨架運回后進行下一個任務的揀選。AGV作為自動揀貨系統(tǒng)的關鍵設備，不同的任務分配方式影響AGV行走距離和系統(tǒng)負載量均衡，從而影響揀貨速度。從圖1可以觀察到，自動揀貨系統(tǒng)中，AGV作業(yè)連續(xù)性強，AGV數(shù)量與任務分配的決策將直接影響作業(yè)場景的擁堵情況、完成訂單揀選的效率等，是提升系統(tǒng)作業(yè)性能的重要因素。

本文采用柵格法進行環(huán)境建模。柵格法易于算法實現(xiàn)，且能清楚地表示揀貨系統(tǒng)中的實物，每個柵格代表相應系統(tǒng)單位節(jié)點，便于計算節(jié)點負載量。如圖1所示，表示一個AGV完成三個任務的作業(yè)流程。以完成第一個任務為例，首先該AGV從AGV出入口沿路徑①出發(fā)前往第一個任務位置，取出貨架之后再沿路徑②前往揀貨臺取出貨物，接著沿路徑③運載空貨架返回該任務位置，最后沿路徑④前往下一任務位置，該AGV在完成所有任務之后原地等待下一批訂單的執(zhí)行命令。自動揀貨系統(tǒng)AGV完成一組任務序列包含四個步驟：

a）AGV從初始入口位置到第一個任務位置。

b）AGV搬運任務貨架至揀貨臺取出貨物。

c）AGV搬運空貨架從揀貨臺返回當前任務位置。

d）AGV從當前任務位置到下一任務位置。

2 參數(shù)設定與模型構建

2.1 條件假設及參數(shù)定義

為了便于模型的構建，作出以下假設（參數(shù)設定如表1所示）：

a）每個AGV同時只可以搬運一個貨架，每個貨架同時只能由一個AGV進行搬運。

b）每個AGV作業(yè)能力相同，均能獨立完成搬運任務。

c）不考慮AGV電量問題，作業(yè)AGV不考慮充電情況。

d）每個AGV速度相同且運行過程中速度保持不變。

e）不同的任務分布在不同的貨架，不存在缺貨情況。

f）待揀選任務的位置隨機，不考慮貨位影響負載均衡的因素。

參數(shù)如表1所示。

2.2 模型建立

雙層規(guī)劃具有層次性、制約性等特點，上層的決策影響下層的執(zhí)行，而下層的反饋影響上層的決策。針對自動揀貨系統(tǒng)場景，考慮AGV數(shù)量與任務分配優(yōu)化問題為一個層次性較強的問題。由于在確定AGV調(diào)度數(shù)量的前提下才能考慮后續(xù)的任務分配問題，而后續(xù)作業(yè)過程中產(chǎn)生的各項成本又對AGV數(shù)量和任務分配的決策產(chǎn)生影響，這一特性符合雙層規(guī)劃模型的應用特征，所以提出運用雙層規(guī)劃模型解決該系統(tǒng)優(yōu)化問題。上層模型以考慮完成任務的AGV行駛距離成本、負載量不均衡產(chǎn)生的延誤時間成本、AGV空閑成本以及AGV固定成本為目標函數(shù)，決策變量為AGV數(shù)量；下層模型考慮系統(tǒng)節(jié)點負載量標準差和AGV空閑率最小為目標函數(shù)，以任務分配為決策變量，刻畫系統(tǒng)負載量均衡程度和AGV損耗程度。

2.2.1 基于AGV數(shù)量的上層模型

基于上述問題描述、假設條件及參數(shù)變量，構建上層數(shù)學模型：

min Z=∑ni=1Di×Yi×Cr+t×Cd+lavg×n×Cf+n×Cp（1）

s.t. Yi∈{0，1}（2）

Nmin≤n≤Nmax，n∈Euclid ExtraeBp+（3）

上層模型中式（1）表示最小化AGV完成任務的總成本，其目標函數(shù)的成本由以下四部分構成：Cr表示所有AGV完成所有任務的行駛距離成本；Cd表示由節(jié)點負載量不均衡導致的擁堵產(chǎn)生的延誤時間成本；Cf表示AGV的空閑成本；Cp表示AGV運行的固定成本。Cr、Cf和Cd均由下層目標函數(shù)結果決定。約束條件式（2）中，Yi為0則不調(diào)用此AGV，Yi為1則調(diào)用。式（3）表示AGV的配置數(shù)量n要在設定的范圍之內(nèi)，且n必須為正整數(shù)。

2.2.2 基于AGV任務分配的下層模型

下層模型：

f1=θ=f（Ngh）=min∑g∈G，h∈H（Ngh-∑g∈G，h∈HNghNG×NH）2NG×NH（4）

f2=min lavg=1n×∑ni=1li=1n×∑ni=1{1-（∑mj=1Tij×XijT）}=

∑ni=11-∑mj=1∑pk=1{［（d1ioj+d2ijk+d3ikj）/Vi］×Xij}Tn（5）

根據(jù)實際作業(yè)場景中的重要性程度，設置f1和f2的權重為ω1和ω2，∑ωα=1。因此，多目標函數(shù)計算方法如式（6）所示，其中μα為調(diào)整系數(shù)。

f=∑ωα（μαfα）（6）

s.t Xij∈{0，1} i=1，2，3，…，n;j=1，2，3，…，m（7）

∑ni=1Xij=1 j=1，2，3，…，m（8）

∑mj=1Xij×Yi≥Yi i=1，2，3，…，n（9）

Ngh≥0，Ngh∈N，g∈G，h∈H（10）

下層目標函數(shù)為多目標函數(shù)。式（4）為最小化系統(tǒng)的負載量標準差，其反映自動揀貨系統(tǒng)的擁堵程度，通過轉(zhuǎn)換系數(shù)β將負載量標準差轉(zhuǎn)換為負載量不均衡導致的延誤時間t，并計算相應成本，Ngh表示第g行第h列子區(qū)域負載量，NG×NH表示揀貨系統(tǒng)總節(jié)點數(shù)；式（5）表示AGV在完成單批訂單完成的時間內(nèi)，最小化AGV的平均空閑率；式（7）表示決策變量Xij，表示AGV Ri是否完成任務Zj；式（8）表示一個任務只允許由一個AGV完成；式（9）表示被調(diào)度的AGV至少完成一個任務；式（10）表示負載量的非負約束與整數(shù)約束。

3 模型求解

多AGV任務分配問題是典型的NP-hard 問題，解決此類問題常使用遺傳算法，其編碼規(guī)則簡單有效，具有高度并發(fā)性和全局搜索能力。而傳統(tǒng)GA易早熟、計算效率低，導致計算結果易陷入局部最優(yōu)。因此為了得到更優(yōu)的任務分配方案，本文提出基于sigmoid改進的自適應遺傳算法。其中，在交叉與變異過程中引入sigmoid函數(shù)計算個體的值，提高個體較多、個體間差異較小時自適應遺傳算法的優(yōu)越性；交叉操作考慮了一種快速判斷個體是否交叉的方法，避免相同個體間的無效交叉；引入災變算子，當最優(yōu)個體重復出現(xiàn)一定次數(shù)以后增加變異基因，以尋求更優(yōu)秀的個體。

3.1 改進遺傳算法設計

3.1.1 初始化種群

確定AGV數(shù)量初始配置、批量訂單任務數(shù)量，對任務分配問題進行隨機生成初始種群pop。

3.1.2 編碼

采用整數(shù)編碼方式進行編碼，染色體長度為待搬運任務的數(shù)量，第i個位置的編號j表示第i個任務由第j臺AGV完成，并保證所調(diào)度AGV的序號在染色體中至少出現(xiàn)一次，如圖2所示，為10個任務由3臺AGV分配完成的染色體編碼。

3.1.3 選擇

使用二元錦標賽與精英保留策略進行選擇操作，從種群pop中以同一概率隨機選擇兩個個體，根據(jù)每個個體的適應度值，選擇其中適應度值最好的個體進入下一代種群，直到新的種群規(guī)模達到原來的種群規(guī)模。

3.1.4 基于sigmoid函數(shù)的自適應交叉與變異算子

1）交叉算子

采用隨機交叉位置的單點交叉法。交叉操作是為了產(chǎn)生更多可選擇的AGV任務分配方案，可以增大任務分配解空間的搜索范圍。按照交叉概率Pc將染色體隨機一段基因進行交叉，產(chǎn)生新個體。重復此操作直到所有個體都被訪問，用所有產(chǎn)生的新的個體替換掉newPop中的原個體。

由于選擇操作將適應度值最好的個體加入下一代種群，隨著迭代次數(shù)增加，個體相同的情況變多，此時個體交叉是無效的。本文考慮了一種快速判斷個體是否交叉的方法，采用行駛距離長度和AGV序號的累加值作為判斷依據(jù)進行快速篩選，若相似度100%，則不進行交叉，提高算法的計算效率。

S（Ii，Ij）=λ1×dis（Ii）+λ2×∑QUANim=1Ii（m）λ1×dis（Ij）+λ2×∑QUANjn=1Ij（n）（11）

i≠j∈pop（12）

其中：S（Ii，Ij）為兩個個體相似度評價函數(shù)，如果其比值為1，則這兩個個體不進行交叉；Ii和Ij表示個體i和j；λ1和λ2為行駛距離長度與AGV序號累加值的權重，λ1=0.1，λ2=2；dis（Ii）、dis（Ij）分別為兩個個體的行駛距離長度；m、n為個體i、j中的某一個AGV編號，QUANi為QUANj為兩個個體的AGV編碼總量。

2）變異算子

采用隨機位置染色體單點變異方式，按照變異概率Pm進行變異，生成新的個體。重復操作直至所有個體都被訪問，變異時染色體的某個基因變異成某個AGV的序號。

3）基于sigmoid的自適應策略

sigmoid 函數(shù)是最常用的激活函數(shù)之一，其具有指數(shù)函數(shù)形狀，常用于二分類問題中，將輸出映射到［0，1］，表示某個事件發(fā)生的概率。其可導性好的特性使得sigmoid函數(shù)在神經(jīng)網(wǎng)絡中得到廣泛應用［21］。sigmoid函數(shù)的數(shù)學表達式為

f（x）=11+e-x（13）

為了保證當前種群中最優(yōu)個體的Pc和Pm不為零，防止進化初期種群最高適應度停滯不前的可能性，降低算法陷入局部最優(yōu)解的可能，使優(yōu)質(zhì)個體更有機會傳遞到下一代，引入sigmoid函數(shù)。由sigmoid函數(shù)計算某一代種群pop中，N個個體中的某一個體的適應度值fk對應的sigmoid值，其計算公式為

Sk=efkefk+1（14）

本文基于sigmoid函數(shù)思想建立了交叉概率Pc和變異概率Pm調(diào)節(jié)公式：當個體較優(yōu)時，交叉率和變異率會減小，反之則增大。由于某一代種群中的最優(yōu)個體未必是全局最優(yōu)解，不應設定最優(yōu)個體的交叉概率和變異概率為0。為避免早熟，交叉概率和變異概率不應過小。

Pc=Pc1×Sbest-SselectedSbest-Save fs≥fave

Pc2fs＜fave（15）

Pc=Pc1×efbestefbest+1-efsefs+1efbestefbest+1-1N fs≥favePc2fs<fave（16）

Pm=Pm1×Sbest-SindividualSbest-Save fs′≥favePm2fs′<fave（17）

Pm=Pm1×efbestefbest+1-efsefs+1efbestefbest+1-1N fs′≥favePm2fs′<fave（18）

其中：fs為某一代種群中參與交叉的兩個個體中較大的適應度值；fs′為某一代種群中變異個體的適應度值； fave為某一代種群適應度平均值；Sbest為適應度最優(yōu)個體的sigmoid值；Save為某一代種群平均適應度的sigmoid值；Sselected為fs對應的sigmoid值；Sindividual為fs′對應sigmoid值。改進的自適應交叉率由式（15）（16）計算得出，自適應變異率由式（17）（18）計算得出。

3.1.5 災變策略

遺傳算法的演化過程中常常會出現(xiàn)早熟現(xiàn)象，導致算法無法找到全局最優(yōu)解或者最優(yōu)解的質(zhì)量較差。為了避免遺傳算法早熟，本文引入了改進的災變操作，以增加算法的全局搜索能力和局部搜索能力。

災變策略的實施步驟為：在種群經(jīng)過n代進化后，若未能生成更優(yōu)個體，且連續(xù)出現(xiàn)達到閾值次數(shù)的情況，即觸發(fā)災變操作，保留最優(yōu)個體的同時增加一個變異位進行變異；如果執(zhí)行災變次數(shù)達到設定范圍，停止災變，若此時局部最優(yōu)個體無變化，則認為此個體為全局最優(yōu)個體，算法結束，如圖3所示。

3.2 模型求解流程

A*算法是一種常用的啟發(fā)式搜索算法，用于解決路徑規(guī)劃和圖搜索等問題，它在找到最短路徑時能夠具有較好的效率和準確性，因此本文采用A*算法進行AGV路徑仿真實驗。使用改進的自適應遺傳算法對不同數(shù)量AGV完成批量訂單任務的任務分配進行優(yōu)化。具體步驟如下：

a）設置上層模型中AGV的最大數(shù)量和最小數(shù)量。

b）以最小AGV數(shù)量為初始配置，確定批量訂單任務數(shù)量，對任務分配問題進行隨機生成初始種群pop；設置種群規(guī)模N，交叉概率Pc，變異概率Pm，迭代次數(shù)I。

c）編碼。

d）仿真路徑實驗：遍歷當前種群中的染色體，構成對應的圖模型路徑進行仿真實驗。

（a）確定貨架位置、揀選臺位置、AGV初始位置、任務位置，形成相應的地圖模型。

（b）設置AGV出入口到任務序列的第一個任務為第一段路徑、設置當前任務到揀貨臺為第二段路徑、設置揀貨臺到當前任務為第三段路徑、設置當前任務到下一任務為第四段路徑。

（c）行駛路徑尋優(yōu)。使用A*算法搜索AGV完成任務的最優(yōu)路徑。考慮到實際場景遍歷式迭代搜索路徑的復雜性，仿真路徑實驗思路為：設置路徑池，記錄所有任務與任務之間的路徑、揀選臺與任務之間的路徑、AGV初始入口與任務之間的路徑；根據(jù)待搜索路徑的任務序列調(diào)用此路徑池，其中第一段路徑調(diào)用path2_pool、第二與三段路徑調(diào)用path3_pool、第四段路徑調(diào)用path1_pool；記錄路徑。算法尋徑流程如圖4所示。

（d）計算值。計算AGV完成任務經(jīng)過節(jié)點的節(jié)點負載量與行駛距離。

（e）實驗終止條件。判斷AGV是否完成所有任務的揀選，若完成則輸出負載量和行駛距離，實驗結束。

e）適應度函數(shù)。下層考慮的目標函數(shù)為多目標函數(shù)，因此在計算適應度函數(shù)時，采用將多目標函數(shù)轉(zhuǎn)換為單目標函數(shù)的方法計算適應度值，適應度值為AGV完成任務的節(jié)點負載量標準差、AGV行駛總距離的倒數(shù)（AGV行駛距離由運行A*算法尋徑得到），將兩個適應函數(shù)值分別賦予權重，并相加作為適應度評價指標。為保證AGV任務分配結果不被多目標函數(shù)其中某一個目標函數(shù)過度影響，因此設置合理的調(diào)整系數(shù)值。

f）選擇。

g）交叉。

h）變異。

i）收斂判斷。如果Inter>I，迭代終止，否則pop（Inter）=newPop（Inter），Inter=Inter+1，返回步驟e）。

j）將下層計算結果輸入上層模型，計算AGV完成所有任務所花費的總成本。找到調(diào)度該數(shù)量AGV下的最小總成本，并得到任務分配結果。

k）將AGV的調(diào)度數(shù)量增加一個，返回步驟b）。

l）若AGV的調(diào)度數(shù)量達到AGV數(shù)量設置上限，則停止計算，輸出歷史最優(yōu)成本、調(diào)度AGV的數(shù)量與任務分配結果。模型求解流程如圖5所示。

4 算例仿真

為驗證SAGA的有效性，使用MATLAB 2019a完成各項仿真實驗，分別對GA［22］、AGA［23］、IAGA［24］以及文獻［16］的蟻群算法部分進行仿真，設置小規(guī)模算例和大規(guī)模算例實驗。仿真環(huán)境設定為某32 m×42 m的電子商務倉庫，以32×42的柵格刻畫仿真環(huán)境。每臺AGV的固定成本為6 萬元，按照每臺AGV的功率為100 W/h，電費為0．86 元/kW·h計算得出，其行走單位距離所花費的成本為0.000 83 元/m，考慮每臺AGV的折舊費用為2萬/年計算得出，一臺AGV在單位時間內(nèi)負載量不均衡造成的延誤時間成本和空閑成本為0.000 6 元/s，轉(zhuǎn)換系數(shù)β為40，由于AGV的固定成本相同，以下仿真結果只包括AGV的運行成本、延誤時間成本以及空閑成本。下層多目標函數(shù)設置如下：

f=0.5×75.5×f1+0.5×0.3×f2

算法參數(shù)中，SAGA、GA、AGA、IAGA設置如下：初始化種群個數(shù)設為100個，交叉概率Pc=0.8，變異概率Pm=0.07，小規(guī)模迭代400次，大規(guī)模迭代700次。蟻群算法參數(shù)設置如下：小規(guī)模算例螞蟻數(shù)antNum1=20，大規(guī)模算例螞蟻數(shù)antNum2=40，信息揮發(fā)因子為0.1，信息素重要程度為1，啟發(fā)因子重要程度為5，信息素增加強度系數(shù)為50，小規(guī)模迭代400次，大規(guī)模迭代700次。為了保證測試的公平性，實驗中所有的數(shù)據(jù)都是運行20次的均值。

4.1 小規(guī)模算例

小規(guī)模實驗參數(shù)中，設置3～10個AGV完成任務數(shù)量為30個的單批訂單，揀選臺的位置為（20，1） ，由于AGV在進行一批訂單的揀選前都在一個AGV出入口排隊等待，故指定AGV的初始位置都為（29，1），任務坐標位置如表2所示。仿真結果如圖6～9、表3所示。

4.2 大規(guī)模算例

為驗證本文方法能有效解決大規(guī)模AGV的任務分配問題，在大規(guī)模算例中倉庫環(huán)境設置與小規(guī)模相同，AGV初始位置為（29，1），大規(guī)模任務位置如表4所示。AGV的數(shù)量為11～20個，模擬三批訂單，其任務數(shù)量為90個，仿真結果如圖10～13、表5所示。

4.3 實驗結果分析

如圖6、10所示，對于小規(guī)模算例和大規(guī)模算例，皆存在一個最佳AGV數(shù)量使得系統(tǒng)作業(yè)成本最小，當調(diào)度7個、16個AGV時，此時作業(yè)總成本最小。調(diào)用高于7個、16個AGV的成本更高，是由于隨著AGV調(diào)度的數(shù)量增加，AGV空閑率增加，進而使得成本增加。

對調(diào)度成本最優(yōu)下的AGV數(shù)量進行任務分配優(yōu)化，仿真結果如圖7、11所示，表示調(diào)度7個、16個AGV時，AGV任務分配優(yōu)化前后的系統(tǒng)節(jié)點負載量對比情況，由于任務到揀選臺之間的路徑行走產(chǎn)生的負載情況不受任務分配的影響，所以仿真未記錄此部分路徑負載圖。使用改進的SAGA算法分別就大小規(guī)模算例進行優(yōu)化，節(jié)點負載量優(yōu)化結果如表6所示，優(yōu)化后負載量標準差分別優(yōu)化了20.5%和39.3%。將節(jié)點負載量高于平均節(jié)點負載量2倍定義為擁擠節(jié)點，優(yōu)化后擁擠節(jié)點數(shù)分別下降了26.7%和28.2%。由于任務分配的優(yōu)化，AGV在完成當前任務后分配下一任務時，前往下一任務需經(jīng)過的節(jié)點可能存在擁擠節(jié)點數(shù)多，而對于另一個AGV從上一任務前往此任務位置，可能經(jīng)過的擁擠節(jié)點相對較少，則會在算法迭代時不斷尋優(yōu)，尋找全局負載量標準差相對最優(yōu)的任務分配方案。綜合來說，優(yōu)化之后的節(jié)點負載量明顯均衡提升，大小規(guī)模算例中擁擠度最高節(jié)點負載量分別降低了30.6%和29.2%。

圖9和13為單目標適應度迭代情況，如圖8、12顯示，相比較GA、AGA、IAGA、蟻群算法，本文基于sigmoid函數(shù)改進的自適應遺傳算法所計算的總適應度、單目標都有較好的收斂效果，并得到AGV任務分配方案。

從五種算法的收斂結果來看，GA收斂速度最慢，且收斂平滑度較差，而AGA與IAGA兩種算法相較于傳統(tǒng)GA，收斂速度和平滑度有所改善，但都較容易早熟。蟻群算法收斂速度最快，但其早熟概率也比較高，容易導致任務分配質(zhì)量下降，是由于螞蟻在搜索過程中依賴于其他螞蟻的信息，可能會導致算法陷入局部最優(yōu)解，特別是在搜索進行到一定程度后，所有個體所發(fā)現(xiàn)的解完全一致，不能對解空間進一步搜索，不利于發(fā)現(xiàn)更好的解。而SAGA在收斂平滑的同時，避免了陷入局部最優(yōu)解而導致的早熟，其原因在于：使用sigmoid函數(shù)來轉(zhuǎn)換適應度值，在一定程度上增強了算法的自適應性，sigmoid函數(shù)的特點是將值域映射到0～1，對適應度值進行了歸一化處理，每個個體被選中的概率就與其適應度值成比例，增加了適應度值相對較小的個體在算法中的生存機會。并且函數(shù)值變化較為平滑，防止適應度值在遺傳算法迭代過程中發(fā)生劇烈的變化，避免算法的震蕩和陷入局部最優(yōu)，這樣增強了算法的探索能力，使其更有可能跳出局部最優(yōu)解，找到更優(yōu)的解決方案。此外，在算法的初期階段，由于適應度值差異較大，一些個體的操作概率過高，導致算法收斂速度緩慢，使用sigmoid函數(shù)轉(zhuǎn)換適應度值，降低了個體操作概率的差異性，加入快速判斷個體是否交叉的方法，減少了無效交叉操作，從而加速算法的收斂速度。同時為防止算法跳出局部最優(yōu)，加入了改進的災變策略。改進GA優(yōu)化結果如表7所示。

5 結束語

為提高自動揀貨系統(tǒng)作業(yè)效率、降低作業(yè)成本，本文考慮了造成自動揀貨系統(tǒng)擁堵的關鍵因素，提出一種基于AGV數(shù)量與任務分配的雙層規(guī)劃模型，上層以最小化運行成本、延誤時間成本、AGV空閑成本和AGV固定成本為目標函數(shù)，以AGV數(shù)量為決策變量，下層構建最小化節(jié)點負載量標準差和AGV空閑率的多目標函數(shù)，以任務分配為決策變量。運用A*算法對AGV完成任務所行駛的路徑進行仿真實驗，并設計改進的自適應遺傳算法對模型求解。仿真結果顯示，通過此模型，提升了系統(tǒng)的負載量均衡水平，降低了AGV完成任務的行駛距離，考慮成本因素優(yōu)化了AGV數(shù)量配置。

本文針對現(xiàn)有任務分配算法計算低效、易早熟等問題：a）在自適應遺傳算法的基礎上，加入sigmoid函數(shù)，增強自適應性、探索能力和收斂速度，并且增加算法的魯棒性；b）改進交叉算子通過引入快速判別步驟防止了相同個體之間的無效交叉，減少計算資源；c）加入并改進了災變策略，執(zhí)行災變時在變異環(huán)節(jié)增加變異位進行變異，幫助遺傳算法跳出局部最優(yōu)解，增加算法的搜索范圍，從而提高搜索效率和優(yōu)化結果的質(zhì)量。通過不同規(guī)模仿真實驗證明，SAGA的收斂效果均優(yōu)于其他算法，驗證了模型和算法對于自動揀貨系統(tǒng)AGV任務分配優(yōu)化問題具有良好的效果，幫助自動揀貨系統(tǒng)降低作業(yè)成本。對于后續(xù)的研究，由于路徑優(yōu)化也是降低系統(tǒng)擁堵與AGV作業(yè)行駛距離的關鍵決策，未來還需加入AGV路徑優(yōu)化與任務分配進行協(xié)同優(yōu)化，這有待進一步研究。

參考文獻：

［1］Zhong Meisu， Yang Yongsheng， Sun Shu， et al. Priority-based speed control strategy for automated guided vehicle path planning in automated container terminals［J］. Trans of the Institute of Measurement and Control， 2020， 42（16）： 3079-3090.

［2］Suman P P， Reddy P， Chenna R P. Energy and congestion-aware load balanced multi-path routing for wireless sensor networks in am-bient environments［J］. Computer Communications， 2022， 195（5）： 217-226.

［3］宋海權. 基于復雜網(wǎng)絡理論的網(wǎng)絡交通擁堵問題研究［D］. 成都： 西南交通大學， 2016. （Song Haiquan. Research of network traffic congestion based on complex networks theory［D］. Chengdu： Southwest Jiaotong University， 2016.）

［4］項俊平. 城市道路交通信號區(qū)域均衡控制方法及應用研究［D］. 合肥： 中國科學技術大學， 2018. （Xiang Junping. Study on the method and application for urban road traffic signal regional equilibri-um control［D］. Hefei： University of Science and Technology of China， 2018.）

［5］許麗麗， 詹燕， 魯建廈，等. 四向穿梭車倉儲系統(tǒng)復合作業(yè)調(diào)度優(yōu)化［J］. 浙江大學學報：工學版， 2023， 57（11）： 2188-2199. （Xu Lili， Zhan Yan， Lu Jianxia， et al. Optimization of composite job scheduling for four way shuttle warehouse system［J］. Journal of Zhejiang University： Engineering Edition， 2023， 57（11）： 2188-2199.）

［6］周航， 秦實宏， 方?jīng)茇? 基于混合遺傳禁忌搜索算法的多機器人任務分配［J］. 自動化與儀表， 2023， 38（11）： 35-39. （Zhou Hang， Qin Shihong， Fang Jingcheng. Multi robot task allocation based on hybrid genetic taboo search algorithm［J］. Automation and Instrumentation， 2023， 38（11）： 35-39.）

［7］李騰， 張茹蘭， 丁佩佩. 機器人履約系統(tǒng)任務分配與貨架儲位再指派聯(lián)合優(yōu)化［J］. 科學技術與工程， 2023， 23（26）： 11271-11281. （Li Teng， Zhang Rulan， Ding Peipei. Joint optimization of task allocation and shelf storage reassignment in robot fulfillment systems［J］. Science， Technology and Engineering， 2023， 23（26）： 11271-11281.）

［8］李緣. 多AGV路徑規(guī)劃算法與任務分配調(diào)度策略研究［D］. 杭州：浙江大學， 2022. （Li Yuan. Research on multi AGV path planning algorithm and task allocation and scheduling strategy［D］. Hangzhou： Zhejiang University， 2022.）

［9］于佳喬， 李巖. 基于改進遺傳算法的自動導航小車路徑規(guī)劃調(diào)度［J］. 機床與液壓， 2022， 50（5）： 16-20. （Yu Jiaqiao， Li Yan. Path planning and scheduling of automatic navigation vehicles based on improved genetic algorithm［J］. Machine Tool and Hydraulic， 2022， 50（5）： 16-20.）

［10］Zou Wenqiang， Pan Quanke， Wang Ling， et al. Efficient multiobjective optimization for an AGV energy-efficient scheduling problem with release time［J］. Knowledge-Based Systems， 2022， 242（2）： 45-56.

［11］王子意. 多AGV系統(tǒng)的路徑規(guī)劃與調(diào)度算法的研究［D］. 北京：北京郵電大學， 2019. （Wang Ziyi. Research on path planning and scheduling algorithms for multi AGV systems［D］. Beijing ：Beijing University of Posts and Telecommunications， 2019.）

［12］孟憲福， 張曉燕. 對等網(wǎng)絡環(huán)境下多目標約束的并行任務調(diào)度策略研究［J］. 計算機集成制造系統(tǒng)， 2008（4）： 761-766. （Meng Xianfu， Zhang Xiaoyan. Research on parallel task scheduling strategy with multi-objective constraints in peer-to-peer network environment［J］. Computer Integrated Manufacturing System， 2008（4）： 761-766.）

［13］Zlot R A， Stentz A T， Dias A B， et al. Multi-robot exploration controlled by a market economy［C］//Proc of IEEE International Confe-rence on Robotics and Automation. Piscataway， NJ： IEEE Press， 2002： 3016-3023.

［14］Das G P， McGinnity T M， Coleman S A， et al. A distributed task allocation algorithm for a multi-robot system in healthcare facilities［J］. Journal of Intelligent & Robotic Systems， 2015， 80（1）： 33-58.

［15］Garapati K， Roldan J J， Gatron M， et al. A game of drones： game theoretic approaches for multi-robot task allocation in security missions［C］//Proc of the 3rd Iberian Robotics Conference. Cham： Springer， 2017： 855-866.

［16］秦新立， 宗群， 李曉瑜，等. 基于改進蟻群算法的多機器人任務分配［J］. 空間控制技術與應用， 2018， 44（5）： 55-59. （Qin Xinli， Zong Qun， Li Xiaoyu， et al. Multi robot task allocation based on improved ant colony algorithm［J］. Space Control Technology and Applications， 2018， 44（5）： 55-59.）

［17］Wei Changyun， Ji Ze， Cai Boliang. Particle swarm optimization for cooperative multi-robot task allocation： a multi-objective approach［J］. IEEE Robotics and Automation Letters， 2020， 5（2）： 2530-2537.

［18］丁一， 袁浩， 方懷瑾，等. 考慮沖突規(guī)避的自動化集裝箱碼頭AGV優(yōu)化調(diào)度方法［J］. 交通信息與安全， 2022， 40（3）： 96-107. （Ding Yi， Yuan Hao， Fang Huaijin， et al. Optimization sche-duling method for automated container terminal AGV considering conflict avoidance［J］. Traffic Information and Safety， 2022， 40（3）： 96-107.）

［19］張子迎， 陳云飛， 王宇華，等. 基于啟發(fā)式深度Q學習的多機器人任務分配算法［J］. 哈爾濱工程大學學報， 2022， 43（6）： 857-864. （Zhang Ziying， Chen Yunfei， Wang Yuhua， et al. Multi robot task allocation algorithm based on heuristic deep Q-learning［J］. Journal of Harbin Engineering University， 2022， 43（6）： 857-864.）

［20］鄧輔秦， 黃煥釗， 譚朝恩，等. 結合遺傳算法和滾動調(diào)度的多機器人任務分配算法［J］. 計算機應用， 2023， 43 （12）： 3833-3839. （Deng Fuqin， Huang Huanzhao， Tan Chaoen， et al. Multi robot task allocation algorithm combining genetic algorithm and rolling scheduling［J］. Journal of Computer Applications， 2023， 43（12）： 3833-3839.）

［21］方耀寧， 郭云飛， 扈紅超，等. 一種基于sigmoid函數(shù)的改進協(xié)同過濾推薦算法［J］. 計算機應用研究， 2013，30（6）： 1688-1691. （Fang Yaoning， Guo Yunfei， Hu Hongchao， et al. An improved collaborative filtering recommendation algorithm based on sigmoid function［J］. Application Research of Computers， 2013， 30（6）： 1688-1691.）

［22］張遠春， 范秀敏， 駒田邦久. 基于仿真優(yōu)化的多種類型AGV數(shù)量配置優(yōu)化方法［J］. 中國機械工程， 2011， 22（14）： 1680-1685. （Zhang Yuanchun， Fan Xiumin， Kota Bangjiu. Optimization method for multiple types of AGV quantity allocation based on simulation optimization［J］. China Mechanical Engineering， 2011， 22（14）： 1680-1685.）

［23］張京釗， 江濤. 改進的自適應遺傳算法［J］. 計算機工程與應用， 2010， 46（11）： 53-55. （Zhang Jingzhao， Jiang Tao. Improved adaptive genetic algorithm［J］. Computer Engineering and Application， 2010， 46（11）： 53-55.）

［24］劉暢， 張承瑞， 孫玉璽. 改進自適應遺傳算法在多載AGV調(diào)度的應用研究［J］. 小型微型計算機系統(tǒng)， 2021， 42（11）： 2241-2245. （Liu Chang， Zhang Chengrui， Sun Yuxi. Research on the app-lication of improved adaptive genetic algorithm in multi load AGV scheduling［J］. Journal of Chinese Micro Computer System， 2021， 42（11）： 2241-2245.）