徐修立，沈夢(mèng)超，陳浩杰，張 劍

（西南交通大學(xué) 先進(jìn)設(shè)計(jì)與制造技術(shù)研究所，成都 610031）

0 引言

隨著市場(chǎng)競(jìng)爭(zhēng)的日趨激烈化，要求企業(yè)對(duì)生產(chǎn)車(chē)間進(jìn)行精準(zhǔn)或者重構(gòu)布局，以適應(yīng)市場(chǎng)的快速變化，因此車(chē)間布局及優(yōu)化問(wèn)題成為了制造領(lǐng)域重要研究課題之一[1]。據(jù)統(tǒng)計(jì)，一個(gè)企業(yè)車(chē)間的物料搬運(yùn)費(fèi)用約為制造總成本的20%～50%，而優(yōu)化車(chē)間布局能減少搬運(yùn)量、搬運(yùn)距離和等待時(shí)間，使物流成本至少降低10%～30%[2]。

車(chē)間布局問(wèn)題是指將機(jī)床設(shè)備及其輔助設(shè)施在給定的空間內(nèi)進(jìn)行布局，并且滿(mǎn)足相應(yīng)的約束條件，通過(guò)優(yōu)化以獲取最佳目標(biāo)函數(shù)值[3]。目前，在車(chē)間布局問(wèn)題中建立的數(shù)學(xué)模型主要包括二次分配模型、混合整數(shù)規(guī)劃模型、二次集合覆蓋模型、線(xiàn)性多行直線(xiàn)布局模型等[4]。在車(chē)間布局模型求解方面，已廣泛采用啟發(fā)式優(yōu)化算法[5]。如郭源源[6]將粒子群算法與經(jīng)典的系統(tǒng)布置設(shè)計(jì)法相結(jié)合來(lái)求解面向車(chē)間布局的連續(xù)空間優(yōu)化問(wèn)題，Kulturel-Konak[7]提出了一種混合粒子群算法來(lái)求解不等面積的車(chē)間布局問(wèn)題，Pourhassan[8]提出了采用非支配排序遺傳算法（NSGA-II）求解多目標(biāo)動(dòng)態(tài)設(shè)施布局優(yōu)化問(wèn)題。由于遺傳算法操作簡(jiǎn)單、且具備魯棒性，文獻(xiàn)[9～11]等均采用遺傳算法或其改進(jìn)來(lái)對(duì)車(chē)間布局問(wèn)題進(jìn)行優(yōu)化求解。

建立車(chē)間布局?jǐn)?shù)學(xué)模型是一個(gè)化繁為簡(jiǎn)的過(guò)程，但過(guò)于簡(jiǎn)化往往導(dǎo)致數(shù)學(xué)模型與實(shí)際物理模型之間存在較大的差異。例如布局時(shí)不等面積功能區(qū)橫縱向放置問(wèn)題、豎向主干道、行距可變等實(shí)際情況被忽略，同時(shí)優(yōu)化的目標(biāo)通常是物料搬運(yùn)成本最小化的單目標(biāo)，而忽略了車(chē)間的面積利用率等因素的影響。因此本文基于當(dāng)前車(chē)間布局中較為常用的線(xiàn)性多行直線(xiàn)布局模型，充分考慮車(chē)間各種實(shí)際約束，建立更為精準(zhǔn)的車(chē)間總體布局多目標(biāo)優(yōu)化數(shù)學(xué)模型，同時(shí)采用求解更為有效的多種群遺傳算法，實(shí)現(xiàn)精準(zhǔn)布局模型的求解，并將該方法應(yīng)用于實(shí)例中說(shuō)明其可行性與優(yōu)越性。

1 車(chē)間總體布局精準(zhǔn)數(shù)學(xué)模型的建立

采用多層次式布局策略[12]，對(duì)已經(jīng)劃分布置好的N個(gè)不等面積功能區(qū)進(jìn)行車(chē)間總體布局，可以減少計(jì)算規(guī)模。根據(jù)車(chē)間現(xiàn)場(chǎng)的多重約束和規(guī)則，建立精準(zhǔn)數(shù)學(xué)模型，構(gòu)建多目標(biāo)優(yōu)化函數(shù)并求解，實(shí)現(xiàn)車(chē)間中總的物料搬運(yùn)成本最低、車(chē)間面積利用率最大等目標(biāo)，以便得到最優(yōu)車(chē)間布局解。

1.1 模型假設(shè)與符號(hào)說(shuō)明

本文采用線(xiàn)性多行直線(xiàn)布局模型對(duì)車(chē)間進(jìn)行總體布局。考慮實(shí)際廠房的空間約束，而功能區(qū)單元布置行數(shù)未知，故采用自動(dòng)換行策略。為便于建模和提高計(jì)算效率，對(duì)多行直線(xiàn)布局做出如下假設(shè)：1）待布局的車(chē)間為二維平面，且是長(zhǎng)寬大小已知的矩形；2）待布置的功能區(qū)均為長(zhǎng)、寬已知的矩形，忽略其高度；3）各功能區(qū)分行排列，且平行于車(chē)間長(zhǎng)寬方向，即平行于x軸和y軸；4）排列在同一行的功能區(qū)其中心點(diǎn)在同一條水平線(xiàn)上。

車(chē)間與功能區(qū)的幾何模型如圖1所示。

圖1 線(xiàn)性多行設(shè)備功能區(qū)布局示意圖

其中L、W分別表示待布局車(chē)間的長(zhǎng)度和寬度，Ai表示功能區(qū)單元i，xi表示i功能區(qū)的x軸方向坐標(biāo)，yi表示i功能區(qū)的y軸方向坐標(biāo)，li表示i功能區(qū)的長(zhǎng)度，bi表示i功能區(qū)的寬度，hik表示i功能區(qū)和k功能區(qū)之間的橫向最小安全距離，Δi表示i功能區(qū)和k功能區(qū)之間的凈間距，s0表示第一行功能區(qū)與車(chē)間邊界設(shè)定的距離，Sm,m-1表示兩相鄰行之間的行距，hj0表示j功能區(qū)與車(chē)間邊界的最小安全距離，yn表示n功能區(qū)所在行的y軸方向坐標(biāo)位置值大小。

1.2 優(yōu)化目標(biāo)

本文以車(chē)間總物料搬運(yùn)成本最小和面積利用率最大為優(yōu)化目標(biāo)建立多目標(biāo)精準(zhǔn)數(shù)學(xué)模型，以滿(mǎn)足物流原則和布局緊湊原則。

1）車(chē)間中總的物料搬運(yùn)成本最小化

式中：Pij為功能區(qū)i和功能區(qū)j之間的單位物料在每單位距離之間進(jìn)行搬運(yùn)所需的費(fèi)用，Qij為功能區(qū)i和功能區(qū)j之間的物料搬運(yùn)頻率，m為車(chē)間總體布局后的總行數(shù)，n為功能區(qū)的總數(shù)量，Dij為功能區(qū)i和功能區(qū)j之間的矩形距離，其公式如下：

2）車(chē)間面積利用率最大化

面積利用率最大問(wèn)題可以轉(zhuǎn)化為布局結(jié)果所包絡(luò)功能區(qū)的矩形面積St最小問(wèn)題，St的計(jì)算公式如式(3)所示：

布局過(guò)程采用自動(dòng)換行策略，其中yend為布置在車(chē)間最后一行功能區(qū)的縱坐標(biāo)，B(end)max為最后一行功能區(qū)中寬度最大的功能區(qū)寬度尺寸。由此該目標(biāo)函數(shù)的表達(dá)式為：

根據(jù)優(yōu)化目標(biāo)之間的相對(duì)重要程度，采用加權(quán)法構(gòu)造新的優(yōu)化目標(biāo)函數(shù)，將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解：

式中：ω1、ω2為加權(quán)因子，且滿(mǎn)足ω1+ω2=1，α1、α2為歸一化因子。

1.3 精準(zhǔn)數(shù)學(xué)模型約束條件

建立車(chē)間布局精準(zhǔn)數(shù)學(xué)模型的約束條件如下：

式中：（Xi'，Yi'）、（Xi''，Yi''）分別為矩形功能區(qū)i的左下角和右上角的坐標(biāo)；LWl、LWr分別表示豎向主干道沿x軸方向的左、右兩邊的坐標(biāo)大?。粵Q策變量Zik=1表示功能區(qū)i在第k行上，否則Zik=0；決策變量UAi=0表示功能區(qū)i橫向放置，UAi=1表示功能區(qū)i豎向放置；B(k)max為第k行功能區(qū)中寬度最大的功能區(qū)寬度尺寸；yi(k)表示功能區(qū)i的y軸方向坐標(biāo)（功能區(qū)i位于第k行），y(k-1)表示第k-1行的y坐標(biāo)大小，WP表示設(shè)定橫向主干道的尺寸大小，一般不設(shè)定橫向主干道則WP=0。

式(6)、式(7)表示功能區(qū)的橫縱坐標(biāo)方向不超過(guò)車(chē)間最大長(zhǎng)度和最大寬度，式(8)保證功能區(qū)布局避開(kāi)豎向主干道，式(9)保證同一行的功能區(qū)不能重疊且滿(mǎn)足其安全距離，式(10)保證一個(gè)功能區(qū)在布局中只能出現(xiàn)一次，式(11)表示功能區(qū)可橫向、豎向選擇放置，式(12)表示設(shè)置自適應(yīng)行距：即布置有功能區(qū)的任意相鄰兩行k行、k-1行的行距可根據(jù)所布置的功能區(qū)尺寸大小自適應(yīng)確定行距大小，而非采用固定行距約束要求：根據(jù)所有功能區(qū)中最寬功能區(qū)的寬度設(shè)置每相鄰兩行行距為定值大小[13]，式(13)、式(14)分別表示功能區(qū)矩心的橫（x軸）、縱（y軸）坐標(biāo)求解公式。

2 改進(jìn)多種群遺傳算法求解

遺傳算法是模擬生物進(jìn)化過(guò)程搜索最優(yōu)解的方法，具備很強(qiáng)的全局搜索能力和魯棒性，但是也存在早熟收斂和收斂性能差等缺陷與不足[14]。為此，本文采用一種改進(jìn)多種群遺傳算法（MPGA）對(duì)車(chē)間總體布局問(wèn)題進(jìn)行優(yōu)化求解，該算法通過(guò)模擬自然生態(tài)系統(tǒng)協(xié)同進(jìn)化，具有全局、局部搜索能力強(qiáng)和收斂精度高等特點(diǎn)[15]。

2.1 改進(jìn)多種群遺傳算法流程

多種群遺傳算法流程如圖2所示，具體操作過(guò)程如下：

Step1：隨機(jī)產(chǎn)生N個(gè)初始種群，每個(gè)種群的規(guī)模大小為M，初始化種群并計(jì)算個(gè)體的目標(biāo)函數(shù)值。

Step2：利用2.2節(jié)中設(shè)計(jì)的交叉和變異概率參數(shù)控制式(15)、式(16)對(duì)每個(gè)種群分別設(shè)定不同的交叉和變異概率控制參數(shù)。

Step3：N個(gè)種群各自獨(dú)立進(jìn)行標(biāo)準(zhǔn)遺傳算法（simple genetic algorithm，SGA）的選擇、交叉、變異等操作。

Step4：采用移民算子交換種群間信息。

Step5：利用人工選擇算子選出每個(gè)種群的最優(yōu)個(gè)體保存至精華種群中。精華種群不進(jìn)行選擇、交叉、變異等遺傳操作，保證迭代過(guò)程中不破壞和丟失最優(yōu)個(gè)體。

Step6：判斷精華種群中的最優(yōu)個(gè)體最少保持代數(shù)是否達(dá)到設(shè)定的最大保持代數(shù)，若是，則尋優(yōu)過(guò)程結(jié)束，輸出最優(yōu)解；否，則繼續(xù)循環(huán)迭代。

圖2 多種群遺傳算法（MPGA）流程示意圖

2.2 交叉和變異概率參數(shù)控制公式設(shè)計(jì)

遺傳算法中交叉概率和變異概率的參數(shù)設(shè)置決定了全局和局部搜索能力，若按傳統(tǒng)多種群遺傳算法的操作，對(duì)每個(gè)種群設(shè)定相同的交叉概率Pc和變異概率Pm，會(huì)存在交叉、變異概率設(shè)置不合理致使多種群遺傳算法陷入早熟收斂的問(wèn)題。故本文通過(guò)設(shè)計(jì)交叉和變異概率參數(shù)控制公式給予每個(gè)種群不同的控制參數(shù)，則不同種群以不同的交叉和變異概率協(xié)同進(jìn)化，兼顧了算法的全局和局部搜索，降低了算法求解陷入局部最優(yōu)的可能性，提高了多種群遺傳算法的收斂精度。結(jié)合交叉概率取值范圍（pcmin，pcmax）和變異概率取值范圍（pmmin，pmmax），設(shè)計(jì)交叉和變異概率參數(shù)控制公式：

其中，randN（0，1）為在0～1區(qū)間產(chǎn)生的隨機(jī)數(shù)，有N個(gè)種群則分別產(chǎn)生N個(gè)0～1之間的隨機(jī)數(shù)值。

2.3 多種群遺傳算法設(shè)計(jì)

2.2.1 基因的編碼

基因編碼方式由功能區(qū)排列順序、凈間距和功能區(qū)單元橫豎放置選擇三部分構(gòu)成，采用混合的編碼結(jié)構(gòu)，表達(dá)方式為：[{A1，A2，…，An}{Δ1，Δ2，…，Δn}{0，1，0，0，1，...}]。其中：功能區(qū)排序時(shí)采用整數(shù)編碼，Ai為功能區(qū)，其順序?yàn)楣δ軈^(qū)i的排列順序；凈間距采用實(shí)數(shù)編碼，Δi為功能區(qū)i和功能區(qū)i-1或邊界之間的凈間距；功能區(qū)單元橫豎放置選擇采用二進(jìn)制編碼，1表示功能區(qū)單元豎向放置，0表示功能區(qū)單元橫向放置。

2.3.2 種群評(píng)價(jià)函數(shù)

根據(jù)1.3節(jié)中式(13)、式(14)求出該染色體序列每個(gè)功能區(qū)的x、y坐標(biāo)；根據(jù)1.2節(jié)中式(5)求出加權(quán)后的多目標(biāo)優(yōu)化函數(shù)值C，由于所求目標(biāo)為極小值，故而適應(yīng)度函數(shù)設(shè)為：

其中：f為適應(yīng)值；T為罰函數(shù)，使得不滿(mǎn)足約束條件的較差個(gè)體具有較低適應(yīng)度值。

2.3.3 遺傳算子

選擇操作采用輪盤(pán)賭的方式，各種群采用文獻(xiàn)[16]中標(biāo)準(zhǔn)遺傳算法（simple genetic algorithm，SGA）的交叉、變異操作。

2.3.4 算法終止條件

與標(biāo)準(zhǔn)遺傳算法（SGA）中人為設(shè)定最大終止迭代次數(shù)不同，本文算法通過(guò)判斷當(dāng)精華種群中的最優(yōu)個(gè)體連續(xù)保持代數(shù)達(dá)到設(shè)定的保持代數(shù)時(shí)，則算法終止，輸出最優(yōu)解。避免因設(shè)定迭代次數(shù)不合理而導(dǎo)致算法在收斂前過(guò)早結(jié)束或收斂后浪費(fèi)計(jì)算資源的情況。

2.4 移民算子

由于各種群是相對(duì)獨(dú)立的，故本文通過(guò)引入移民算子將其聯(lián)系起來(lái)。移民算子是將迭代過(guò)程中各種群里的最優(yōu)個(gè)體定期的交換至其他種群，從而實(shí)現(xiàn)種群間的信息交換，交換的染色體作為外來(lái)優(yōu)秀個(gè)體引入，避免了迭代進(jìn)化后期因種群多樣性降低致使算法陷入局部最優(yōu)。移民算子具體操作為：將目標(biāo)種群中的最差個(gè)體用其他種群中的最優(yōu)個(gè)體替換，即將N個(gè)種群編號(hào)（1，2，…，r，…，N），種群r中的最差個(gè)體由種群r+1中的最優(yōu)個(gè)體代替，以此類(lèi)推，種群1中的最差個(gè)體由種群N中的最優(yōu)個(gè)體代替，完成移民操作。

2.5 參數(shù)設(shè)置

本文分別采用SGA算法和MPGA算法對(duì)目標(biāo)函數(shù)進(jìn)行求解，取加權(quán)因子ω1=0.6，ω2=0.4。SGA算法：M=50，Pc=0.8，Pm=0.08，設(shè)定終止判據(jù)：最大迭代次數(shù)為200代；MPGA算法：N=10，M=50，設(shè)定Pc取值范圍（0.6,0.9）和Pm取值范圍（0.01,0.1），設(shè)定終止判據(jù)：最優(yōu)個(gè)體最少保持代數(shù)為5代。

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

某制造企業(yè)準(zhǔn)備建新廠房，長(zhǎng)90米，寬60米，考慮在廠房長(zhǎng)度方向中間位置處設(shè)置一條4米寬的豎向主干道。企業(yè)確定了未來(lái)五年生產(chǎn)所需設(shè)備的類(lèi)型及數(shù)量，同時(shí)基于成組技術(shù)，對(duì)設(shè)備進(jìn)行了功能區(qū)單元的構(gòu)建，功能區(qū)劃分構(gòu)建結(jié)果如表1所示。根據(jù)零件加工工藝和功能區(qū)構(gòu)建結(jié)果，分析物流情況可獲取從至表，同時(shí)設(shè)置安全距離。

表1 功能區(qū)信息表

采用上文的相關(guān)參數(shù)設(shè)置，設(shè)計(jì)了如表2中的6組實(shí)驗(yàn)；并且根據(jù)不同實(shí)驗(yàn)方案，運(yùn)用Matlab軟件編寫(xiě)了相應(yīng)程序。每種實(shí)驗(yàn)方案均運(yùn)行10次，取其中最優(yōu)解及目標(biāo)函數(shù)的平均值作為數(shù)據(jù)結(jié)果如表3所示；為了比較算法性能，實(shí)驗(yàn)1與實(shí)驗(yàn)2同時(shí)迭代到200代的進(jìn)化結(jié)果對(duì)比如圖4所示。

表2 實(shí)驗(yàn)方案表

表3 優(yōu)化數(shù)據(jù)結(jié)果對(duì)比表

圖3 MPGA與SGA進(jìn)化迭代結(jié)果對(duì)比圖

結(jié)果分析：對(duì)比表3中實(shí)驗(yàn)1和實(shí)驗(yàn)2的數(shù)據(jù)結(jié)果，采用多種群遺傳算法（MPGA）比采用標(biāo)準(zhǔn)遺傳算法（SGA）求解的目標(biāo)函數(shù)值小5%，同時(shí)從圖3中MPGA與SGA進(jìn)化迭代結(jié)果對(duì)比可見(jiàn)，SGA在進(jìn)化到100代左右即陷入了局部最優(yōu)解，采用MPGA算法求解的精度明顯比SGA求解精度更高。

對(duì)比實(shí)驗(yàn)2和實(shí)驗(yàn)5的優(yōu)化數(shù)據(jù)結(jié)果，采用自適應(yīng)行距得出的布局結(jié)果會(huì)比采用固定行距約束結(jié)果更優(yōu)，其總物流成本降低了3%，面積利用率提高了6%。

對(duì)比實(shí)驗(yàn)2和實(shí)驗(yàn)6的數(shù)據(jù)結(jié)果，考慮功能區(qū)橫豎放置的最優(yōu)解精度可提高3%，更容易得到車(chē)間布局最優(yōu)解。

對(duì)比實(shí)驗(yàn)2、實(shí)驗(yàn)3（在實(shí)驗(yàn)2布局結(jié)果中強(qiáng)行加入豎向主干道）和實(shí)驗(yàn)4的優(yōu)化結(jié)果說(shuō)明，在不考慮豎向主干道進(jìn)行優(yōu)化時(shí)，雖然簡(jiǎn)化后的優(yōu)化模型得到目標(biāo)函數(shù)值是這3個(gè)實(shí)驗(yàn)中最小的，但是真正加入豎向主干道后，實(shí)際目標(biāo)值卻增大9%，說(shuō)明在建立數(shù)學(xué)模型時(shí)應(yīng)考慮豎向主干道的實(shí)際約束，從而更能求得符合實(shí)際車(chē)間布局的最優(yōu)解。故本文實(shí)例最終采取實(shí)驗(yàn)4方案，最大化地減小了物流成本且提高了面積利用率，求解所得布局結(jié)果示意圖如圖4所示。

圖4 車(chē)間布局方案示意圖

4 結(jié)論

本文改進(jìn)了多行直線(xiàn)布局模型中行與行之間固定行距的約束，給出自適應(yīng)行距約束定義，使布局面積更小、物流成本更低。同時(shí)針對(duì)目前車(chē)間總體布局?jǐn)?shù)學(xué)模型過(guò)于簡(jiǎn)化的缺陷，在優(yōu)化數(shù)學(xué)模型中加入了功能區(qū)單元橫豎選擇放置及豎向通道設(shè)置，建立了更為符合車(chē)間實(shí)際布局情況的精準(zhǔn)數(shù)學(xué)模型。采用改進(jìn)多種群遺傳算法（MPGA）對(duì)該數(shù)學(xué)模型進(jìn)行多目標(biāo)優(yōu)化求解，通過(guò)設(shè)計(jì)交叉和變異概率參數(shù)控制公式，使群體保持多樣性，采用移民算子聯(lián)系種群，降低了算法求解陷入局部最優(yōu)的可能性，提高了多種群遺傳算法的收斂精度，最后通過(guò)實(shí)例驗(yàn)證了所建模型的實(shí)用性和所用算法的優(yōu)越性。