肖海寧，樓佩煌，武 星 ，翟晶晶，胡 亞,趙 斌

(1.鹽城工學院 機械工程學院，江蘇 鹽城 224051；2.南京航空航天大學 機電學院，江蘇 南京 210016)

0 引言

由多臺自動導(dǎo)引車(Automated Guided Vehicle，AGV)組成的AGV系統(tǒng)(AGV System，AGVS)是一種用于物料配送的多移動機器人系統(tǒng)，具有柔性及自動化程度高、運行噪音低、系統(tǒng)擴展能力強等諸多優(yōu)點，已成為標志性智能物流裝備，在倉儲物流、制造車間、港口運輸?shù)阮I(lǐng)域的應(yīng)用愈加廣泛[1-2]。在對AGVS規(guī)劃設(shè)計與優(yōu)化調(diào)控時需要解決導(dǎo)引路徑網(wǎng)絡(luò)設(shè)計[3-4]、任務(wù)調(diào)度[5]、交通管理[6]、路徑規(guī)劃[7]等諸多難題。其中，AGVS任務(wù)調(diào)度一直是AGVS研究領(lǐng)域的熱點，雖然國內(nèi)外關(guān)于AGVS任務(wù)調(diào)度問題的研究文獻較多，但多數(shù)是以傳統(tǒng)單載量AGVS為研究對象[8]，鮮見關(guān)于多載量AGVS任務(wù)調(diào)度問題的研究報道。然而，多載量AGVS因其單車運輸能力強、交通擁堵率低等優(yōu)勢[9-11]，已成為AGVS應(yīng)用的趨勢。

近年來，針對多載量AGVS任務(wù)調(diào)度問題，國內(nèi)外學者分別提出了相應(yīng)的離線靜態(tài)調(diào)度與動態(tài)調(diào)度方法。在AGVS離線靜態(tài)調(diào)度算法方面，文獻[12-13]針對多載量AGVS調(diào)度問題，構(gòu)建了相應(yīng)的調(diào)度模型及算法。然而，AGVS屬于典型的離散事件動態(tài)系統(tǒng)，離線靜態(tài)調(diào)度方案難以適應(yīng)系統(tǒng)的各種非理想條件或隨機因素。因而，基于啟發(fā)式調(diào)度規(guī)則的動態(tài)調(diào)度方法更具實際應(yīng)用價值。如HO等[14]將多載量AGVS任務(wù)調(diào)度問題分解為裝卸載選擇調(diào)度、卸載點訪問順序調(diào)度、裝載點訪問順序調(diào)度、裝載任務(wù)選擇調(diào)度4個子問題，并設(shè)計了多種調(diào)度規(guī)則[15]。在此基礎(chǔ)上，AZIMI[16]借助計算機仿真工具分析了多種組合調(diào)度規(guī)則的實際調(diào)度效果，并應(yīng)用逐步回歸方法研究了多目標優(yōu)化決策模型的構(gòu)建方法[17]。ANGRA等[18]分析了5種裝載任務(wù)選擇調(diào)度規(guī)則的實際效果。然而，以上研究均以一般作業(yè)車間為應(yīng)用背景，與車輛、飛機、導(dǎo)彈等復(fù)雜產(chǎn)品裝配制造應(yīng)用環(huán)境相比，對物料配送的準時化要求低，約束條件少，AGVS規(guī)模小。

以本文研究的車輛裝配制造應(yīng)用環(huán)境為例，由于車輛裝配制造工藝復(fù)雜、節(jié)拍快、物料種類多，且對配送準時性要求高，與港口應(yīng)用環(huán)境相比，車間空間相對有限，導(dǎo)致其物料配送多載量AGVS規(guī)模大、密度高，使得該應(yīng)用環(huán)境下的多載量AGVS調(diào)度問題呈現(xiàn)出高復(fù)雜性、動態(tài)性及不確定性，已成為整車企業(yè)亟待解決的關(guān)鍵難題。針對車輛裝配應(yīng)用環(huán)境下的多載量小車調(diào)度問題，周炳海教授研究小組首先按照拖車裝卸時的LIFO約束，將其分解為物料搬運任務(wù)生成、派遣決策、物料搬運任務(wù)選擇等四個決策子問題，其次，借助仿真模型，構(gòu)建了調(diào)度規(guī)則知識庫，在調(diào)度時根據(jù)產(chǎn)品配比，分別采用人工神經(jīng)網(wǎng)絡(luò)[19]、支持向量機[20]和強化學習[21]的方法，從知識庫中選擇最優(yōu)調(diào)度規(guī)則，解決了調(diào)度規(guī)則的動態(tài)選擇問題。然而，這些方法均基于單一或組合調(diào)度規(guī)則，優(yōu)點是決策時間短、響應(yīng)速度快。但調(diào)控時無法預(yù)測或評估調(diào)控方案的實際調(diào)控效果，不僅缺乏全局尋優(yōu)能力，還難以滿足系統(tǒng)多目標優(yōu)化協(xié)調(diào)控制的需求。與啟發(fā)式調(diào)度規(guī)則相比，基于仿生學的智能優(yōu)化算法優(yōu)化速度快、魯棒性好，具有較強的全局尋優(yōu)能力。近年來，一些研究人員已在單載量AGVS調(diào)度中引入遺傳算法[3]、粒子群算法[7]、花授粉算法[22]等智能優(yōu)化算法。以上研究表明，結(jié)合啟發(fā)式調(diào)度規(guī)則與智能優(yōu)化算法的優(yōu)勢，設(shè)計出的動態(tài)智能調(diào)控方法，不僅能夠獲得較優(yōu)的全局尋優(yōu)能力，還具有較快的響應(yīng)速度，能夠滿足系統(tǒng)多目標優(yōu)化調(diào)控的需求，為求解多載量AGVS任務(wù)調(diào)度問題提供了很好的思路。

其次，現(xiàn)有的多載量AGVS任務(wù)調(diào)度問題均未考慮各工作站所能容納掛車數(shù)量的約束。該約束屬于緩沖區(qū)容量約束，在對單載量AGVS的研究中[23]已證實：忽略該類約束會引發(fā)系統(tǒng)死鎖現(xiàn)象，最終使調(diào)度規(guī)則喪失有效性，是AGVS任務(wù)調(diào)度時必須解決的重點和難點問題。由于AGVS死鎖現(xiàn)象的引發(fā)條件與物料配送流程及應(yīng)用環(huán)境密切相關(guān)，因此AGVS死鎖問題的研究必須結(jié)合物料配送流程及其應(yīng)用環(huán)境。已有的關(guān)于第一類死鎖的研究均以作業(yè)車間應(yīng)用環(huán)境下的單載量AGVS[5,23]為研究對象，目前，尚未見關(guān)于多載量AGVS第一類死鎖現(xiàn)象的研究報道。有必要針對復(fù)雜產(chǎn)品裝配制造應(yīng)用環(huán)境下的多載量AGVS物料配送流程,探明死鎖現(xiàn)象引發(fā)條件，設(shè)計對應(yīng)的死鎖避免策略，并融入到多載量AGVS任務(wù)調(diào)度方法中。

本文以車輛裝配制造應(yīng)用環(huán)境中的大規(guī)模輔料配送多載量AGVS為研究對象，針對其任務(wù)調(diào)度難題，建立以最小化任務(wù)配送路程和最大化待料停產(chǎn)剩余時間為綜合優(yōu)化目標的任務(wù)調(diào)度數(shù)學模型，并通過分析死鎖現(xiàn)象引發(fā)條件, 設(shè)計了以保證系統(tǒng)中無阻塞AGV的防死鎖策略。結(jié)合啟發(fā)式調(diào)度規(guī)則與帶精英策略的非支配排序遺傳算法[24-25](fast elitist Non-dominated Sorting Genitic Algorithm,NSGA-Ⅱ)的優(yōu)勢，提出了基于改進NSGA-Ⅱ算法的多載量AGVS防死鎖任務(wù)調(diào)度方法，最后通過仿真實驗對所提出的調(diào)度方法進行了驗證。

1 問題描述及數(shù)學模型

1.1 問題描述

以某應(yīng)用于車輛內(nèi)飾裝配線的輔料配送多載量AGVS為例，其示意布局如圖1所示，該內(nèi)飾裝配線共48個裝配工位。在制車輛自工位1進入內(nèi)飾裝配線，依序通過各裝配工位，當車輛到達各工位時，裝配設(shè)備或操作工人根據(jù)裝配工藝要求，將零部件按規(guī)定類別和數(shù)量裝配至車輛。完成所有內(nèi)飾裝配的車輛自工位48離開內(nèi)飾裝配線。各工位裝配作業(yè)所需輔料由拖車式多載量AGV以掛車為單位配送至各工位掛車緩存區(qū)。中間為AGV單向?qū)б窂骄W(wǎng)絡(luò)。為了聚焦多載量AGVS任務(wù)調(diào)度問題,對輔料備料及配送流程進行如下假設(shè)：

(1)假設(shè)倉庫的備件能力充足，任一裝配工位所需輔料以齊套方式提前裝入掛車中，每輛掛車只能放置一個工位的輔料，但可同時放置多套輔料，滿載后的掛車位于零件庫存區(qū)，等待AGV配送。

(2)滿料掛車按照類似貨運列車的方式依次與拖車式AGV連接，AGV每次能夠拖運的掛車數(shù)量有上限；裝載后的多載量AGV從零件庫存區(qū)出發(fā)，按照滿料掛車后掛先卸的順序沿最短路徑依次前往各裝配工位，到達后卸載相應(yīng)掛車，AGV裝卸掛車的時間忽略不計。

(3)每個工位所能容納的掛車數(shù)量有限，若AGV到達工位時無掛車卸載空間，則AGV將一直沿卸載點所在最短環(huán)型路徑運行，直至獲得足夠的掛車卸載空間。

(4)AGV按順序卸完所有滿料掛車后，在任務(wù)調(diào)度系統(tǒng)的協(xié)調(diào)下，將空置掛車運回零件庫存區(qū)，即空置掛車回庫任務(wù)，運回后的空置掛車在零件庫存區(qū)重新裝入輔料以備后續(xù)配送。

(5)為了避免影響其他AGV運行，空閑AGV始終沿某環(huán)形路徑運行直至收到新的搬運任務(wù)。

(6)裝配線采用節(jié)拍作為基本時間單位,各工位的裝配作業(yè)耗時均為一個節(jié)拍時間，各工位在裝配作業(yè)開始時刻均需消耗一套輔料，若作業(yè)開始時緩存區(qū)缺料，則整條裝配線變?yōu)榇贤．a(chǎn)狀態(tài)。因此，為保證整條內(nèi)飾裝配線的高效穩(wěn)定運行，必須保證所有裝配工位不缺料。

1.2 數(shù)學模型

1.2.1 符號定義

ΩG={Gm|m∈N且1≤m≤NG},為多載量AGV的集合，其中Gm為第m輛AGV,NG為系統(tǒng)中的AGV總數(shù)。

ΩW={Wi|i∈N且1≤i≤NW}，為裝配工位的集合，其中Nw為系統(tǒng)中的工位總數(shù)。

ΩP={Pj|j∈N且1≤j≤Nw}為各裝配工位裝卸載工位點的集合，其中P0為輔料庫存區(qū)的裝卸載工位點。

d(Pi,Pj)為工位點Pi至工位點Pj的最短路程。

v為AGV的運行速度。

Sm為Gm完成本次所有任務(wù)所需行走的總路程。

τ(i,j)為AGV從工位點Pi直接運行至工位點Pj的平均時間，初始值為dij/v。

P(Gm)為Gm的當前動態(tài)位置。

CG為AGV所能掛載的最大掛車數(shù)。

Ci為工位Wi所能容納的掛車數(shù)量。

Ki為工位Wi的每輛掛車所能裝載的最大輔料套數(shù)。

ξ為車輛裝配線的生產(chǎn)節(jié)拍。

SQW={Wi…Wj…Wk}為各工位補料順序序列。

1.2.2 決策變量

1.2.3 優(yōu)化目標

由于物料配送的根本目的是保證各裝配工位輔料充足，避免內(nèi)飾裝配線出現(xiàn)待料停產(chǎn)現(xiàn)象，因此，本文選定的首要優(yōu)化目標是最大化內(nèi)飾裝配線待料停產(chǎn)剩余時間——內(nèi)飾裝配線距離因某工位缺料而進入停產(chǎn)狀態(tài)的時間。其次，為了提高多載量AGVS的運行效率，必須優(yōu)化AGV訪問各工位的順序，以減少AGV的運行路程，因此本文選定的第二個優(yōu)化目標為最小化任務(wù)配送路程，兩者分別表達為：

最小化任務(wù)平均配送路程:

(1)

其中:

(2)

最大化內(nèi)飾裝配線待料停產(chǎn)剩余時間：

f2=max(min(?)),

(3)

其中：

(4)

1.2.4 約束條件

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

其中：式(5)表示Gm不可同時執(zhí)行空置掛車回庫任務(wù)和滿料掛車配送任務(wù)；式(6)表示AGV每次掛載的掛車數(shù)量不可超過其所能掛載的最大掛車數(shù)；式(7)為工位掛車緩存區(qū)容量限制；式(8)～式(12)為AGV執(zhí)行任務(wù)時必須滿足的順序及時間約束，式(8)表示只有當空閑AGV從其?？奎c行駛至零件庫存區(qū)，滿料掛車才可開始裝載，式(9)表示AGV必須按順序配送滿料掛車，式(10)表示空閑AGV必須從其?？课恢眯旭傊料鄳?yīng)工位，第一輛空置掛車才可開始裝載，式(11)表示AGV必須按順序裝載空置掛車，式(12)表示AGV裝載所有空置掛車后，必須行駛至零件庫存區(qū)才可卸載所有空置掛車。

1.3 系統(tǒng)死鎖現(xiàn)象及其引發(fā)條件

如圖2所示，G1正承擔工位W47的滿料掛車配送任務(wù)，但由于工位W47當前已無掛車緩存空間，此時，若無其他AGV執(zhí)行工位W47的空置掛車回庫任務(wù)，工位W47將始終無法釋放緩存空間，按照假定條件(3)，G1只能沿卸載點所在最短環(huán)型路徑運行，這種狀態(tài)稱為AGV的阻塞。若系統(tǒng)中所有AGV都阻塞，則所有AGV將一直無法卸載，這種狀態(tài)稱為系統(tǒng)死鎖。為了確定AGV是否處于阻塞狀態(tài)，必須首先確定各工位所能容納的掛車剩余空間。工位Wi所能容納的掛車剩余空間Ri定義為：

(13)

因此，若Gm承擔了某工位的滿料掛車配送任務(wù)，且該工位的掛車緩存區(qū)剩余空間為0，則Gm為阻塞AGV，可描述為：

(14)

因此，系統(tǒng)進入死鎖的條件為：

(15)

本文所采用的死鎖避免策略為：在任何時刻保證系統(tǒng)中任一工位的掛車剩余空間均非負，從而避免系統(tǒng)中出現(xiàn)阻塞AGV, 即：

Ri≥0，?Wi∈ΩW。

(16)

綜上所述，面向車輛裝配制造的多載量AGVS任務(wù)調(diào)度問題不僅需要確定任務(wù)的執(zhí)行順序及其與AGV的分配關(guān)系、各滿料/空置掛車掛載數(shù)量，還需考慮各工位掛車空間、AGV掛載能力等約束，并避免系統(tǒng)進入死鎖狀態(tài)，決定了其具有決策變量及優(yōu)化目標多、約束條件復(fù)雜的特點，增加了任務(wù)調(diào)度問題的求解難度。

2 前瞻性防死鎖任務(wù)調(diào)度方法

雖然面向車輛裝配制造的多載量AGVS任務(wù)調(diào)度問題決策變量多，但其根本目的是保證各裝配工位輔料充足，因此，本文結(jié)合NSGA-Ⅱ與啟發(fā)式調(diào)度規(guī)則的優(yōu)勢，提出了以工位補料順序優(yōu)化為切入點的前瞻性防死鎖任務(wù)調(diào)度方法，其整體流程如圖3所示。首先通過構(gòu)建的工位補料順序啟發(fā)式生成規(guī)則，生成工位補料順序方案集，并將其作為NSGA-Ⅱ初始種群中的部分個體；然后，以NSGA-Ⅱ為主控優(yōu)化流程，不斷進化產(chǎn)生新的工位補料順序種群。當工位補料順序集中的個體需要評價時，以啟發(fā)式指派流程確定各任務(wù)與AGV的分配關(guān)系，并根據(jù)前瞻性預(yù)測機制和防死鎖策略分別確定各工位所需裝載/配送的空置或滿料掛車數(shù)，生成工位補料順序方案對應(yīng)的調(diào)度方案，進而利用構(gòu)建的多目標優(yōu)化函數(shù)實現(xiàn)對方案個體的評價，具體策略詳述如下。

2.1 任務(wù)調(diào)度流程決策周期

2.2 帶精英策略與鄰域搜索的改進非支配排序遺傳算法

2.2.1 問題編碼及初始種群

(1)問題編碼

(2)初始種群生成策略

1)工位當前空置掛車數(shù)量多者優(yōu)先(More Empty Trailers Current are Preferred，METCP),

(17)

2)工位當前非空掛車數(shù)量少者優(yōu)先(Less Non-empty Trailers Current is Preferred，LNTCP),

(18)

3)工位當前零件套數(shù)少者優(yōu)先(Less Sets of parts Current is Preferred，LSPCP),

(19)

4)基于系統(tǒng)當前狀態(tài)的多屬性規(guī)則(Multi-attribute Rule based on Current System Status,MRBCSS),

(20)

5)工位下次補料時空置掛車數(shù)量多者優(yōu)先(More Empty Trailers in the Next Feeding are Preferred，METNFP),

(21)

6)工位下次補料時非空掛車數(shù)量少者優(yōu)先(Less Non-empty Trailers in the Next Feeding are Preferred，LNTNFP),

(22)

式中 Ceil()表示向上取整運算。

7)工位下次補料時零件套數(shù)少者優(yōu)先(Less Sets of Parts in the Next Feeding are Preferred，LSPNFP),

(23)

8)基于工位下次補料時系統(tǒng)狀態(tài)的多屬性規(guī)則(Multi-attribute Rule based on System Status in the Next Feeding,MRBSSNF),

(24)

式中Ceil()表示向上取整運算。

上述每條規(guī)則根據(jù)對應(yīng)的效用值均可生成一工位補料順序序列，這些工位補料順序序列均作為初始種群的個體,而初始種群其他個體則完全隨機產(chǎn)生。

2.2.2 啟發(fā)式解碼決策

(1)空閑AGV分組決策

(2)空置掛車回庫任務(wù)調(diào)度決策

(25)

(26)

轉(zhuǎn)步驟5。

(3)滿料掛車配送任務(wù)調(diào)度決策

(27)

2.2.3 遺傳算子

(1)交叉算子

從經(jīng)非支配排序后的父代種群中隨機選擇兩個不相同的個體進入交叉操作，任一個體的選擇步驟如下：

步驟1確定個體所在的排序等級，個體所在排序等級r被選中的概率δ(r)為：

δ(r)=δ(1)ρ(r-1)。

(28)

式中：ρ為概率因子，0<ρ<1；δ(1)為排序等級1的個體被選中的概率，其需要根據(jù)種群非支配排序的最高等級max(r)和概率因子ρ計算，

(29)

該方法可保證個體排序等級越低，選中概率越高，且所有排序等級選中概率總和為1。

步驟2將排序等級r所有個體根據(jù)其擁擠度排序，采用輪盤賭的方法確定被選中個體。

交叉算子的示意圖如圖6所示，假定兩個父代個體分別為Parent1和Parent2，則隨機選擇兩個交叉位置Pos1和Pos2，將Parent1交叉點間的工位序列按照其在Parent2中的順序重新排列，將重新排列后的Parent1作為子代個體Child。

(2)變異算子

變異操作示例如圖7所示，隨機選擇兩個交叉位置,并交換兩位置編碼，經(jīng)變異后的個體需驗證其是否在父代種群中出現(xiàn)過，若父代種群中已出現(xiàn)此個體，需重新進行交叉、變異操作。

2.2.4 帶精英保留策略與鄰域搜索的種群進化機制

(30)

(31)

3 實驗分析

為驗證所提出的防死鎖任務(wù)調(diào)度方法的效果，本文以應(yīng)用于某新能源汽車內(nèi)飾裝配線輔料輸送的多載量AGVS為例，利用Tecnomatix Plant Simulation 15.0軟件開發(fā)了多載量AGVS仿真分析平臺，仿真平臺界面如圖8所示，該內(nèi)飾裝配線共45個裝配工位，規(guī)劃的生產(chǎn)節(jié)拍ξ為60 s，多載量AGV所能掛載的最大掛車數(shù)CG為5，AGV運行速度為1 m/s, 通過該仿真平臺從以下幾方面對本文所提出的防死鎖任務(wù)調(diào)度方法進行驗證。

3.1 初始種群生成策略的驗證

本文NSGA-Ⅱ初始種群中的個體來源有兩類：一類為隨機產(chǎn)生，另一類通過設(shè)計的啟發(fā)式規(guī)則產(chǎn)生。通過仿真平臺分析初始種群非支配排序后兩類個體的分布情況以驗證該策略的效果，以種群規(guī)模為45為例，幾種隨機算例初始種群兩類個體的分布情況如圖9所示，以圖9a所示的初始種群分布情況為例，在構(gòu)成非支配前沿的3個個體中，有兩個由啟發(fā)式規(guī)則產(chǎn)生，而其他啟發(fā)式規(guī)則產(chǎn)生的個體也普遍優(yōu)于隨機個體，這表明通過設(shè)計啟發(fā)式規(guī)則生成初始種群的部分個體，能夠顯著提高初始種群的質(zhì)量,有利于提高NSGA-Ⅱ的收斂速度。

3.2 種群進化機制的驗證

本文在傳統(tǒng)NSGA-Ⅱ種群進化機制的基礎(chǔ)上，進一步引入鄰域搜索以提高算法的收斂速度。為了驗證該策略的優(yōu)勢，本文利用仿真平臺對比3種進化機制性能：

(1)傳統(tǒng)NSGA-Ⅱ(Tradition NSGA-Ⅱ, TNSGA-Ⅱ)算法進化機制。僅帶精英保留策略的進化機制，交叉概率為1，即全部交叉，變異概率為0.1，種群規(guī)模為45。

(2)改進的NSGA-Ⅱ(Improved NSGA-Ⅱ, INSGA-Ⅱ)算法進化機制。本文提出的帶精英保留策略與鄰域搜索的種群進化機制，參數(shù)與TNSGA-Ⅱ相同。

(3)多目標粒子群算法[27](Multi-objective Optimization Particle Swarm Optimization，MOPSO)的進化機制。粒子群規(guī)模設(shè)置為45，主要策略簡要介紹如下：Archive集的更新策略：Archive集用于保存算法已搜索到的所有非支配解，本文實驗時，粒子群每輪更新后的所有粒子均與舊的Archive集組合并進行非支配排序，將排序后的非支配前沿作為新的Archive集；gBest的選擇策略：某粒子需要更新時，均從當前Archive集中選擇距離該粒子最近的個體作為其gBest；pBest 的更新策略：pBest用于記錄某粒子搜索到的最優(yōu)解，本文實驗時，某粒子更新后需驗證新個體與對應(yīng)pBest的支配關(guān)系，若新個體支配pBest，則將pBest更新為新個體；粒子位置更新策略：參考鄧新國等[27]提出的方法。

當系統(tǒng)中的AGV數(shù)量為45時，利用仿真平臺記錄3種進化機制下的種群非支配前沿每隔0.3 s的更新情況，每種進化機制分別運行3次，將相同進化機制相同時間間隔搜索到的非支配前沿合并并重新進行非支配排序，取得3次實驗的綜合非支配前沿作為每種進化機制的評價依據(jù)，各前沿個體對應(yīng)的各目標函數(shù)值如圖10所示，圖中“MOPSO-0.0”表示MOPSO在0.0秒時的非支配前沿。由圖10可知，隨著進化代數(shù)的增加，3種進化機制的非支配前沿均能夠向優(yōu)化方向收斂，這表明：通過智能優(yōu)化算法的進化機制能夠進一步優(yōu)化啟發(fā)式調(diào)度規(guī)則產(chǎn)生的初始化個體，從而實現(xiàn)對調(diào)度方案的優(yōu)化。將MOPSO與TNSGA-Ⅱ、INSGA-Ⅱ可知，MOPSO在0.3 s的收斂性優(yōu)于TNSGA-Ⅱ和INSGA-Ⅱ，但隨著進化時間的延長，MOPSO的非支配前沿更新減緩，明顯劣于TNSGA-Ⅱ和INSGA-Ⅱ，這表明MOPSO比較容易收斂到局部Pareto前沿，全局尋優(yōu)能力還有待提升。對比TNSGA-Ⅱ與INSGA-Ⅱ可知，INSGA-Ⅱ在相同進化時間下的非支配前沿始終優(yōu)于TNSGA-Ⅱ，在0.9 s時，INSGA-Ⅱ所能取得的所有AGV平均任務(wù)總路程比TNSGA-Ⅱ低約3%，表明鄰域搜索的引入能夠加速非支配個體向更優(yōu)方向收斂，從而提高NSGA-Ⅱ的收斂速度。

3.3 死鎖避免策略的驗證

本文在滿料掛車配送任務(wù)調(diào)度決策中根據(jù)式(27)計算為工位配送的滿料掛車數(shù)，該策略可避免系統(tǒng)中出現(xiàn)AGV阻塞，從而避免系統(tǒng)死鎖。為了驗證該策略的有效性，利用仿真平臺對比下列兩類方法的實際調(diào)度效果。

(32)

如圖11和圖12所示，當AGV數(shù)量為45輛時，由于沒有采用死鎖避免策略且AGV數(shù)量較少，導(dǎo)致TNSGA-Ⅱ-N、INSGA-Ⅱ-N和MOPSO-N3種方法10次仿真均陷入死鎖狀態(tài)，平均單位小時產(chǎn)能極低，均在10以下。隨著AGV數(shù)量的上升，三種方法10次仿真發(fā)生死鎖的次數(shù)有所降低，然而，即便是AGV數(shù)量達到65輛時，TNSGA-Ⅱ-N、INSGA-Ⅱ-N和MOPSO-N3種方法依然會出現(xiàn)死鎖現(xiàn)象。而TNSGA-Ⅱ、INSGA-Ⅱ和MOPSO3種方法由于采用了本文所提出的死鎖避免策略，3種方法在各AGV數(shù)量下均未出現(xiàn)死鎖現(xiàn)象，且如圖11所示，TNSGA-Ⅱ、INSGA-Ⅱ和MOPSO這3種方法所能實現(xiàn)的單位小時產(chǎn)能均遠高于TNSGA-Ⅱ-N、INSGA-Ⅱ-N和MOPSO-N。這說明死鎖避免策略是必須且高效的。

3.4 實際調(diào)度效果的驗證

如圖13所示，當AGV數(shù)量低于50輛時，由于AGVS搬運能力不足，內(nèi)飾裝配線易出現(xiàn)待料停產(chǎn)現(xiàn)象，難以達到60 s的生產(chǎn)節(jié)拍要求，因此，如圖13所示，仿真平臺在各方法的調(diào)度下，單位小時產(chǎn)能均低于60輛/小時。隨著AGV數(shù)量的增多，物料運輸能力逐步提升，各方法所能實現(xiàn)的單位小時產(chǎn)能逐步提升，當AGV數(shù)量多于50輛時，本文所提出的INSGA-Ⅱ最先達到60 s的生產(chǎn)節(jié)拍要求，而且在各AGV數(shù)量下，INSGA-Ⅱ能夠?qū)崿F(xiàn)的單位小時產(chǎn)能均最高，這表明與其他方法相比，INSGA-Ⅱ有利于改善各工位待料停產(chǎn)狀況，從而提高內(nèi)飾裝配線產(chǎn)能。而TNSGA-Ⅱ和MOPSO的單位小時產(chǎn)能也高于啟發(fā)式調(diào)度規(guī)則，這表明通過智能優(yōu)化算法的進化機制能夠優(yōu)化啟發(fā)式調(diào)度規(guī)則產(chǎn)生的初始調(diào)度方案，從而提高內(nèi)飾裝配線產(chǎn)能。MOPSO由于容易收斂到局部Pareto前沿，單位小時產(chǎn)能略低于TNSGA-Ⅱ。在8條啟發(fā)式調(diào)度規(guī)則中，MRBSSNF所能實現(xiàn)的單位小時產(chǎn)能最高，這是因為MRBSSNF屬于前瞻性的多屬性規(guī)則，其不僅關(guān)注系統(tǒng)在當前的狀態(tài)屬性指標，還通過前瞻性預(yù)測機制提前考慮了系統(tǒng)在未來時刻多個狀態(tài)屬性指標，因而能夠獲得比其他調(diào)度規(guī)則更優(yōu)的性能。

所有AGV平均單次任務(wù)執(zhí)行時間如圖14所示，本文所提出的INSGA-Ⅱ在各AGV數(shù)量下的平均執(zhí)行時間均最短，TNSGA-Ⅱ和MOPOS略高，啟發(fā)式調(diào)度規(guī)則性能相對較差，這表明本文所提出的INSGA-Ⅱ 通過優(yōu)化各工位訪問順序，有助于降低AGV單次任務(wù)路程時間，從而提高AGVS的運行效率，結(jié)合圖13與圖14可知，INSGA-Ⅱ 能夠以較低的任務(wù)執(zhí)行時間獲得更高的內(nèi)飾裝配線產(chǎn)能。

如圖14所示，隨著AGV數(shù)量的上升，各調(diào)度方法所有AGV平均單次任務(wù)執(zhí)行時間均顯著上升，造成這一現(xiàn)象的主要原因是：①隨著AGV數(shù)量的上升，路網(wǎng)將更為擁堵，增加了AGV因路徑?jīng)_突而造成的交通延誤時間；②隨著AGV數(shù)量的上升，物料輸送能力得以提升，各工位空置掛車或滿料掛車能夠及時運送，因此，AGV每次為單個工位運送的空載掛車或滿料掛車較少，增加了AGV每次任務(wù)可訪問的工位數(shù)，造成AGV平均單次任務(wù)路程和執(zhí)行時間增加。因此，實際內(nèi)飾裝配線運行時，為了提高AGVS的運行效率并降低投資成本，在滿足生產(chǎn)節(jié)拍的基礎(chǔ)上，應(yīng)盡量減少系統(tǒng)中的AGV數(shù)量。

4 結(jié)束語

多載量AGV因其單車運輸能力更強、交通擁堵率低等優(yōu)勢，在工業(yè)場合具有廣闊的應(yīng)用前景，本文以車輛裝配應(yīng)用環(huán)境中的大規(guī)模輔料配送多載量AGVS為研究對象，首先建立了以最小化任務(wù)配送路程和最大化待料停產(chǎn)剩余時間為綜合優(yōu)化目標的任務(wù)調(diào)度數(shù)學模型，分析了多載量AGVS死鎖引發(fā)的條件，并設(shè)計了相應(yīng)的死鎖避免策略。其次，針對多目標優(yōu)化數(shù)學模型的特點，結(jié)合啟發(fā)式調(diào)度規(guī)則與NSGA-Ⅱ算法的優(yōu)勢，提出了基于改進NSGA-Ⅱ算法的多載量AGVS防死鎖任務(wù)調(diào)度方法，設(shè)計了結(jié)合前瞻性預(yù)測機制和防死鎖策略的個體解碼決策流程，為了提高NSGA-Ⅱ初始種群的質(zhì)量，設(shè)計了多個啟發(fā)式規(guī)則以生成構(gòu)成初始種群的部分優(yōu)質(zhì)個體；為了提高NSGA-Ⅱ算法的收斂速度，設(shè)計了帶精英保留策略與鄰域搜索的種群進化機制；最后，利用Tecnomatix Plant Simulation 15.0軟件開發(fā)了多載量AGVS仿真平臺，通過仿真平臺對本文方法進行了驗證，仿真結(jié)果表明：通過啟發(fā)式規(guī)則生成初始種群的部分優(yōu)質(zhì)個體能夠顯著提升初始種群的質(zhì)量；鄰域搜索的引入能夠加速非支配個體向更優(yōu)方向收斂，從而提高NSGA-Ⅱ的收斂速度；與啟發(fā)式調(diào)度規(guī)則、傳統(tǒng)NSGA-Ⅱ和MOPOS相比，本文所提出的防死鎖任務(wù)調(diào)度方法，能夠以更低的任務(wù)執(zhí)行時間獲得更高的內(nèi)飾裝配線產(chǎn)能。

未來將針對多目標優(yōu)化任務(wù)調(diào)度數(shù)學模型的特點，進一步構(gòu)建啟發(fā)式調(diào)度規(guī)則庫，結(jié)合啟發(fā)式調(diào)度規(guī)則與智能優(yōu)化算法兩者優(yōu)勢，研究性能更為優(yōu)越的任務(wù)調(diào)度新方法。