基于物流關(guān)系和非物流關(guān)系的郵輪分段車(chē)間布局優(yōu)化

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

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

0 引 言

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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

(1)

(2)

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

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

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

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

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

(3)

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

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

(4)

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

(5)

(6)

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

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

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

(7)

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

(8)

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

(9)

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

同理Y方向上有：

(10)

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

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

X方向左右兩邊的邊界為

(11)

Y方向上下兩邊的邊界為

(12)

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

(13)

(14)

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

3.1 編碼設(shè)計(jì)

假設(shè)在需要優(yōu)化布局的車(chē)間中有N個(gè)設(shè)備單元，把每種可能的優(yōu)化方案看作一個(gè)粒子，則每個(gè)粒子的位置和速度都為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次迭代時(shí)的飛行速度和位置更新公式為

(17)

(18)

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

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

2) 懲罰項(xiàng) 傳統(tǒng)的粒子群算法不考慮約束條件，而在實(shí)際郵輪分段車(chē)間布局問(wèn)題中，需特別考慮設(shè)備單元不能超過(guò)邊界的約束條件.本文在改進(jìn)的粒子群算法中增加一個(gè)懲罰項(xiàng)pe(i)，因?yàn)樗惴ㄓ凶詣?dòng)換行機(jī)制保證設(shè)備單元在X方向上不會(huì)超過(guò)邊界，所以只需判斷車(chē)間的設(shè)備單元在Y方向上是否會(huì)超過(guò)邊界，即

(19)

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

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

(20)

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

(21)

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

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

4 實(shí)例檢驗(yàn)

4.1 車(chē)間基本情況

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

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

考慮到郵輪分段車(chē)間中的實(shí)際情況，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è)備單元間物料搬運(yùn)線(xiàn)路視為直線(xiàn)，兩設(shè)備單元間的距離可以用矩形單元中心的直角距離表示，物料搬運(yùn)單價(jià)矩陣Pij、物料搬運(yùn)量矩陣Qij和非物流關(guān)系密切程度分別見(jiàn)表3～6.

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

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

表5 非物流密切程度等級(jí)

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

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

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

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

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

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

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

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

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

時(shí)間內(nèi)分段車(chē)間物料搬運(yùn)成本和非物流密切程度的加權(quán)值最低，物流效益最大，故此方案優(yōu)化效果最好，該郵輪分段車(chē)間布局優(yōu)化方案下的結(jié)果約為4.941 2×105，比初始布局方案的結(jié)果9.296 3×105低，證明用自適應(yīng)慣性權(quán)重改進(jìn)粒子群算法求解郵輪分段車(chē)間布局優(yōu)化模型的方法是有效的.根據(jù)求解結(jié)果，可以得出郵輪分段車(chē)間布局優(yōu)化后的每個(gè)設(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)化郵輪分段車(chē)間布局時(shí)，程序的迭代過(guò)程見(jiàn)圖1.

圖1 改進(jìn)粒子群算法收斂過(guò)程

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

5 結(jié) 束 語(yǔ)

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

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

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