0

引　言

集裝箱碼頭自動化包括半自動化和全自動化。一般認為，半自動化碼頭是僅有堆場作業(yè)系統(tǒng)實現(xiàn)自動化；全自動化碼頭是除堆場作業(yè)系統(tǒng)實現(xiàn)自動化外，水平運輸和裝卸船作業(yè)也都實現(xiàn)自動化。1993年，世界上第1個集裝箱自動化碼頭在荷蘭鹿特丹的ECT Delta Sealand正式投產。到目前為止，荷蘭的ECT、Euromax、M II、RWG碼頭，德國的CTA碼頭，美國的LBCT、TraPac碼頭，澳大利亞的Patric碼頭，日本的名古屋碼頭以及我國的廈門遠海、青島和上海洋山已建成了全自動化碼頭。碼頭計算機管理系統(tǒng)（Terminal Operation System，TOS）是碼頭正常運營的基礎和關鍵，自動化集裝箱碼頭的TOS系統(tǒng)在原有TOS系統(tǒng)的基礎上需要重點解決設備之間的實時交互問題，并增加計劃與控制之間的相互協(xié)同功能。

1

自動化碼頭的生產作業(yè)管理系統(tǒng)

目前，國內外的TOS系統(tǒng)，主流的有美國的Navis系統(tǒng)、比利時的COSMOS系統(tǒng)、韓國的TBS系統(tǒng)、上海港的TOPS系統(tǒng)等。其中：Navis公司成立于1988 年，是全球首家提供自動化集裝箱碼頭管理系統(tǒng)的公司，其提供的TOS系統(tǒng)是全球碼頭運營商馬士基集裝箱碼頭公司（APM Terminals）、迪拜環(huán)球港務集團（DP World）、美國總統(tǒng)輪船公司（APL）和菲律賓國際貨柜碼頭服務公司（ICTSI）的首選解決方案。上海港在充分吸收國內外先進經驗的基礎之上，研發(fā)基于自動化集裝箱碼頭的TOS系統(tǒng)，通過橋機作業(yè)計劃、實時配載以及自動發(fā)箱等智能化模塊產生實時作業(yè)指令，并通過實際執(zhí)行結果進行指令的動態(tài)調整。該系統(tǒng)已經在上海港洋山自動化碼頭投入使用。

TOS系統(tǒng)基本上都是由客戶端、服務端和后臺中心數據庫等組成的，并主要以碼頭為單位進行部署。服務端根據碼頭業(yè)務的需要，在自動化集裝箱碼頭中基本都是采用集群的方式進行部署的，根據業(yè)務量和交互量大小來決定集群的規(guī)模。自動化碼頭TOS系統(tǒng)結構見圖1。

在TOS系統(tǒng)中，涉及的優(yōu)化問題多集中在泊位策劃、作業(yè)資源策劃、自動配載和堆場策劃等模塊中。

2

生產作業(yè)管理系統(tǒng)的優(yōu)化問題

2.1　泊位策劃

作為貨物運輸進入港口的第1步，泊位分配是重要環(huán)節(jié)。合理的泊位分配可以提高集裝箱碼頭的生產效率、減少船舶在港時間，從而提高集裝箱碼頭競爭力。在集裝箱船舶到達港口之前為其安排?？奎c、靠離泊時間和作業(yè)時間，直接體現(xiàn)碼頭收納集裝箱船的能力。因此，泊位策劃的質量直接影響到整個碼頭效率。同時，作為后續(xù)裝卸機械資源安排、作業(yè)計劃和自動配載的先決條件，泊位策劃是自動化集裝箱碼頭智能化系統(tǒng)中的“引領者”。

該問題的一般描述為：港口擁有m個碼頭，每個碼頭擁有不同的海岸線、吃水深度等，船舶靠泊受運送貨物種類、船長、吃水、優(yōu)先級和碼頭當前?？壳闆r等綜合因素的限制，泊位策劃是在已知船舶和各碼頭信息的基礎上，對未來一段時間內每艘船舶靠泊進行規(guī)劃，使港口海岸線整體的利用率盡可能大。若m=1，則為單碼頭泊位策劃問題；否則，則為港口集團級碼頭泊位策劃問題。對于港口集團級碼頭泊位策劃問題，又往往涉及公共航道的管理問題，可稱為帶有航道約束的多碼頭泊位策劃。港口集團級碼頭泊位策劃示意圖見圖2。

國內外學者針對泊位分配與裝卸橋調度問題展開大量的研究，開發(fā)一系列模型和算法，主要分為2類：一類是離散泊位分配模型，如Nishimura等建立離散泊位分配模型，設計基于遺傳算法的求解方法；Imai等在模型中考慮不同船舶營運人不同停泊優(yōu)先權，設計基于遺傳算法的啟發(fā)式算法；Kim等利用模擬退火算法求解離散泊位分配問題。另一類是連續(xù)泊位分配模型，將碼頭岸線看作連續(xù)的整體，根據船舶長度依次停泊，Wang等將泊位問題視為多階段決策問題，設計基于隨機束搜索算法的求解方法。在港口作業(yè)這種常常出現(xiàn)各種干擾事件（如惡劣天氣、設備故障等）的環(huán)境下，常常會打亂原有的調度計劃，降低集裝箱碼頭的作業(yè)效率與服務水平。因此，需要對泊位計劃進行調整，以減少干擾事件對系統(tǒng)的負面影響。Tian等和曾慶成等建立泊位分配與裝卸橋調度干預管理模型和算法。本文將進一步介紹和研究港口集團級碼頭泊位策劃問題的模型和算法。

2.2　橋機工作計劃

橋式起重機（以下簡稱“橋機”）作為港口裝卸貨物的主要工具，其工作計劃的合理制定對提高裝卸效率起著重要作用。橋機裝卸示意圖見圖3。船舶靠泊后，由橋機進行集裝箱的裝卸操作，橋機在工作時需要滿足諸多約束：

• 多個橋機在同一船舶進行裝卸作業(yè)時，需在同一水平軌道中作業(yè)，橋機可雙向移動但不同橋機不可交叉移動。

• 任意時段，1臺橋機最多只能停放在1個貝位，1個貝位最多只能停放1臺橋機。

• 相鄰橋機同時工作時需要保持一定的安全距離，通常為1個貝位的距離。

橋機工作計劃就是安排可調用橋機盡快完成集裝箱裝卸作業(yè)，在上述約束條件之下，將完成單船裝卸作業(yè)的工作時間最小化。橋機工作計劃問題是TOS系統(tǒng)的核心問題，得到國內外學界和產業(yè)界的廣泛關注。Zhu等[8]以橋機之間不可交叉移動為約束，以橋機工作時間最小化為優(yōu)化目標，利用分支定界和模擬退火算法分別對模型進行求解，最終得到橋機在不同貝位的工作順序；Daganzo[9]研究橋機在1個貝位上工作時可被打斷的情況，與以往的研究不同，1個貝位上的工作可由多個橋機共同完成，但作者并未考慮橋機不能交叉移動的約束；Kim等將船貝看作是船艙和甲板的集合，考慮橋機移動時間、不可交叉、安全操作距離等約束建立數學規(guī)劃模型，并設計分支定界算法和貪婪隨機自適應搜索算法；Moccia等在Kim等的基礎上，提出更加嚴格的數學模型，并提出分支切割算法；Sammarra等在此基礎上又提出一種禁忌搜索方法，通過降低解的質量，大幅縮短求解時間；陸書翔等建立該問題的多目標工作計劃數學模型和基于完工時間下界的近似算法。

2.3　自動配載

自動配載是指在需要裝船的集裝箱及其在堆場的具體位置已知的前提下，按照船公司的預配要求給堆場內每個需要裝船的集裝箱安排對應的船舶位置，使總裝卸效益最大。自動配載的結果需要滿足預配船圖的所有規(guī)則，給出所有需要配載的出口集裝箱對應船艙上的位置，在此基礎上還需要給出每個集裝箱的裝載順序。因此，自動配載的任務不僅需要考慮集裝箱屬性對于其最終裝載位置的影響，還需要考慮出口集裝箱的堆場分布和出箱點對于裝配順序的影響。由于自動配載的目標就是在保證船公司配載規(guī)則的條件下使碼頭作業(yè)效率最高，因此必須考慮船公司的配載要求。船公司的配載要求中只指定船艙上的列位位置的集裝箱的屬性（特殊箱、卸貨港、高平箱和箱尺寸等），所以該問題可以抽象成如下集合匹配問題：列位位置集合S={s1，s2，…，sn}，預裝集裝箱集合T={t1，t2，…，tn}。每個集裝箱的屬性（重量、尺寸、卸貨港等）已知，每個列位位置規(guī)定所放集裝箱滿足的屬性已知。需要建立1個映射f：S→T在滿足每個位置對應的箱子屬性要求的前提下，使碼頭裝卸效率最高（橋機效率高、翻箱量少、堆場設備無謂移動少等）。

Wilson等對自動配載問題提出兩階段分塊求解策略；Kang等在此基礎上進行了進一步研究；張維英等采用基于二叉搜索樹的啟發(fā)式裝箱算法求解；Delgado等給出了一種快速的近似算法。

3

港口泊位策劃模型和算法

考慮到帶有航道約束的多碼頭泊位策劃問題，采用連續(xù)型泊位分配方法，在優(yōu)化泊位方案的同時考慮單向航道進出的問題。模型假設如下：

• 船只駛入航道后不允許等待，立刻停泊進行作業(yè)。

• 船只間的安全距離已包含在船只長度中。

• 船只的裝卸貨時間可根據船只的貨物重量Wi、每個橋機的工作效率E、船只的長度li（根據船舶長度來預測用多少橋機）這3個變量來預估出。

• 船舶?？繀^(qū)域不限制船舶的停放數量。

本文中，將泊位策劃問題轉化為二維裝箱問題（Two-Dimensional BinPacking Problem，2DBPP）。經典的二維裝箱問題為：給定1定數量的小矩形，給定1個大矩形，將所有的小矩形裝入大矩形中，使得裝入高度最低。二維裝箱問題示意圖見圖4。

將二維裝箱問題與泊位策劃模型聯(lián)系起來，泊位分配與二維裝箱問題之間的聯(lián)系見圖5。圖中左邊的船舶1至船舶4對應右側中的矩形。也就是說，1個矩形就代表了1艘船只的泊位分配。因此，要求右圖所有的矩形不重合，并按一定約束裝入該“大矩形”，使總作業(yè)時間盡可能地少。

3.1　模型參數、目標和約束條件

方案目標為最后一艘船只離開港口的時間點減去第一艘船只到港的時間點的間隔時間最小化，該時間差代表所有船只從開始到結束作業(yè)所用時間的總和。因此，該模型的目標函數為

模型約束條件為

式中：i∈N（i=1，...，n）為n艘船只集合；L為碼頭岸線長；T為規(guī)劃時間；li為每艘船的長度，包含安全距離；di為每艘船的吃水深度；ai為每艘船預計到達的時間；Hi為每艘船作業(yè)時間；tin為駛入航道所需時間；tout為駛出航道所需時間；Vi為每艘船的速度；Wi為每艘船的貨物量；depth（bi）為?？课恢胋i處能承受的最深出水深度；bi為船舶?？课恢?；tiin為船舶駛入航道的時間點；tistart為船舶開始裝卸作業(yè)的時間點；tiend為船舶結束作業(yè)的時間點；tiout為船舶駛出航道的時間點，xij表示若船舶i完全在j的左方，則為1，否則為0；yij表示若船舶i完全在j的下方，則為1，否則為0。

約束（2）~（6）保證船只作業(yè)計劃在二維圖上不重疊，約束（7）保證航道單向的特點，約束（8）保證?？课恢迷诎毒€范圍內，約束（9）保證駛出時刻一定在結束作業(yè)時刻之后，約束（10）保證駛入航道時間一定在到港時間之后，約束（11）保證作業(yè)時間一定在規(guī)劃時間之內，約束（12）保證船只?？康奈恢梅洗怀运疃取ｏ@然，若遇到多個碼頭的情況，只需將L分為多個Li，然后對bi進行約束即可。

3.2　模型求解

MATLAB中Intlinprog進行整數線性規(guī)劃編程。在實驗數據的設計上，一共模擬23艘船只，這些船只需要分別?？吭诟劭诘?個碼頭，在5 d的泊位分配計劃周期內預計到達的船舶信息見表1，其中包含船只預計到達時間、船舶的裝載量以及船長。

假設# 1碼頭岸線為0~800 m，# 2碼頭岸線為800~1 800 m，#3碼頭岸線為1 800~ 2 500 m，假設每個碼頭裝卸效率為150自然箱/h，碼頭泊位水深都能滿足船只吃水線要求。在此基礎上運行程序240 s，得到泊位分配計劃，實驗1泊位策劃結果見圖6。其中，左側3列、中間3列、右側2列方框分別表示只能?？? 1、# 2、# 3碼頭。方框中，第1個數字代表第i艘船，第2個數字代表船只到達時間，第3個數字代表在?？繀^(qū)域等待時間，需要盡量讓船只在完成手續(xù)的前提下盡快作業(yè)，因此等待時間越短越好。

在完成泊位計劃后，該情況下的航道占有情況也相應而出。

最后得到23艘船在港作業(yè)總時間為84.5h。試驗1每艘船只的具體計劃信息見表2。表2的每一列將船只的具體?？课恢谩⒕唧w進出港口的時間點、作業(yè)時間、等待時常都相應地表示出來，在泊位策劃時可將此表作為參考來進行船只的排位，并進行單向航道的具體規(guī)劃。由航道規(guī)劃可知，航道進出的時間就整個5 d的規(guī)劃長度來說較為離散。因此，在實際運用中，可以人為地對航道進出時間進行調試，而不會影響到整體的規(guī)劃。由圖6可以看出，二維圖中的空缺處較少，可知每個碼頭的碼頭利用率較高。船只的長度有400 m量級的大船，也有200 m量級的小船，總體符合港口實際情況。

考慮到部分船舶可以?？咳我獯a頭。因此,在原來數據基礎上，新增4艘可以?？咳我獯a頭的船舶，新增船舶信息見表3，其他參數不變，重新運行程序，經過1 400 s的計算，試驗2泊位分配結果見圖8，其中最優(yōu)在港時間為90.58 h。