考慮任務行程時間的多載量自動導引車系統(tǒng)防死鎖任務調(diào)度

武 星 翟晶晶 樓佩煌 胡 亞 肖海寧

1.南京航空航天大學機電學院，南京，2100162.鹽城工學院機械工程學院，鹽城，224051

0 引言

自動導引車(automated guided vehicle，AGV)是一種最具代表性的物流輸送機器人，由多臺AGV構(gòu)成的AGV系統(tǒng)已廣泛應用于各種制造系統(tǒng)以及倉儲配送領域[1-3]。為了保證多臺AGV在同一工作空間中有序運行，需要研究任務調(diào)度[4]、路徑規(guī)劃[5]和交通管控[6]三項核心的系統(tǒng)級使能技術。其中，AGV系統(tǒng)任務調(diào)度為：當系統(tǒng)中存在多個物料配送任務及空閑AGV時，在滿足一定的約束條件下，確定各物料配送任務的執(zhí)行順序及其與空閑AGV的分配關系，使系統(tǒng)的某些性能達到最優(yōu)。

針對AGV系統(tǒng)任務調(diào)度問題，當前國內(nèi)外研究主要以單載量AGV為對象，其主要研究方法有：傳統(tǒng)分析方法、建模與仿真方法、智能優(yōu)化算法、混合優(yōu)化方法[7-9]。相對于傳統(tǒng)的每次裝卸一個/組載荷的單載量AGV，多載量AGV(如一臺牽引AGV拖帶多個數(shù)量可變的掛車)可在一次物料配送任務中，分別從多個發(fā)料點進行多個載荷的裝載，或到多個送料點進行多個載荷的卸載，顯然具有更高的單車運輸能力和更強的配送作業(yè)柔性。但目前關于多載量AGV任務調(diào)度問題的研究主要采用的是啟發(fā)式規(guī)則，HO等[10-14]將多載量AGV系統(tǒng)任務調(diào)度問題分解為裝卸載選擇調(diào)度[11]、卸載點訪問順序調(diào)度[12]、裝載點訪問順序調(diào)度[13]和裝載任務選擇調(diào)度[14]四個子問題，分別設計了相應的啟發(fā)式規(guī)則。在此基礎上，AZIMI等[15-17]借助計算機仿真工具分析了多種組合調(diào)度規(guī)則的實際調(diào)度效果，結(jié)合了線性回歸、離散偶數(shù)模擬和線性整數(shù)規(guī)劃三種數(shù)學方法，提出了一種用于優(yōu)化多載量AGV系統(tǒng)吞吐量的啟發(fā)式算法。LEE等[18]研究了系統(tǒng)資源配置對裝載及卸載規(guī)則的影響規(guī)律。RAMANAIAH等[19]分析了啟發(fā)式調(diào)度規(guī)則在不同導引路徑布局下的性能表現(xiàn)。

上述研究主要關注設計多載量AGV系統(tǒng)任務調(diào)度規(guī)則或分析任務調(diào)度規(guī)則的實際調(diào)度效果，缺乏考慮應用環(huán)境中的各種約束條件，如多載量AGV裝卸載順序、AGV容量、工位緩沖區(qū)容量、配送截止時間等。大量實驗結(jié)果表明[20-21]，忽略這些約束會使系統(tǒng)發(fā)生堵塞、死鎖，從而顯著降低整個調(diào)度系統(tǒng)的性能。AGV系統(tǒng)中的死鎖可分為因緩沖區(qū)容量不足引發(fā)的緩沖區(qū)死鎖以及因多個AGV之間路徑?jīng)_突導致的環(huán)路死鎖[22]。針對緩沖區(qū)死鎖，XIAO等[23]提出了一種將死鎖狀態(tài)臨界任務暫時禁止運行的死鎖避免策略；KALINOVCIC等[24]通過禁止將工件送往已堵塞的工位來避免死鎖，但保守的資源分配限制策略往往會降低系統(tǒng)運行效率。針對環(huán)路死鎖，ZHAO等[25]提出了一種基于動態(tài)資源預留的多AGV調(diào)度和避碰方法；XIAO等[26]提出了一種基于交通序列優(yōu)化策略的碰撞死鎖預防方法，并通過仿真結(jié)果驗證了上述方法的可行性和有效性。

實際上，環(huán)路死鎖是AGV系統(tǒng)交通管控或路徑規(guī)劃時所需面臨的問題，筆者所在團隊已在文獻[27]中進行了相關分析研究。而緩沖區(qū)死鎖則是AGV系統(tǒng)任務調(diào)度時必須解決的重點和難點問題。因此，本文以多載量AGV系統(tǒng)為研究對象，針對某復雜軍工產(chǎn)品裝配線[27]下多載量AGV系統(tǒng)的任務調(diào)度和緩沖區(qū)死鎖問題，建立了任務行程時間預測模型，提出了一種基于人工免疫-灰狼優(yōu)化(artificial immune-grey wolf optimization，AI-GWO)算法的多目標防死鎖任務調(diào)度方法。

1 總體方案

1.1 問題描述

該復雜軍工產(chǎn)品的生產(chǎn)計劃與物料配送過程既涉及機械、電氣組件的外協(xié)與采購，也包含機械零部件、電子元器件、組件、套件等各種物料與在制品在不同車間、不同工位之間的配送、轉(zhuǎn)運和出入庫等。按照傳統(tǒng)的裝配生產(chǎn)線布局與裝配人員工作安排，各工序操作現(xiàn)場分散，車間內(nèi)部半成品周轉(zhuǎn)耗時長，配送準時性差，裝配工位可能待料停產(chǎn)。

針對傳統(tǒng)配送準時性差的問題，考慮到裝配工位物料種類多、配送要求差異性大的實際需求，本文采用多載量AGV在輔料庫與裝配工位之間配送標準機械零件和電子元器件，利用單載量AGV在半成品庫與裝配工位之間配送用于部裝的套件、組件等。整條裝配生產(chǎn)線包括：A艙部裝線、C艙部裝線和艙段總裝線以及外協(xié)生產(chǎn)部裝的B艙、D艙和E艙的三條輸送線，裝配生產(chǎn)線中的AGV系統(tǒng)采用單向?qū)б窂骄W(wǎng)絡。

裝配線中每個工位都配有容量有限的關重件輸入緩沖區(qū)、輔料輸入緩沖區(qū)以及輸出緩沖區(qū)。當某個工位需要物料時，AGV從物料倉庫中裝載物料，按照路徑網(wǎng)絡中的最優(yōu)路徑，在截止時間前將物料送往相應裝配工位的輸入緩沖區(qū)。當工位所需物料齊全后開始裝配，裝配完成后工件進入輸出緩沖區(qū)。此時，裝配工位向AGV調(diào)度系統(tǒng)發(fā)出工件搬運請求，依次輸送到下一個工位或最終的成品庫。為聚焦多載量AGV任務調(diào)度的研究，本文沿用文獻[27]對物流配送過程的假設，并規(guī)定：多載量AGV從前往后依次裝載掛車，并以先進后出的方式卸載掛車。

為保證整條裝配線的高效有序運行，必須先保證各裝配工位的裝配物料準時配送。然而，各工位輸入、輸出緩沖區(qū)容量有限。當輸出緩沖區(qū)中工件未及時運出時，工位會因輸出緩沖區(qū)無剩余容量而堵塞；當裝配物料未及時送達某工位時，工位會因物料缺乏而待產(chǎn)。因此，多載量AGV系統(tǒng)的任務調(diào)度需要確定物料配送任務執(zhí)行順序及其與空閑AGV的分配關系，并防止工位緩沖區(qū)死鎖，從而保證AGV配送的準時性和裝配物料的齊套性。

1.2 研究方案

為解決多載量AGV系統(tǒng)的任務調(diào)度和緩沖區(qū)死鎖問題，本文構(gòu)建了包含實際應用約束的任務調(diào)度模型，提出了一種考慮任務行程時間的多載量AGV系統(tǒng)任務調(diào)度方案，如圖1所示，圖中藍色底紋所示內(nèi)容為本文所要研究的關鍵內(nèi)容。

圖1 總體方案Fig.1 General scheme

在任務調(diào)度模型中，多載量AGV裝卸載順序、AGV容量、工位緩沖區(qū)容量等約束相對易于建模，而任務行程時間因具有動態(tài)性和不確定性而難以預測，該約束還會直接影響準時性優(yōu)化目標。因此，首先針對AGV運動特性和交通延誤規(guī)律，構(gòu)建任務行程時間預測模型。為了求解得到最優(yōu)的任務執(zhí)行序列和AGV分配關系以及避免緩沖區(qū)死鎖，本文提出了一種帶防死鎖策略的任務調(diào)度優(yōu)化方法，利用死鎖避免規(guī)則禁止即將引發(fā)工位緩沖區(qū)死鎖的任務運行，基于AI-GWO算法優(yōu)化任務執(zhí)行順序，根據(jù)AGV負載均衡度進行配送任務分配。

2 任務調(diào)度建模

2.1 任務調(diào)度模型

多載量AGV調(diào)度是一個需要考慮多目標的數(shù)學建模問題。如圖1所示，本文以關重件、輔料等動態(tài)配送任務執(zhí)行序列及其AGV分配方案為決策變量，以物料配送準時率和路徑段交通負荷均衡度為綜合優(yōu)化目標，并以任務行程時間、物料緩沖區(qū)容量、AGV裝卸載順序、組件協(xié)調(diào)裝配等為約束條件構(gòu)建任務調(diào)度模型。其中，該模型的目標函數(shù)為

(1)

(2)

式中，f1為物料配送延遲率；f2為交通負荷不均衡度(即路徑擁堵率)；R為物料配送任務總數(shù)(即可分配任務的總數(shù))；De為第e個物料配送任務的延遲狀態(tài)；qi為第i條路徑上的車輛平均長度；s1i為第i條路徑段的長度；I為

(3)

(4)

其中，Te為第e個物料配送任務的延遲時間，其表達式為

Te=de-(Se+TCe)e=1，2，…，R

(5)

式中，de為第e個物料配送任務的交付時間；Se為第e個物料配送任務的開始時間；TCe為第e個物料配送任務的任務行程時間。

在任務調(diào)度模型中，任務行程時間因具有動態(tài)性和不確定性而難以預測，它不僅與單臺AGV所通過的運行路徑有關，還與整個系統(tǒng)的路網(wǎng)交通狀態(tài)有關，因此，本文將任務行程時間分解為自由行程時間與交通延誤時間，并建立相應的時間預測模型。

2.2 任務行程時間預測模型

任務行程時間分為自由行程時間和交通延誤時間兩部分。前者是指在沒有其他AGV干擾的情況下，單臺AGV在路徑網(wǎng)絡中的自由運行時間。后者是指由于受路網(wǎng)交通流分布及交通管控策略的影響，單臺AGV通過路徑網(wǎng)絡額外所需的等待時間。

2.2.1自由行程時間預測模型

自由行程時間受運行路徑、AGV 運動速度、裝卸載時間等多種因素的共同影響。對于不同類型的AGV，各影響因素也存在較大差異。在運行路徑方面，單載量AGV每次只配送一種零部件，其運行路徑取決于該零部件的裝卸載工位點。然而，多載量AGV每次輸送多節(jié)拖車，其運行路徑不僅取決于所有拖車的裝卸載工位點，還與拖車的裝卸順序密切相關，遠比單載量AGV的情況復雜。此外，AGV運動速度也非恒定值，受AGV運動學及動力學特性(執(zhí)行速度、轉(zhuǎn)彎速度、加減速特性等)、運行路徑段特征(單路徑段、直行路口、轉(zhuǎn)彎路口等)、承載狀態(tài)(空載、滿載、拖車類型等)等眾多因素的共同影響。為此，本文將所有裝卸載工位點之間的最優(yōu)單向路徑分解為典型路徑段，在考慮AGV加減速特性的情況下，假設AGV在路徑段、直行路口、轉(zhuǎn)彎路口的速度標量分別為v1、v2、v3，單載量AGV與多載量AGV自由行程時間的計算方法具體如下。

(6)

(7)

(8)

其中，γ為單載量AGV的速度因子。假設單載量AGV當前的負載量和額定負載量分別為Fs、Fes，單載量AGV負載系數(shù)為α，則

(9)

(10)

(11)

(12)

(13)

其中，δ為多載量AGV的速度因子。假設多載量AGV經(jīng)過某路徑段、直行路口或轉(zhuǎn)彎路口時拖車的編號和數(shù)量分別為p、P，第p個拖車的速度因子為εp，則

(14)

(15)

(16)

2.2.2交通延誤時間預測模型

在AGV任務執(zhí)行過程中，交通延誤時間的影響因素包括AGV拖車的長度、AGV之間的安全距離、單路徑段長度等。由于交通延誤時間受路網(wǎng)交通流分布及交通管控策略的共同影響，則它主要體現(xiàn)為因路徑堵塞而導致的路口等待時間。假設從當前任務裝載到卸載期間所需經(jīng)過的直行路口、轉(zhuǎn)彎路口的數(shù)量分別為S和C，所需經(jīng)過的直行路口、轉(zhuǎn)彎路口的編號分別為s和c，所經(jīng)過的第s個直行路口的長度和第c個轉(zhuǎn)彎路口的長度分別為s2s、s3c，某AGV到達路口時已在路口排隊的AGV編號和數(shù)量分別為a、A，則根據(jù)已在路口排隊的第a輛AGV的長度la和安全距離系數(shù)β(通常取值為0.6～1.0，本文取0.8)可以得出該AGV在直行路口和轉(zhuǎn)彎路口的累積延誤時間t2d、t3d分別為

(17)

(18)

其中，τa為已在路口排隊的第a輛AGV的速度因子，其表達式為

(19)

則任務的交通延誤時間為

Td=t2d+t3d

(20)

2.2.3任務行程時間預測模型

由于任務行程時間包含任務自由行程時間與交通延誤時間，因此根據(jù)式(10)、式(16)、式(20)可得第e個物料配送任務的任務行程時間TCe為

TCe=Tf+Td

(21)

根據(jù)任務行程時間數(shù)學模型，可確定待分配任務的執(zhí)行時間，并對任務進行排序和分配。然而，多載量AGV系統(tǒng)任務調(diào)度除了要考慮任務行程時間外，還需考慮環(huán)路死鎖、路徑交通流等系統(tǒng)約束。因此，本文針對上述多目標任務調(diào)度模型，研究了求解任務最優(yōu)執(zhí)行序列及其AGV分配方案的多目標優(yōu)化方法。

3 任務調(diào)度優(yōu)化方法

大多數(shù)已有研究的調(diào)度系統(tǒng)主要針對單載量AGV，通常采用基于啟發(fā)式規(guī)則的調(diào)度方法以降低問題復雜性。然而，本文研究的多載量AGV系統(tǒng)任務調(diào)度問題更加復雜，啟發(fā)式調(diào)度規(guī)則已不能滿足要求。

為了求解多載量AGV系統(tǒng)任務調(diào)度問題，本文結(jié)合人工免疫(AI)算法與灰狼優(yōu)化(GWO)算法的優(yōu)點，提出了一種基于人工免疫-灰狼優(yōu)化(AI-GWO)算法的混合多目標優(yōu)化方法。首先考慮工位緩沖區(qū)的容量，利用死鎖避免規(guī)則暫時禁止引發(fā)死鎖的任務運行，然后采用AI-GWO混合多目標優(yōu)化方法確定任務的執(zhí)行順序，最后基于負載均衡度進行空閑AGV的任務分配，以提高系統(tǒng)的任務準時率和路徑段的交通負荷均衡度。AGV任務調(diào)度的主要流程如下：

(1)當系統(tǒng)達到一個定時周期T時，進入步驟(2)。

(2)統(tǒng)計系統(tǒng)中所有的物料配送任務和空閑AGV，分別構(gòu)成待分配任務集和待調(diào)度AGV集。若待分配任務集或待調(diào)度AGV集為空集，則轉(zhuǎn)步驟(1)；反之，則進入步驟(3)。

(3)計算各工位的剩余容量和系統(tǒng)的可利用載量，根據(jù)死鎖避免規(guī)則從待分配任務集中去除被禁止的任務，未被禁止的任務構(gòu)成預分配任務集。若預分配任務集為空集，則轉(zhuǎn)步驟(1)；反之，則進入步驟(4)。

(4)計算預分配任務的數(shù)量RC和待調(diào)度AGV的總載量G。若RC≤G，此時預分配任務集即為可分配任務集，并進入步驟(6)；反之，則進入步驟(5)。

(5)根據(jù)任務緊迫度進行排序，選擇緊迫度排名前G的任務構(gòu)成可分配任務集，并進入步驟(6)。

(6)采用AI-GWO混合多目標優(yōu)化方法對可分配任務集進行任務排序，并進入步驟(7)。

(7)根據(jù)待調(diào)度AGV的工作負載狀態(tài)，將排序好的任務優(yōu)先分配給負載總量低的空閑AGV，并更新系統(tǒng)工位和AGV狀態(tài)后轉(zhuǎn)步驟(1)。

3.1 死鎖避免規(guī)則

工位緩沖區(qū)死鎖是指以下情形：當某工位及其輸入緩沖區(qū)、輸出緩沖區(qū)都被工件占滿時，若無AGV運離其輸出緩沖區(qū)的工件，則運送工件到輸入緩沖區(qū)的AGV因無法獲得釋放空間而一直等待卸載，該狀態(tài)稱為工位緩沖區(qū)堵塞。若所有AGV都處于這種堵塞狀態(tài)，則整個系統(tǒng)進入工位緩沖區(qū)死鎖，這將嚴重影響物料運送效率與任務準時率。

為避免工位緩沖區(qū)死鎖，筆者提出了多載量AGV死鎖避免方法[28]。根據(jù)每輛AGV的堵塞任務數(shù)得到AGV可利用載量，對于可利用載量不大于死鎖臨界值(本文取4)的AGV，禁止分配同時滿足以下兩個條件的任務：①起始工位剩余容量大于或等于0；②目標工位剩余容量小于或等于0。

所有未被禁止的任務構(gòu)成預分配任務集。如果預分配任務的數(shù)量RC大于待調(diào)度AGV的總載量G，則存在RC-G個任務缺乏空閑AGV進行搬運。為了保證任務準時率，以交付時間de來評價任務緊迫度，距離交付時間越近，任務越緊急。因此，在預分配任務集中選取交付時間de排名前G的物料配送任務構(gòu)成可分配任務集。

3.2 任務排序優(yōu)化算法

本文提出的AI-GWO混合多目標優(yōu)化方法的具體流程如圖2所示。

圖2 AI-GWO算法流程Fig.2 AI-GWO algorithm flow chart

(1)編碼。采用任務排序為算法編碼，可表示為B={b1，b2，…，br，…，bR}，其中r為任務br在所有可分配任務排序中的位置，R為可分配任務的總數(shù)。然后將B中元素依據(jù)排序位置(從前至后)和AGV的載量Av分成Z=RoundUp(R/Av)簇，以便于按簇將任務分配給AGV，其中RoundUp(·)表示向上取整函數(shù)。例如：假定系統(tǒng)中可分配任務序號為任務1至任務7，各任務的排序位置如表1所示，則對應的編碼B={5，3，6，1，7，4，2}，若多載量AGV的載量Av=4，則任務1至任務7可被分成2簇，其中{5，3，6，1}被分配給空閑AGV1，{7，4，2}被分配給空閑AGV2。

表1 可分配任務集及排序示例

(2)種群初始化。在種群初始化過程中，選取可分配任務的總數(shù)R作為種群規(guī)模。為了盡可能地將所有卸載工位點距離相近的任務分配給同一輛AGV，本文采用最大最小距離聚類算法[29]對前R/2個種群進行種群初始化，其余種群隨機產(chǎn)生。

(3)適應度計算。根據(jù)物料配送準時率(即1-f1)和路徑段交通負荷均衡度(即1-f2)，構(gòu)建多目標優(yōu)化的種群適應度函數(shù)，其表達式為

F=wa(1-f1)+wb(1-f2)

(22)

其中，wa、wb為兩個目標的權重系數(shù)，其取值由仿真分析獲得。

(4)社會等級分層。GWO算法優(yōu)化中最核心的操作是確定種群中最佳的三個個體，并讓其帶領其他個體往最優(yōu)解方向進行搜索。根據(jù)個體適應度從高到低的排序，將適應度前三的灰狼個體設置為α狼、β狼、δ狼，并以它們?yōu)槭最I對其他灰狼位置進行更新。

本研究中混合式學習班及傳統(tǒng)授課班期末均采用手機在線無紙化測試，按照試題庫隨機選題的方式進行考核，題型、題量及難易程度相當于助理會計師考試，試卷采用百分制，考核結(jié)果顯示，兩種授課班級平均成績分別是58.46分和47.75分，混合式學習班成績高于傳統(tǒng)授課班級22.45%；但最高、最低成績均出自于傳統(tǒng)授課班級，我們認為這可能與個別同學的基礎和個人的努力有關，不影響混合式學習的優(yōu)勢。

(5)位置更新操作。GWO算法雖然具有較好的搜索性能，但隨著迭代次數(shù)的增加，容易陷入局部最優(yōu)。因此，本文采用AIA算法的克隆變異操作進行種群位置更新，以增加種群多樣性，避免算法過早收斂。按照適應度從高到低排序選擇R1個(R1=R/4)精英個體進行克隆變異。其中，由社會等級分層得到的α狼、 β狼和δ狼必須參加克隆變異操作。

克隆操作如下：克隆精英種群中的所有個體并得到新的克隆種群，克隆后種群規(guī)模RG的表達式為

(23)

其中，g為精英種群中個體的編號；R1為精英種群規(guī)模，克隆種群種群規(guī)模RG與R1成正比；Round(·)表示取整函數(shù)；φ為0～1之間的隨機數(shù)；Eg為精英個體g在降序排列的精英種群中的序位。由于精英個體在種群中的序位是按個體適應度的高低排列的，因此精英種群中每個個體克隆的數(shù)量與個體自身的適應度有關。并且式(23)可以確保精英種群中的每個個體都有一定數(shù)量的克隆體。

變異操作如下：變異算子可以增加種群的多樣性，防止算法陷入局部最優(yōu)解，本文對常用的高斯變異算子進行了改進，表達式為

(24)

因為種群個體中每個基因在基因排序中的位置(即可分配任務的排序位置)為1～R中的不重復正整數(shù)，所以新基因在高斯變異后需要進行取整和取余操作，并形成臨時子代。為了保證臨時子代每個基因的排序不重復，臨時子代的基因需從第一個基因到第R個基因依次調(diào)整：若待調(diào)整基因與變異成功的基因不重復，則變異成功；否則舍棄此結(jié)果，并根據(jù)相近原則從1～R中選擇一個與前面結(jié)果不重復的整數(shù)作為該基因的變異結(jié)果。臨時子代個體經(jīng)過基因調(diào)整后可成為種群子代個體。

變異算子是通過采取某種基因突變的方式來實現(xiàn)局部搜索的，然而單級變異(即只進行一次變異操作)的搜索范圍較小，不容易跳出局部最優(yōu)解，因此，本文提出了一種多級變異策略，即以單級變異形成的子代為多級變異的父代，再次執(zhí)行變異操作形成新的子代，并從單級變異與多級變異的子代中選擇最優(yōu)的子代作為該次變異操作的子代。由于多級變異會消耗更多的資源，因此只有陷入局部最優(yōu)解時才啟用多級變異策略。本文以迭代次數(shù)來評價算法是否陷入局部最優(yōu)解，當?shù)螖?shù)φ≤50時，采用單級變異；當?shù)螖?shù)φ>50時，則采用多級變異策略，該策略可以增加種群多樣性，促進算法尋找全局最優(yōu)解。

(6)精英保留策略。將種群規(guī)模為R的父代種群和種群規(guī)模為RG的子代種群合并為一個大小為R+RG的新種群。在新種群中，對適應度相同的個體進行擁擠距離[30]排序，從中選擇出最優(yōu)的R個個體作為下一代的父代種群。

(7)終止條件。若種群規(guī)模不同，則得到最優(yōu)解的迭代次數(shù)也不同。為了在得到近似最優(yōu)解的同時避免算法陷入無限循環(huán)，本文以完成100次迭代過程為終止條件。

3.3 任務分配規(guī)則

可分配任務經(jīng)過排序后，本文采用AGV負載均衡度評價方法進行任務分配。首先計算每個空閑AGV已搬運完成的任務總距離，并按照搬運總距離升序的方式進行排列，將可分配任務按簇方式優(yōu)先分配給搬運總距離小的AGV。

4 仿真實驗

4.1 仿真模型創(chuàng)建

為驗證本文防死鎖任務調(diào)度方法的有效性，采用仿真軟件Plant Simulation創(chuàng)建裝配線物流系統(tǒng)的仿真模型，仿真界面參見文獻[27]。AGV和導引路徑分別使用Transporter和Track對象表示，工位點的輸入緩沖區(qū)、工位、輸出緩沖區(qū)分別用Buffer、SingleProc和Store對象表示。工位點功能通過在Track對象增加Sensor對象來實現(xiàn)，各種任務調(diào)度方法通過在Method對象中編制Simtalk程序來實現(xiàn)。多載量AGV系統(tǒng)的生產(chǎn)節(jié)拍為15 min，裝配工位點的輸入、輸出緩沖區(qū)容量為4，多載量AGV載量Av=4，AGV在各情況下的運行速度為：v1=1 m/s，v2=0.5 m/s，v3=0.5 m/s。仿真運行時，通過統(tǒng)計任務狀態(tài)來分析任務調(diào)度方法的性能(如求解速度、收斂性能等)。

4.2 仿真實驗數(shù)據(jù)分析

4.2.1任務行程時間預測實驗

任務行程時間受到AGV運動特性、任務路程、路網(wǎng)交通流等多因素影響，其中，路網(wǎng)交通流與路徑網(wǎng)絡中并發(fā)運行AGV的數(shù)量有關，AGV數(shù)量越多，路徑段交通流越大。因此，本文通過對比不同AGV數(shù)量下某一物料配送任務的任務行程時間預測值與實際值，以驗證上述任務行程時間預測模型的準確性，實驗結(jié)果如表2所示。

表2 任務行程時間預測實驗

由表2可知，當系統(tǒng)中AGV數(shù)量較少(小于或等于10輛)時，任務行程時間預測值與實際值相同，說明當路徑網(wǎng)絡交通不太擁堵時，預測模型的準確度很高。然而，隨著系統(tǒng)中AGV數(shù)量的增加(大于10輛)，任務行程時間預測值與實際值的誤差逐漸增大，但預測誤差最大不超過1%，且該誤差不隨AGV數(shù)量的增加而持續(xù)增大。實際上，該誤差主要來源于當發(fā)生擁堵時AGV需要與調(diào)度控制系統(tǒng)頻繁通信而耗費的時間?？梢?，上述任務行程時間預測模型是有效的。

4.2.2任務調(diào)度實驗

為了驗證本文任務調(diào)度方法的有效性，將AI-GWO算法與傳統(tǒng)的遺傳算法(GA算法)、GWO算法進行了對比，以適應度值來衡量各算法性能。本文以GA算法為優(yōu)化方法，通過仿真得到了適應度計算公式(式(22))中的權重系數(shù)wa、wb。假設某個調(diào)度周期內(nèi)，空閑AGV的數(shù)量為8，可分配任務數(shù)量為32(即種群規(guī)模為32)，算法的交叉概率為0.6，變異概率為0.2，分別設置5組取值不同的權重系數(shù)，實驗結(jié)果如表3所示。

表3 不同wa和wb取值下的適應度值

由表3可知，當wa、wb的取值分別為0.2、0.8時，種群的適應度值最高，此時系統(tǒng)的任務準時率和路徑段的交通負荷均衡度達到較優(yōu)值。因此，本文取該組權值計算適應度。

為了比較三種算法的調(diào)度效果，本文采用緩沖區(qū)死鎖避免規(guī)則設置了4組不同的可分配任務數(shù)和空閑AGV數(shù)量，如表4所示，采用仿真軟件Plant Simulation進行裝配線物流系統(tǒng)的運行仿真，各算法的適應度最優(yōu)解如圖3所示。

表4 系統(tǒng)環(huán)境參數(shù)

圖3 各算法的最優(yōu)解Fig.3 The optimal solution of each algorithm

由圖3可知，當系統(tǒng)中任務數(shù)量與AGV數(shù)量較少(可分配任務數(shù)不超過24)時，GA算法、GWO算法和AI-GWO算法求解出的最優(yōu)解是相同的，此時系統(tǒng)的任務調(diào)度問題比較簡單，說明所提新算法在處理小規(guī)模調(diào)度問題時優(yōu)勢不突出。然而，隨著系統(tǒng)中任務數(shù)量和空閑AGV數(shù)量的增加(可分配任務數(shù)大于24時)，相對于傳統(tǒng)的GA算法和GWO算法，本文AI-GWO算法所獲得的最優(yōu)解適應度值最高，所以準時率最高、路徑擁堵率最低。因為隨著多載量AGV系統(tǒng)任務調(diào)度問題復雜化，傳統(tǒng)的GA算法和GWO算法容易陷入局部最優(yōu)解，而AI-GWO算法具有較強的全局尋優(yōu)能力，用于求解較大規(guī)模的多載量AGV調(diào)度問題是有效的。

為了比較三種算法的收斂性能，以表4中第3種環(huán)境參數(shù)為例，采用仿真軟件Plant Simulation進行裝配線物流系統(tǒng)的運行仿真，適應度值收斂曲線見圖4。

圖4 適應度值收斂曲線Fig.4 Fitness value convergence curve

由圖4可知，當系統(tǒng)可分配任務數(shù)為32和空閑AGV數(shù)量為8時，AI-GWO算法較傳統(tǒng)GA算法和GWO算法具有更好的收斂速度和尋優(yōu)能力。在前40次迭代過程中，AI-GWO算法采用最大最小距離聚類算法初始化，這有利于該算法更快地尋找到最優(yōu)解。在迭代后期，GA算法和GWO算法均陷入局部最優(yōu)解，而AI-GWO算法在迭代50次后使用多級變異，具有更強的全局尋優(yōu)能力，足以跳出局部最優(yōu)解的限制，有利于搜索適應度更高的個體。并且，與傳統(tǒng)的GA算法和GWO算法相比，AI-GWO算法的最優(yōu)解適應度值提高了3%以上，進一步表明該算法具有更強的全局尋優(yōu)能力。

為進一步比較三種算法的運行速度，在第3種環(huán)境參數(shù)條件下，通過軟件仿真獲取算法的實際運行時間，實驗結(jié)果如表5所示。

表5 算法運行時間

由表5可知，AI-GWO算法較傳統(tǒng)的GA算法和GWO算法具有更快的運行速度，分別提高了約22%和31%。這將有利于提高整個AGV調(diào)度控制系統(tǒng)的實時性和運行效率。

5 結(jié)語

針對多載量AGV復雜任務調(diào)度控制問題，本文以最小化延遲率和交通負荷不均衡度為目標，建立了任務調(diào)度模型；分析了任務調(diào)度中的實際約束，并針對任務行程時間約束構(gòu)建了預測模型；針對任務調(diào)度模型提出了一種基于人工免疫-灰狼優(yōu)化(AI-GWO)算法的多目標防死鎖任務調(diào)度方法，利用死鎖避免規(guī)則禁止即將引發(fā)工位緩沖區(qū)死鎖的任務運行，并融合AI-GWO算法對任務執(zhí)行順序進行多目標優(yōu)化；最后根據(jù)AGV負載均衡度進行AGV任務分配，以提高系統(tǒng)的準時率和路徑段交通負荷均衡度。仿真結(jié)果表明，AI-GWO算法具有較好的尋優(yōu)能力和收斂速度，相比傳統(tǒng)的遺傳算法(GA算法)和灰狼優(yōu)化算法(GWO算法)，AI-GWO算法的運行速度分別提高了約22%和31%，可以保證系統(tǒng)的準時率，防止系統(tǒng)發(fā)生堵塞。