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

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

0 引言

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

1.2 數(shù)學(xué)模型

1.2.1 符號(hào)定義

Ω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}為各裝配工位裝卸載工位點(diǎn)的集合，其中P0為輔料庫存區(qū)的裝卸載工位點(diǎn)。

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

v為AGV的運(yùn)行速度。

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

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

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

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

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

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

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

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

1.2.2 決策變量

1.2.3 優(yōu)化目標(biāo)

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

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

(1)

其中:

(2)

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

f2=max(min(?)),

(3)

其中：

(4)

1.2.4 約束條件

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

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

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

(13)

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

(14)

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

(15)

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

Ri≥0，?Wi∈ΩW。

(16)

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

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

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

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

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

2.2.1 問題編碼及初始種群

(1)問題編碼

(2)初始種群生成策略

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

(17)

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

(18)

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

(19)

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

(20)

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

(21)

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

(22)

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

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

(23)

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

(24)

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

上述每條規(guī)則根據(jù)對應(yīng)的效用值均可生成一工位補(bǔ)料順序序列，這些工位補(bǔ)料順序序列均作為初始種群的個(gè)體,而初始種群其他個(gè)體則完全隨機(jī)產(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)非支配排序后的父代種群中隨機(jī)選擇兩個(gè)不相同的個(gè)體進(jìn)入交叉操作，任一個(gè)體的選擇步驟如下：

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

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

(28)

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

(29)

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

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

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

(2)變異算子

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

2.2.4 帶精英保留策略與鄰域搜索的種群進(jìn)化機(jī)制

(30)

(31)

3 實(shí)驗(yàn)分析

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

3.1 初始種群生成策略的驗(yàn)證

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

3.2 種群進(jìn)化機(jī)制的驗(yàn)證

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

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

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

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

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

3.3 死鎖避免策略的驗(yàn)證

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

(32)

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

3.4 實(shí)際調(diào)度效果的驗(yàn)證

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

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

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

4 結(jié)束語

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

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