鄒裕吉 宋豫川 王馨坤 王 毅

重慶大學(xué)機械傳動國家重點實驗室，重慶，400044

0 引言

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

(5)機器不能同時加工多個工件且一旦開始加工便不會中斷；

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

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

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

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

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

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

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

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

式中，Rw表示編號為w的AGV。

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

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

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

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

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

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

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

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

(1)

(2)

(3)

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

(4)

(3)機器總負荷最小，即

(5)

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

1.2.2約束條件

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

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

(6)

(2)任意一道工序最多只能選擇1臺AGV進行運輸，即

(7)

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

(8)

(9)

(4)AGV負載結(jié)束時間為負載開始時間與負載運行時間之和，即

(10)

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

(11)

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

(12)

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

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

(13)

(14)

(15)

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

(16)

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

(10)同一時刻任意一個節(jié)點只容得下1臺AGV，即有

(17)

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

2 算法描述

2.1 問題編碼

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

圖1 個體編碼示意圖Fig.1 Individual coding diagram

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

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

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

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

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

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

2.2.2父代來源選擇策略

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

A=a(2r1-1)

(18)

(19)

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

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

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

2.2.3交叉操作

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

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

圖4 多點交叉示意圖Fig.4 Multipoint crossover diagram

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

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

(20)

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

2.3 變異操作

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

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

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

(21)

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

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

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

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

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

(22)

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

(23)

(24)

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

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

(25)

(26)

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

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

(27)

gt(x,y)=

(28)

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

2.6 基于時間窗的Dijkstra算法

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

圖5 車間地圖Fig.5 Workshop map

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

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

2.7 解碼

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

t≤min(t1,t2)

(29)

t1=ei-sit2=ei-j

(30)

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

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

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

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

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

(31)

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

2.9 算法流程

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

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

3 實驗分析

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

3.1 算法對比

3.1.1非柔性算例對比

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

表1 非柔性算例Pareto解集

3.1.2柔性算例對比

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

3.2 算法分析

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

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

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

表3 加工信息表

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

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

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

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

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

圖10 甘特圖Fig.10 Gantt chart

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

4 結(jié)論

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

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