修船廠移泊作業優化方法研究

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

?

修船廠移泊作業優化方法研究

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

船舶泊位調度是修船廠作業的重要組成部分，本文基于動態規劃和圖論的相關理論，對修船廠碼頭移泊調度問題進行了研究，闡述了移泊系統的馬爾科夫特性，并將船廠碼頭移泊問題就轉化為求解其所對應的賦權網絡最優路問題，通過對問題網絡結構圖的逆向推進，把一個最優路徑問題轉化為多段決策問題，最終獲得該問題的最優路徑。最后用算例證明了本文研究的方法對于處理修船碼頭移泊問題，有著非常好的尋優性。

修船廠移泊調度；馬爾科夫鏈；圖與網絡模型；最優路徑

引　言

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

依靠調度人員經驗來管理的船舶調度系統在實際操作時，由于現場的局限性，計劃表中的任務有時無法完成，并現場會有些突發狀況使方案要隨時更改，這就加大了工人工作量，降低了工作效率。而且由于方案邊做邊落實，未能直觀的在停靠船舶數量以及多樣性不斷增加的情況下，難免會有重復工作的現象。

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

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

1　移泊問題描述

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

圖1　碼頭泊位布置

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

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

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

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

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

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

3　船舶移泊調度問題的圖與網絡模型

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

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

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

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

圖2　船舶碼頭多階段賦值

圖2中要求從出發地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條路線，選擇最優的一條。同理可知st-22到st之間的最短距離，第三階段也依次繼續進行下去，這樣就把一個最優路徑問題轉化為了多段決策問題。求解過程如圖3。

圖3　動態規劃求解過程

4　算　例

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

圖4　原始泊位布置

用matlab按照上節求解步驟編寫程序后最優移泊路徑如圖5。

圖5　最優移泊路徑

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

5　總　結

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

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

［2］司守奎，孫璽菁.數學建模算法與應用［M］.北京：國防教育出版社，2011：37-39.

［3］王庚，王敏生.現代數學建模方法［M］.北京：科學出版社，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-），女，博士，主要研究方向為船舶與海洋結構物制造。