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

?

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

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

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

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

引　言

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

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

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

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

1　移泊問題描述

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

圖1　碼頭泊位布置

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

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

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

馬爾科夫過(guò)程一種典型的隨機(jī)過(guò)程［1］。通過(guò)對(duì)不同狀態(tài)的初始概率以及狀態(tài)之間的轉(zhuǎn)移概率的研究，來(lái)確定狀態(tài)的變化趨勢(shì)，從而達(dá)到對(duì)未來(lái)進(jìn)行預(yù)測(cè)的目的。馬爾科夫鏈?zhǔn)侵笗r(shí)間和狀態(tài)參數(shù)都是離散的馬爾科夫過(guò)程，是最簡(jiǎn)單的馬爾科夫過(guò)程。每個(gè)滿足離散性、隨機(jī)性、無(wú)后效性3個(gè)特點(diǎn)的系統(tǒng)，均可用馬爾科夫鏈研究其過(guò)程，并預(yù)測(cè)未來(lái)。

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

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

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

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

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

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

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

圖2　船舶碼頭多階段賦值

圖2中要求從出發(fā)地s0到達(dá)目的地st，首先，可將圖2劃分為t個(gè)階段，然后逆向依次尋求距離最小的最短路徑。第一階段，從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ù)進(jìn)行下去，這樣就把一個(gè)最優(yōu)路徑問題轉(zhuǎn)化為了多段決策問題。求解過(guò)程如圖3。

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

4　算　例

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

圖4　原始泊位布置

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

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

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

5　總　結(jié)

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

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

［2］司守奎，孫璽菁.數(shù)學(xué)建模算法與應(yīng)用［M］.北京：國(guó)防教育出版社，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-），女，博士，主要研究方向?yàn)榇芭c海洋結(jié)構(gòu)物制造。