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

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

中圖分類號(hào)：TP391.9;TP11 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

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

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

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

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

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

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

1 問題描述

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

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

a）AGV從初始入口位置到第一個(gè)任務(wù)位置。

b）AGV搬運(yùn)任務(wù)貨架至揀貨臺(tái)取出貨物。

c）AGV搬運(yùn)空貨架從揀貨臺(tái)返回當(dāng)前任務(wù)位置。

d）AGV從當(dāng)前任務(wù)位置到下一任務(wù)位置。

2 參數(shù)設(shè)定與模型構(gòu)建

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

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

a）每個(gè)AGV同時(shí)只可以搬運(yùn)一個(gè)貨架，每個(gè)貨架同時(shí)只能由一個(gè)AGV進(jìn)行搬運(yùn)。

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

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

d）每個(gè)AGV速度相同且運(yùn)行過(guò)程中速度保持不變。

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

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

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

2.2 模型建立

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

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

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

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

2.2.2 基于AGV任務(wù)分配的下層模型

下層模型：

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ù)實(shí)際作業(yè)場(chǎng)景中的重要性程度，設(shè)置f1和f2的權(quán)重為ω1和ω2，∑ωα=1。因此，多目標(biāo)函數(shù)計(jì)算方法如式（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）

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

3 模型求解

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

3.1 改進(jìn)遺傳算法設(shè)計(jì)

3.1.1 初始化種群

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

3.1.2 編碼

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

3.1.3 選擇

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

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

1）交叉算子

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

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

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）為兩個(gè)個(gè)體相似度評(píng)價(jià)函數(shù)，如果其比值為1，則這兩個(gè)個(gè)體不進(jìn)行交叉；Ii和Ij表示個(gè)體i和j；λ1和λ2為行駛距離長(zhǎng)度與AGV序號(hào)累加值的權(quán)重，λ1=0.1，λ2=2；dis（Ii）、dis（Ij）分別為兩個(gè)個(gè)體的行駛距離長(zhǎng)度；m、n為個(gè)體i、j中的某一個(gè)AGV編號(hào)，QUANi為QUANj為兩個(gè)個(gè)體的AGV編碼總量。

2）變異算子

采用隨機(jī)位置染色體單點(diǎn)變異方式，按照變異概率Pm進(jìn)行變異，生成新的個(gè)體。重復(fù)操作直至所有個(gè)體都被訪問，變異時(shí)染色體的某個(gè)基因變異成某個(gè)AGV的序號(hào)。

3）基于sigmoid的自適應(yīng)策略

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

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

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

Sk=efkefk+1（14）

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

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為某一代種群中參與交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；fs′為某一代種群中變異個(gè)體的適應(yīng)度值； fave為某一代種群適應(yīng)度平均值；Sbest為適應(yīng)度最優(yōu)個(gè)體的sigmoid值；Save為某一代種群平均適應(yīng)度的sigmoid值；Sselected為fs對(duì)應(yīng)的sigmoid值；Sindividual為fs′對(duì)應(yīng)sigmoid值。改進(jìn)的自適應(yīng)交叉率由式（15）（16）計(jì)算得出，自適應(yīng)變異率由式（17）（18）計(jì)算得出。

3.1.5 災(zāi)變策略

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

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

3.2 模型求解流程

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

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

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

c）編碼。

d）仿真路徑實(shí)驗(yàn)：遍歷當(dāng)前種群中的染色體，構(gòu)成對(duì)應(yīng)的圖模型路徑進(jìn)行仿真實(shí)驗(yàn)。

（a）確定貨架位置、揀選臺(tái)位置、AGV初始位置、任務(wù)位置，形成相應(yīng)的地圖模型。

（b）設(shè)置AGV出入口到任務(wù)序列的第一個(gè)任務(wù)為第一段路徑、設(shè)置當(dāng)前任務(wù)到揀貨臺(tái)為第二段路徑、設(shè)置揀貨臺(tái)到當(dāng)前任務(wù)為第三段路徑、設(shè)置當(dāng)前任務(wù)到下一任務(wù)為第四段路徑。

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

（d）計(jì)算值。計(jì)算AGV完成任務(wù)經(jīng)過(guò)節(jié)點(diǎn)的節(jié)點(diǎn)負(fù)載量與行駛距離。

（e）實(shí)驗(yàn)終止條件。判斷AGV是否完成所有任務(wù)的揀選，若完成則輸出負(fù)載量和行駛距離，實(shí)驗(yàn)結(jié)束。

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

f）選擇。

g）交叉。

h）變異。

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

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

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

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

4 算例仿真

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

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

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

4.1 小規(guī)模算例

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

4.2 大規(guī)模算例

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

4.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

［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］宋海權(quán). 基于復(fù)雜網(wǎng)絡(luò)理論的網(wǎng)絡(luò)交通擁堵問題研究［D］. 成都： 西南交通大學(xué)， 2016. （Song Haiquan. Research of network traffic congestion based on complex networks theory［D］. Chengdu： Southwest Jiaotong University， 2016.）

［4］項(xiàng)俊平. 城市道路交通信號(hào)區(qū)域均衡控制方法及應(yīng)用研究［D］. 合肥： 中國(guó)科學(xué)技術(shù)大學(xué)， 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］許麗麗， 詹燕， 魯建廈，等. 四向穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)調(diào)度優(yōu)化［J］. 浙江大學(xué)學(xué)報(bào)：工學(xué)版， 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］周航， 秦實(shí)宏， 方?jīng)茇? 基于混合遺傳禁忌搜索算法的多機(jī)器人任務(wù)分配［J］. 自動(dòng)化與儀表， 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］李騰， 張茹蘭， 丁佩佩. 機(jī)器人履約系統(tǒng)任務(wù)分配與貨架儲(chǔ)位再指派聯(lián)合優(yōu)化［J］. 科學(xué)技術(shù)與工程， 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ī)劃算法與任務(wù)分配調(diào)度策略研究［D］. 杭州：浙江大學(xué)， 2022. （Li Yuan. Research on multi AGV path planning algorithm and task allocation and scheduling strategy［D］. Hangzhou： Zhejiang University， 2022.）

［9］于佳喬， 李巖. 基于改進(jìn)遺傳算法的自動(dòng)導(dǎo)航小車路徑規(guī)劃調(diào)度［J］. 機(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］. 北京：北京郵電大學(xué)， 2019. （Wang Ziyi. Research on path planning and scheduling algorithms for multi AGV systems［D］. Beijing ：Beijing University of Posts and Telecommunications， 2019.）

［12］孟憲福， 張曉燕. 對(duì)等網(wǎng)絡(luò)環(huán)境下多目標(biāo)約束的并行任務(wù)調(diào)度策略研究［J］. 計(jì)算機(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ìn)蟻群算法的多機(jī)器人任務(wù)分配［J］. 空間控制技術(shù)與應(yīng)用， 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ī)避的自動(dòng)化集裝箱碼頭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學(xué)習(xí)的多機(jī)器人任務(wù)分配算法［J］. 哈爾濱工程大學(xué)學(xué)報(bào)， 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］鄧輔秦， 黃煥釗， 譚朝恩，等. 結(jié)合遺傳算法和滾動(dòng)調(diào)度的多機(jī)器人任務(wù)分配算法［J］. 計(jì)算機(jī)應(yīng)用， 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ù)的改進(jìn)協(xié)同過(guò)濾推薦算法［J］. 計(jì)算機(jī)應(yīng)用研究， 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］張遠(yuǎn)春， 范秀敏， 駒田邦久. 基于仿真優(yōu)化的多種類型AGV數(shù)量配置優(yōu)化方法［J］. 中國(guó)機(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ìn)的自適應(yīng)遺傳算法［J］. 計(jì)算機(jī)工程與應(yīng)用， 2010， 46（11）： 53-55. （Zhang Jingzhao， Jiang Tao. Improved adaptive genetic algorithm［J］. Computer Engineering and Application， 2010， 46（11）： 53-55.）

［24］劉暢， 張承瑞， 孫玉璽. 改進(jìn)自適應(yīng)遺傳算法在多載AGV調(diào)度的應(yīng)用研究［J］. 小型微型計(jì)算機(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.）