葛安華，姚向楠，張玉巧

(東北林業(yè)大學 工程技術學院，哈爾濱 150040)

隨著市場競爭的加劇和生產(chǎn)方式的變革，原有的設施布局漸漸不適應要求，迫使企業(yè)對已有系統(tǒng)、人員和設施進行重新評估和認識，這使得布局的問題逐漸顯現(xiàn)出來，人們也越來越重視如何設計出更高效的布局。但布局問題是一個及其復雜且矛盾的優(yōu)化問題，目前一些學者提出的布置模型還不夠完善，其求解算法也有許多不足。改進的蟻群優(yōu)化算法是在克服蟻群優(yōu)化算法缺點的基礎上發(fā)展而來，應用范圍幾乎遍及各個領域[1]。鑒于此，本文將采用一種改進的蟻群算法來求解車間布局的優(yōu)化問題。

1 車間布局問題的二次分配建模

1957年Koopamans和Beckmann為彼此間有物料流動的設施的位置問題提出了二次分配問題(QAP)[2]。為簡化該模型做如下假設：

(1)確定數(shù)量的需要布置在矩形區(qū)域中的矩形設施。

(2)設施的位置相互之間不能重疊，且不能超出矩形區(qū)域。

(3)設施間的距離度采用直角距離進行計量。

(4)不同設施間單位物流量搬運單位距離所需費用相同，且為1。

以總搬運成本Z最小為目標，現(xiàn)有n個設施和n個位置，每個設施要求布置在一個不同位置上，假如設施i被布置在位置點k上，設施j被布置在位置點h上，設施i與j之間流量用fij來表示，位置點k與h之間的距離用dkh來表示。

那么QAP的數(shù)學模型可表示為

(1)

式中：xik、xih為決策變量，如果設施i布置在位置點k上，則xik取值為1，否則xik取值為0。公式(2)為其約束條件。

。(2)

2 改進蟻群優(yōu)化算法的求解

蟻群優(yōu)化算法(ACO)已成為解決各種組合優(yōu)化問題的最有效的算法之一[3-12]，根據(jù)二次分配的特點，蟻群優(yōu)化算法適用于解決二分配問題。但傳統(tǒng)的螞蟻算法采用固定的信息素增減來進行信息素更新，使得這種算法容易出現(xiàn)收斂速度慢、陷入局部最優(yōu)、運算時間長等現(xiàn)象[13]。為了解決這個問題，Stutzle和Hoos對此提出了兩點改進，一是把路徑上的信息素濃度的大小限制在[τmin,τmax]范圍之內(nèi)，二是對信息素強度更新提出了新的更新規(guī)則，這就是最大最小螞蟻系統(tǒng)(MAX-MIN Ant System，MMAS)。本文將運用最大最小螞蟻系統(tǒng)來求解車間布局QAP模型。

2.1 問題圖形表示

根據(jù)目標函數(shù)和約束條件，車間布局問題的構件圖設計如圖1所示。從而構成了n個設施選擇n個位置的決策問題。每個節(jié)點{rij|i=1,2,…n;j=1,2…n}表示設施i選擇布局的位置j。這樣共有nn向量將節(jié)點從第1個位置連接到第n位置。

圖1 車間布局的構建圖

2.2 螞蟻的路徑選擇

螞蟻在各個節(jié)點上游走，并留下不同的信息素的濃度，以此來影響下一批螞蟻選擇的移動方向。令τij(t)為t時刻各個節(jié)點上信息素的濃度大小，初始時刻節(jié)點上的信息素濃度為τ0。生成的Nant只螞蟻被放在圖1第一個位置的各個節(jié)點上，然后每一只螞蟻根據(jù)信息素和啟發(fā)式信息獨立的選擇下一位置的某個節(jié)點，t時刻，處于節(jié)點rij時的螞蟻k選擇下一位置節(jié)點rz(j+1)的概率公式為：

(3)

3 車間布局的蟻群算法

3.1 車間布局蟻群算法的描述

在初始化數(shù)據(jù)、參數(shù)和信息素之后，設NCmax為最大迭代次數(shù)，ACO算法反復在主循環(huán)中迭代，當Nant只螞蟻都迭代完成，得到了Nant組解初始解，然后，通過局部搜索法對初始解進行優(yōu)化，最后更新信息素矩陣。總共分為三大步驟，具體運行如下。

3.1.1 初始解

(1)把初始化禁忌表的值設為零。

(2)fork=1toNant，按照公式3概率公式計算選擇下一個位置的節(jié)點，如螞蟻沒走到最后一個位置，將其所選擇的節(jié)點加入螞蟻k的禁忌表，結束。

(3)當螞蟻第k=Nant時，每一只螞蟻都已經(jīng)建立了初始解。否則返回(2)。

3.1.2 局部搜索優(yōu)化

本文運用的局部搜索方法是運用傳統(tǒng)的2-選擇交換和一種新的交換方法相結合的形式來計算的，結果表明其改善方法更優(yōu)一些。運用局部搜索法對初始解優(yōu)化的步驟為：

(1)fork=1，局部搜索次數(shù)設定為1。

(2)隨機產(chǎn)生兩個要交換元素的位置，對其進行交換。

(3)交換后目標函數(shù)值的新解小于初始解時，實施交換，否則不進行交換。

(4)當局部搜索次數(shù)為n次，fork=Nant時，完成了對所有初始解的局部搜索。

3.1.3 信息素更新

MMAS對信息素的大小值施加限制，控制在范圍[τmin,τmax]，如果更新后的信息素大于τmax或者小于τmin，強令其值τmax或者為τmin。當所有螞蟻都完成局部搜索后，將進行信息素更新。信息素更新分為信息素的揮發(fā)和信息素的釋放，具體規(guī)則為：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)。

(4)

(5)

(6)

式中：ρ表示揮發(fā)因子；1-ρ則為殘留因子；Cbest為當前迭代最優(yōu)解或者是至今最優(yōu)解。信息素的釋放只對系統(tǒng)產(chǎn)生的最優(yōu)解和當前最優(yōu)解，其他解Δτij(t)=0。

具體步驟為：

(1)產(chǎn)生隨機數(shù)，判斷其解是否為至今最優(yōu)還是當代最優(yōu)，計算信息素相應的釋放量Δτij(t)。

(2)對信息素矩陣進行信息素進行揮發(fā)，然后計算更新之后的信息素τij(t+1)。

(3)判斷信息更新之后的量是否在[τmin,τmax]之內(nèi)，若不在則按信息素更新規(guī)則更改。

根據(jù)上面三大步驟的不斷循環(huán)和分析，最終將獲得車間的最優(yōu)布局方案。下面給出一個簡單的應用范例。

3.2 實例應用

一個總面積為35 m×20 m的生產(chǎn)車間，車間有12個生產(chǎn)單元，現(xiàn)以最小化物料運輸成本為目標函數(shù)，建立該車間的QAP模型，對該車間的布局進行優(yōu)化?，F(xiàn)根據(jù)QAP模型要求把車間區(qū)域重新劃分，由于有12個生產(chǎn)車間，則劃分為12個面積相等的區(qū)域，按照三行進行布置?，F(xiàn)有各個生產(chǎn)單元之間的物流流量表1。區(qū)域之間的距離運用距心之間的直角距離來計算，相鄰之間為一個單位，這樣就構造了一個距離矩陣見表2。車間的原來的布局方案為R=(D，H，C，I，F(xiàn)，A，L，J，G，B，E，K)，如圖2所示。

該布局方案的物料的搬運成本為

(7)

圖2原始布置方案

Fig.2 The original layout plan

表1 各單元之間的物流量矩陣 kg

表2 各區(qū)域間的距離矩陣表 m

運行環(huán)境：PC機，內(nèi)存為2G，操作環(huán)境為win7，開發(fā)VC++6.0實現(xiàn)，程序中用到的參數(shù)設置為Nant=12，NCmax=12，α=1，β=2，ρ=0.05，τmax=2，τmin=0.4，Q=1000，Cbest=5，τ0=2，n=30。運行結果，得出最優(yōu)的布置方案為R=(E，B，I，C，G，K，J，H，D，F(xiàn)，A，L)。相應的布置如圖3所示。該布置方案的物料的搬運成本為3680。

圖3最優(yōu)布置方案

Fig.3 Optimal layout scheme

顯然，和原布局方案進行比較，新方案高潛在物流量的生產(chǎn)單位分配到具有低潛在距離的位置上，所以在物料搬運的成本上更低。

4 結論和討論

本文根據(jù)車間布局優(yōu)化的最小物流費用原則，建立了布局優(yōu)化的QAP數(shù)學模型，針對QAP的特點，提出了一種改進的蟻群優(yōu)化算法來對其進行求解，該算法強調對最優(yōu)路徑的開發(fā)，并且對路徑上信息素濃度的大小進行了限制，避免了搜索的停滯；同時對信息素強度更新提出了新的更新規(guī)則，并且融合局部搜索的方法，使得改進后的蟻群算法解的性能得到較大提高。結合具體實例，并通過VC++6.0編程來實現(xiàn)求解，結果表明，新布局方案物料搬運成本要比原布局方案節(jié)約10%，驗證了改進的蟻群優(yōu)化算法對布局優(yōu)化的QAP數(shù)學模型的求解是可行且有效的。

不可否認的是蟻群優(yōu)化算法是一個復雜的系統(tǒng)，它的行為受到參數(shù)、宏觀算法部件和問題特性等多方面影響，本文使用的改進的蟻群優(yōu)化算法一定程度上克服了它的一些缺陷，但如何最有效的發(fā)揮算法的性能還需做進一步研究；另外，本文求解的車間布局問題是靜態(tài)的車間設施平面布局，對于更復雜的車間布局問題也還需做進一步研究和探討。

【參 考 文 獻】

[1]桑國珍，李智勇.蟻群算法研究與應用[J].內(nèi)江科技，2009(8)：33-34.

[2]Lari M B.Layout designs in cellular manufacturing[J].European Journal of Operational Research，1999，112：258-272.

[3]張利城，吳金卓，何 榮.基于循環(huán)取貨模式的車輛路徑優(yōu)化研究[J].森林工程，2013，29(4)：87-89.

[4]魯 強，陳 明.平面布局的蟻群算法[J].計算機應用，2005，25(5)：1119-1121.

[5]范 文，余隋懷.蟻群算法求解人及布局優(yōu)化問題[J].機械科學與技術，2004，14(4)：423-427.

[6]魯 強，陳 明.平面布局的蟻群算法[J].計算機應用，2005，25(5)：1019-1021.

[7]Al-Attar A.A hybrid GA-heuristic search strategy[J].Al Expert USA，1994，9(9)：34-37.

[8]Komarudin K.Applying ant system for solving unequal area facility layout problems[J].European Journal of Operational Research，2010，202：730-746.

[9]王家善.設施規(guī)劃與設計[J].工業(yè)工程，1998，1(1)：11-14.

[10]吳永忠.面向大規(guī)模定制的生產(chǎn)線優(yōu)化設計系統(tǒng)的研究與開發(fā)[D].廣州：廣東工業(yè)大學，2004.

[11]葛安華，周晏明，李權章.改進遺傳算法求解作業(yè)車間提前/托期調度問題[J].森林工程，2013，29(3)：138-141.

[12]詹玉洪.求解車輛路徑問題的混合螞蟻系統(tǒng)[J].計算技術與自動化，29(1)：138-141.

[13]倪慶劍，邢漢承.蟻群算法及其應用研究[J].計算機應用與軟件，2008，25(8)：12-15.