董舒豪，徐志剛+，常艷茹，秦開仲，朱建峰，蘇開遠(yuǎn)

(1.山東大學(xué) 機(jī)械工程學(xué)院，山東 濟(jì)南 250061；2.山東大學(xué) 深圳研究院，廣東 深圳 518057)

0 引言

設(shè)施布局是將若干作業(yè)單元合理地布置在給定的空間內(nèi)，布局方案形成后，將對(duì)企業(yè)的生產(chǎn)成本、在制品、交貨期、生產(chǎn)效率、工作環(huán)境等產(chǎn)生重要影響，關(guān)系到企業(yè)能否充分發(fā)揮其經(jīng)濟(jì)效益與社會(huì)效益[1-2]。因此，設(shè)計(jì)出合理的設(shè)施布局方案對(duì)企業(yè)生產(chǎn)運(yùn)營(yíng)尤為重要。

設(shè)施布局問題因其有重要性與復(fù)雜性而受到國(guó)內(nèi)外眾多學(xué)者的廣泛關(guān)注與研究。當(dāng)前設(shè)施布局問題的研究多是首先構(gòu)建出布局優(yōu)化模型，然后采用智能優(yōu)化算法求解，常見的算法有遺傳算法(Genetic Algorithm, GA)[3]、蛙跳算法[4]、模擬退火(Simulated Annealing, SA)算法[5]、蟻群算法[6]、粒子群算法[7]，還有一些較新型的算法應(yīng)用在設(shè)施布局中，如殖民競(jìng)爭(zhēng)算法[8]、螢火蟲算法[9]、隨機(jī)生長(zhǎng)算法[10]等。設(shè)施布局模型的準(zhǔn)確性和真實(shí)性是采用算法求解并獲得有效布局方案的前提，文獻(xiàn)[3-10]的布局模型中將物料裝卸點(diǎn)的位置定義在作業(yè)單元的中心點(diǎn)，然而實(shí)際生產(chǎn)中，作業(yè)單元的面積、物料裝卸點(diǎn)位置各不相同，因此假定物料裝卸點(diǎn)處于作業(yè)單元中心的布局模型在反映實(shí)際情況時(shí)具有一定局限性。Das[11]提出一種布局模型，模型中裝料點(diǎn)與卸料點(diǎn)在同一位置，并限制在作業(yè)單元的中心線上；Kim等[12]、Xiao等[13]對(duì)前述布局模型中的物料裝卸點(diǎn)位置進(jìn)行了改進(jìn)，討論了布局中裝料點(diǎn)與卸料點(diǎn)分離的情況，且其位置不限定在作業(yè)單元中心或中心線上，該思想比較符合實(shí)際。

物料搬運(yùn)費(fèi)用通常是設(shè)施布局設(shè)計(jì)中首要考慮的因素，因此設(shè)施布局模型中搬運(yùn)距離的準(zhǔn)確表示也將直接影響布局方案的優(yōu)劣。目前諸多設(shè)施布局問題研究中，常用歐氏距離(直線距離)[5-6,9]和曼哈頓距離(矩形距離)[3-4,7-8,10-13]表示作業(yè)單元之間的物料搬運(yùn)距離，然而實(shí)際物料搬運(yùn)中，搬運(yùn)設(shè)備通常沿著避開障礙的通道進(jìn)行物料搬運(yùn)，因此采用歐氏距離和曼哈頓距離這兩種簡(jiǎn)化的搬運(yùn)距離計(jì)算方法可能會(huì)引起較大誤差，使最終布局方案不能滿足設(shè)計(jì)要求[14]。為了使搬運(yùn)距離的計(jì)算更加符合實(shí)際，黃小榮[15]以多行設(shè)施布局問題為研究對(duì)象，提出一種實(shí)際搬運(yùn)距離計(jì)算方法，然而文中布局方案沒有設(shè)計(jì)搬運(yùn)通道，且未考慮物料裝卸點(diǎn)實(shí)際位置對(duì)搬運(yùn)距離計(jì)算的影響；lee等[16-17]采用預(yù)先構(gòu)建的鄰接圖將搬運(yùn)設(shè)備的行進(jìn)路線限定在通道上，進(jìn)而采用Dijkstra算法求出物料搬運(yùn)的最短距離，然而所有通道的位置均假設(shè)為固定，且未考慮物料裝卸點(diǎn)的實(shí)際位置。

為解決以上問題，本文以多行設(shè)施布局問題為研究對(duì)象，提出考慮物料裝卸點(diǎn)與搬運(yùn)通道的多行設(shè)施布局設(shè)計(jì)方法；對(duì)多行設(shè)施布局問題中的物料裝卸點(diǎn)表示方法進(jìn)行分析，并在考慮物料裝卸點(diǎn)的前提下，分析多行設(shè)施布局中搬運(yùn)設(shè)備沿搬運(yùn)通道進(jìn)行物料搬運(yùn)的距離計(jì)算方法，其中著重分析與構(gòu)建避障搬運(yùn)的最短路徑表示方法和求解算法；建立更加符合實(shí)際的多行設(shè)施布局優(yōu)化模型，并設(shè)計(jì)遺傳模擬退火(Genetic Simulated Annealing, GSA)算法對(duì)模型進(jìn)行求解，以對(duì)GA和SA兩種算法取長(zhǎng)補(bǔ)短，生成更加有效且切合實(shí)際的布局方案。

1 問題描述和分析

1.1 問題描述

考慮物料裝卸點(diǎn)和搬運(yùn)通道的多行設(shè)施布局可以描述為：將若干個(gè)作業(yè)單元分配到多個(gè)具有相同高度的固定行中，裝料點(diǎn)和卸料點(diǎn)通常位于作業(yè)單元內(nèi)的邊緣位置，搬運(yùn)設(shè)備沿搬運(yùn)通道行進(jìn)，目的是使設(shè)計(jì)目標(biāo)集達(dá)到最大或最小化。同時(shí)，問題還有以下假設(shè)條件：

(1)作業(yè)單元內(nèi)的裝料點(diǎn)和卸料點(diǎn)通常位于作業(yè)單元內(nèi)部的邊緣，并靠近同一橫向通道的位置，有特殊作業(yè)單元(如原料存放區(qū))的物料裝卸點(diǎn)在其中心位置。

(2)給定作業(yè)單元內(nèi)物料裝卸點(diǎn)的初始位置，但可以根據(jù)特定規(guī)則發(fā)生一定改變。

(3)布局總區(qū)域的面積大于所有作業(yè)單元與通道所占面積之和。

(4)橫向通道與縱向通道的數(shù)量、寬度均為已知，橫向通道的位置已定，縱向通道位于中間行內(nèi)，每一中間行內(nèi)縱向通道的數(shù)量已知，但其位置不定。

(5)布局總區(qū)域與作業(yè)單元的形狀均為矩形，長(zhǎng)寬為固定值，作業(yè)單元的寬度與行的寬度相等。

圖1所示為考慮物料裝卸點(diǎn)與搬運(yùn)通道的多行設(shè)施布局形式，wf為行或作業(yè)單元的寬度，wh和wv為橫向通道與縱向通道的寬度。

1.2 物料裝卸點(diǎn)位置的定義與分析

考慮物料裝卸點(diǎn)位置的情況下需要進(jìn)一步考慮作業(yè)單元的方向，即作業(yè)單元的擺放形式。本文定義了多行設(shè)施布局中作業(yè)單元的4種擺放形式，如圖2所示。其中：圖2a為給定原始作業(yè)單元i的中心位于笛卡爾坐標(biāo)系的原點(diǎn)，裝料點(diǎn)坐標(biāo)為(xO,yO)，卸料點(diǎn)坐標(biāo)為(xI,yI)；圖2b為原始作業(yè)單元內(nèi)的設(shè)備與物料裝卸點(diǎn)同時(shí)繞作業(yè)單元中心旋轉(zhuǎn)180°后所呈現(xiàn)的擺放形式；圖2c為原始作業(yè)單元中的設(shè)備倒置或倒序排列后所呈現(xiàn)的擺放形式，物料裝卸點(diǎn)會(huì)以y軸為對(duì)稱軸發(fā)生類似于鏡像的位置變化；圖2d為原始作業(yè)單元同時(shí)旋轉(zhuǎn)與鏡像后所呈現(xiàn)的擺放形式。

表1 物料裝卸點(diǎn)在作業(yè)單元中的表示

以上定義了物料裝卸點(diǎn)位置在局部作業(yè)單元內(nèi)的表示方法，作業(yè)單元的中心位置定義為坐標(biāo)原點(diǎn)。然而在布局整體坐標(biāo)系中，作業(yè)單元的中心位置為其實(shí)際中心位置，因此需要將作業(yè)單元內(nèi)的物料裝卸點(diǎn)坐標(biāo)轉(zhuǎn)化為布局整體坐標(biāo)系中的坐標(biāo)。對(duì)于圖2中的4種情況，物料裝卸點(diǎn)坐標(biāo)從局部作業(yè)單元轉(zhuǎn)化至布局整體坐標(biāo)系的過(guò)程均可表示為：

(1)

1.3 物料搬運(yùn)精確距離分析

為了避免歐氏距離和曼哈頓距離表示物料搬運(yùn)距離時(shí)的缺點(diǎn)，提出多行設(shè)施布局中搬運(yùn)設(shè)備沿通道進(jìn)行物料搬運(yùn)的精確距離計(jì)算方法。為了便于分析，本文將多行設(shè)施布局中的物料搬運(yùn)分為無(wú)障礙搬運(yùn)和避障搬運(yùn)。

1.3.1 無(wú)障礙搬運(yùn)

無(wú)障礙搬運(yùn)描述為：為完成一次物料搬運(yùn)，搬運(yùn)設(shè)備除了裝卸物料時(shí)需要轉(zhuǎn)變行進(jìn)方向以進(jìn)入作業(yè)單元內(nèi)部外，其余時(shí)刻只沿一條橫向通道直線行進(jìn)，其基本類型如圖3所示。

圖3中的無(wú)障礙搬運(yùn)距離

diOjI=

(2)

式中：diOjI為作業(yè)單元i的裝料點(diǎn)到作業(yè)單元j的卸料點(diǎn)的實(shí)際搬運(yùn)距離；y′為作業(yè)單元i的裝料點(diǎn)和j的卸料點(diǎn)臨近的同一橫向通道y方向上的中心坐標(biāo)。

1.3.2 避障搬運(yùn)及其表示方法

避障搬運(yùn)描述為：為完成一次物料搬運(yùn)，搬運(yùn)設(shè)備除了裝卸物料時(shí)需要轉(zhuǎn)變行進(jìn)方向外，還會(huì)因需要沿避開作業(yè)單元阻擋的縱向通道行進(jìn)而轉(zhuǎn)變方向，即搬運(yùn)過(guò)程中會(huì)穿過(guò)某些行。避障搬運(yùn)中，通常要經(jīng)過(guò)兩條或兩條以上橫向通道，且會(huì)經(jīng)過(guò)縱向通道，其基本類型如圖4所示。

節(jié)點(diǎn)個(gè)數(shù)和坐標(biāo)確定后，需要確定如圖5所示的鄰接圖和鄰接矩陣，鄰接圖中每條有向邊的長(zhǎng)度表示相連兩節(jié)點(diǎn)之間的曼哈頓距離，而不可達(dá)節(jié)點(diǎn)之間的距離為∞，可見圖5中①～⑥有兩條可以選擇的路徑。需要注意的是，若中間行的數(shù)量或中間行內(nèi)縱向通道的數(shù)量增加，則物料搬運(yùn)可供選擇的路徑將會(huì)增加，如圖6所示。

1.3.3 避障搬運(yùn)距離計(jì)算的Dijkstra算法

Dijkstra算法是一種基于圖論的算法，適用于計(jì)算單源點(diǎn)最短路徑問題。設(shè)G={V,E}為一類似于圖5和圖6中構(gòu)建的帶權(quán)有向圖，EN×N類似于圖5中的鄰接矩陣，V={V1,V2,…,VN}為節(jié)點(diǎn)集合，節(jié)點(diǎn)集合分為S和U，S中的節(jié)點(diǎn)已經(jīng)計(jì)算出源點(diǎn)至其最短路徑，U中的節(jié)點(diǎn)未計(jì)算出源點(diǎn)至其最短路徑。設(shè)VO為裝料點(diǎn)(源點(diǎn))，用d[i]記錄當(dāng)前已知的VO至Vi的最短距離，則Dijkstra算法計(jì)算物料搬運(yùn)避障最短距離的步驟如下：

(1)初始化S={VO}與U中各節(jié)點(diǎn)的d[i]值，若VO至Vi可達(dá)，則d[i]為VO至Vi的曼哈頓距離，否則d[i]=∞。

(2)從U中選擇d[i]值最小的節(jié)點(diǎn)Vk加入S。

(3)以Vk作為新的中間點(diǎn)，更新U中各節(jié)點(diǎn)的d[i]值，更新方式為d[i]=min{d[i],d[k]+Eki}。

(4)重復(fù)(2)和(3)，直到U中無(wú)節(jié)點(diǎn)。

上述步驟執(zhí)行完之后，即可求得裝料點(diǎn)到卸料點(diǎn)的避障最短搬運(yùn)距離，即實(shí)際搬運(yùn)距離。

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

2.1 物料搬運(yùn)成本

物料搬運(yùn)成本為作業(yè)單元間物流量與實(shí)際搬運(yùn)距離乘積的總和，其目標(biāo)函數(shù)表示為

(3)

式中：n為作業(yè)單元的數(shù)量；fiOjI為作業(yè)單元i的裝料點(diǎn)至作業(yè)單元j的卸料點(diǎn)的單向物流量；diOjI為作業(yè)單元i的裝料點(diǎn)至作業(yè)單元j的卸料點(diǎn)的實(shí)際搬運(yùn)距離，計(jì)算方法見1.3節(jié)。

2.2 搬運(yùn)設(shè)備空載運(yùn)行成本

搬運(yùn)設(shè)備空載運(yùn)行以圖7說(shuō)明。搬運(yùn)設(shè)備搬運(yùn)作業(yè)單元k至l之間物料的同時(shí)，作業(yè)單元i的物料需要運(yùn)送至作業(yè)單元j，搬運(yùn)設(shè)備則將正在搬運(yùn)的物料送至作業(yè)單元l后，由作業(yè)單元l處的卸料點(diǎn)空載運(yùn)行至作業(yè)單元i的裝料點(diǎn)處，才能完成作業(yè)單元i至j的物料搬運(yùn)請(qǐng)求。

搬運(yùn)設(shè)備執(zhí)行下一項(xiàng)物料搬運(yùn)任務(wù)前處于不確定的作業(yè)單元卸料點(diǎn)處，用Pl表示其處于作業(yè)單元l的卸料點(diǎn)處的概率，

(4)

由式(4)可知，如果其他作業(yè)單元至作業(yè)單元l有較大的物流量，則搬運(yùn)設(shè)備處于作業(yè)單元l的卸料點(diǎn)處的概率較大，反之則較小。搬運(yùn)設(shè)備為完成作業(yè)單元i至作業(yè)單元i的物料搬運(yùn)所需空載運(yùn)行的距離為

(5)

進(jìn)一步，搬運(yùn)設(shè)備空載運(yùn)行成本的目標(biāo)函數(shù)可以表示為

(6)

式中c為搬運(yùn)設(shè)備的空載系數(shù)。

2.3 相互關(guān)系

與物料搬運(yùn)不同的是，作業(yè)單元之間的相互關(guān)系是一種功能性關(guān)系，其目標(biāo)函數(shù)中，使用作業(yè)單元中心點(diǎn)之間的曼哈頓距離進(jìn)行計(jì)算。目標(biāo)函數(shù)可以表示為：

(7)

表2 相互關(guān)系等級(jí)的量化取值

2.4 約束分析

多行設(shè)施布局在尋求目標(biāo)集最優(yōu)化的同時(shí)，還要滿足作業(yè)單元不重疊、不越出布局區(qū)域邊界、物料裝卸點(diǎn)靠近橫向通道等約束。為了便于描述與理解，首先定義以下變量：

(8)

(9)

(10)

(11)

(12)

進(jìn)一步，考慮物料裝卸點(diǎn)與搬運(yùn)通道的多行設(shè)施布局約束條件如下：

(13)

(14)

(15)

(16)

αi1βi=1，i∈[1,n]；

(17)

αimβi=0，i∈[1,n]；

(18)

i,j∈[1,n],i≠j；

(19)

i∈[1,n],l∈[1,nt]；

(20)

i,j∈[1,n],i≠j；

(21)

i∈[1,n],l∈[1,nt]；

(22)

l,u∈[1,nt],l≠u；

(23)

(24)

(25)

βi,ηi=0,1，i∈[1,n]；

(26)

αik=0,1，i∈[1,n],k∈[1,m]；

(27)

δlk=0,1，l∈[1,nt],k∈[2,m-1]。

(28)

式(13)和式(14)保證一個(gè)作業(yè)單元只能屬于一行；式(15)和式(16)保證一個(gè)縱向通道只能屬于一個(gè)中間行內(nèi)；式(17)和式(18)保證第一行與最后一行中作業(yè)單元內(nèi)的物料裝卸點(diǎn)靠近橫向通道；式(19)保證任意兩個(gè)作業(yè)單元不重疊，式(20)保證任意一個(gè)作業(yè)單元與任意一個(gè)縱向通道不重疊；式(21)～式(23)為布局中的邊界約束；式(24)保證任意兩個(gè)縱向通道不相鄰排列；式(25)為縱向通道的位置約束；式(26)保證任意一個(gè)作業(yè)單元有4種可能的擺放形式；式(27)和式(28)為決策變量的取值范圍。

3 求解算法設(shè)計(jì)

3.1 遺傳算法與模擬退火算法的結(jié)合

本文所提多行設(shè)施布局問題是一種多目標(biāo)離散優(yōu)化問題，該布局問題的求解不僅與作業(yè)單元之間的相對(duì)位置排列有關(guān)，還受作業(yè)單元自身擺放形式、縱向通道位置等影響，求解難度更大。為能較好地解決本文所提問題，提出一種采用分段編碼方式表示布局方案信息的GSA算法。

3.2 適應(yīng)度函數(shù)的構(gòu)建

由于式(3)、式(6)和式(7)中diOjI與rij的度量單位不同，如果將這3種目標(biāo)函數(shù)直接結(jié)合，則可能引起較大誤差。因此在構(gòu)建適應(yīng)度函數(shù)之前，首先對(duì)其分別進(jìn)行標(biāo)準(zhǔn)化處理，物流量與相互關(guān)系等級(jí)標(biāo)準(zhǔn)化處理的過(guò)程如式(29)和式(30)所示。

(29)

(30)

引入權(quán)重系數(shù)w1，w2，w3與常數(shù)C，構(gòu)建適應(yīng)度函數(shù)

(31)

式中:F恒大于0；0

3.3 編碼方式

本文采用GA編碼的思想，以染色體表示布局方案。將染色體分為4段，如圖8所示。

圖中染色體表示作業(yè)單元數(shù)量為n、縱向通道數(shù)量為nt的多行設(shè)施布局。其中：第1段表示作業(yè)單元的排列順序，ui為作業(yè)單元的代號(hào)，本文規(guī)定作業(yè)單元的排列順序?yàn)樽陨舷蛳?、自左向右，遵守自?dòng)換行策略；第2段表示作業(yè)單元是否發(fā)生旋轉(zhuǎn)，其上的基因與第1段的基因相對(duì)應(yīng)，si=0時(shí)原始作業(yè)單元不發(fā)生旋轉(zhuǎn)，si=1時(shí)原始作業(yè)單元旋轉(zhuǎn)；第3段表示作業(yè)單元是否發(fā)生鏡像，同樣其上的基因分別與第1段的基因相對(duì)應(yīng)，mi=0時(shí)原始作業(yè)單元不發(fā)生鏡像，mi=1時(shí)原始作業(yè)單元鏡像；第4段表示縱向通道在指定行中的位置，vi為整數(shù)，取值范圍與其對(duì)應(yīng)行中作業(yè)單元的個(gè)數(shù)有關(guān)。

3.4 交叉操作

本文采用順序交叉方式，針對(duì)染色體前3段進(jìn)行交叉，交叉步驟為：首先從父代P1的第1段染色體片段中隨機(jī)選擇連續(xù)的一組位置，將這些位置對(duì)應(yīng)的基因復(fù)制到一個(gè)空染色體的相應(yīng)位置上，構(gòu)成一個(gè)原始后代；刪去父代P2第1段上相應(yīng)的基因，將P2第1段上剩余的基因按順序填入原始后代第1段染色體片段的空缺位置上；染色體第2段與第3段基因隨第1段也發(fā)生相應(yīng)交叉，父代P1的第4段基因直接復(fù)制到原始后代中，形成子代C1，并以同樣的方式產(chǎn)生另一個(gè)子代C2。順序交叉方式如圖9所示。

3.5 變異操作

(1)基因位置的互換變異

基因位置的變異采用互換變異的方法，隨機(jī)選擇染色體第1片段上的兩個(gè)位置，將這兩個(gè)位置上的基因互換，相應(yīng)第2段和第3段染色體片段上基因的位置也進(jìn)行互換，如圖10所示。

(2)旋轉(zhuǎn)、鏡像與通道變異

旋轉(zhuǎn)變異、鏡像變異和通道變異分別針對(duì)第2～4段染色體片段進(jìn)行變異，變異過(guò)程如圖11所示。

以上3種變異中，通道變異是染色體未發(fā)生交叉和互換變異時(shí)才會(huì)進(jìn)行的一項(xiàng)變異操作，目的是在作業(yè)單元相互位置不改變時(shí)，通過(guò)改變縱向通道位置進(jìn)行局部尋優(yōu)。例如染色體第4段上的一個(gè)基因由1變?yōu)?，則縱向通道位置由該行第1個(gè)作業(yè)單元的右側(cè)，變?yōu)樵撔械?個(gè)作業(yè)單元的右側(cè)，其變異表達(dá)方式如圖12所示。

3.6 修正操作

(1)邊界修正

本文規(guī)定作業(yè)單元的排列為自上向下、自左向右的順序，遵守自動(dòng)換行策略，因此最下方一行作業(yè)單元可能會(huì)越出右側(cè)邊界，如圖13所示。

(2)方向修正

圖14中邊界約束修正完成后，即可產(chǎn)生縱向通道的位置，如圖15所示。因?yàn)榇蟛糠肿鳂I(yè)單元內(nèi)的物料裝卸點(diǎn)要求位于靠近橫向通道的位置，所以修正了邊界約束后，還要對(duì)作業(yè)單元的方向進(jìn)行修正。以圖14為例，方向修正后的染色體及布局如圖15所示。

3.7 模擬退火操作

SA操作每產(chǎn)生一個(gè)新的解，都會(huì)與當(dāng)前解進(jìn)行對(duì)比，該操作可能接受比當(dāng)前解更差的解。設(shè)ΔE為新解與當(dāng)前解的適應(yīng)度值之差，則對(duì)于求最大值的優(yōu)化問題，新解被接受的概率

(32)

式中：k為Boltzmann常數(shù)；T為當(dāng)前溫度。

本文SA操作采用3.5節(jié)的變異方式產(chǎn)生新解。設(shè)Rand為取自區(qū)間[0,1)上服從均勻分布的隨機(jī)浮點(diǎn)數(shù)，若Rand∈[0,0.25)，則隨機(jī)發(fā)生一次基因位置的互換變異；若Rand∈[0.25，0.5)，則隨機(jī)發(fā)生一次旋轉(zhuǎn)變異；Rand∈[0.5,0.75)，則隨機(jī)發(fā)生一次鏡像變異；若Rand∈[0.75,1)，則隨機(jī)發(fā)生一次通道變異。

3.8 遺傳模擬退火算法流程

本文將GA與SA結(jié)合，旨在使兩種算法取長(zhǎng)補(bǔ)短，提高算法求解設(shè)施布局問題的尋優(yōu)能力和穩(wěn)定性。本文GSA算法的步驟如下：

步驟1初始化染色體種群中個(gè)體的前3段。

步驟2修正邊界，產(chǎn)生染色體的第4段(即隨機(jī)產(chǎn)生縱向通道的位置)，然后修正方向。

步驟3計(jì)算適應(yīng)度，并檢驗(yàn)是否達(dá)到最大迭代次數(shù)，若滿足則輸出最優(yōu)解，否則執(zhí)行步驟4。

步驟4更新迭代次數(shù)i和當(dāng)前火溫T，火溫更新大小由退火因子r決定，采用精英保留策略與輪盤賭方法選出下一代染色體。

步驟6檢驗(yàn)是否達(dá)到最大迭代次數(shù)，若滿足則輸出最優(yōu)解，否則轉(zhuǎn)步驟4。

圖16所示為本文所提GSA算法的流程。

4 案例分析

4.1 原始數(shù)據(jù)

某矩形車間長(zhǎng)76 m，寬30 m，車間內(nèi)有15個(gè)作業(yè)單元，擬布置在3行內(nèi)。橫向通道、縱向通道的寬度均為3 m，行與作業(yè)單元的寬度均為8 m，其中中間一行要求有兩條縱向通道。作業(yè)單元的長(zhǎng)度與局部作業(yè)單元內(nèi)物料裝卸點(diǎn)的坐標(biāo)信息如表3所示。

表3 作業(yè)單元信息

作業(yè)單元間的物流量矩陣D與相互關(guān)系矩陣R分別為：

4.2 實(shí)例求解

適應(yīng)度函數(shù)中，常數(shù)C=25，空載系數(shù)c與搬運(yùn)設(shè)備類型相關(guān)，本文取為0.6，權(quán)重系數(shù)w1，w2，w3由專家打分法得出，分別取為0.4，0.3，0.3，根據(jù)原始數(shù)據(jù)可求得dmax=94.5 m。

針對(duì)上述案例，分別采用GA，SA，GSA求解，并將改進(jìn)煙花算法(Improved Fireworks Algorithm, IFA)[19]、布谷鳥搜索(Cuckoo Search, CS)算法[20]與兩階段改進(jìn)模擬退火(Improved Simulated Annealing, ISA)算法[21]應(yīng)用于本文案例進(jìn)行對(duì)比分析。6種算法的迭代終止規(guī)則均由迭代終止次數(shù)Iter控制，Iter=500。GA的種群規(guī)模Pop_size=50，交叉概率Pc=0.9，互換變異概率Pe=0.1，旋轉(zhuǎn)變異概率Ps=0.1，鏡像變異概率Pm=0.05，通道變異概率Pv=0.1；SA算法中為單個(gè)體尋優(yōu)，初始火溫T=2 000，擾動(dòng)次數(shù)Sn=200，退火因子r=0.96，Boltzmann常數(shù)k=1；GSA算法中種群規(guī)模Pop_size=50，交叉概率Pc=0.9，互換變異概率Pe=0.1，旋轉(zhuǎn)變異概率Ps=0.1，鏡像變異概率Pm=0.05，通道變異概率Pv=0.1，初始火溫T=2 000，擾動(dòng)次數(shù)Sn=200，退火因子r=0.96，Boltzmann常數(shù)k=1；IFA中種群規(guī)模Pop_size=50，搜索深度系數(shù)αd=5；CS算法中種群規(guī)模Pop_size=50，拋棄概率pab=0.25，步長(zhǎng)縮放因子αs=0.02；ISA算法中為單個(gè)體尋優(yōu)，初始溫度T=100，退火因子r=0.98，Boltzmann常數(shù)k=1，最小抽樣次數(shù)Mstep=5，抽樣閾值Rin=8，退火閾值Rout=20，終止溫度Tend=1。

采用C++語(yǔ)言分別編寫以上6種算法的程序，每種算法分別進(jìn)行20次獨(dú)立測(cè)試。6種算法得到的最優(yōu)適應(yīng)度為39.133 6，對(duì)應(yīng)的最優(yōu)染色體及最優(yōu)染色體解碼后的布局如圖17所示。

4.3 算法分析

表4所示為6種算法分別獨(dú)立測(cè)試20次得到的最優(yōu)適應(yīng)度數(shù)據(jù)，可以看出相比其他5種算法，GSA算法搜索到的解的質(zhì)量與穩(wěn)定性具有比較明顯的優(yōu)勢(shì)。

表4 不同算法最優(yōu)適應(yīng)度的對(duì)比

圖18所示為6種算法分別獨(dú)立測(cè)試20次的平均最優(yōu)適應(yīng)度進(jìn)化曲線。從6種算法搜索到的解的質(zhì)量來(lái)看，GA，CS，ISA較差，原因可能是GA，CS兩種算法的局部搜索能力較差，ISA算法為單個(gè)體尋優(yōu)，多樣性差，而且采用的2-opt算子在本案例搜索中不具優(yōu)勢(shì)，搜索深度不夠。而SA，GSA，IFA搜索到的解的質(zhì)量較高，SA算法相對(duì)較好的搜索質(zhì)量在一定程度上表明本文SA操作的可行性，但由于缺乏跳出局部最優(yōu)的算子，導(dǎo)致其在進(jìn)化中后期難以搜索到更好的解；IFA在進(jìn)化初期就進(jìn)行了局部深度搜索，因此表現(xiàn)出了較好的性能，但進(jìn)化中后期搜索速度較慢，原因可能是IFA所采用的兩點(diǎn)變異操作不能較好地跳出局部最優(yōu)；GSA算法在進(jìn)化初期主要進(jìn)行遺傳操作，該時(shí)期GSA算法不具優(yōu)勢(shì)，但在進(jìn)化中期，隨著SA操作執(zhí)行次數(shù)的增加與火溫T的降低，其搜索到的解的質(zhì)量很高，逐漸超過(guò)CS，ISA，IFA，并在進(jìn)化后期一定程度上克服了SA的缺點(diǎn)，平均最優(yōu)適應(yīng)度進(jìn)化曲線仍然有上升的趨勢(shì)，原因是GSA算法由多個(gè)個(gè)體尋優(yōu)，且進(jìn)化后期少量的交叉、變異操作有利于算法擴(kuò)大搜索空間，跳出局部最優(yōu)并使搜索進(jìn)一步趨于全局最優(yōu)，因此GSA算法較好地融合了GA和SA的優(yōu)點(diǎn)，求解本文案例的效果較好。

5 結(jié)束語(yǔ)

本文針對(duì)多行設(shè)施布局尤其是兩行以上的布局問題，提出考慮物料裝卸點(diǎn)與搬運(yùn)通道的多行設(shè)施布局設(shè)計(jì)方法，具體如下：

(1)分析了物料裝卸點(diǎn)位置在作業(yè)單元內(nèi)的表示方法，及其從作業(yè)單元內(nèi)向布局整體坐標(biāo)系轉(zhuǎn)化的方法，使布局問題更加切合實(shí)際。

(2)分析了多行設(shè)施布局中搬運(yùn)設(shè)備沿通道進(jìn)行物料搬運(yùn)的精確距離計(jì)算方法，重點(diǎn)構(gòu)建了避障搬運(yùn)的鄰接圖和鄰接矩陣表示法，并設(shè)計(jì)了基于鄰接圖和鄰接矩陣的避障搬運(yùn)距離Dijkstra算法，可為復(fù)雜系統(tǒng)中的物料搬運(yùn)系統(tǒng)設(shè)計(jì)提供參考。

(3)構(gòu)建了以物料搬運(yùn)成本、搬運(yùn)設(shè)備空載運(yùn)行成本和作業(yè)單元間相互關(guān)系為目標(biāo)函數(shù)的布局優(yōu)化模型，分析了考慮物料裝卸點(diǎn)與搬運(yùn)通道的多行設(shè)施布局約束條件，并設(shè)計(jì)了求解模型的GSA。以一個(gè)三行設(shè)施布局為實(shí)例，采用所提算法生成了切合實(shí)際的布局方案，證明了所提算法在尋優(yōu)能力和穩(wěn)定性方面均具有較好的性能。

未來(lái)將進(jìn)一步研究具有不規(guī)則作業(yè)單元形狀的設(shè)施布局問題，以豐富該領(lǐng)域的模型和設(shè)計(jì)方法。另外，還需要深入研究多行設(shè)施布局形式以外的其他設(shè)施布局問題，并針對(duì)物料搬運(yùn)通道或路線進(jìn)行重點(diǎn)分析和設(shè)計(jì)。