基于物流關系和非物流關系的郵輪分段車間布局優化

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

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

0 引 言

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

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

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

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

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

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

1 問題描述

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

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

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

2 數學建模

考慮分段車間內物料配送路徑和加工流程連續性的優化目標，建立單位時間內物料搬運成本最小Z1和非物流關系密切程度Z2最大的雙目標函數表達式：

(1)

(2)

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

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

表1 設備關系密切度分類

表2 密切度關聯因子

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

(3)

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

為簡化模型，將雙目標函數轉化為單目標函數Z：

(4)

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

(5)

(6)

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

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

1) 每個設備單元只能在某一行中出現一次，表達式為

(7)

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

(8)

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

(9)

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

同理Y方向上有：

(10)

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

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

X方向左右兩邊的邊界為

(11)

Y方向上下兩邊的邊界為

(12)

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

(13)

(14)

3 基于自適應粒子群算法求解

3.1 編碼設計

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

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

(15)

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

(16)

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

(17)

(18)

3.2 參數設計

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

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

(19)

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

3) 適應度函數 適應度函數是粒子群算法在運算過程中評價迭代效果和優化效果的重要函數，以保證實現全局最佳尋優的目的.結合目標函數，設置郵輪分段車間布局問題的適應度函數為

(20)

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

(21)

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

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

4 實例檢驗

4.1 車間基本情況

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

表2 分段車間內作業單元尺寸 單位：m

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

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

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

表3 分段車間內設備單元間的物料搬運單價 單位：m·件

表4 單位時間內分段車間設備單元間的物料搬運量

表5 非物流密切程度等級

表6 非物流密切度關聯因子

4.2 相關參數設置及優化步驟

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

表7 參數設置

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

4.3 優化結果及分析

在Matlab軟件上進行自適應慣性權重改進粒子群算法的求解過程，三種不同的加速系數運行得到的適應值及平均值結果見表8.

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

表8 加速系數對比分析

時間內分段車間物料搬運成本和非物流密切程度的加權值最低，物流效益最大，故此方案優化效果最好，該郵輪分段車間布局優化方案下的結果約為4.941 2×105，比初始布局方案的結果9.296 3×105低，證明用自適應慣性權重改進粒子群算法求解郵輪分段車間布局優化模型的方法是有效的.根據求解結果，可以得出郵輪分段車間布局優化后的每個設備單元的位置坐標：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].

利用自適應慣性權重粒子群算法優化郵輪分段車間布局時，程序的迭代過程見圖1.

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

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

5 結 束 語

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

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

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