周爾民，鄧 洪，費衛(wèi)衛(wèi)，張廣航

(華東交通大學 交通運輸與物流學院，南昌 330013)

0 引言

設施布局問題(FLP)是一個值得研究的非線性組合優(yōu)化問題，其目的是確定設施在車間中的位置，以最小化物流成本。合理的設施布局對均衡設備能力、保持物流平衡、降低生產成本起著至關重要的作用[1-2]。

隨著智能算法的發(fā)展，諸如遺傳算法、模擬退火算法、蟻群算法、細菌覓食算法以及改進的智能算法被用來解決FLP[3-11]。初始種群一般采用系統(tǒng)布局規(guī)劃(SLP) 的結果，計算復雜且?guī)в幸欢ㄖ饔^性，在選用算法方面存在單一性，而且結果的優(yōu)化對比不足，存在一定的改進空間。

本文以運籌學軟件WinQSB軟件得出的設備布局作為初始方案，將遺傳算法和模擬退火算法混合，以物料流動成本最小化為目標，使用混合算法對實例求解，再與原來的結果進行對比，以驗證算法的有效性。并且拓展問題的規(guī)模，證明算法的廣泛適用性。

1 設備布局的問題描述和模型

1.1 問題描述

本文主要研究多行設備的布局問題，目標是使設備之間的物流搬運成本最小。為方便研究，有以下假設：

(1)簡化車間和設備的形狀，將他們視為矩形結構，車間和設備的尺寸已知。

(2)每行的設備的重心縱坐標相同，且擺放方向與車間的x軸平行。

(3)各設備的橫向間距和縱向間距已知。

模型的具體描述如圖1所示。

圖1 模型參數(shù)圖

1.2 數(shù)學模型

(1)

Dij=|xi-xj|+|yi-yj|,i,j=1,2,...,n

(2)

xi+1,k=xi,k+(li+li+1)/2+hi,i+1+Δi,i+1,k=1,2,...,m

(3)

yi,k+1=yi,k+d,k=1,2,...,m-1;
yi,k=d0,k=1

(4)

(5)

(6)

max(xi,k)+hi0+li,k/2≤L,k=1,2,...,m

(7)

max(yi,m)+wi,m≤W,i=1,2,...,n

(8)

式(1)是模型的目標函數(shù)，Pij為設備間的單位物料搬運費用，Qij為設備間的搬運頻率，Dij為設備間的搬運距離；式(2)為設備i、j之間的距離；式(3)、式(4)是設備間的橫縱坐標推導公式；式(5)表示每個設備只能被安排一次，Zik的值如式(6)所示；式(7)、式(8)表示設備的長度、寬度不能超出車間，L為車間長度，W為車間寬度。

2 混合算法

2.1 嵌套混合算法

遺傳算法(GA)和模擬退火算法(SA)有各自的優(yōu)缺點[12]。嵌套混合算法既包含了GA的選擇、交叉、變異等操作擴大種群的多樣性，也包含了SA結合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解的特性。流程設計如圖2所示。

圖2 GA-SA嵌套算法流程

2.2 兩階段混合算法

針對GA局部尋優(yōu)能力較弱，在GA尋找到較優(yōu)解后，再通過SA繼續(xù)尋優(yōu)。流程設計如圖3所示。

圖3 GA-SA兩階段算法流程

3 混合算法的設計

3.1 設備編碼方式

采用設備編號和設備間的凈距離進行編碼，表達式如下：

[{m1,m2,...,mn},{Δ1,Δ2,...,Δn}]

(9)

其中，n為設備數(shù)量，mi為第i臺設備，Δi為第i臺設備和i-1臺設備之間的凈距離。采用自動換行策略布置所有的設備[13]。

3.2 WinQSB軟件

運籌學軟件WinQSB軟件中Facility Location and Layout(FLL)模塊中的設備產地設計、功能布局可以根據(jù)設備之間的物流量對車間進行布局，或根據(jù)新增的設備對原有布局改進，可為設備布局提供初始解決方案[14]。

3.3 初始種群選取

優(yōu)質的初始群體可以提高算法的效率。WinQSB的FLL模塊產生的設備布局考慮了設備間的物流量，具有一定的合理性，且求解方便，只需導入物流數(shù)據(jù)即可得到布局方案，相比于SLP方法更加高效、科學。

3.4 適應度函數(shù)

采用自動換的策略，只需判斷最后一行設備在y軸方向是否超出范圍，然后給目標函數(shù)加上一個足夠大的懲罰值T。

(10)

3.5 選擇算子

遺傳算法一般采用輪盤賭選擇法，這樣會導致種群單一，容易陷入局部最優(yōu)。采用基于適應度的比例復制，適應度高的復制份數(shù)越多，一定程度上提高了種群的多樣性，有利于算法的全局尋優(yōu)能力[15]。

3.6 交叉算子

本文僅對設備序列采用隨機范圍內的基于次序的交叉，具體執(zhí)行過程如下：

(1)隨機選擇種群中的2條染色體，并隨機產生2個交叉位置。

(2)將2條父代染色體中處于交叉范圍外的基因分別復制到2條子代染色體的對應位置上。

(3)記錄父代1中交叉范圍內的基因，然后將這些基因按照在父代2中的順序復制到子代1對應位置，對于子代2的基因操作同理。交叉過程如圖4所示。

圖4 設備布局序列的交叉過程

3.7 變異操作

只對凈距離序列進行變異。根據(jù)變異概率選擇凈距離序列，在{minΔ,maxΔ}范圍內隨機產生n個隨機凈距離，然后用產生的凈距離將原來的凈距離替換，取適應度好的染色體替換原有染色體。

3.8 SA產生新解

通過對當前解S1采用二鄰域變換法產生新的設備序列，即新的可行解S2。例如n=7時，產生兩個[1,7]范圍內的隨機整數(shù)4和6，將其對應位置的基因交換，如圖5所示。

圖5 新設備序列解產生過程

4 實例計算

4.1 實例驗證

為了檢驗混合算法在車間布局的有效性，選取參考文獻[9]的實例數(shù)據(jù)計算。將設備間的物流成本輸入WinQSB，計算得到3種初始布局方案：(5 9 8 2 1 6 7 10 4 3)、(5 6 7 2 9 8 10 1 4 3)、(4 6 7 3 9 5 8 1 2 10)。

嵌套混合算法的參數(shù)設置如下：種群規(guī)模sizepop=50，最大進化次數(shù)maxgen=50，交叉概率Pc=0.6，變異概率Pm=0.5，懲罰數(shù)值T=500，模擬退火初始溫度T0=1000，降溫速率q=0.9，結束溫度Tend=1×10-3，鏈長L=500。兩階段算法的參數(shù)遺傳代數(shù)和模擬退火迭代次數(shù)和為maxgen=232，其余參數(shù)同嵌套混合算法。通過MATLAB2016a應用兩種算法對實例進行運算，得到結果如圖6和圖7所示。

圖6 兩階段混合算法尋優(yōu)情況

圖7 嵌套混合算法尋優(yōu)情況

算法類型最優(yōu)目標值最優(yōu)適應度產生代數(shù)迭代次數(shù)原文遺傳算法2237.14.47×10-4198500二階段混合算法2083.14.80×10-4139232嵌套混合算法2040.14.90×10-4850

二階段算法中，經過GA運算的目標函數(shù)值為2192.59，再進行SA尋優(yōu)，目標函數(shù)值降低109.494，說明遺傳算法得到的結果具有改進空間，最優(yōu)目標函數(shù)值相比于原文優(yōu)化了6.89%。最優(yōu)解產生代數(shù)早于GA，說明由WinQSB產生的初始布局方案對于算法的尋優(yōu)速度具有顯著的改善。

嵌套混合算法中，通過GA產生的多樣性種群和SA的大規(guī)模搜索，使算法能很快找到最優(yōu)解。最優(yōu)解比原文優(yōu)化了8.80%，所以將嵌套混合算法中的染色體作為最優(yōu)解，設備坐標和布局方案如表2和圖8所示。

表2 設備坐標

圖8 設備最終布局

4.2 針對更大規(guī)模實例的驗證

針對20個設備布局方案進行驗證，數(shù)據(jù)如下：車間尺寸為19m×18m，Δ取值范圍[0,0.4]，d0=3m， d=4m，其余數(shù)據(jù)部分來自文獻[13]，設備尺寸如表3所示。

表3 設備尺寸

通過分析適應度變化曲線可知，兩階段算法和嵌套混合算法在第一代適應度就高于遺傳算法，因為WinQSB產生了合理初始布局方案，提高了初始群體的適應度，而且改進算子使算法的尋優(yōu)速度有所提升。

圖9 算法迭代過程對比

通過計算結果對比可知，兩種混合算法得出的目標函數(shù)值比GA得出的目標函數(shù)值優(yōu)，證明了混合算法的廣泛適用性。

表4 算法結果對比

5 結論

將運籌學軟件WinQSB產生的設備布局方案作為嵌套混合算法和兩階段算法的初始染色體，分別用兩種混合算法對實例進行運算，結果顯示混合算法得到的結果有了顯著的改進，針對更大規(guī)模的實例也有不錯的優(yōu)化效果。同樣地，在解決其他車間問題時(如車間調度)，也可以采用運籌學軟件(如WinQSB、LINGO)自帶求解模塊科學快速的求出初始可行解，再通過混合算法尋求最優(yōu)解，以提升算法的運行效率。

DOI:10.1016/j.eswa.2018.01.011.

DOI:10.1016/j.eswa.2017.10.038.