基于遺傳算法的車(chē)間布局優(yōu)化研究

閆向彤，張永鑫，李佩澤，楊 琦

(西安科技大學(xué)機(jī)械工程學(xué)院，陜西 西安 710054)

工廠設(shè)施布置的規(guī)劃一直是工業(yè)工程領(lǐng)域不斷研究和探索的內(nèi)容，其中最具代表性之一的是系統(tǒng)布置設(shè)計(jì)(system layout planning，SLP)方法。作為一種經(jīng)典且有效的方法，其為設(shè)施布置提供了很好的改善思路，但在長(zhǎng)期的發(fā)展中也存在一些不可避免的缺點(diǎn)，如計(jì)算結(jié)果不夠精確，很難確保計(jì)算結(jié)果較優(yōu)且受人員主觀因素的影響較大等。而隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，基于計(jì)算機(jī)技術(shù)的啟發(fā)式算法在數(shù)據(jù)處理、數(shù)學(xué)建模、運(yùn)算速度等方面相比傳統(tǒng)方法具備更大的優(yōu)勢(shì)，因此在用SLP方法布置時(shí)完全可以將大量計(jì)算求解的工作交由計(jì)算機(jī)處理，從而可大幅度提高布置效率和布置結(jié)果的精確性[1]。目前設(shè)施布置設(shè)計(jì)的模型與算法已經(jīng)比較成熟，常見(jiàn)的有遺傳算法、蟻群算法、模擬退火算法等啟發(fā)式算法。相比于其他算法，遺傳算法具有處理范圍廣、全局尋優(yōu)等特點(diǎn)，因此本文采用基于遺傳算法的SLP方法對(duì)設(shè)施布置進(jìn)行優(yōu)化研究。

1 模型建立

1.1 模型假設(shè)

M公司絲印車(chē)間場(chǎng)地大、物流量高，且存在設(shè)施布局不當(dāng)、現(xiàn)場(chǎng)作業(yè)環(huán)境混亂等缺點(diǎn)，因此會(huì)造成很大的搬運(yùn)浪費(fèi)。為了分析該制造企業(yè)生產(chǎn)車(chē)間的物流現(xiàn)狀及存在的問(wèn)題，首先采用SLP方法對(duì)該車(chē)間進(jìn)行改善分析[2]。生產(chǎn)車(chē)間布局優(yōu)化的主要目標(biāo)是實(shí)現(xiàn)作業(yè)單位間非物流關(guān)系的最大化和物料搬運(yùn)成本的最小化，本文根據(jù)這兩個(gè)目標(biāo)和設(shè)施布置的相關(guān)理論，建立生產(chǎn)車(chē)間布局優(yōu)化模型。根據(jù)車(chē)間的實(shí)際情況，可將該布局問(wèn)題視為生產(chǎn)設(shè)施布局優(yōu)化問(wèn)題[3]，假設(shè):

1)所有作業(yè)單位所在平面為共平面；

2)各單位形狀均為矩形，忽略形狀細(xì)節(jié)，且各個(gè)矩形邊與X軸、Y軸平行[4]；

3)不同作業(yè)單位間單位運(yùn)輸成本一致；

4)作業(yè)單位間X軸間距已知，Y軸間距根據(jù)實(shí)際情況進(jìn)行考慮。

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

根據(jù)以上假設(shè)條件，建立車(chē)間作業(yè)單位布局模型，如圖1所示。

圖1 作業(yè)單位布局模型示意圖

模型目標(biāo)函數(shù)為搬運(yùn)費(fèi)用最小化及非物流關(guān)系最大化。

假設(shè)布置方案為X，i和j為該方案的作業(yè)單位，兩者距離用dij表示，搬運(yùn)量用fij表示，可得距離矩陣及物流量矩陣[5]，進(jìn)而求得物料搬運(yùn)成本表達(dá)式如下：

(1)

式中：C1為總搬運(yùn)成本；cij為各單位之間的搬運(yùn)成本。非物流關(guān)系表達(dá)式如下：

(2)

式中：C2為非物流關(guān)系總和；Tij為作業(yè)單位之間非物流關(guān)系的緊密程度[6]，等級(jí)為A,E,I,O,U,X，對(duì)應(yīng)數(shù)值為4,3,2,1,0，-1；bij為非物流關(guān)系等級(jí)與距離的關(guān)聯(lián)因子。設(shè)dmax為任意兩個(gè)設(shè)施之間的最大距離，關(guān)聯(lián)因子量化表見(jiàn)表1。

表1 關(guān)聯(lián)因子量化表

由此可得兩個(gè)基本目標(biāo)，即C1的最小化及C2的最大化，從而構(gòu)建雙目標(biāo)函數(shù)如下：

(3)

(4)

為方便求解，將雙目標(biāo)函數(shù)C1和C2進(jìn)行合并，得到單目標(biāo)函數(shù)C表達(dá)式如下：

(5)

由于兩者量綱不同，需要對(duì)函數(shù)C1和C2做標(biāo)準(zhǔn)化處理：

(6)

(7)

得到最終目標(biāo)函數(shù)表達(dá)式C為

(8)

為符合現(xiàn)實(shí)實(shí)施情況，需要對(duì)目標(biāo)函數(shù)作相應(yīng)約束，首先設(shè)定作業(yè)單位不重疊約束：

(9)

(10)

其次設(shè)定邊界約束：

(11)

(12)

式中:xi，xj為作業(yè)單位的X軸中心坐標(biāo)；yi，yj為作業(yè)單位的Y軸中心坐標(biāo)；L,W分別為車(chē)間的長(zhǎng)與寬；Li，Lj與Wi，Wj分別為作業(yè)單位i,j的長(zhǎng)與寬；Δxij與Δyij分別為作業(yè)單位i與j之間的橫向及縱向距離。約束以懲罰函數(shù)加以限制。

2 基于遺傳算法的SLP方法實(shí)施步驟

利用傳統(tǒng)SLP方法分析物流與非物流間的相互關(guān)系，得到作業(yè)單位相互關(guān)系矩陣及車(chē)間的操作設(shè)備位置相關(guān)圖，并求得兩組初始染色體編碼。為避免設(shè)計(jì)人員的經(jīng)驗(yàn)與主觀性的影響，本文利用遺傳算法求得較優(yōu)解，以增加計(jì)算精確度及實(shí)用性。

2.1 基于SLP的作業(yè)單位相互關(guān)系

1)初始種群。

用數(shù)字1～9表示車(chē)間的各個(gè)作業(yè)單位，通過(guò)傳統(tǒng)SLP方法計(jì)算得到車(chē)間作業(yè)單位位置圖，如圖2所示[7]，從而得到兩組初始方案編碼：方案一，{9,7,3,5,4,2,1,6,8}；方案二，{1,4,2,5,3,9,8,6,7}。

圖2 作業(yè)單位位置相關(guān)圖

2)適應(yīng)度設(shè)定。

適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到較優(yōu)解，通過(guò)判斷個(gè)體的優(yōu)劣程度來(lái)增加其在個(gè)體產(chǎn)生下一代的概率，從而得到較優(yōu)解，即得出更好的目標(biāo)個(gè)體。這里采用取倒數(shù)法將目標(biāo)函數(shù)C轉(zhuǎn)化為適應(yīng)度函數(shù)F(x)：

(13)

3)選擇方式。

遺傳算法中最常見(jiàn)的選擇方法為輪盤(pán)賭方法，也叫比例選擇法，即個(gè)體被選中的概率與其適應(yīng)度值大小存在一定的比例關(guān)系，適應(yīng)度值越高，占比越大，被選中的概率就越大[8]。假設(shè)種群大小為k,則個(gè)體i被選中的概率pi為：

(14)

式中：Fi為每個(gè)個(gè)體的適應(yīng)度。

4)交叉與變異。

本文采用部分匹配交叉方式進(jìn)行交叉操作，如圖3所示。

圖3 部分匹配交叉

由于基本位變異在二進(jìn)制編碼中的適應(yīng)性，因此變異方式選擇基本位變異，基本位變異圖如圖4所示。

圖4 基本位變異圖

基于實(shí)施步驟，可對(duì)M公司車(chē)間的布置優(yōu)化問(wèn)題進(jìn)行求解。

2.2 實(shí)例研究

M公司整體車(chē)間面積為3 000 m2，各作業(yè)單位面積見(jiàn)表2。

表2 作業(yè)單位面積表

作業(yè)最小間距矩陣Δxij與Δyij關(guān)系如下所示：

(15)

物流量矩陣fij為：

(16)

相互關(guān)系矩陣Tij如下：

(17)

設(shè)定初始種群數(shù)量NP為50個(gè)，其中部分初始種群由傳統(tǒng)SLP方法得到的2個(gè)優(yōu)化方案組成[9]，其余隨機(jī)產(chǎn)生，設(shè)置最大迭代次數(shù)為100次，變異概率pm為0.1，交叉概率pc為0.8，運(yùn)行MATLAB得到的最優(yōu)染色體集為{ 1，9，8，3，7，2，4，5，6}，最優(yōu)作業(yè)單位布局坐標(biāo)見(jiàn)表3，遺傳算法迭代曲線圖如圖5所示，最終最優(yōu)布局圖如圖6所示。

表3 最優(yōu)作業(yè)單位布局坐標(biāo)表

圖5 遺傳算法迭代曲線圖

圖6 遺傳算法優(yōu)化得到的布局圖

2.3 效果評(píng)價(jià)

對(duì)布置方案從定量及定性的角度進(jìn)行評(píng)價(jià)。

定性分析：1)符合定位式布局特點(diǎn)，可減少大型設(shè)備的移動(dòng)，有效增強(qiáng)車(chē)間作業(yè)整潔程度。2)盡可能利用了原有廠房，通過(guò)改變暫存區(qū)位置來(lái)減少半成品堆積，工藝、物流清晰。3)對(duì)人體有較大影響的烘干區(qū)遠(yuǎn)離人員作業(yè)區(qū)域，減少揮發(fā)性氣體及高溫對(duì)人的影響。4)以混合式布局為指導(dǎo)，結(jié)合流程式布局(以流程為中心)及功能式布局(以設(shè)備為中心)，盡可能減少搬運(yùn)浪費(fèi)，提升作業(yè)人員對(duì)機(jī)器的監(jiān)控能力。

定量分析：以作業(yè)單位相互運(yùn)輸量及距離表進(jìn)行統(tǒng)計(jì)計(jì)算，作業(yè)單位距離及物流量表見(jiàn)表4。

表4 作業(yè)單位距離及物流量表

以傳統(tǒng)SLP方法布置得出的總物流搬運(yùn)距離為：

5.3×113+3.3×81+9.8×83+12.8×67+2.2×91+12.7×5+14.6×3+8.6×5+10.3×3+4.6×89+2.4×5=3 340 (m)

基于遺傳算法的SLP方法得出的布置方案總物流搬運(yùn)距離為：

4.7×113+5.3×81+3.6×83+6.6×67+2.3×91+5.4×5+4.6×3+9.7×5+12.3×3+10.3×89+2.3×5=2 965 (m)

由此可見(jiàn)，結(jié)合了遺傳算法的SLP方法相對(duì)于傳統(tǒng)SLP方法布置優(yōu)化的物流量搬運(yùn)距離量同比降低11.3%，有效減少了作業(yè)單位間的物流成本。

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

本文通過(guò)基于遺傳算法的SLP方法對(duì)絲印車(chē)間設(shè)施布局進(jìn)行優(yōu)化，通過(guò)定量分析對(duì)比出基于遺傳算法的SLP方法比傳統(tǒng)SLP方法可以更有效減少搬運(yùn)距離，因此更具實(shí)踐性。這種方法補(bǔ)充了離散型制造車(chē)間在生產(chǎn)布局方面的優(yōu)化方法，更具創(chuàng)新性。由于模型建立時(shí)將各個(gè)工作單元抽象為矩形，因此在實(shí)際布置中，可以根據(jù)具體情況進(jìn)行參數(shù)上的調(diào)整。