自動(dòng)導(dǎo)向小車與加工設(shè)備多目標(biāo)集成調(diào)度的聚類遺傳算法

鄒裕吉 宋豫川 王馨坤 王 毅

重慶大學(xué)機(jī)械傳動(dòng)國家重點(diǎn)實(shí)驗(yàn)室，重慶，400044

0 引言

大規(guī)模定制化和多品種小批量的生產(chǎn)模式逐漸成為車間生產(chǎn)的主流。該種模式下，產(chǎn)品種類繁多且工藝流程各不相同，導(dǎo)致物流系統(tǒng)具有任務(wù)多、流程變化大、動(dòng)態(tài)實(shí)時(shí)性強(qiáng)、實(shí)時(shí)性高等特點(diǎn)。AGV作為一種集成了多種先進(jìn)技術(shù)的物流裝備能很好地滿足這種需求[1]，因此越來越多的車間使用AGV來完成工件的運(yùn)輸任務(wù)。這種情況下，AGV和加工設(shè)備的協(xié)同工作對(duì)提高生產(chǎn)效率至關(guān)重要。傳統(tǒng)的車間調(diào)度方案往往不考慮AGV在車間生產(chǎn)的作用，對(duì)現(xiàn)代化生產(chǎn)車間的指導(dǎo)性存在不足，因此，面向復(fù)雜生產(chǎn)環(huán)境的AGV與加工設(shè)備的集成調(diào)度越來越受學(xué)者的關(guān)注。

AGV和加工設(shè)備集成調(diào)度問題可以分為三個(gè)子問題：加工設(shè)備調(diào)度、AGV調(diào)度、AGV路徑規(guī)劃。為降低問題的復(fù)雜性，有學(xué)者在不考慮路徑?jīng)_突的前提下對(duì)該問題展開研究。ULUSOY等[2]將AGV和加工設(shè)備集成調(diào)度作為研究對(duì)象，假設(shè)AGV在只能沿路徑單向行駛的情況下，應(yīng)用遺傳算法求解調(diào)度問題，并建立標(biāo)準(zhǔn)算例庫。此后，許多學(xué)者按照這種思路求解AGV與加工設(shè)備集成調(diào)度問題，即將AGV在不同機(jī)器之間的運(yùn)行時(shí)間假設(shè)為常數(shù)，而實(shí)際生產(chǎn)車間中，AGV往往沿著固定的軌道運(yùn)行且可雙向行駛，因此AGV之間發(fā)生路徑?jīng)_突是不可避免的。于是有學(xué)者開始研究考慮路徑?jīng)_突的AGV與加工設(shè)備的集成調(diào)度問題。SAIDIMEHRABAD等[3]建立了一個(gè)由車間調(diào)度和無沖突路徑組成的數(shù)學(xué)模型，提出的二階段蟻群算法先解決AGV的分配問題，再解決AGV的無沖突路徑規(guī)劃問題，分析了不同數(shù)量AGV下的最大完工時(shí)間的變化情況。LYU等[4]提出一種改進(jìn)遺傳算法來求解以最大完工時(shí)間為優(yōu)化目標(biāo)的AGV和加工設(shè)備的集成調(diào)度問題，實(shí)驗(yàn)結(jié)果表明：在可解決AGV沖突的情況下，單道雙向路徑的路網(wǎng)系統(tǒng)可以進(jìn)一步提高生產(chǎn)效率。多目標(biāo)優(yōu)化不會(huì)只注重一個(gè)目標(biāo)的優(yōu)化，可以平衡生產(chǎn)系統(tǒng)的各項(xiàng)指標(biāo)，逐漸引起大家的重視。REEDYB等[5]研究了AGV與加工設(shè)備集成的多目標(biāo)調(diào)度問題，以最大完工時(shí)間、工件平均流動(dòng)時(shí)間和工件平均拖期為優(yōu)化目標(biāo)，在非柔性作業(yè)車間中不考慮路徑?jīng)_突的前提下，提出一種混合遺傳算法。劉二輝等[6]提出一種改進(jìn)花授粉算法來求解AGV和加工設(shè)備的集成調(diào)度問題，在AGV可以自由行走的環(huán)境中，將最大完工時(shí)間和AGV利用率作為優(yōu)化目標(biāo)，從系統(tǒng)可靠性、成本、效率等多個(gè)角度分析并確定系統(tǒng)最優(yōu)的AGV數(shù)量，該方法不足之處在于將兩個(gè)目標(biāo)獨(dú)立優(yōu)化，不是真正意義上的多目標(biāo)優(yōu)化。

綜上所述，考慮路徑?jīng)_突的AGV和加工設(shè)備集成調(diào)度的多目標(biāo)優(yōu)化問題研究還較少，筆者以最大完工時(shí)間、AGV運(yùn)行時(shí)間和機(jī)器總負(fù)荷為優(yōu)化目標(biāo)構(gòu)建優(yōu)化模型。該問題是多個(gè)NP-hard問題的疊加，解空間龐大且復(fù)雜，精確算法難以在可接受的時(shí)間內(nèi)求得最優(yōu)解。啟發(fā)式算法往往可以快速得到最優(yōu)解或者次優(yōu)解，更適合這種類型問題。遺傳算法是一種啟發(fā)式算法，具有全局搜索能力強(qiáng)、魯棒性較好[7]等優(yōu)點(diǎn)，在多目標(biāo)優(yōu)化領(lǐng)域已經(jīng)有比較多的應(yīng)用。

交叉是遺傳算法中的重要操作，在很大程度上決定算法性能[8]，而原始的交叉操作具有一定的隨機(jī)性和盲目性，因此許多學(xué)者通過引導(dǎo)交叉操作來提高算法的性能[9-11]。聚類是數(shù)據(jù)挖掘領(lǐng)域中常用的一種方法，在進(jìn)化算法中用來提取個(gè)體之間的相似度。越來越多的研究將聚類算法和智能優(yōu)化算法結(jié)合來提高算法性能[12-14]。本文通過聚類算法得到的相似度將種群分為多個(gè)子種群，引入鯨魚優(yōu)化算法[15]中的收斂因子來限制交叉父代的子種群來源，從而提高算法性能。解集的分布性是多目標(biāo)優(yōu)化另外一個(gè)重要的性能。NSGA-Ⅱ算法的非支配排序和擁擠距離可在一定程度上保證Pareto最優(yōu)解集的均勻性和分布性，但在計(jì)算擁擠距離時(shí)只計(jì)算相鄰個(gè)體的距離并不能完全反映多樣性。本文提出的基于自適應(yīng)網(wǎng)格距離的選擇方法可以避免邊界個(gè)體必被選中，并能更好地增強(qiáng)種群的多樣性。

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

1.1 問題描述

傳統(tǒng)的作業(yè)車間調(diào)度問題不考慮工件在不同加工設(shè)備之間的運(yùn)輸時(shí)間。本文所研究的問題中，工件的運(yùn)輸時(shí)間不可忽略且隨著路況變化，不僅要為每道工序分配負(fù)責(zé)其運(yùn)輸?shù)腁GV，還要為AGV規(guī)劃無沖突的路徑以確定精確的運(yùn)輸時(shí)間。假設(shè)有n個(gè)需要加工的工件，m臺(tái)可以用于加工的機(jī)器，工件i有g(shù)i道工序。每道工序至少存在1臺(tái)可加工的機(jī)器，工序的加工時(shí)間和機(jī)器的加工能力有關(guān)。每臺(tái)AGV可以在任意機(jī)器及倉庫之間運(yùn)輸工件，假設(shè)AGV的行駛速度恒定不變，因此運(yùn)輸時(shí)間只取決于運(yùn)輸距離及路途中的沖突狀況。AGV的任務(wù)周期由兩部分組成，首先AGV從當(dāng)前位置行駛到當(dāng)前工序加工機(jī)器所在位置，然后將工件運(yùn)輸?shù)较乱坏拦ば蚣庸C(jī)器所在位置。工件的所有工序都完成之后，需要運(yùn)送回倉庫，根據(jù)2.1節(jié)編碼方法，為所有工件增加一道虛擬工序，該道工序的加工時(shí)間為0，加工機(jī)器位置為倉庫所在的位置，用以分配將工件運(yùn)輸?shù)絺}庫的AGV。為了簡(jiǎn)化問題，作在以下假設(shè)：

(1)工件和AGV的初始位置為倉庫，從倉庫出發(fā)時(shí)，所有AGV以隨機(jī)順序按照固定的間隔時(shí)間出發(fā)；

(2)各AGV運(yùn)輸能力相同，每次只能完成1個(gè)工件的運(yùn)輸任務(wù)；

(3)加工機(jī)器的工件緩沖區(qū)無限大；

(4)AGV完成運(yùn)輸任務(wù)后?？吭跈C(jī)器旁；

(5)機(jī)器不能同時(shí)加工多個(gè)工件且一旦開始加工便不會(huì)中斷；

(6)工件加工準(zhǔn)備時(shí)間及裝卸時(shí)間算在加工時(shí)間中；

(7)所有路段在同一時(shí)刻只允許1臺(tái)AGV通過，且任意路段可容納AGV的車身，不存在AGV占用兩個(gè)車道的情況；

(8)不同工件之間的工序無加工先后約束，同一工件之間的工序存在加工先后約束；

(9)調(diào)度周期內(nèi)AGV與加工設(shè)備不會(huì)發(fā)生故障，AGV電量充足。

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

為了便于模型的建立和描述，引入如下符號(hào)和變量。變量xijk用以限定一道工序只能由一臺(tái)加工設(shè)備完成加工，即有

式中，Oij表示第i個(gè)工件的第j道工序。

變量zijw限定每道工序的運(yùn)輸任務(wù)只能由一臺(tái)AGV負(fù)責(zé)，即有

式中，Rw表示編號(hào)為w的AGV。

變量apqijk表示在同一臺(tái)加工設(shè)備上加工的工序(加工順序)的關(guān)系，即有

變量βpqijw表示由同一臺(tái)AGV負(fù)責(zé)運(yùn)輸?shù)墓ば?運(yùn)輸順序)的關(guān)系，即有

變量δwst表示AGV對(duì)節(jié)點(diǎn)的占據(jù)情況，即有

變量εsrt表示節(jié)點(diǎn)的鎖定情況，即有

1.2.1目標(biāo)函數(shù)

本文提出AGV與加工設(shè)備集成調(diào)度問題的3個(gè)優(yōu)化目標(biāo)如下：

(1)最大完工時(shí)間最小，即

f1=min(max(C1,C2,…,Cn))

(1)

(2)

(3)

(2)AGV運(yùn)行距離最短，即

(4)

(3)機(jī)器總負(fù)荷最小，即

(5)

式中，pijk為工序Oij在加工設(shè)備Mk上加工所需時(shí)間。

1.2.2約束條件

根據(jù)以上假設(shè)條件以及實(shí)際生產(chǎn)情況，給出如下約束條件：

(1)任意一道工序必須選擇1臺(tái)且只能選擇1臺(tái)機(jī)器完成加工，即

(6)

(2)任意一道工序最多只能選擇1臺(tái)AGV進(jìn)行運(yùn)輸，即

(7)

(3)AGV負(fù)載出發(fā)時(shí)間不早于AGV空載結(jié)束時(shí)間和上一道工序完工時(shí)間，即

(8)

(9)

(4)AGV負(fù)載結(jié)束時(shí)間為負(fù)載開始時(shí)間與負(fù)載運(yùn)行時(shí)間之和，即

(10)

(5)AGV空載出發(fā)時(shí)間不早于上一次運(yùn)輸任務(wù)的負(fù)載完成時(shí)間，即

(11)

(6)AGV空載結(jié)束時(shí)間為AGV空載出發(fā)時(shí)間與空載運(yùn)行時(shí)間之和，即

(12)

式中，eijw為編號(hào)w的AGV負(fù)責(zé)工序Oij運(yùn)輸任務(wù)時(shí)，AGV空載階段的運(yùn)行時(shí)間。

(7)工件開工時(shí)間不早于AGV負(fù)載結(jié)束時(shí)間、前道工序的完工時(shí)間以及前一道在機(jī)器上加工工序完工時(shí)間，即

(13)

(14)

(15)

(8)工序完工時(shí)間為工序開工時(shí)間與加工時(shí)間之和，即

(16)

(9)在AGV進(jìn)入某個(gè)路段之后和駛出該路段之前的時(shí)間段內(nèi)，不允許其他AGV進(jìn)入，路段出口處的節(jié)點(diǎn)標(biāo)識(shí)值εsrt=1。

(10)同一時(shí)刻任意一個(gè)節(jié)點(diǎn)只容得下1臺(tái)AGV，即有

(17)

式中，H為調(diào)度周期。

2 算法描述

2.1 問題編碼

AGV和加工設(shè)備的集成調(diào)度問題可以分為三個(gè)子問題：工序排序、機(jī)器分配、AGV分配，因此，本文采用三段式編碼對(duì)應(yīng)3個(gè)子問題。如圖1所示，工序編碼段中的基因和工件號(hào)對(duì)應(yīng)，從左至右的數(shù)字為工件的工序號(hào)。第一個(gè)基因上第一次出現(xiàn)的3表示3號(hào)工件的第一道工序，第4個(gè)基因位上第二次出現(xiàn)的3表示3號(hào)工件的第二道工序。機(jī)器和AGV編碼段中的基因與工序一一對(duì)應(yīng)，如機(jī)器編碼段的前3個(gè)基因2、4、3表示工件1的三道工序分別選擇2號(hào)、4號(hào)與3號(hào)機(jī)器進(jìn)行加工。

圖1 個(gè)體編碼示意圖Fig.1 Individual coding diagram

2.2 基于自適應(yīng)聚類的交叉策略

聚類是一種無監(jiān)督學(xué)習(xí)方法，可發(fā)現(xiàn)數(shù)據(jù)之間的聯(lián)系。采用聚類對(duì)種群分類后，同一子種群內(nèi)的個(gè)體相似度大，不同子種群之間的個(gè)體相似度小。相似度大的個(gè)體之間進(jìn)行交叉會(huì)以較大概率產(chǎn)生質(zhì)量更高的解，提高算法局部搜索能力；相似度小的個(gè)體之間進(jìn)行交叉可產(chǎn)生多樣性更強(qiáng)的解，增強(qiáng)算法的全局探索能力。鯨魚優(yōu)化算法[15]中的收斂因子可以平衡算法的探索與開發(fā)，本文以此為基礎(chǔ)，通過非線性收斂因子來限制遺傳算法交叉?zhèn)€體的來源。

2.2.1基于海明距離的自適應(yīng)聚類算法

聚類方法中，距離是廣泛應(yīng)用的一個(gè)度量指標(biāo)。對(duì)于本文研究的組合優(yōu)化問題，海明距離能更好地反映個(gè)體之間的相似度，因此本文將海明距離作為聚類的依據(jù)。K-means作為一種經(jīng)典的聚類算法，具有原理簡(jiǎn)單、容易實(shí)現(xiàn)、收斂快等優(yōu)點(diǎn)。分類數(shù)目是聚類算法的重要參數(shù)之一，算法的聚類效果與給定的分類數(shù)目有很大的關(guān)系，而Canopy算法[16]作為一種“粗聚類”算法，能較快求得一個(gè)種群的最優(yōu)分類數(shù)量，因此，本文首先采用Canopy聚類算法對(duì)種群進(jìn)行初步聚類、得到分類數(shù)量，使聚類數(shù)量隨種群進(jìn)化自適應(yīng)變化，然后應(yīng)用K-means聚類算法將種群進(jìn)行聚類。

在Canopy算法中設(shè)置最大迭代次數(shù)，統(tǒng)計(jì)所有迭代所獲得的結(jié)果，最佳分類數(shù)量k1取出現(xiàn)頻率最高的結(jié)果。每次迭代中，Canopy算法以閾值(種群所有個(gè)體之間海明距離的平均值與5倍方差的和)T2對(duì)種群進(jìn)行迭代運(yùn)算。開始運(yùn)算時(shí)，隨機(jī)選擇一個(gè)個(gè)體作為聚類中心。有了聚類中心之后，從種群列表中隨機(jī)選擇個(gè)體，計(jì)算其到各聚類中心的距離，如果距離小于T2，則將該個(gè)體歸入該聚類中心的子種群，并從種群列表中刪除；如果該個(gè)體到所有聚類中心的距離都大于T2，則以該個(gè)體為中心創(chuàng)建一個(gè)類，并將該個(gè)體從種群列表中刪除。所有個(gè)體按照相同的方式進(jìn)行分類，直到種群列表為空，最終得到本次迭代的分類數(shù)量。然后，采用K-means方法從種群中隨機(jī)選擇k1個(gè)個(gè)體作為聚類中心點(diǎn)，計(jì)算剩余個(gè)體到各聚類中心的海明距離，將個(gè)體分到距離最小的類，算法流程見圖2。

圖2 Canopy算法流程圖Fig.2 Canopy algorithm flow chart

2.2.2父代來源選擇策略

對(duì)遺傳算法而言，前期側(cè)重于全局探索，應(yīng)以更大的概率進(jìn)行異組交叉以找到全局最優(yōu)解，后期在得到部分較優(yōu)解的情況下，側(cè)重于局部開發(fā)，應(yīng)進(jìn)行同組交叉，提高解的質(zhì)量。鯨魚優(yōu)化算法的收斂因子隨迭代而變化，可記錄算法的迭代信息，用以判斷個(gè)體在更新過程中是否向最優(yōu)個(gè)體靠近，能很好地平衡算法的全局探索和局部勘探。鯨魚優(yōu)化算法中收斂因子隨著迭代次數(shù)線性變化。研究表明非線性收斂因子可進(jìn)一步提升算法的性能[17]，因此，本文設(shè)計(jì)一種非線性收斂因子：

A=a(2r1-1)

(18)

(19)

式中，r1為0～1之間隨機(jī)生成的數(shù)；td為當(dāng)前的迭代次數(shù)；tmax為最大迭代次數(shù)。

來判斷種群個(gè)體進(jìn)行異組交叉還是同組交叉。如果A>1/2，則選擇異組交叉，否則選擇同組交叉。由式(19)可知，A的取值為[0,a]，a隨著迭代的進(jìn)行，從2減小到0，前期以較大的概率進(jìn)行異組交叉，后期進(jìn)行同組交叉。

同組交叉，即在同一個(gè)子類里面隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行交叉。為使所有個(gè)體都能進(jìn)行同組交叉，子種群個(gè)體數(shù)量應(yīng)為偶數(shù)，因此需對(duì)個(gè)體數(shù)量為奇數(shù)的子種群進(jìn)行調(diào)整，在子種群中移除或增加部分個(gè)體使群個(gè)體數(shù)量為偶數(shù)。首先計(jì)算個(gè)體最多的子類中離其聚類中心最遠(yuǎn)的個(gè)體到其他個(gè)體數(shù)量為奇數(shù)的子種群聚類中心的距離，然后將該個(gè)體從該子類中刪除，添加到離聚類中心距離最小的子類中，如果到多個(gè)子類的最小距離相等，則隨機(jī)選擇其中一個(gè)子類。重復(fù)以上操作直到所有子類中的個(gè)體數(shù)量變?yōu)榕紨?shù)。異組交叉需要從不同的子類中選擇父代個(gè)體進(jìn)行交叉。每個(gè)子類中的個(gè)體數(shù)量有差別，為盡量讓所有個(gè)體都能和異組的個(gè)體交叉，本文采用基于個(gè)體數(shù)量的選擇方法，即隨機(jī)選擇種群中的一個(gè)個(gè)體與當(dāng)前個(gè)體數(shù)量最大的子類中隨機(jī)選擇的一個(gè)個(gè)體進(jìn)行交叉，重復(fù)該操作直到完成種群交叉。

2.2.3交叉操作

對(duì)基于工序的編碼方式而言，改進(jìn)優(yōu)先操作交叉(improved precedence operation crossover，IPOX)是一種十分合適的交叉算子，具體操作為：隨機(jī)選擇部分工件，使這些工件所有工序的絕對(duì)位置不變，使其他工件工序之間的相對(duì)位置不變。這不僅可以避免產(chǎn)生不可行解，還能保證工序在父代中的順序約束。本文對(duì)工序序列采用的IPOX見圖3。多點(diǎn)交叉作為一種經(jīng)典交叉方式，具有操作簡(jiǎn)單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)[7]，依據(jù)機(jī)器和AGV的編碼特點(diǎn)，本文對(duì)加工設(shè)備和AGV系列采用多點(diǎn)交叉的方式進(jìn)行交叉，見圖4。

圖3 IPOX交叉示意圖Fig.3 IPOX crossover diagram

圖4 多點(diǎn)交叉示意圖Fig.4 Multipoint crossover diagram

2.2.4自適應(yīng)個(gè)體交叉概率

種群中的個(gè)體質(zhì)量參差不齊，所有個(gè)體的交叉概率相同會(huì)導(dǎo)致質(zhì)量較好個(gè)體信息的流失，因此，本文給每個(gè)個(gè)體分配一個(gè)交叉概率。算法進(jìn)化過程中，如果一個(gè)個(gè)體經(jīng)過很多代都沒有被淘汰，表明其質(zhì)量較好，將該個(gè)體存在的代數(shù)稱作生存長(zhǎng)度。非支配等級(jí)是另外一個(gè)常見的個(gè)體質(zhì)量指標(biāo)，因此本文使用生存長(zhǎng)度、非支配等級(jí)衡量個(gè)體的質(zhì)量。質(zhì)量高的個(gè)體應(yīng)該以更大的概率進(jìn)行交叉，進(jìn)而將優(yōu)良基因傳給后代，本文中種群個(gè)體自適應(yīng)交叉概率為

(20)

式中，Pc為設(shè)置的初始交叉概率；l為當(dāng)前個(gè)體生存長(zhǎng)度；lmax為當(dāng)前最大的生存長(zhǎng)度；r為當(dāng)前個(gè)體的支配等級(jí)；rmax為當(dāng)前種群的最大支配等級(jí)。

2.3 變異操作

變異是遺傳算法進(jìn)化過程中的重要操作，對(duì)改善算法的局部搜索能力有極大的幫助，在一定程度上可防止算法早熟。筆者考慮產(chǎn)生后代的可行性，采用兩種方式對(duì)新生成的個(gè)體進(jìn)行變異操作：①對(duì)于工序編碼段，隨機(jī)互換染色體中的兩個(gè)基因；②對(duì)于加工設(shè)備編碼段，隨機(jī)選擇染色體中的一個(gè)位置，然后在該位置對(duì)應(yīng)工序的可加工設(shè)備集中隨機(jī)選擇加工設(shè)備來替換當(dāng)前加工設(shè)備。AGV編碼段的變異操作也是如此。

精英保留可保證不會(huì)丟失最優(yōu)個(gè)體，本文采用一種精英保留的環(huán)境選擇方法，將父代種群和子代種群合并后選擇較優(yōu)個(gè)體以維持種群大小，其中，從父代種群中保留的個(gè)體稱為精英個(gè)體。新生成種群保留較多精英個(gè)體表明種群難以生成更好的解，種群進(jìn)化進(jìn)入停滯，可能陷入局部最優(yōu)，此時(shí)應(yīng)當(dāng)增大變異概率：

P′m=Pm+(1-Pm)z1/z

(21)

式中，Pm為設(shè)置的初始變異概率；z1為精英個(gè)體數(shù)量；z為種群規(guī)模。

2.4 基于聚類數(shù)量的擾動(dòng)因子

個(gè)體之間的相似度在算法后期會(huì)越來越大，使得種群?jiǎn)适Ф鄻有?。本文提出一種基于聚類數(shù)量的擾動(dòng)因子，具體做法為：種群經(jīng)過Canopy算法粗聚類后，如果聚類數(shù)量連續(xù)多代小于閾值，則隨機(jī)生成一部分個(gè)體替換支配等級(jí)最大的個(gè)體，并強(qiáng)制進(jìn)行一次異組交叉。

2.5 基于網(wǎng)格的環(huán)境選擇

本文參考文獻(xiàn)[18]的方法，設(shè)計(jì)一種基于支配等級(jí)與網(wǎng)格距離的環(huán)境選擇方法，對(duì)目標(biāo)空間進(jìn)行網(wǎng)格劃分并計(jì)算每個(gè)個(gè)體的網(wǎng)格坐標(biāo)。網(wǎng)格劃分?jǐn)?shù)對(duì)于劃分效果至關(guān)重要，文獻(xiàn)[19]提出一種基于目標(biāo)數(shù)和種群規(guī)模的劃分方法，其中的網(wǎng)格劃分?jǐn)?shù)為

(22)

為將邊界的點(diǎn)納入網(wǎng)格坐標(biāo)中，需要對(duì)目標(biāo)空間的上下限進(jìn)行擴(kuò)容，即有

(23)

(24)

式中，fm(X)為優(yōu)化目標(biāo)值，um、lm分別為擴(kuò)容后的上下限。

擴(kuò)容后，個(gè)體網(wǎng)格坐標(biāo)為

(25)

(26)

式中，dm為單位網(wǎng)格的大小。

衡量同一支配等級(jí)個(gè)體的擁擠度的指標(biāo)為

(27)

gt(x,y)=

(28)

G(x)越大，密集程度越大。環(huán)境選擇時(shí)，選擇擁擠度小的個(gè)體可使種群包含更強(qiáng)的多樣性，使得算法朝著各個(gè)方向進(jìn)化，因此優(yōu)先選擇擁擠度小的個(gè)體，以增強(qiáng)算法的全局探索能力。

2.6 基于時(shí)間窗的Dijkstra算法

柔性制造系統(tǒng)中，AGV沿著固定的路線往返于機(jī)器和倉庫，因此可將車間抽象為一個(gè)拓?fù)涞貓D，將機(jī)器和倉庫抽象為節(jié)點(diǎn)，將可行的路段抽象為可雙向通行路徑，如圖5所示，AGV在運(yùn)行地圖上可沿固定的軌道雙向行駛，行進(jìn)過程中可能遇到的路徑?jīng)_突主要有4種：節(jié)點(diǎn)占用沖突、路口沖突、相向沖突和趕超沖突。本文假設(shè)AGV的行駛速度不變，因此最后一種沖突不予考慮，見圖6。目前，解決路徑?jīng)_突的策略主要有等待和二次規(guī)劃。相向沖突采用等待策略是無法解決的，只能采用基于二次規(guī)劃的方法。對(duì)于節(jié)點(diǎn)沖突和路口沖突，等待策略和二次規(guī)劃都能解決沖突，但二次規(guī)劃可能縮短AGV的行駛時(shí)間，也可能導(dǎo)致新的沖突甚至死鎖，增加算法的計(jì)算量，因此本文采用等待法解決節(jié)點(diǎn)沖突和路口沖突。

圖5 車間地圖Fig.5 Workshop map

(a)相向沖突 (b)路口沖突

時(shí)間窗方法是一種經(jīng)典的沖突檢測(cè)方法，給有AGV通過的路段添時(shí)間窗，以將路段鎖定一段時(shí)間，當(dāng)有AGV要通過該路段時(shí)，通過時(shí)間窗是否重疊來判斷是否有沖突。Dijkstra算法可以快速求得兩點(diǎn)之間的最短路徑，但地圖中的節(jié)點(diǎn)和路段變多時(shí)，算法的求解時(shí)間會(huì)急劇延長(zhǎng)。本文研究的問題中，AGV只往返于機(jī)器和倉庫之間，地圖并不復(fù)雜，Dijkstra算法較合適。綜上，本文采用基于時(shí)間窗的Dijkstra算法為AGV規(guī)劃路徑。

2.7 解碼

將正規(guī)性指標(biāo)作為優(yōu)化目標(biāo)時(shí)，最優(yōu)調(diào)度結(jié)果必定存在于主動(dòng)調(diào)度集中，因此，本文采用一種基于插入式貪婪解碼的主動(dòng)解碼方法，在不延后已安排工序開工時(shí)間的前提下，通過查找滿足條件的加工設(shè)備空閑時(shí)間段將工序加工插入，使當(dāng)前工序盡可能早的開工。與傳統(tǒng)調(diào)度問題不同的是，本文研究的問題考慮工件的轉(zhuǎn)移時(shí)間，所以工序的最早可開工時(shí)間為負(fù)責(zé)該工序運(yùn)輸任務(wù)的AGV負(fù)載結(jié)束時(shí)間。機(jī)器被安排加工任務(wù)后，空閑時(shí)間被分割成多段，如果在工序最早可開工時(shí)間之后能插入加工設(shè)備空閑時(shí)間段即

t≤min(t1,t2)

(29)

t1=ei-sit2=ei-j

(30)

式中，ei為空閑時(shí)間段i的結(jié)束時(shí)間，i=1，2，…，nI；nI為空閑時(shí)間段的數(shù)量；si為空閑時(shí)間段i的開始時(shí)間；j為本道工序運(yùn)輸任務(wù)的負(fù)載結(jié)束時(shí)間。

2.8 時(shí)間復(fù)雜度分析

本文所提算法進(jìn)行交叉、解碼、非支配排序所耗費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)大于其他操作所耗費(fèi)的時(shí)間，而解碼為算法必不可少的部分，所以只討論交叉和非支配排序部分的時(shí)間復(fù)雜度。

假設(shè)種群規(guī)模為N，個(gè)體維度為w，聚類數(shù)量為m，則普通交叉操作的時(shí)間復(fù)雜度為O(Nw)。本文交叉操作首先需要進(jìn)行聚類，然后再進(jìn)行交叉重組，時(shí)間復(fù)雜度為

T=O(Nw)+O(mNw)+O(Nw)=O(Nw)

(31)

本文用快速非支配排序方法計(jì)算個(gè)體的支配等級(jí)，用網(wǎng)格距離替換擁擠距離，所以其時(shí)間復(fù)雜度和快速非支配排序的時(shí)間復(fù)雜度一樣，也為O(NlgN)。

2.9 算法流程

圖7所示為本文所提算法的總流程，其中，mc為聚類數(shù)量小于3的持續(xù)代數(shù)。種群在經(jīng)過初始化之后進(jìn)入算法迭代階段。算法迭代階段內(nèi)，首先對(duì)種群進(jìn)行聚類，根據(jù)提出的交叉重組策略進(jìn)行交叉操作后再進(jìn)行變異操作，最后根據(jù)所提的環(huán)境選擇方法保持種群規(guī)模。

圖7 算法流程圖Fig.7 Algorithm flowchart

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

為檢驗(yàn)本文算法在求解多目標(biāo)AGV和加工設(shè)備集成調(diào)度問題的性能，在MATLAB 2019a的編程環(huán)境，Intel Core i5-8500 CPU(3.0GHz主頻)、8.0GB內(nèi)存的運(yùn)行環(huán)境下開展以下實(shí)驗(yàn)。

3.1 算法對(duì)比

3.1.1非柔性算例對(duì)比

文獻(xiàn)[5]在不考慮AGV路徑?jīng)_突的前提下，以最大完工時(shí)間、工件平均流轉(zhuǎn)時(shí)間、工件平均延誤時(shí)間為優(yōu)化目標(biāo)，研究AGV與加工設(shè)備集成調(diào)度問題，為了方便表示，用PGA表示文獻(xiàn)[5]算法，用MACGA表示本文算法。表1所示為兩個(gè)算法獲得的非支配解優(yōu)化目標(biāo)值，所得解用向量表示，向量中的元素依次表示最大完工時(shí)間、工件平均流轉(zhuǎn)時(shí)間、工件平均延誤時(shí)間。所有案例運(yùn)行在單向單道的地圖中，不考慮AGV之間的沖突，所有工序只能由一臺(tái)加工設(shè)備負(fù)責(zé)加工。本文算法的關(guān)鍵參數(shù)設(shè)置和文獻(xiàn)[5]相同，最大迭代次數(shù)設(shè)為100，種群規(guī)模設(shè)為80，交叉率設(shè)為0.8，變異概率設(shè)為0.4，AGV數(shù)量設(shè)為2。PGA的結(jié)果為文獻(xiàn)[5]的原始數(shù)據(jù)，MACGA的結(jié)果為算法獨(dú)立運(yùn)行5次的最優(yōu)結(jié)果。表1中，紅色的解會(huì)被另一個(gè)算法Pareto解集中的解支配，可以發(fā)現(xiàn)，MACGA所獲得的Pareto解集中未出現(xiàn)任意一個(gè)解被支配的情況；隨著解空間的增大，MACGA支配解的優(yōu)勢(shì)更明顯。另外，案例1中兩個(gè)算法均能獲得4個(gè)非支配解，最大完工時(shí)間和平均流轉(zhuǎn)時(shí)間的最小值相等，本文算法能獲得平均拖期的更優(yōu)值。案例2中，PGA能獲得6個(gè)非支配解，MACGA能獲得8個(gè)非支配解，PGA能獲得更小的最大完工時(shí)間，MACGA能獲得更小的平均流轉(zhuǎn)時(shí)間和平均拖期。隨著案例解空間的增大，從案例3開始，MACGA在Pareto解集的數(shù)量及各目標(biāo)最小值均優(yōu)于PGA。

表1 非柔性算例Pareto解集

3.1.2柔性算例對(duì)比

表2中的各算法獨(dú)立運(yùn)行5次，算法的參數(shù)如下：最大迭代次數(shù)100，種群規(guī)模80，交叉率0.9，變異率0.1。NSGA-Ⅱ、SPEA2均采用錦標(biāo)賽的選擇策略，交叉池大小為種群大小的90%。SPEA2外部存檔集的大小為40。Me欄中的紅色數(shù)字表示算法獲得解集的3個(gè)優(yōu)化目標(biāo)值的平均值都為最優(yōu)，由表2可發(fā)現(xiàn)，MACGA的Me在多個(gè)算例的運(yùn)算結(jié)果中優(yōu)于SPEA2和NSGA-Ⅱ，且所有算例不存在3個(gè)優(yōu)化目標(biāo)值都為最劣的情況，這表明MACGA獲得解集的整體質(zhì)量要優(yōu)于其他兩種算法。當(dāng)沒有解可以支配某個(gè)體時(shí)，該個(gè)體的Ev<1，某個(gè)體的支配個(gè)體越多，其Ev越小。除了算例2中AGV數(shù)量為3時(shí)的情況，其他情況下MACGAP解集中最小的Ev都是小于1，說明MACGA獲得的Pareto解集至少存在一個(gè)不被另外兩種算法所得解集個(gè)體支配的解。算例規(guī)模較小時(shí)，3種算法性能相差不大，不同算法所得解之間基本不存在支配的情況，但算例規(guī)模增大后，MACGA的優(yōu)勢(shì)更加明顯。Me和Ev可以反映解集的收斂性，從收斂性角度而言，本文所提算法具有一定的優(yōu)越性。SP越小，Pareto解集分布越均勻，算法可以朝著各個(gè)方向進(jìn)化。57個(gè)算例中，MACGA在43個(gè)算例所得Pareto解集的SP均優(yōu)于SPEA2和NSGA-Ⅱ。3種算法中，SPEA2在所有算例中的運(yùn)行時(shí)間最短；與NSGA-Ⅱ相比，在相同算例的情況下，MACGA的運(yùn)行時(shí)間更長(zhǎng)，但都不會(huì)超過NSGA-Ⅱ算法運(yùn)行時(shí)間的1.2倍，說明MACGA并不會(huì)由于所提的操作使得運(yùn)行時(shí)間大幅增加。

3.2 算法分析

將本文所提出的算法用于求解算例，算例的運(yùn)行地圖為圖8，加工信息見表3，表中的信息包括工件的加工路線及其對(duì)應(yīng)的加工時(shí)間，每道工序有多個(gè)可加工設(shè)備。

表2 不同算法求解的算例結(jié)果

圖8 案例車間地圖Fig.8 Case workshop map

表3 加工信息表

表4所示為最大完工時(shí)間TC、AGV運(yùn)行時(shí)間TT以及機(jī)器總負(fù)荷TM的最小值隨AGV數(shù)量增多而變化的情況。由表4發(fā)現(xiàn)，不管AGV數(shù)量怎么變化，機(jī)器總負(fù)荷的最小值都收斂到145。最大完工時(shí)間隨AGV數(shù)量的增多先減小后不變，這是因?yàn)樽畲笸旯r(shí)間在AGV不多的情況下受AGV數(shù)量的制約，加工機(jī)器有較多空閑時(shí)間；AGV數(shù)量增多后，加工機(jī)器成為制約最大完工時(shí)間的因素，出現(xiàn)工件運(yùn)輸完成、等待機(jī)器執(zhí)行加工任務(wù)的情況，所以AGV增加到一定數(shù)量后，最大完工時(shí)間不會(huì)隨之減少。AGV運(yùn)行時(shí)間隨AGV數(shù)量的增多一直在縮短，因?yàn)锳GV數(shù)量增多時(shí)，AGV分配的解空間增大，存在使運(yùn)行時(shí)間更短的分配情況。

表4 各目標(biāo)在不同AGV數(shù)量下的值

圖9所示為AGV數(shù)量為3的情況下，初始值、迭代10次、迭代100次Paterto解集的分布情況，可知，隨著迭代的進(jìn)行，算法得到的Pareto曲面逐漸收斂。

圖9 Pareto前沿變化Fig.9 Pareto front change

圖10、圖11分別為AGV數(shù)量為3情況下的生產(chǎn)甘特圖和各路段的時(shí)間窗圖。圖10包括各加工設(shè)備的加工任務(wù)以及各AGV的運(yùn)輸任務(wù)，其中，不同顏色表示不同的工件，O表示加工階段，第一個(gè)下標(biāo)為工件號(hào)，第二個(gè)下標(biāo)為工序號(hào)，ET表示空載運(yùn)行階段，AGV的不同顏色表示相應(yīng)工件的負(fù)載運(yùn)行階段。由圖10可看出，最大完工時(shí)間為84 min，各工序的開工時(shí)間均不早于在同一加工設(shè)備上加工的前序工序的完工時(shí)間以及負(fù)責(zé)該工序的AGV負(fù)載完成時(shí)間，AGV的空載開始時(shí)間均在工件的前道工序完工時(shí)間之后，負(fù)載開始時(shí)間均在空載完成時(shí)間之后，滿足數(shù)學(xué)模型中的約束條件。各路段時(shí)間窗未出現(xiàn)重疊的情況，也不存在同一時(shí)刻AGV出現(xiàn)在不同路段的情況，說明基于時(shí)間窗的Dijkstra算法可以有效地為AGV規(guī)劃無沖突的路徑。

圖10 甘特圖Fig.10 Gantt chart

圖11 各路段時(shí)間窗Fig.11 Time window of each road section

4 結(jié)論

本文在考慮AGV沖突的情況下，對(duì)AGV與加工設(shè)備集成調(diào)度問題展開研究，提出一種改進(jìn)的交叉操作，采用了基于自適應(yīng)聚類算法的父代來源選擇策略和個(gè)體自適應(yīng)交叉概率；為加強(qiáng)解集的多樣性，引入了一種基于網(wǎng)格坐標(biāo)的環(huán)境選擇策略。

AGV的電量對(duì)AGV的調(diào)度會(huì)產(chǎn)生一定的影響，且實(shí)際生產(chǎn)中，機(jī)器和AGV可能會(huì)發(fā)生故障。因此，考慮AGV電量和車間異常等因素的集成調(diào)度更貼近生產(chǎn)實(shí)際，這將是接下來的研究方向。