鄒裕吉，宋豫川，王 毅，王馨坤

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

隨著“中國制造2025”的提出，以及云計算、互聯(lián)網(wǎng)和大數(shù)據(jù)等信息技術(shù)的發(fā)展，大規(guī)模定制化和多品種小批量的生產(chǎn)模式逐漸成為主流。在這種以個性化為主的生產(chǎn)模式下，產(chǎn)品種類繁多，工藝流程復雜，合理的車間調(diào)度方案對于提高生產(chǎn)效率至關(guān)重要。在傳統(tǒng)的柔性作業(yè)車間調(diào)度問題研究中通常不考慮工件的轉(zhuǎn)移時間，導致這種調(diào)度結(jié)果并不是理論最優(yōu)調(diào)度結(jié)果，對于實際生產(chǎn)的指導存在不足。AGV(automated guided vehicles)是一種高柔性、高可靠性及高效率的先進物流裝備，在數(shù)字化車間中負責實現(xiàn)工件的轉(zhuǎn)移[1]。在這種情況下，機器的調(diào)度和AGV的調(diào)度會相互影響，所以AGV和機器集成調(diào)度問題越來越受關(guān)注。

土耳其學者Ulusoy等[2-4]于1993年首先將AGV和機器集成調(diào)度作為研究對象，在不考慮AGV路徑?jīng)_突的前提下，應用遺傳算法求解調(diào)度問題，并建立了標準算例庫。Abdelmaguid等[5]在Ulusoy的基礎(chǔ)上提出一種精英保留策略，研究了6種交叉操作和3種變異操作的最佳組合以及交叉和變異最優(yōu)概率范圍。Zheng等[6]針對該問題，建立了混合整數(shù)線性規(guī)劃模型，以最大完工時間為優(yōu)化目標，提出禁忌搜索算法結(jié)合12種鄰域結(jié)構(gòu)求解該模型。Deroussi等[7]提出一種混合粒子群遺傳算法用以解決柔性制造系統(tǒng)中AGV和機器集成調(diào)度問題，包含了一種基于AGV的解決方案。劉二輝等[8]提出一種改進花授粉算法求解AGV和機器集成調(diào)度問題，并研究了AGV數(shù)量對調(diào)度結(jié)果的影響。

以上研究為了將問題簡化，都聚焦于AGV和機器的調(diào)度，著力于解決AGV和機器的任務指派、任務執(zhí)行時序問題，將AGV的行駛道路設定為單道單向，并且不考慮潛在的路徑?jīng)_突。當AGV的行駛道路為單道雙向時，系統(tǒng)的運行效率將會得到提高，但路徑?jīng)_突也會隨之增加。路徑?jīng)_突如果不解決，就會出現(xiàn)AGV碰撞以及路徑被死鎖等問題，打亂調(diào)度計劃甚至造成生產(chǎn)系統(tǒng)癱瘓。因此，在AGV和機器集成調(diào)度問題中，考慮AGV路徑?jīng)_突具有重要的現(xiàn)實意義。Said-imehrabad等[9]建立了一個由車間調(diào)度和無沖突路徑組成的數(shù)學模型，提出一種二階段蟻群算法，首先解決AGV的分配問題，然后再解決AGV的路徑?jīng)_突問題。Shi等[10]考慮AGV運行時間、停車和轉(zhuǎn)彎的影響，提出一種兩階段調(diào)度策略，首先通過Dijkstra算法規(guī)劃路徑，然后考慮AGV之間的約束關(guān)系并通過遺傳算法對結(jié)果進一步優(yōu)化。Lyu等[11]提出一種改進遺傳算法求解柔性作業(yè)車間AGV和機器的集成調(diào)度問題，通過Dijkstra算法為AGV規(guī)劃無沖突的最短路徑，并把AGV數(shù)量當做變量研究最大完工時間的變化，若在算法中采用主動解碼，其結(jié)果將會更優(yōu)。

AGV和機器集成調(diào)度問題已經(jīng)被證明是NP難問題的疊加[7]，這類問題的解空間龐大且復雜，精確算法難以在可接受的時間內(nèi)求得最優(yōu)解，啟發(fā)式算法更適合求解此類問題。鯨魚優(yōu)化算法是Mirjalili等[12]于2016年模仿座頭鯨獨特捕食行為提出的仿生算法，和其他智能優(yōu)化算法相比，具有結(jié)構(gòu)簡單、參數(shù)少、搜索能力強且易于實現(xiàn)等優(yōu)點，在航路規(guī)劃[13]、港口拖船調(diào)度[14]及選址問題[15]等離散優(yōu)化問題中的應用越來越多。

綜上所述，傳統(tǒng)的作業(yè)車間調(diào)度研究不考慮工件轉(zhuǎn)移時間，無法滿足當前生產(chǎn)模式轉(zhuǎn)變所帶來的新需求。同時，目前對于AGV和機器集成調(diào)度問題的研究大多不考慮路徑?jīng)_突，與實際生產(chǎn)情況不符，而考慮路徑?jīng)_突的研究大多采用分階段的策略進行求解，并非真正意義上的集成調(diào)度。鯨魚優(yōu)化算法作為一種啟發(fā)式算法在離散優(yōu)化領(lǐng)域取得了一定的成功，但在調(diào)度領(lǐng)域的應用不多。為了實現(xiàn)無沖突路徑的AGV和機器集成調(diào)度，筆者首先以最大完工時間為優(yōu)化目標，建立數(shù)學模型；然后，為了求解該模型，將鯨魚優(yōu)化算法應用在集成調(diào)度領(lǐng)域，對于鯨魚優(yōu)化算法存在的不足，提出針對性的改進方法，即基于時間窗和Dijkstra的離散型鯨魚優(yōu)化算法；鯨魚優(yōu)化算法作為算法迭代的整體框架，基于時間窗的Dijkstra算法用于算法解碼過程中AGV的路徑規(guī)劃；最后，通過標準算例對比實驗和柔性算例實驗驗證了所提算法的性能。

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

1.1 問題描述

假設有n個需要加工的工件，m臺用于加工的機器，k臺用于運輸工件的AGV。每一個工件有ni道工序，每道工序至少可由一臺機器加工，選擇不同的機器加工時間一般不同。每臺AGV可以在任意兩臺機器以及倉庫之間運輸工件，運輸?shù)穆肪€一般是起點和終點之間可行的最短路徑，運輸時間取決于運輸路線的長度以及路途中的沖突狀況。AGV完成一個運輸任務分為空載和負載兩個階段，空載階段AGV需要從當前位置行駛到工件當前所在的位置；負載階段AGV將工件從當前位置運輸?shù)郊庸C器所在位置。

已知條件有：AGV數(shù)量、各機器的位置、所有工序可選擇進行加工的機器及對應的加工時間、任意兩節(jié)點之間的距離(當不可通行時為無窮大)。要求在滿足一定的約束條件的情況下達到優(yōu)化目標的目的，具體可分為以下幾個子問題：為每一道工序分配機器和AGV；為各機器安排加工任務序列和各加工任務開工時間；為各AGV安排運輸任務序列和各運輸任務開始時間。此外，為了簡化問題，存在以下假設：

1)在開始時刻，所有AGV和工件都在倉庫，AGV隨機出發(fā)，有先后順序。

2)每臺AGV均可運輸所有工件且一次只能運輸一個工件。

3)AGV的行駛速度恒定不變。

4)每臺加工機器的工件緩沖區(qū)無限大。

5)AGV完成運輸任務后可以?？吭跈C床旁邊，不需要返回倉庫。

6)每臺機器一次只能加工一個工件且一旦開始加工就不會中斷。

7)加工準備時間以及裝卸工件的時間算在加工時間中。

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

9)同一個工件的工序有先后約束，不同工件之間的工序無約束。

10)不考慮AGV故障、電量等因素，也不考慮機器故障。

11)所有工件都增加一道虛擬工序，加工時間為0，加工機器的位置為倉庫位置，便于處理將工件運送回倉庫。

1.2 數(shù)學模型

目標函數(shù)如下：

f=min(max(C1,…,Ci，…,Cn))。

(1)

約束條件如下：

1)任意工序都只能由一臺機器完成加工。

(2)

2)任意一道工序最多只由一臺AGV負責運輸。

(3)

3)AGV空載出發(fā)時間不早于AGV上一次運輸任務結(jié)束時間和工件開工時間。

(4)

(5)

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

(6)

5)AGV負載出發(fā)時間不早于AGV空載結(jié)束時間和工件完工時間。

(7)

(8)

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

(9)

7)某工序的開工時間不早于負載結(jié)束時間和機器前序工序的完工時間。

(10)

(11)

8)工序的完工時間為開工時間和加工時間之和。

(12)

9)工件的完工時間為AGV將其運送到倉庫的時間。

(13)

10)某個路段有AGV進入之后，在該AGV駛出該路段之前，不允許其他AGV從該路段出口駛?cè)搿?/p>

(14)

11)同一時刻任意一個節(jié)點只能容下一臺AGV。

(15)

2 算法描述

2.1 基本鯨魚優(yōu)化算法

鯨魚優(yōu)化算法是Mirjalili通過座頭鯨獨特的泡泡網(wǎng)狩獵方式抽象而來，種群中鯨魚的最優(yōu)位置就是算法所獲得的最優(yōu)解，迭代過程主要分為兩個階段：探索階段和開發(fā)階段，通過|A|和1的大小關(guān)系來區(qū)分[12]。

(16)

(17)

式中:r1是0到1之間的隨機數(shù)；f為當前迭代次數(shù)；fmax為最大迭代次數(shù)。

當|A|≤1時，算法側(cè)重于局部開發(fā)，鯨魚個體向當前種群最優(yōu)鯨魚個體靠近，有收縮包圍和螺旋更新兩種靠近方式，為了實現(xiàn)這兩種方式的同步，引入概率p去判斷應該執(zhí)行哪種更新方式。

(18)

D=|CXbest-Xt|，

(19)

C=2·r2。

(20)

式中：D為更新步長；b為控制螺旋線形狀的常量系數(shù)；l為[0,1]范圍服從均勻分布的隨機數(shù)；r2為0到1之間的隨機數(shù)。

當|A|>1時，算法側(cè)重于進行全局搜索，鯨魚個體向當前種群中一個隨機選擇的鯨魚個體靠近。

Xt+1=Xrand(t)-A·D，

(21)

D=|C·Xrand-Xt|。

(22)

鯨魚優(yōu)化算法作為新型群智能優(yōu)化算法，存在結(jié)構(gòu)簡單、參數(shù)少、搜索能力強且易于實現(xiàn)等優(yōu)點，但也有群智能優(yōu)化算法的通病，如收斂速度慢、容易陷入局部最優(yōu)及收斂精度較低等。針對以上缺點，筆者結(jié)合車間調(diào)度問題的特點提出一種改進型鯨魚優(yōu)化算法。

2.2 離散化改造

為了更加清晰地描述問題，此處引入一個實例加以說明，各工件的信息如表1所示。

表1 加工信息

2.2.1 問題編碼

作業(yè)車間機器和AGV共同調(diào)度問題中的調(diào)度子問題包含3個部分：工序排序、機器分配和AGV分配。筆者采用三段式編碼，由3條基因串組成：第1條為基于工序的基因串，第2條為基于機器的基因串，第3條為基于AGV的基因串?；虼忻總€位置值的取值范圍為[-δ,δ]。由于引入了Levy步長更新鯨魚個體，如果δ取得過小，更新后的個體工序序列基因值相對大小變化較大，導致個體被破壞；如果δ取得過大，則會導致Levy步長策略效果不明顯，一般設為2～5之間的數(shù)。圖1所示為一個合法的編碼。

圖1 個體連續(xù)編碼示意圖Fig. 1 Schematic diagram of individual continuous coding

2.2.2 編碼轉(zhuǎn)換

鯨魚優(yōu)化算法的解空間是連續(xù)空間，然而調(diào)度問題是離散組合優(yōu)化問題。為了使得鯨魚優(yōu)化算法適用于調(diào)度問題，需要將連續(xù)的解空間映射到離散的解空間。由于工序排序、機器選擇和AGV選擇的約束不同，需要采取不同的轉(zhuǎn)換機制。

采用LPV(largest position value)規(guī)則[16]對工序序列進行解空間的轉(zhuǎn)換。具體的操作過程為，首先給所有基因從左至右安排一個從1開始的固定ID與之對應，然后將他們按從大到小的順序排序，最后根據(jù)每個基因?qū)腎D得到一個新的基因串，按照每個工件的工序數(shù)轉(zhuǎn)換為可以用以解碼的序列，過程見圖2。

圖2 LPV轉(zhuǎn)換示意圖Fig. 2 LPV conversion diagram

圖2中，離散編碼中的值表示的是工件號，從左至右出現(xiàn)的次數(shù)表示的是工序，第1個3表示的是工序O31，第2個3表示的是工序O32。

對于機器和AGV的解空間轉(zhuǎn)換，采用文獻[17]的方法。首先根據(jù)式(16)將連續(xù)的編碼轉(zhuǎn)換為離散編碼，然后根據(jù)工序可選機器和AGV序列，轉(zhuǎn)換為具體的機器和AGV編號。同時，通過逆運算實現(xiàn)從離散空間映射到連續(xù)空間，具體見式(23)。在AGV和機器基因串中，從左至右依次為從第一個工件到最后一個工件每一道工序?qū)臋C器和AGV。具體見圖3和圖4。

(23)

式中:m(i)為連續(xù)編碼的基因值；z(i)為該工序可選的加工機器數(shù)或者AGV數(shù)；u(i)為得到的離散基因值。

圖3 機器編碼轉(zhuǎn)換示意圖Fig. 3 Schematic diagram of machine coding conversion

圖4 AGV編碼轉(zhuǎn)換示意圖Fig. 4 Schematic diagram of AGV encoding conversion

基于機器的基因串前3個基因值為工件1對應的3道工序?qū)臋C器，圖3和4表達的意思為：工件1的3道工序分別選擇1，4，3號機器進行加工；基于AGV的基因串與基于機器的基因串類似。AGV的基因串前3個數(shù)字的意思為：工件1 3道工序分別選擇1，3，2號AGV進行運輸。針對機器和AGV共同調(diào)度問題，上述編碼及其轉(zhuǎn)換方式不會產(chǎn)生非法解。

2.2.3 規(guī)則調(diào)整

算法迭代過程中，可能會導致鯨魚個體的某些維度越界。在原始鯨魚優(yōu)化算法中，每一輪迭代完成以后才會對越界個體進行調(diào)整。然而這種處理方式會導致一些問題，如在鯨魚個體迭代過程中可能會選中越界的個體作為位置更新的基準，進而造成更多個體越界，不僅會增加算法的運行時間而且還會導致一些非越界個體被破壞。因此，選擇在個體位置更新以后就進行個體越界的調(diào)整。原始鯨魚優(yōu)化算法中，將越界的維度設置為最大值或者最小值，當越界情況較多時，導致個體之間相似度越來越大。因此，可以將越界的維度設置為接近邊界的一個值。具體調(diào)整規(guī)則見式(24)。

(24)

式中X(i)表示個體X的第i個維度。

2.3 種群初始化

初始化種群對于進化算法來說十分重要[18]，初始解的質(zhì)量和多樣性對于算法的求解精度和收斂速度有非常大的影響。這里提出一種擴展GLR選擇方法結(jié)合混沌映射和對立學習的種群初始化方法。

如果在生成初始解的時候，考慮各機器和AGV的工作時間與負載均衡可以大大提高種群的質(zhì)量。在FJSP(flexible job-shop scheduling problem)問題上GLR(global, local, random)機器選擇方法[19]被證明是一個比較有效的方法，該方法在隨機生成50%個體的基礎(chǔ)上，考慮工作時間與負載均衡，使用全局選擇方法生成20%的個體。在該方法中，首先隨機選擇一道工序，將所有可加工機器已工作時間加上該工序的加工時間，然后選擇目前加工時間最小的那個機器作為本道工序的加工機器并更新其加工時間。局部選擇方法生成30%的個體，在該方法中，首先隨機選擇一個工件，為該工件的所有工序選擇機器，按照全局選擇的方法進行選擇機器，不同的是，當一個工件所有工序都選擇了對應的機器后，將所有的機器運行時間置零。該方法也應用在AGV的選擇上，在AGV序列初始化時，為了減少計算量，在計算AGV的運行時間時不考慮沖突。

由于對于優(yōu)化問題的全局最優(yōu)解沒有任何先驗知識，初始種群應該盡可能地均勻分布在解空間中。所以增強初始種群的多樣性以奠定算法全局搜索的基礎(chǔ)一直是算法優(yōu)化的一個方向。目前，大多數(shù)研究主要采用混沌映射策略和對立學習策略來增強智能優(yōu)化算法初始種群的多樣性。Ewees等[20]提出一種基于混沌映射的多元宇宙優(yōu)化算法用以提高算法的全局搜索性能；Shen等[21]提出一種基于PSO和混沌映射的多種群優(yōu)化算法；Alamri等[22]提出一種對立學習策略對鯨魚優(yōu)化算法進行改進?；煦缬成浜蛯αW習在改進算法上取得了許多成功，但是由于有很多混沌映射和對立學習方法可供選擇，所以選擇什么方法可以最大程度上提高算法性能是一個值得研究的問題；Elaziz等[23]使用基于差分進化算法的超啟發(fā)式算法選擇混沌映射方法和對立學習方法及其比例以得出最優(yōu)組合，通過對35組標準函數(shù)的測試證明了其結(jié)論的可靠性。在經(jīng)過GLR方法生成個體的基礎(chǔ)上使用高斯映射和標準對立學習且比例為25%的策略生成初始化種群。高斯映射和標準對立學習表達式見式(25)(26)。

(25)

(26)

2.4 Levy飛行策略和閾值

Levy飛行是一種服從Levy分布的隨機搜索路徑，Levy分布是法國數(shù)學家Levy提出的一種概率分布。由于Levy分布是一種重尾分布，所以Levy飛行是一種短距離和偶爾長距離相間的搜索方式。隨著Levy飛行在連續(xù)優(yōu)化領(lǐng)域取得大量成功，近年來逐漸有學者將其應用到組合優(yōu)化問題的研究中。王學武等[24]提出一種結(jié)合Levy飛行的粒子群算法以解決點焊機器人的路徑優(yōu)化問題；徐坤等[25]提出一種Levy飛行模式與蟻群算法的信息素更新方式相結(jié)合的算法用來解決TSP問題；Liu等[26]將levy飛行結(jié)合差分進化算法用來解決JSP問題。以上表明Levy策略在解決組合優(yōu)化問題上也有較優(yōu)異的表現(xiàn)。鯨魚優(yōu)化算法在迭代后期a逐漸減小，算法容易陷入局部最優(yōu)。因此，將Levy飛行策略引入到算法迭代后期，增強其跳出局部最優(yōu)的能力。同時，在算法的探索階段引入Levy飛行策略可以增強算法的全局搜索能力。

X(t+1)=X(t+1)+[r-1/2]⊕L。

(27)

式中：X(t)表示的是經(jīng)過鯨魚優(yōu)化算法迭代以后的個體；[r-1/2]有3種取值，r是服從范圍在[0,1]的均勻分布函數(shù)，當r<1/2時，[r-1/2]取-1；當r=1/2時，[r-1/2]取0；當r>1/2時，[r-1/2]取1；⊕表示的是Levy飛行操作。所采用的工序編碼轉(zhuǎn)換方式，本質(zhì)上取決于各個維度的相對值大小，所以對于工序向量要對每個維度單獨進行Levy飛行操作。Levy飛行具體的數(shù)學表達式見式(28)～(31)。

L(s)～|s|-1-β,0<β≤2，

(28)

(29)

(30)

(31)

式中：Γ是標準伽馬函數(shù)；β一般取1.5。

閾值操作也是防止算法陷入局部最優(yōu)常見做法之一。具體的做法為：在算法開始時設置一個全局最優(yōu)保持代數(shù)g并令其等于零，然后在算法迭代過程中記錄當前最優(yōu)值保持代數(shù)，當g達到設置的閾值l時，用隨機生成的個體代替50%較劣個體。閾值的設置對算法有較大的影響，當閾值設置過小時，算法不易收斂且導致算法復雜度增加；當閾值設置過大時，會造成算法收斂速度變慢。一般設為最大迭代次數(shù)的10%～15%。

2.5 局部搜索

在開發(fā)階段，種群個體以當前最優(yōu)個體為基準來更新自己的位置，對較優(yōu)個體進行局部搜索可以較大提升算法求解精度和收斂速度。由于AGV設備比較昂貴，在車間中AGV數(shù)量往往較少。對于機器和AGV共同調(diào)度的問題，經(jīng)常出現(xiàn)工件等待AGV運輸?shù)默F(xiàn)象，合理地分配AGV對于減小最大完工時間至關(guān)重要。提出的局部搜索分為兩部分：基于工序和機器的變鄰域搜索和基于約束AGV的鄰域搜索，把最遲完成搬運任務的AGV定義為約束AGV。

1)鄰域結(jié)構(gòu)N1：在其工序的基因串中，隨機選擇兩個位置，保證這兩個位置必須對應不同工件的工序，互換它們的位置。

2)鄰域結(jié)構(gòu)N2：在其工序的基因串中，隨機選擇兩個位置，將后一個基因插入到前一個基因的前一個位置。

3)鄰域結(jié)構(gòu)N3：在其機器的基因串中，隨機選擇一個位置，保證該位置對應工序的可加工機器不唯一，從該工序的可加工機器中隨機選擇一個替換該位置的機器。

在以上3種鄰域結(jié)構(gòu)的基礎(chǔ)上，基于工序和機器的變鄰域搜索算法步驟如下。

步驟1 設置初始參數(shù)，將要進行變鄰域搜索的個體設為初始個體X；當前迭代次數(shù)n設為1，最大迭代次數(shù)nmax設為5，p設為1，pmax設為3。

步驟2 判斷是否達到循環(huán)終止條件n≥nmax，如滿足，輸出當前個體X；否則，轉(zhuǎn)步驟3。

步驟3 在個體X的基礎(chǔ)上隨機選擇一個鄰域結(jié)構(gòu)，得到一個擾動個體。

步驟4 在擾動個體X′的基礎(chǔ)上進行變鄰域搜索，其具體步驟為：

1)判斷是否達到終止條件p≥pmax，如滿足，輸出當前解X′。

步驟5 令X←X′，n←n+1，轉(zhuǎn)步驟2。

基于約束AGV的鄰域搜索以基于工序和機器的變鄰域搜索輸出的個體為初始解，步驟如下。

步驟① 初始化參數(shù)，將初始個體設為X；當前操作的AGV任務編號n←1，nmax為總?cè)蝿諗?shù)。

步驟② 判斷是否滿足終止條件n≥nmax，如滿足，輸出個體X；否則，轉(zhuǎn)步驟③。

步驟③ 將當前任務分配給當前運行時間最小的AGV得到新個體X′；如果f(X′)

2.6 多AGV路徑規(guī)劃

在算法對個體進行解碼的過程中，工序確定加工機器以后，還需要根據(jù)工件的最早可開工時間以及機器的加工時間確定工序的實際開完工時間。在傳統(tǒng)的車間調(diào)度方案中，工序的最早可開工時間為上道工序的完工時間，而AGV和機器集成調(diào)度問題要考慮工件的轉(zhuǎn)移時間以及路途中可能遇到的路徑?jīng)_突，因此要想確定工序的最早可開工時間，需要先給AGV規(guī)劃無沖突路徑，筆者采用一種基于時間窗的Dijkstra算法為AGV規(guī)劃無沖突路徑。

2.6.1 Dijkstra算法

在最短路徑規(guī)劃中Dijkstra算法能夠從全局出發(fā)，具有較強的穩(wěn)定性且算法簡單[28]。Dijkstra算法要訪問所有節(jié)點及其連通的節(jié)點，肯定可以求出最短路徑，但是在節(jié)點和路段較多的地圖中，求解時間會急劇增大。工廠環(huán)境中，AGV沿著固定的軌道行走，AGV也只需往返于各機器之間。因此，工廠環(huán)境下的地圖節(jié)點和路段都比較少，Dijstra算法可以較好地發(fā)揮性能。另外，優(yōu)化目標是最小化最大完工時間，AGV只有盡早完成任務工件才能盡早開工，基于貪心策略選擇最短路徑是全局最優(yōu)解。因此，應用Dijkstra算法對AGV進行路徑規(guī)劃是一個較好的選擇。

2.6.2 基于時間窗的Dijkstra算法

在多AGV參與的制造系統(tǒng)中，路徑?jīng)_突是路徑規(guī)劃中常見的問題。只有解決了路徑?jīng)_突才能實現(xiàn)真正意義上的集成調(diào)度。在工廠環(huán)境下的AGV沖突主要有：相向沖突、節(jié)點占用沖突和路口沖突。如圖5所示。

圖5 AGV沖突示意圖Fig. 5 AGV conflict diagram

AGV路徑?jīng)_突本質(zhì)上為AGV在時間或者空間上出現(xiàn)了重疊，時間窗方法是一種沖突預測方法，將地圖以路段為單位記錄鎖定的時間。時間窗被證明是一個可以有效避免AGV沖突的方法。對于時間窗的表示方式為：[tin,tout,nin,nout]，nin為進入該路段的節(jié)點，nout為離開該路段的節(jié)點，tin和tout分別為進入和離開的時間。這種表示方式可以包含兩部分信息，節(jié)點的時間窗和路段的時間窗。由于AGV車身通過節(jié)點需要時間且要保持安全距離，因此會在一段時間內(nèi)占用該節(jié)點。當兩個節(jié)點時間窗有重疊時，說明這兩個AGV有節(jié)點沖突。當兩個路段時間窗有重疊并且兩個AGV進入該路段的節(jié)點不同時，說明這兩個AGV有相向沖突。

解決AGV沖突主要有兩種方法：等待法和二次規(guī)劃法。對于相向沖突，只有二次規(guī)劃才能解決沖突。對于節(jié)點占用沖突和路口沖突，等待法肯定可以解決沖突，在時間窗上表現(xiàn)為將要等待的AGV的時間窗往后平移至沒有重疊，二次規(guī)劃也可以解決，但是可能會導致新的沖突甚至死鎖。假設等待法多花費的時間為Δt，二次規(guī)劃的行駛時間為T2。如果滿足式(32)，則采用二次規(guī)劃法。

T1+Δt1>Tn+Δtn。

(32)

將時間窗嵌入到Dijkstra算法中，在對AGV進行路徑規(guī)劃的同時考慮避碰。為了減少計算量，對已經(jīng)規(guī)劃好路徑的AGV不再更改路徑。算法流程圖圖6。

圖6 基于時間窗的Dijkstra算法流程圖Fig. 6 Dijkstra algorithm flow chart based on time window

2.7 解 碼

以最大完工時間最小為優(yōu)化目標時，最優(yōu)解必然在主動調(diào)度集中[29]。故采用主動解碼，在不推遲已經(jīng)被安排的工序開工時間的前提下，根據(jù)工件的最早可開工時間查找機器能夠完成本道工序的空閑時間段進行插入式解碼。傳統(tǒng)的作業(yè)車間調(diào)度中，工件的最早可開工時間為前序工序的完工時間，而AGV和機器集成問題需要考慮工件的轉(zhuǎn)移時間，所以工件的最早可開工時間為AGV負載結(jié)束時間。

2.8 時間復雜度分析

T=2O(n)+O(N)+O(N·(n+f(n)))=O(N·(n+f(n)))。

(33)

T=5O(N·n)+O(N)+O(N·(n+f(n)))+O(f(n))=O(N·(n+f(n)))。

(34)

綜上所述，所提算法和原始鯨魚優(yōu)化算法的時間復雜度是一樣的，在同樣的運行環(huán)境下的運行時間在同一數(shù)量級。

2.9 算法流程

算法流程見圖7，具體流程如下。

步驟1 讀入初始信息，包括工件的加工信息和工廠的地圖信息。設置算法參數(shù)：種群規(guī)模NIND、最大迭代次數(shù)iitmax。

步驟2 根據(jù)種群規(guī)模和編碼方式初始化種群。

步驟3 判斷是否達到最大種群最大迭代次數(shù)，若達到，輸出最優(yōu)解；否則，計算所有個體最大完工時間并按照基于時間窗的Dijkstra算法進行路徑規(guī)劃，記錄當前全局最優(yōu)解，轉(zhuǎn)步驟4。

步驟4 判斷當前全局最優(yōu)解保持代數(shù)是否達到閾值，如達到，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟6。

步驟5 隨機生成種群規(guī)模50%的個體以替代種群中50%較劣的個體，轉(zhuǎn)步驟6。

步驟6 更新鯨魚種群。

步驟7 對當前種群較優(yōu)個體進行局部搜索。

步驟8 保持種群規(guī)模，選擇較優(yōu)個體進入下一次迭代，轉(zhuǎn)步驟3。

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

3 實驗分析

為了確定和檢驗離散型鯨魚優(yōu)化算法在求解AGV和機器集成調(diào)度時的性能，筆者在MATLAB 2019a的編程環(huán)境，Inter(R) Core(TM) i5-8500 CPU，3.0 GHz主頻，8.0 Gb內(nèi)存的運行環(huán)境下開展以下實驗：

1)標準算例對比實驗。對Ulusoy提出的標準算例庫進行實驗，并與其他學者已有的研究成果進行對比。

2)柔性算例實驗。對文獻[11]提出的柔性作業(yè)車間AGV和機器集成調(diào)度算例進行實驗。

3.1 標準算例實驗

表2中，LB by Ulusoy是由Ulusoy等[2]提出的下限法得到的理論最優(yōu)值；LB by Zheng是由Zheng等[6]提出的改進下限估算法得到的理論最優(yōu)值；STW是Bilge等[4]提出的滑動時間窗算法；AGA是Abdelmaguid等[5]提出的混合啟發(fā)式遺傳算法；MTS是Montane等[30]提出的禁忌搜索算法；PGA是Lyu等[11]提出的改進遺傳算法；WOA為原始鯨魚優(yōu)化算法；IWOA是筆者提出的離散型鯨魚優(yōu)化算法。其中STW，AGA，MTS，RGA以及PGA均來自于文獻中的原始數(shù)據(jù)。WOA和IWOA部分公共參數(shù)設置如下：種群規(guī)模80，最大迭代次數(shù)100。WOA的個體邊界設為1，IWOA的個體邊界設為3，最優(yōu)個體保持代數(shù)閾值設為20。WOA和IWOA對每一個算例獨立運行5次取最優(yōu)解，和其他文獻結(jié)果對比如表2和表3所示。

表2 t/p>0.25的算法結(jié)果比較

續(xù)表2

表3 t/p<0.25的算法結(jié)果比較

續(xù)表3

表2和表3中加粗的數(shù)據(jù)為各算法中最優(yōu)結(jié)果。從表2和表3中的82個標準算例的對比中可以發(fā)現(xiàn)原始鯨魚優(yōu)化算法在這種解空間較大的情形下，算法很難收斂到全局最優(yōu)解，性能表現(xiàn)較差。對其進行改進后，所有算例結(jié)果均不劣于原始鯨魚優(yōu)化算法，并有41個算例結(jié)果更優(yōu)；相較于原始鯨魚優(yōu)化算法的結(jié)果，IWOA有19個算例結(jié)果提升了5%以上，其中有7個算例結(jié)果提升了10%以上。在表2的40個標準算例中，IWOA所有算例結(jié)果均不劣于其他學者采用的方法；其中算例EX101、EX103、EX44、EX94、EX104結(jié)果優(yōu)于其他算法結(jié)果；特別的，算例EX22達到了理論最優(yōu)解。在表3中的42個標準算例中，IWOA有15個算例達到了理論最優(yōu)值；除算例EX840外，IWOA剩下所有算例的結(jié)果均不劣于其他學者提出的方法，其中算例EX441的結(jié)果優(yōu)于其他算法結(jié)果。由此可以看出，在解決AGV和機器集成調(diào)度的問題時，IWOA和其他算法相比具有一定的優(yōu)越性。

3.2 柔性算例實驗

為了驗證IWOA在柔性生產(chǎn)系統(tǒng)中的性能，對文獻[11]中的算例進行實驗，該算例中包含4個工件、6臺機器，AGV數(shù)量從1增加到6。文獻[11]中PGA運行參數(shù)為：種群規(guī)模設為80，最大迭代次數(shù)設為80，交叉率設為0.9，變異率設為0.1，算法獨立運行10次取最好結(jié)果。為了更好地對比，IWOA和WOA的種群規(guī)模、最大迭代次數(shù)、獨立運行次數(shù)和文獻[11]設為相同的值。WOA的個體邊界設為1，IWOA的個體邊界設為3，最優(yōu)個體保持代數(shù)閾值設為10。表4中v表示AGV數(shù)量，Cmax表示最大完工時間，單位為min，tcpu表示運行時間，單位為s，MT為平均最大完工時間，單位為min。

表4 柔性算例結(jié)果

從表4中可以看出，除了算例1中AGV數(shù)量為1時，IWOA的最大完工時間大于PGA，在其他算例中，IWOA的最大完工時間均不劣于其他兩種算法；并且在各算例中可以看出，最大完工時間隨著AGV數(shù)量的增加而減少，但增加到一定數(shù)量后不再變化，這是由于在AGV數(shù)量較少時，AGV數(shù)量為制約最大完工時間的主要因素，較多工件加工完成后需要等待AGV的運輸，當AGV增加到一定數(shù)量后，加工設備成為主要制約因素，較多工件運輸完成后需要等待加工機器。從表4中看出在加工機器數(shù)量相同的情況下，在算例1和算例2中，隨著AGV數(shù)量的增加，IWOA的最大完工時間小于PGA，這是由于IWOA使用了貪婪解碼，可以在較大程度上利用加工機器的空閑時間。在運行時間方面，WOA機制簡單，運行時間最短，IWOA的運行時間最長。從最大完工時間可以看出，在IWOA中平均值和最小值相差較大，這是因為IWOA中加入了Levy飛行的策略，可能導致出現(xiàn)一些較差解，但同時也可以使算法擁有跳出局部最優(yōu)的能力。

圖8為算例1中AGV數(shù)量為3時的甘特圖，ET表示AGV的空載行程?？梢钥闯?，所有工序開工時間在AGV負載結(jié)束時間、工件前序工序完工時間及機器前序工序完工時間之后，滿足約束條件。

圖8 最優(yōu)調(diào)度結(jié)果甘特圖Fig. 8 Optimal scheduling result Gantt chart

圖9為算例1中AGV數(shù)量為3時各路段的時間窗圖，用不同顏色區(qū)分AGV，可以看出，在任意時刻的縱坐標上不會出現(xiàn)同一輛AGV，說明AGV分配方案是可行的；在任意路段，不會出現(xiàn)不同AGV時間窗的重疊，說明AGV之間不會發(fā)生碰撞，IWOA可以為AGV規(guī)劃無沖突的路徑。

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

圖10是算例1中WOA和IWOA在AGV數(shù)量為3時的收斂曲線。WOA在迭代中后期目標值出現(xiàn)最大完工時間較大幅度減少，體現(xiàn)了WOA在后期具有較強局部開發(fā)能力的特點；但在這之后，最大完工時間不再改變，說明WOA陷入了局部最優(yōu)。相對WOA來說，IWOA的初始種群的質(zhì)量較高，驗證了IWOA的種群初始化方法的有效性；IWOA在第25代就開始收斂到了89 min，說明算法有較好的收斂速度和收斂精度。

圖10 算法收斂曲線Fig. 10 Algorithm convergence curve

4 結(jié) 論

針對柔性作業(yè)車間AGV和機器集成調(diào)度的問題，以最小化最大完工時間為優(yōu)化目標建立了相應的數(shù)學模型，并提出一種離散型鯨魚優(yōu)化算法進行求解。在離散型鯨魚優(yōu)化算法中，提出一種結(jié)合GLR選擇方法和混沌映射及對立學習的初始化策略，可以提高初始種群的多樣性；對原始鯨魚優(yōu)化算法中的調(diào)整規(guī)則進行了改進，節(jié)省算法運行時間的同時不僅可以避免個體被破壞，還可以在出現(xiàn)較多越界情況時防止個體相似度增大；引入levy飛行策略和閾值重啟操作，增強算法的全局搜索能力的同時增強算法跳出局部最優(yōu)的能力；設計了一種局部搜索策略，增強算法的收斂精度。通過和82個標準算例以及柔性算法的仿真對比實驗，證明了所提出算法的可行性和優(yōu)越性。下一步將研究考慮完工時間、AGV行駛時間、AGV等待時間等AGV和機器集成調(diào)度多目標優(yōu)化問題。