唐偉煒，楊坤榮，艾志興（.華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 5064；.中船澄西船舶（廣州）有限公司，廣東 廣州546；.中船黃埔文沖船舶有限公司，廣東 廣州 5075）

?

修船廠移泊作業(yè)優(yōu)化方法研究

唐偉煒1，楊坤榮2，艾志興3
（1.華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510641；2.中船澄西船舶（廣州）有限公司，廣東 廣州511462；3.中船黃埔文沖船舶有限公司，廣東 廣州 510715）

船舶泊位調(diào)度是修船廠作業(yè)的重要組成部分，本文基于動態(tài)規(guī)劃和圖論的相關(guān)理論，對修船廠碼頭移泊調(diào)度問題進行了研究，闡述了移泊系統(tǒng)的馬爾科夫特性，并將船廠碼頭移泊問題就轉(zhuǎn)化為求解其所對應(yīng)的賦權(quán)網(wǎng)絡(luò)最優(yōu)路問題，通過對問題網(wǎng)絡(luò)結(jié)構(gòu)圖的逆向推進，把一個最優(yōu)路徑問題轉(zhuǎn)化為多段決策問題，最終獲得該問題的最優(yōu)路徑。最后用算例證明了本文研究的方法對于處理修船碼頭移泊問題，有著非常好的尋優(yōu)性。

修船廠移泊調(diào)度；馬爾科夫鏈；圖與網(wǎng)絡(luò)模型；最優(yōu)路徑

引　言

船舶泊位調(diào)度是修船企業(yè)碼頭作業(yè)的重要組成部分，隨著修船行業(yè)的發(fā)展，各修船廠碼頭?？看暗臄?shù)量以及多樣性不斷增加，人員工作量日益增大。事先對修船廠碼頭各個泊位的停泊計劃進行合理安排，可以極大地提高修船碼頭的作業(yè)效率。通常情況下，船廠的船舶泊位問題可以定義為：在計劃周期開始時，對計劃周期內(nèi)預(yù)計抵達的船舶合理地安排停泊時間和靠泊位置，并由于某些特定原因，對一艘或者多艘船舶進行位置調(diào)整，也就是泊位調(diào)整。由于修船廠碼頭泊位數(shù)量是有限的，船舶越靠近碼頭，起重機作業(yè)范圍越佳，工程需求越能得到滿足，當(dāng)各泊位組同時停泊數(shù)艘船時，就需要不斷的去移泊，調(diào)整泊位，使各船可以交替使用起重設(shè)備，滿足不同船舶的工程要求。

依靠調(diào)度人員經(jīng)驗來管理的船舶調(diào)度系統(tǒng)在實際操作時，由于現(xiàn)場的局限性，計劃表中的任務(wù)有時無法完成，并現(xiàn)場會有些突發(fā)狀況使方案要隨時更改，這就加大了工人工作量，降低了工作效率。而且由于方案邊做邊落實，未能直觀的在?？看皵?shù)量以及多樣性不斷增加的情況下，難免會有重復(fù)工作的現(xiàn)象。

由此可見，這種由人力來制定移泊計劃在碼頭船舶較多時已逐漸不能滿足生產(chǎn)需求，以至于企業(yè)資源無法充分利用，運行成本過高。為了提高生產(chǎn)效率，降低生產(chǎn)成本，減輕工人作業(yè)量，亟需一套新的方法來解決問題。

本文依據(jù)船廠船舶停泊的特點，即移泊過程容易離散的特征，通過分析移船作業(yè)過程，抽象歸納問題的基本要素，逐步建立問題的數(shù)學(xué)模型，然后尋找解答問題的方法。

1　移泊問題描述

修船碼頭的泊位為一個二維泊位，分別由橫向岸線與縱向檔位組成一個二維空間，如圖 1所示。

圖1　碼頭泊位布置

每艘船舶都存在一個最佳工作泊位，最佳工作泊位即能最大限度的保障船舶在計劃周期內(nèi)完成作業(yè)的泊位，由于設(shè)備工作范圍的局限性，一般越靠近碼頭岸線的泊位越能提前安排作業(yè)。在企業(yè)接到預(yù)定進廠船舶的船期表時，會給船舶制定停泊計劃和作業(yè)計劃，但當(dāng)碼頭船舶較多時，新進廠船舶則需暫停其他泊位，在開始作業(yè)前經(jīng)一系列移泊移到最佳工作泊位，其次，當(dāng)船舶停泊到目標泊位后，若勘探的工作量與與其工作量有差別，因工作計劃的調(diào)整也需要對船舶進行移泊，此外，需要移泊的情形通常還有：1）船舶因進出塢造成的泊位調(diào)整；2）因船舶的進出廠造成泊位的調(diào)整；3）發(fā)生干擾事件后，因預(yù)定靠泊位置被其他船舶占用造成的泊位調(diào)整。在實際生產(chǎn)中移泊原因通常不是單一的而是由各種因素復(fù)合而成的。

當(dāng)船舶需要從一個泊位移動到另一個泊位時，制定移泊方案目標一般為移船次數(shù)最少，一般來說，船舶移動次數(shù)與移動時間成正比，船舶移動次數(shù)越少，移動路徑越簡單，所花費時間也就越少。這樣既能確保船舶在計劃周期內(nèi)完成作業(yè)，又能使碼頭環(huán)境不那么復(fù)雜，降低安全事故的發(fā)生率。而船舶在水中被拖輪拖移的速度可認定為一常數(shù)。船廠的移泊任務(wù)按要求順利完成首先取決于船廠碼頭移泊資源（泊位和拖輪），修船廠的泊位由岸線和沿航道寬度方向的檔位構(gòu)成，碼頭岸線的長度和航道的寬度決定著船舶可?？繑?shù)量；同時移船工具—拖輪的數(shù)量和馬力，也對移泊進程和優(yōu)化路徑有著關(guān)鍵性的影響，往往拖輪的數(shù)量和馬力大小決定著每次移泊的船舶數(shù)量，若拖輪數(shù)量不足或馬力太小，可同時移動的船舶數(shù)量就會減少。另外，船廠碼頭的系泊能力和碼頭外航道的通行能力等，也會限制碼頭的容量，間接地影響了移泊的進程。所以求移泊最優(yōu)路徑的核心問題就是合理利用有的碼頭資源，尋找一個最佳的移船方案，對移泊過程進行優(yōu)化，使船舶的移動次數(shù)最少，這也就是建立問題的模型以及求解的過程。

2　移泊問題的馬爾科夫特性

馬爾科夫過程一種典型的隨機過程［1］。通過對不同狀態(tài)的初始概率以及狀態(tài)之間的轉(zhuǎn)移概率的研究，來確定狀態(tài)的變化趨勢，從而達到對未來進行預(yù)測的目的。馬爾科夫鏈是指時間和狀態(tài)參數(shù)都是離散的馬爾科夫過程，是最簡單的馬爾科夫過程。每個滿足離散性、隨機性、無后效性3個特點的系統(tǒng)，均可用馬爾科夫鏈研究其過程，并預(yù)測未來。

從直觀上看，船舶在碼頭停靠的形式似一個矩陣，假設(shè)初始狀態(tài)為 A0，即船舶未開始移泊前的狀態(tài)。該矩陣經(jīng)過n次變化，變?yōu)榫仃嘇n，即船舶移泊后的最終狀態(tài)，也是目標狀態(tài)。這時，我們可以將整個移泊過程離散成n個子系統(tǒng)，每個子系統(tǒng)對應(yīng)著一次遵循著一定演化規(guī)則的船舶排列變化，而且每個子系統(tǒng)的狀態(tài)只與其前后狀態(tài)相關(guān)。此時，整個船舶移泊系統(tǒng)可以看成一個離散體系。

按照馬爾科夫鏈的定義，可知由n個離散系統(tǒng)所組成的船廠碼頭移泊系統(tǒng)可以看成為一個馬爾科夫鏈，它具有無后效性的特征，即在某個狀態(tài)已經(jīng)確定的情況下，它的后續(xù)狀態(tài)只受當(dāng)前狀態(tài)的影響，跟以前的狀態(tài)無關(guān)，換言之，當(dāng)前狀態(tài)就是后續(xù)狀態(tài)的初始狀態(tài)；具有離散性的特征，即整個船舶移泊作業(yè)過程可以看成由n個子系統(tǒng)構(gòu)成，每一個子系統(tǒng)對應(yīng)著一個船舶移動的方案。解決問題的關(guān)鍵就是尋找系統(tǒng)內(nèi)各狀態(tài)間的演化規(guī)則，從而得出系統(tǒng)的最優(yōu)路徑。

3　船舶移泊調(diào)度問題的圖與網(wǎng)絡(luò)模型

對于建立修船廠的船舶移泊模型問題，國內(nèi)外研究很少涉獵，相關(guān)的內(nèi)容主要集中在交通運輸與車輛調(diào)度上，比較典型的有圖與網(wǎng)絡(luò)的最短路徑問題［2］，其模型的建立也值得我們參考。面對的一個現(xiàn)實問題，到底什么樣的方法建立數(shù)學(xué)模型，沒有絕對的標準，不同的人可能使用不同的方法，另外，同樣的問題，可以用幾個階段來完成模型，不同的階段有不同的方法，組合起來形或完整模型，數(shù)學(xué)模型的形式可以是多種多樣的，可以是表格形式，也可以以圖形的形式，不一定非得有數(shù)學(xué)公式才算是數(shù)學(xué)模型［1］。

圖與網(wǎng)絡(luò)中所謂的“圖”并不是通常意義下的幾何圖形或物體的形狀圖，而是指某類具體事物和這些事物之間的聯(lián)系，是以一種抽象的形式來表達一些確定的事物之間的聯(lián)系的數(shù)學(xué)系統(tǒng)［3］。借助于圖論的概念、理論和方法，可以對任何一個包含了二元關(guān)系的離散系統(tǒng)的數(shù)學(xué)模型求解。

由網(wǎng)絡(luò)圖形成的特性，我們知道一個移泊作業(yè)方案的形成，就是尋找一系列從初始狀態(tài)到目標狀態(tài)的決策，而這些決策則對應(yīng)著網(wǎng)絡(luò)圖中的某一條路徑，所以我們可以把移泊作業(yè)問題轉(zhuǎn)化為多階段賦權(quán)單向網(wǎng)絡(luò)模型。問題描述如下：假定有一網(wǎng)絡(luò)，其頂點為移泊作業(yè)的某個狀態(tài)，其S=｛s1，s2，…，sn｝是頂點集，E=｛eij｝是邊集，eij=（si，sj）表示連接頂點si和sj的邊，且稱這兩個頂點與邊 eij相關(guān)聯(lián)。頂點 s0為問題的初始狀態(tài)，頂點st為問題的最終狀態(tài)，每一個決策值對應(yīng)著一條有向邊，從狀態(tài)si到狀態(tài)sj時，所經(jīng)過的每條路徑都是所做的決策，即移泊的動作組合。由狀態(tài)和路徑所構(gòu)成的網(wǎng)絡(luò)圖包含從初始狀態(tài)到最終狀態(tài)的所有路徑，其中也包括了最優(yōu)路徑。這樣，就將求船廠碼頭最佳移泊方案的問題轉(zhuǎn)化為求解決其所對應(yīng)的賦權(quán)網(wǎng)絡(luò)最優(yōu)路問題。移泊作業(yè)的決策過程是一個不可逆過程，具有單向的特征，所以其最優(yōu)途徑就是該網(wǎng)絡(luò)最優(yōu)路徑［4］。

船舶碼頭多階段賦值見圖2。

圖2　船舶碼頭多階段賦值

圖2中要求從出發(fā)地s0到達目的地st，首先，可將圖2劃分為t個階段，然后逆向依次尋求距離最小的最短路徑。第一階段，從st-11到st只有一條路線，同樣從st-21到st-11也只有一條路線。到了第二階段，從st-21到st有st-21-st-11-st，st-22-st-12-st，…，st-2n-st-1n-st共 n條路線，選擇最優(yōu)的一條。同理可知st-22到st之間的最短距離，第三階段也依次繼續(xù)進行下去，這樣就把一個最優(yōu)路徑問題轉(zhuǎn)化為了多段決策問題。求解過程如圖3。

圖3　動態(tài)規(guī)劃求解過程

4　算　例

在t0時刻碼頭原始停泊布置如圖4所示，在t0時刻碼頭共?？?6艘船，（3，4）處為目標泊位，（1，3）處為目標船舶，碼頭泊位為5×6的矩陣，要求將圖中目標船舶移到目標泊位。

圖4　原始泊位布置

用matlab按照上節(jié)求解步驟編寫程序后最優(yōu)移泊路徑如圖5。

圖5　最優(yōu)移泊路徑

按照優(yōu)化計算方法，總的移船艘次為3次。從結(jié)果看，該模型和求解方法有著很好的優(yōu)化計算結(jié)果，與傳統(tǒng)人工制定方案相比，能直觀的提供移泊路線方案，這就避免了一些重復(fù)的動作，節(jié)省了作業(yè)時間，為企業(yè)節(jié)約了成本。

5　總　結(jié)

本文闡述了船廠碼頭移泊作業(yè)的馬爾科夫特性，船舶移泊作業(yè)是一個逐漸演化的過程，具有無后效性，離散性的特征，針對這些特點，提出了碼頭移泊作業(yè)問題的圖與網(wǎng)絡(luò)模型，將移泊問題轉(zhuǎn)化成多階段決策問題，給出尋找最優(yōu)路徑方法，并給出了模型的一般算法思路和流程。最后通過實例的計算分析，證明了本文的研究方法對尋找移泊最佳路徑問題有著很好的指導(dǎo)作用。

［1］陳光亭，裘哲勇.數(shù)學(xué)建模［M］.北京：高等教育出版社，2010：191-197.

［2］司守奎，孫璽菁.數(shù)學(xué)建模算法與應(yīng)用［M］.北京：國防教育出版社，2011：37-39.

［3］王庚，王敏生.現(xiàn)代數(shù)學(xué)建模方法［M］.北京：科學(xué)出版社，2010：4-8.

［4］Jianping Chen，Jiawei Ye.The Graph Model and the Dijkstra Algorithmic of the Ship Shifting and Berthing Operation at the Dockyard［C］.ISOPE-2011，Vol.3：1207-1214.

Optimization Research of Berth Shifting Operation of Ship-repairing Dock

Tang Weiwei1，Yang Kunrong2，Ai Zhixing3
（1.Civil and Transportation Institute，South China University of Technology，Guangzhou Guangdong 510614，China； 2.CSSC Chengxi Shipyard （Guangzhou） Co.，Ltd.，Guangzhou Guangdong 511462，China；3.CSSC Huangpu Wenchong shipbuilding Co.，Ltd.，Guangzhou Guangdong 510715，China）

Ship berth adjustment is an important part of Ship-repairing dock operation.The berth shifting of ship-repairing dock is studied on the basis of dynamic programming and relevant content of graph theory.An introduction is given to markov property of berth shifting system，and the berth shifting problem is transformed into the solving process of the corresponding optimal path of empowerment network.Through the reverse propulsion of network structure，an optimal path problem is eventually converted into the multiple-stage decision problem so as to get the optimal path of the problem at last.The calculation example verifies that the above method can optimize the berth shifting process of ship-repairing dock well.

shifting of ship-repairing dock； markov chain； figure & network model； the optimal path

U673

A

1004-9592（2016）04-0056-04

10.16403/j.cnki.ggjs20160414

2015-05-13

唐偉煒（1983-），女，博士，主要研究方向為船舶與海洋結(jié)構(gòu)物制造。