劉佳琦 徐 靖 楊家其 胡恒杰 駱奇峰 張霖波

(武漢理工大學(xué)交通與物流工程學(xué)院1) 武漢 430063) (上海外高橋造船有限公司2) 上海 200137)

0 引 言

我國高端郵輪建造市場還處于起步階段，建造車間內(nèi)的物流效益一直是建造過程評價的關(guān)鍵指標(biāo)之一.如今船廠普遍采用分段建造模式開展船舶建造作業(yè)，即分段工位位置確定，工作人員、切割、焊機等加工設(shè)備，以及叉車、平板車等物流設(shè)備在各個分段間來回移動、作業(yè).由于分段建造周期長，對車間場地、空間要求高，而車間內(nèi)可以調(diào)配的加工和物流資源往往有限，且加工、物流設(shè)備自身的性能,以及相互之間的聯(lián)系和作用又會影響到車間物料的搭載和后續(xù)物流環(huán)節(jié)如裝卸和搬運的實施，因此物料加工流程的安排成為郵輪分段建造車間合理布局的關(guān)鍵環(huán)節(jié)[1].

分段建造過程主要包括堆放處提貨、物料預(yù)處理、物料加工、部件拼接等多個環(huán)節(jié)，其中涉及到的設(shè)備有用于處理鋼材和型材的大型加工設(shè)備，以及車間內(nèi)實現(xiàn)物料運輸?shù)奈锪髟O(shè)備.郵輪分段車間涉及許多不同物料的加工流程，各加工流程之間既存在差異，也有一定的關(guān)聯(lián)，不合理的車間布局容易導(dǎo)致物料搬運路線交叉干擾，加工和物流設(shè)備空置率高的問題.在考慮物料搬運路線的基礎(chǔ)上，如何協(xié)調(diào)不同物料的加工流程，使車間的布局更加簡潔、合理，作業(yè)環(huán)節(jié)連續(xù)性高，生產(chǎn)服務(wù)配套性強是目前分段車間物流優(yōu)化所面臨的難題之一.除此之外，分段車間布局優(yōu)化還需要滿足一系列定性和定量條件.

目前已有一些針對普通船舶的車間布局研究.雷明達[2]考慮船舶車間物料的合理配送路線，建立以物料搬運成本最小的單目標(biāo)車間布局優(yōu)化模型.張青雷等[3]在原有船舶動力生產(chǎn)車間的生產(chǎn)需求上，提出以物料搬運成本最少和車間占有面積最小的雙目標(biāo)車間布局優(yōu)化模型，進一步提升了車間物流效益.在船舶物流流程優(yōu)化問題上，陳衛(wèi)彬等[4]把物料加工裝配時間最短納入考慮，并基于加工工件總作業(yè)時間最小求解船舶平面分段智能車間的物流系統(tǒng)優(yōu)化問題.蔣巖[5]將物料訂單可能的延誤時間作為優(yōu)化重點，進一步提升郵輪建造物資配貨作業(yè)的效率.

綜合來看，普通船舶的物料品種少，物流過程比較簡單，涉及的車間布局問題和物流優(yōu)化問題多以物料搬運成本最小或者加工時間最小的單目標(biāo)優(yōu)化模型為主，且很少從車間布局問題的角度出發(fā)對船舶車間的物流流程提出系統(tǒng)的優(yōu)化方案.而對于多品種小批量生產(chǎn)的郵輪建造過程來說，復(fù)雜的物料品種和多層級的物流體系賦予了車間布局問題更為復(fù)雜的需求，對加工流程的連續(xù)性也提出了較高的要求.同時基于實際建造過程考慮，加工設(shè)備和物流設(shè)備的性能也會對物料搬運過程產(chǎn)生影響，所以設(shè)備之間的聯(lián)系、加工流程的連續(xù)性等非物流關(guān)系均應(yīng)在規(guī)劃分段車間布局時納入考慮，而這一水平通常用非物流關(guān)系密切程度作為衡量指標(biāo).結(jié)合以上分析，本文在郵輪分段建造車間面積和物料加工工序已確定的前提下，通過建立物料搬運成本最小和非物流關(guān)系密切程度最大的雙目標(biāo)規(guī)劃模型，以物料在不同設(shè)備間整體工作流程作為切入點，探討郵輪分段車間內(nèi)設(shè)備布局的最優(yōu)位置.

隨著現(xiàn)代算法的發(fā)展，在研究車間問題時多選用粒子群算法進行求解.郭源源等[6]在粒子群優(yōu)化算法中引入經(jīng)典的系統(tǒng)布局規(guī)劃法的思想，提升了粒子群算法在連續(xù)布局問題上的尋優(yōu)效果.Hamed等[7]在粒子群算法中結(jié)合編碼和解碼技術(shù)進行單行設(shè)施布局問題的求解.于蒙等[8]在粒子群算法中考慮隨遺傳與遷移代數(shù)自適應(yīng)調(diào)整參數(shù)的策略，使改進后的算法不易陷入局部最優(yōu).韓宜珂[9]為了克服粒子群算法容易陷入局部最優(yōu)的問題，結(jié)合模擬退火算法高效地運用雙目標(biāo)函數(shù)得到了優(yōu)化布局方案.

傳統(tǒng)的粒子群算法在解決雙目標(biāo)的車間布局優(yōu)化問題時，容易陷入“早熟”收斂，較難在局部最優(yōu)和全局最優(yōu)之間尋求到一個平衡點.為了最大可能得到全局最優(yōu)的結(jié)果，文中在傳統(tǒng)粒子群算法的基礎(chǔ)上，引入一種自適應(yīng)調(diào)整慣性權(quán)重，使慣性權(quán)重隨著粒子適應(yīng)度值的改變而改變，充分改善近似最優(yōu)解的優(yōu)化程度，有利于提升搜索精度和算法效率，得到可靠的全局最優(yōu)解.

1 問題描述

布局問題的前提是設(shè)備單元的具體位置已經(jīng)確定，而在郵輪分段車間布局中，需要確定的是車間內(nèi)叉車、平板車等物流設(shè)備和切割機、焊機等加工設(shè)備的具體位置.因為物流設(shè)備如叉車、平板車相對加工設(shè)備所占空間面積較小，故在分析問題時只考慮它們的物料搬運功能，不考慮它們的尺寸.

假設(shè)每個加工設(shè)備單元形狀都是標(biāo)準(zhǔn)的矩形，已知每個加工設(shè)備單元的尺寸，且它們以平行車間四周墻壁的方式放置.在分段車間實際生產(chǎn)中，物料的運輸路線一般都是平行于車間墻壁的直線，所以在本文問題中，建立以車間左下角為坐標(biāo)原點的坐標(biāo)系，物料運輸路線統(tǒng)一視為平行于X軸和Y軸.

符號表示上，車間在X和Y方向的長度和寬度分別用G、H表示，設(shè)有n個加工設(shè)備單元，θ={1,2,…,n}，對于?i∈θ,有加工設(shè)備在X方向長度li和Y方向長度wi,設(shè)備中心坐標(biāo)為(xi,yi).為符合車間內(nèi)加工設(shè)備布置的實際情況，每個設(shè)備單元只能在某一行中出現(xiàn)一次，設(shè)備單元的總行數(shù)用m表示.

2 數(shù)學(xué)建模

考慮分段車間內(nèi)物料配送路徑和加工流程連續(xù)性的優(yōu)化目標(biāo)，建立單位時間內(nèi)物料搬運成本最小Z1和非物流關(guān)系密切程度Z2最大的雙目標(biāo)函數(shù)表達式：

(1)

(2)

式中：Z1為物料搬運成本；Z2為非物流關(guān)系值；Pij為設(shè)備i和設(shè)備j之間單位物料單位距離的搬運費用；Qij為單位時間內(nèi)設(shè)備i和設(shè)備j之間物料搬運量；dij為設(shè)備i和設(shè)備j之間的搬運距離，且i≠j，表達式為：dij=|xi-xj|+|yi-yj|；Fij為設(shè)備單元之間的非物流密切度等級.

bij為設(shè)備單元之間的密切度關(guān)聯(lián)因子，它主要和設(shè)備單元間的實際搬運距離dij及最大可能距離dmax有關(guān)，具體取值見表1～2.

表1 設(shè)備關(guān)系密切度分類

表2 密切度關(guān)聯(lián)因子

dmax=G+H-2(G0+H0)

(3)

式中：G0為設(shè)備單元在X方向上與車間邊界的最小距離；H0為設(shè)備單元在Y方向上與車間邊界的最小距離.

為簡化模型，將雙目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)Z：

(4)

式中：u1，u2為歸一化因子，具體表達式為

(5)

(6)

式中：w1為物料搬運成本的權(quán)重；w2為非物流關(guān)系密切程度的權(quán)重，且w1+w2=1.

考慮郵輪分段車間的設(shè)備單元布局情況，約束條件表述如下.

1) 每個設(shè)備單元只能在某一行中出現(xiàn)一次，表達式為

(7)

i=1,2,…,nk=1,2,…,m

(8)

2) 相鄰設(shè)備單元之間需要留有一定的距離，表達式為

(9)

式中：g為X方向上相鄰兩個設(shè)備單元之間必須保持的最小距離，g≥0，且為常數(shù)；lk(i)為第k行第i個設(shè)備單元在X軸上的長度.

同理Y方向上有：

(10)

式中：h為Y方向上相鄰兩行設(shè)備單元間必須保持的最小距離，已知h≥0,且為常數(shù)；wk(i)為第k行第i臺設(shè)備在Y軸上的長度.

3) 設(shè)備單元在X、Y方向上的位置不能超過分段車間的邊界.同時為了確保車間人員工作和物料配送的安全，各設(shè)備單元與車間的邊界距離應(yīng)設(shè)置一個安全范圍內(nèi)的最小值.為方便表達，將車間在X、Y方向上的邊界也視為設(shè)備單元.

X方向左右兩邊的邊界為

(11)

Y方向上下兩邊的邊界為

(12)

X、Y方向與邊界的最小距離約束為

(13)

(14)

3 基于自適應(yīng)粒子群算法求解

3.1 編碼設(shè)計

假設(shè)在需要優(yōu)化布局的車間中有N個設(shè)備單元，把每種可能的優(yōu)化方案看作一個粒子，則每個粒子的位置和速度都為2N維向量.位置向量中前N維代表設(shè)備單元在X軸上的坐標(biāo)，后N維代表設(shè)備單元在Y軸上的坐標(biāo)；速度向量中前N維代表粒子在X軸上的飛行速度，后N維代表粒子在Y軸上的飛行速度[10].位置P和速度V的具體坐標(biāo)為

P=(x1,…,xn，y1,…,yn)

(15)

V=(vx1,…,vxn，vy1,…,vyn)

(16)

傳統(tǒng)的粒子群算法中，粒子在第k次迭代時的飛行速度和位置更新公式為

(17)

(18)

3.2 參數(shù)設(shè)計

1) 加速系數(shù)的確定 為避免算法陷入局部極值，需合理設(shè)置加速系數(shù)的取值.由文獻[10]可知通常取c1=c2，且c1+c2≤4，根據(jù)經(jīng)驗，一般取值在[0.5，2]能夠取得較好的優(yōu)化結(jié)果.

2) 懲罰項 傳統(tǒng)的粒子群算法不考慮約束條件，而在實際郵輪分段車間布局問題中，需特別考慮設(shè)備單元不能超過邊界的約束條件.本文在改進的粒子群算法中增加一個懲罰項pe(i)，因為算法有自動換行機制保證設(shè)備單元在X方向上不會超過邊界，所以只需判斷車間的設(shè)備單元在Y方向上是否會超過邊界，即

(19)

表達式中的T一般是較大的正數(shù).本文T的取值為500.

3) 適應(yīng)度函數(shù) 適應(yīng)度函數(shù)是粒子群算法在運算過程中評價迭代效果和優(yōu)化效果的重要函數(shù)，以保證實現(xiàn)全局最佳尋優(yōu)的目的.結(jié)合目標(biāo)函數(shù)，設(shè)置郵輪分段車間布局問題的適應(yīng)度函數(shù)為

(20)

4) 慣性權(quán)重 粒子的全局與局部搜索能力之間的平衡與慣性權(quán)重的大小直接相關(guān)，迭代初期需要較大的慣性權(quán)重保持較強的全局搜索能力，后期則需要較小的慣性權(quán)重進行更加精確的局部搜索，同時也要盡可能地縮短運算時間，提高搜索效率.由文獻[11]可知，慣性權(quán)重的調(diào)整主要受粒子適應(yīng)度、種群規(guī)模以及搜索空間維度影響，所以在實際應(yīng)用中，可以把慣性權(quán)重定義為

(21)

式中：Fi為第i個粒子的適應(yīng)度值；N為搜索空間維度；n為粒子數(shù)目；a、b為經(jīng)驗參數(shù).

算法在每次迭代后通過上式更新所有粒子的慣性權(quán)重，同時保證了局部尋優(yōu)和全局尋優(yōu)的準(zhǔn)確性，提高了最優(yōu)解的精度，有效地避免了陷入局部最優(yōu)的可能.

4 實例檢驗

4.1 車間基本情況

以長170 m、寬170 m的郵輪分段生產(chǎn)車間為例，該車間主要設(shè)備有進行鋼材和型材的半自動切割機、門式切割機和板條切割機、數(shù)控冷彎機、裝焊設(shè)備和油壓機等，主要得到產(chǎn)品有小組立、中組立、平臺和零件等.為簡化描述，按照郵輪分段車間的生產(chǎn)設(shè)備狀況，用序號表示車間內(nèi)各個設(shè)備組和堆放處，總計十個工作單元.其序號，名稱及尺寸見表2.

表2 分段車間內(nèi)作業(yè)單元尺寸 單位：m

考慮到郵輪分段車間中的實際情況，G0和H0分別為各設(shè)備單元在X軸和Y軸方向上應(yīng)與邊界必須保持的最小距離，G0=5.4 m，H0=4.3 m.X軸和Y軸方向上相鄰兩行設(shè)備間必須保持的最小距離g和h分別為0.8和0.4 m.

初始布局中設(shè)備單元原坐標(biāo)向量為：X=[109 48 34 123 132 42 83 118 126 37]；Y=[105 20 101 81 55.2 74 52 31 15 38].

把設(shè)備單元間物料搬運線路視為直線，兩設(shè)備單元間的距離可以用矩形單元中心的直角距離表示，物料搬運單價矩陣Pij、物料搬運量矩陣Qij和非物流關(guān)系密切程度分別見表3～6.

表3 分段車間內(nèi)設(shè)備單元間的物料搬運單價 單位：m·件

表4 單位時間內(nèi)分段車間設(shè)備單元間的物料搬運量

表5 非物流密切程度等級

表6 非物流密切度關(guān)聯(lián)因子

4.2 相關(guān)參數(shù)設(shè)置及優(yōu)化步驟

在本案例中,對相關(guān)參數(shù)包括粒子維度(即工作單元數(shù))D、種群規(guī)模(即粒子數(shù))N、加速系數(shù)c1和c2、慣性系數(shù)w、迭代次數(shù)n、懲罰系數(shù)pe(i)進行設(shè)置，各參數(shù)具體數(shù)值見7.

表7 參數(shù)設(shè)置

由于粒子群算法的結(jié)果和迭代速度、加速系數(shù)具體的取值有關(guān)，為提高改進后粒子群算法的可靠性，本文在加速系數(shù)三種不同取值的情況下分別運行500次，選取每種加速系數(shù)較優(yōu)的3次結(jié)果求平均值，然后對比分析它們的平均值大小.由于適應(yīng)度值是目標(biāo)函數(shù)的倒數(shù)，取最小的目標(biāo)函數(shù)值，即取最大的平均適應(yīng)度值作為最終的優(yōu)化布局方案.

4.3 優(yōu)化結(jié)果及分析

在Matlab軟件上進行自適應(yīng)慣性權(quán)重改進粒子群算法的求解過程，三種不同的加速系數(shù)運行得到的適應(yīng)值及平均值結(jié)果見表8.

由表8可知：c1=c2=1.8時的平均適應(yīng)度值最大，約為2.177 0×10-5，此時函數(shù)值最小，單位

表8 加速系數(shù)對比分析

時間內(nèi)分段車間物料搬運成本和非物流密切程度的加權(quán)值最低，物流效益最大，故此方案優(yōu)化效果最好，該郵輪分段車間布局優(yōu)化方案下的結(jié)果約為4.941 2×105，比初始布局方案的結(jié)果9.296 3×105低，證明用自適應(yīng)慣性權(quán)重改進粒子群算法求解郵輪分段車間布局優(yōu)化模型的方法是有效的.根據(jù)求解結(jié)果，可以得出郵輪分段車間布局優(yōu)化后的每個設(shè)備單元的位置坐標(biāo)：X=[89.35 109.80 114.86 63.69 145.34 70.10 94.57 102.13 89.49 92.53]；Y=[75.15 108.46 75.34 103.05 56.22 58.48 96.06 101.06 101.07 76.13 116.93].

利用自適應(yīng)慣性權(quán)重粒子群算法優(yōu)化郵輪分段車間布局時，程序的迭代過程見圖1.

圖1 改進粒子群算法收斂過程

由圖1可知：函數(shù)值在迭代進行到390次左右的時候基本達到穩(wěn)定，說明算法的收斂能力良好，可以充分改善粒子群算法近似最優(yōu)解的優(yōu)化程度，更利于搜索全局最優(yōu)解.

5 結(jié) 束 語

文中結(jié)合郵輪建造物料多品種小批量生產(chǎn)的物流特點，從郵輪建造現(xiàn)場工作實際出發(fā)，不僅考慮物料的搬運成本，同時聚焦不同物料加工工序間存在的重疊和干擾，以及設(shè)備自身性能等非物流因素對加工過程的影響，考慮引入非物流關(guān)系密切程度作為衡量加工流程連續(xù)性和設(shè)備自身性能等非物流因素的指標(biāo)，在確定的分段車間面積和物料加工工序的前提下，以提升車間內(nèi)部物流效益為目的，研究郵輪分段建造車間布局的優(yōu)化方案.

通過建立基于物料搬運成本最小和非物流關(guān)系密切程度最大的雙目標(biāo)函數(shù)，引入動態(tài)慣性權(quán)重因子對傳統(tǒng)的粒子群算法進行改進，使算法在全局搜索前期具有較高的探索能力，獲得比固定慣性權(quán)重更為精確的尋優(yōu)結(jié)果，更好地解決雙目標(biāo)的車間布局優(yōu)化問題.同時為了確保各設(shè)備單元均不超過邊界，也不互相干擾，在適應(yīng)度函數(shù)上加入了基于約束條件的懲罰函數(shù)，進一步提升方案的可靠性.

結(jié)合郵輪分段建造車間實例驗證，將優(yōu)化后的郵輪分段車間布局方案同原始布局方案進行比較，發(fā)現(xiàn)基于物料搬運成本和非物流關(guān)系優(yōu)化的郵輪分段車間布局方案能在保證整體工作流程貼近實際的基礎(chǔ)上，通過降低物流成本，提升不同加工設(shè)備、物流設(shè)備和加工工序的連續(xù)性，顯著提高分段車間物流過程的效益，雙目標(biāo)規(guī)劃模型能夠較好地從車間整體物流角度出發(fā)規(guī)劃車間布局.