基于改進遺傳算法的瀝青路面再生工廠布局優化

肖子豪,郭小宏

(重慶交通大學經濟與管理學院,重慶 400074)

在瀝青路面再生工廠規劃建設過程中,車間布局是一個重要卻又復雜的部分。不僅各功能單元的相互關系、物料搬運距離會對布局規劃產生影響,而且各功能單元的布置方式也會對布局產生制約。僅使用傳統的方法,比如分支定界法[1]、割平面法[2]和系統布局規劃法[3](system layout planning, SLP),解決多個功能單元的布局規劃問題時效率很低[4],只能完成規模較小的布置組合內容。車間布局優化在降低車間物料搬運成本及提高生產效率方面起到了重要的作用[5]。近年來,智能算法作為主要研究手段被廣泛應用于車間布局優化的研究中。周潤博[6]、謝暉[7]利用遺傳算法結合SLP法,以物流成本最小和功能區相關性最大為目標對公司生產車間進行布局優化,有效縮短了物料搬運距離,提高了企業的生產效率。張廣泰等[8]融合熵權-逼近理想解排序法,基于遺傳算法對SLP法進行了改進,提高了車間布局的非物流關系強度。趙歡[9]采用剩余矩形排樣算法和遺傳算法,考慮設備布局與總體布局的耦合得到二次優化布局,減少了廠區總體布局費用。盧義楨等[10]引入自適應遺傳算子策略,提出改進的遺傳模擬退火算法求解模型,有效降低了物流成本和縮短了搬運時間。董舒豪等[11]采用遺傳模擬退火算法,針對多行設施布局優化模型,進行分段編碼并以實例驗證了其優越性。伍義[12]、李孟雪[13]、楊雅楠[14]采用遺傳算法及遺傳模擬退火算法,以非物流相關性最大、物流成本最小、碳排放最少為目標得到了布局優化方案。但是,目前針對再生工廠車間布局優化問題所采用的遺傳算法仍存在一些不足:1)再生工廠的各個功能單元并非成行布置,其放置位置受到車間邊界、功能單元間距約束的影響。現有算法采用間接編碼方式,各功能單元的布置位置信息表達不直觀,編碼解碼復雜度高,影響了算法的效率;2)現有遺傳算法針對初始種群的設定方法并不明確,對于種群的優化方法欠佳使得算法的全局搜索能力不強,易陷入局部最優。

基于此,筆者采用實數分層編碼,分為坐標層和放置方式層,分別對應各車間的坐標及放置狀態,使信息表達更加直觀,降低編碼難度,減少求解時間;并針對初始布局進行排列組合得到初始種群,提高設定效率,增加其多樣性。坐標層采用多點變異,放置方式層采用單點變異,引入模擬退火算子,增加了繁殖更優個體的概率,提高了算法的局部搜索性能。

1 工廠布局相關概念和數學模型

1.1 功能單元劃分與聯系

瀝青路面再生工廠的工藝流程為將回收的RAP料進行破碎篩分,得到不同粒徑的基準料,烘干后按一定的比例與新集料、粉料、瀝青和再生劑進行混合攪拌,最終得到再生成品料。按加工對象,對生產設備進行分類組合實現功能單元的劃分,如表1所示,再根據工藝關系梳理各功能單元之間的聯系,如圖1所示。

圖1 功能單元聯系圖Fig.1 Contact diagram of functional unit

表1 瀝青路面再生工廠的功能單元劃分

1.2 功能單元位置信息表示

再生工廠車間布局是指按照一定約束,在給定的布局范圍內對各個功能單元進行合理布置,從而達成多目標的協調。需布局的車間范圍在一個長為L,寬為W的矩形內部,車間左下角為坐標原點。各功能單元的形狀假定為矩形,均平行于X軸或Y軸放置,功能單元之間保持一定的活動距離,其位置信息指矩形中心的橫、縱坐標,放置方式是指其平行于X軸或Y軸放置,表示為

(x1,x2,…,xj,…,xn-1,xn),

(1)

(y1,y2,…,yj,…,yn-1,yn),

(2)

(z1,z2,…,zj,…,zn-1,zn)。

(3)

式(1)—式(3)中:xn表示第n個功能單元的橫坐標;yn表示第n個功能單元的縱坐標;zn表示第n個功能單元的放置方式;xj,yj,zj分別表示第j個功能單元的橫坐標、縱坐標、放置方式。

車間和功能單元的布局模型如圖2所示,其中:Fi,Fj,Fk為功能單元代號;lj為某功能單元的長度;wj為某功能單元的寬度;sx,sy為功能單元在X軸、Y軸方向上與車間邊界的活動間距;sxf,syf為2個功能單元之間在X軸、Y軸方向上的安全間距;L為車間長度;W為車間寬度。

圖2 車間和功能單元布局模型圖Fig.2 Layout model of workshop and functional units

1.3 方向約束

當功能單元的長邊平行于X軸時,將其視為橫向放置;當功能單元的長邊平行于Y軸時,將其視為豎向放置。

(4)

功能單元的放置方式如圖3所示。

圖3 功能單元的放置方式示例Fig.3 Example of how functional units are placed

1.4 邊界約束

功能單元的布置位置應落在車間范圍內,且與車間邊界保持一定的間距。

(5)

1.5 間距約束

車間內部的任意功能單元之間互不重合,在X軸或Y軸方向上至少保留大小為sxf或syf的間距,且每個功能單元只能被布置1次。

Ujk×Vjk=0,

(6)

(7)

(8)

式(6)—式(8)中:Ujk表示判斷j功能單元和k功能單元在X軸方向上是否重疊;Vjk表示判斷j功能單元和k功能單元在Y軸方向上是否重疊。

1.6 目標函數

車間布局優化以非物流關系強度最大、物流成本最小及碳排放最少為目標,其具體計算方式參考文獻[15],目標函數設定如下:

(9)

式中:D表示目標函數值;a1表示非物流關系強度權重;D1表示非物流關系強度值;D1max表示非物流關系強度最大值;a2表示物料搬運成本權重;D2表示物流成本值;D2max表示物料搬運成本最大值;a3表示碳排放權重;D3表示碳排放值;D3max表示碳排放最大值。

2 改進遺傳算法

2.1 實數分層編碼

遺傳算法的編碼和解碼方法很大程度上決定了算法的可行性和效率,因此設計適宜的編碼和解碼方法極為重要。針對再生工廠車間布局問題,采用傳統的二進制編碼會使種群個體過于冗長,且不同位置的個體在十進制編碼轉換為二進制編碼時長度可能不一致,導致編碼過于復雜。為解決傳統遺傳算法在布置位置和放置方式表示問題上的不足,提出實數分層編碼方法,在降低編碼難度的同時,能夠直觀表示各功能單元的布置位置和放置方式。用分層編碼的方式映射3個決策層(橫坐標層、縱坐標層以及放置方式層)共同對目標函數產生的影響。

圖4所示為實數分層編碼示例。第1層為橫坐標層,實數表示功能單元在車間布局范圍內的橫坐標;第2層為縱坐標層,實數表示功能單元在車間布局范圍內的縱坐標;第3層為放置方式層,反映各功能單元的放置方式:數字1表示該功能單元橫向放置,數字0表示豎向放置。

圖4 實數分層編碼示例Fig.4 Example of real number layered coding

實數分層編碼的解碼方式相對簡便,只需將橫坐標層、縱坐標層以及放置方式層中的數字按編碼順序列出。圖4所示的再生工廠車間布局方案解碼輸出結果如表2所示。

表2 布局方案解碼輸出結果

2.2 初始種群設定

由于再生工廠車間布局的范圍偏大、功能單元數量偏多,采用車間邊界內隨機生成功能單元布置位置的方法效率低下。提出基于初始方案的排列組合方法,將初始方案作為初始種群之一,其余種群個體采用各功能單元橫、縱坐標和放置方式交換的方法得到。由于生成1～12的全排列數組數量超出MATLAB軟件行數范圍,遂生成1～6和7～12的2個全排列數組,對其進行排列組合并將順序與初始布局方案相同的數組剔除,從而得到1～12的排列數組。將初始方案按該數組排列放置,通過判斷得到的方案是否符合約束條件,并計算符合約束條件方案的目標函數值,從中篩選出剩余的種群個體,保證初始種群個體的有效性,增加初始種群個體的多樣性。

2.3 交叉算子

交叉算子是產生新個體的主要方式,在算法中起核心作用,決定了算法的性能優劣。在交叉操作中,染色體的前2行作為交換的基本單元,即橫坐標層和縱坐標層進行算術交叉,放置方式層不進行交叉,這能夠保證子代與父代的放置方式一致。編碼交叉操作示例如圖5所示,圖中α=0.2,具體步驟如下。

圖5 編碼交叉操作示例圖Fig.5 Example diagram of coding cross operation

步驟1 從種群中選擇相鄰的2條染色體,提取其橫坐標層和縱坐標層作為父代基因P1和P2。

步驟2 將父代基因P1和P2進行算術交叉,生成2個子代基因O1和O2。算術表達式為

O1=α×P1+(1-α)×P2,

(10)

O2=(1-α)×P1+α×P2,

(11)

式中:α表示(-0.5,1.5)內的隨機數。

步驟3 將生成的子代基因O1和O2分別與父代染色體P1和P2的放置方式層基因結合,得到2個新的種群個體。

2.4 變異算子

變異算子任意改變所選染色體的一個或多個基因,以增加種群的結構可變性,能防止算法過早收斂。針對坐標層,引入模擬退火算子,在迭代初期,于全局范圍內搜索最優值。隨著迭代次數的增加,搜索范圍逐漸減小,便于尋找近似最優解的精確解,提高算法的搜索效率。對于放置方式層,采用單點變異的方式。

1)橫坐標層、縱坐標層的變異

示例如圖6所示,具體步驟如下。

圖6 橫坐標層和縱坐標層變異示例圖Fig.6 Example diagram of horizontal and vertical coordinate layer variation

步驟1 生成2個(0,1)范圍內的1×12隨機數列矩陣,找出數值小于變異概率的位置下標并標記。

步驟2 對橫坐標層和縱坐標層標記位置的數據進行變異,變異公式如下:

a=a+a×b×0.95gen,

(12)

式中:a表示橫坐標層和縱坐標層標記位置的數據;b表示(-1,1)內的一個隨機數;gen表示迭代次數。圖中b取-0.5,gen取1。

步驟3 將變異后的數據作為基因對應標記位置放回染色體內。

2)放置方式層的變異

放置方式層采用單點變異,示例如圖7所示,具體步驟如下。

圖7 放置方式層變異示例圖Fig.7 Example diagram of placement method layer variation

步驟1 生成[1,12]范圍內的一個隨機整數,找出該整數對應放置方式層的位置下標并標記。

步驟2 對放置方式層標記位置的數據進行變異,變異公式如下:

(13)

式中:c表示放置方式層標記位置的數據。

步驟3 將變異后的數據作為基因對應標記位置放回染色體內。

將變異后的橫坐標層、縱坐標層和放置方式層基因組合,得到新的種群個體。

2.5 改進遺傳算法實現步驟

傳統的車間布局遺傳算法編碼復雜,增加了解碼的難度和時間,布局位置和放置方式信息表達不夠直觀,且搜索算子設置單一,導致算法的尋優能力不足。本文針對傳統遺傳算法進行改進,提出實數分層編碼方法,引入模擬退火算子,清晰表達功能單元的布局位置和放置方式信息,增強算法尋求最優解的能力,具體步驟如下。

步驟1 根據再生工廠車間布局的約束,基于初始布局方案得到滿足約束條件的初始種群個體。

步驟2 計算種群個體的適應度函數值,采用輪盤賭方法進行種群個體的選擇。

步驟3 依次選擇相鄰的2個種群個體,將其橫坐標層、縱坐標層作為父代基因進行交叉,之后與父代的放置方式層基因結合,得到新的種群個體。

步驟4 根據變異概率,對種群個體依次進行橫坐標層、縱坐標層和放置方式層變異,得到新的種群個體。

步驟5 計算新種群中個體的目標函數值,對目標函數值進行排序。保留部分優秀個體,并將其與父代染色體中優秀的個體結合,形成新的種群。

步驟6 判斷迭代次數是否滿足算法終止條件。是則輸出計算結果,否則返回步驟2。

3 實例驗證

為驗證改進算法的有效性,以某瀝青路面再生工廠為研究對象。該再生工廠車間的長L=180 m,寬W=150 m,生產大門位于(0,118),各功能單元均位于布局范圍內,且與車間邊界的間距sx,sy均大于或等于5 m。各功能單元尺寸、布局位置與車間邊界的間距如表3所示,初始布局方案如圖8所示。

圖8 初始布局方案圖Fig.8 Plan of initial layout

表3 功能單元信息

利用MATLAB 2016a完成改進遺傳算法的編寫。設置初始種群規模大小NIND=200、變異概率Pm=0.2、最大迭代次數MAXGEN=200。通過算法進行求解,得到如下結果:優化后的目標函數值為0.423 3,優化后的布局位置和放置方式如表4所示。

表4 優化后功能單元布局位置和放置方式表

將原始布局方案與優化布局方案數據依照優化目標計算,得到相應結果,其對比如表5所示。

表5 方案優化前后效果對比

根據表5對比結果可知,優化后的布局方案中各功能單元的非物流關系強度提高7.96,每日物料搬運成本減少14 468.85元,每日碳排放減少30.59 kg。

為驗證文中算法的有效性,將傳統遺傳算法、文獻[14]中的遺傳算法應用于該實例并進行比較,迭代過程如圖9所示,3種算法得到的目標函數值與迭代次數的對比如表6所示。

圖9 算法迭代過程Fig.9 Process of algorithm iteration

表6 迭代結果對比

從表6對比3種算法迭代結果可知,改進后的遺傳算法較傳統遺傳算法迭代次數減少34次,目標函數值減少0.012 8,較文獻[14]中遺傳算法迭代次數相近,目標函數值減少0.009 9。

4 結 語

筆者針對瀝青路面再生工廠布局優化,采用遺傳算法對其初始種群設定方式、編碼方式與交叉和變異方式進行明確及改進,得到如下結論。

1)采用實數分層編碼,以功能單元布局位置的橫、縱坐標和放置方式代替傳統的二進制編碼,增強了布局位置信息表示的直觀性,降低了解碼復雜度,減少了算法求解時間,提高了運行效率。

2)基于初始布局方案,采用排列組合得到初始種群,增加了初始種群的多樣性。

3)針對算法的變異引入模擬退火算子,使得尋優能力提升,從而可以高效地對布局方案進行優化。

4)實例表明,改進后的遺傳算法較傳統遺傳算法迭代次數減少34次,目標函數值減少0.012 8,較文獻[14]中目標函數值減少0.009 9。優化后的布局方案中,每日物料搬運成本減少14 468.85元,碳排放減少30.59 kg。改進后的方法可為瀝青路面再生工廠布局優化提供參考與技術支持。

本文利用MATLAB僅生成了1～12全排列的部分數組,未生成全部數組,今后可完善全部數組以豐富初始種群,增加其多樣性,并利用約束條件篩選出更為優秀的種群個體,從而提高算法的尋優能力。此外,本文的研究僅引入模擬退火算子,后續可引入其他算子,并針對再生工廠布局優化算法進行改進。