岸橋移動約束的連續泊位和岸橋集成調度

杜衛華， 黃有方， 楊斌， 孫瑋珊

(上海海事大學 科學研究院，上海 201306)

0 引 言

泊位和岸橋是集裝箱碼頭的兩種緊缺資源，泊位分配問題(Berth Allocation Problem，BAP)和岸橋分配問題(Quay Crane Assignment Problem，QCAP)是集裝箱碼頭運作優化領域的基本問題和熱點問題.[1-3]部分學者將泊位分配和岸橋分配作為兩個獨立階段進行研究.泊位分配中，首先根據船舶裝卸箱量[4]、船舶靠泊位置[5-6]或平均裝卸效率[7]等估算船舶作業時間，通過優化獲得到港船舶的靠泊位置、靠泊時間及離港時間，且在分析時考慮泊位分配的性能指標，如船舶在港時間和碼頭運作成本的最小化，提高船舶裝卸效率[8-9]等.岸橋分配的目標是確定服務每艘船舶的岸橋數和為船舶作業的岸橋集合.[10]因船舶作業時間與為其所分配的岸橋數直接相關，越來越多的學者開始將兩個問題集成起來考慮，即根據船舶靠泊順序、位置和可分配給船舶的岸橋數，通過靠泊計劃和岸橋移動規則確定船舶作業開始時間和離港時間，最后得到泊位和岸橋分配方案.本文在集成調度方法的基礎上給船舶最小最大岸橋分配數和限制岸橋頻繁移動的約束，以達到減少岸橋移動次數和提高岸橋作業效率的目的.

泊位分配模型主要分兩類：離散型泊位分配模型和連續型泊位分配模型.離散型泊位分配模型是把港口碼頭分割成幾個小泊位的集合.NISHIMURA等[11]利用遺傳算法求解離散泊位分配模型;IMAI等[12]在模型中給船舶設定不同的停泊優先順序，設計啟發式算法求解；KIM等[13]利用模擬退火算法求解離散泊位分配問題.連續型泊位分配模型將碼頭岸線看作連續的整體，按照船舶的長度依次進行停泊.IMAI等[14]利用啟發式算法求解連續泊位分配模型；WANG等[15]將泊位分配問題看作多階段決策問題，用隨機束搜索算法求解.

關于岸橋調度模型的研究主要有：DAGANZO[16]建立使船舶延誤成本最小的岸橋調度混合整數規劃模型；KIM等[17]對單艘船舶作業的岸橋調度問題進行研究，分別采用分枝定界法和貪婪隨機適應性搜索算法對模型進行求解;LEE等[18]建立岸橋調度整數規劃模型優化岸橋作業的艙位順序;TAVAKKOLI-MOGHADDAM等[19]建立岸橋配置與路徑優化的混合整數規劃模型，設計遺傳算法求解;GOODCHILD等[20]建立岸橋雙循環模型，減少岸橋空駛，提高岸橋作業效率.

事實上，泊位分配與岸橋調度是相互影響的，船舶靠泊作業時長基本上由所分配給它的岸橋數決定，所以泊位分配計劃中要充分考慮岸橋的分配.同時，在岸橋作業過程中，也要依據泊位分配計劃保證船舶按時離港.因此，對泊位和岸橋集成調度的研究越來越多:PARK等[21]建立同時優化船舶停泊位置、停泊時間及每艘船舶岸橋配置數的混合整數規劃模型;IMAI等[22]采用離散泊位分配方法，建立同時優化泊位分配和岸橋調度的優化模型;LIANG等[23]建立泊位分配-岸橋調度模型，并加入岸橋配置數量對岸橋作業效率影響的約束.

1 模型建立

在IMAI等[14]和LIANG等[23]的基礎上，建立泊位和岸橋集成調度混合整數規劃模型，優化船舶的停泊位置、停靠時間、所分配的岸橋數和岸橋移動次數，以達到船舶延誤成本最小和減少岸橋移動成本的目的.

模型采用連續型泊位分配，用“泊位-時間”[11]表示泊位分配方案；分配給船舶的岸橋數有最小值和最大值約束；服務某一船舶的岸橋可以在該作業未完成之前退出而轉向其他相鄰船舶的作業.

1.1 集合與參數

1.2 決策變量

1.3 模型建立與優化

首先，通過式(1)～(19)建立泊位和岸橋集成分配模型(M1):

(1)

s.t. ?i,m∈S,j∈N

xi+li≤L

(2)

yi≥ei

(3)

Wi≥yi+1

(4)

xi+li≤xm+L(1-Zi,m)，i≠m

(5)

Wi≤ym+M(1-Xi,m)，i≠m

(6)

1≤Zi,m+Zm,i+Xi,m+Xm,i≤2，

i

(7)

Wi≥Vi,j(j+1)

(8)

∑iYi,j≤c

(9)

∑jYi,j≥gi

(10)

Vi,j≤Yi,j

(11)

Yi,j≤MVi,j

(12)

∑1≤j≤i*Yi,j=0，

?i*∈N,1≤i*≤ei

(13)

Yi,j+M(1-Vi,j)≥pi

(14)

Yi,j≤ni

(15)

xi≥0

(16)

Zi,m,Xi,m∈{0,1}，i≠m

(17)

Vi,j∈{0,1}

(18)

(Wi-di)+=max(Wi-di,0)

(19)

圖1 泊位-時間時空圖示例

在建立的泊位岸橋集成調度模型(M1)中未對岸橋的移動加以限制，導致一些船舶靠泊作業時岸橋移動過于頻繁，甚至出現作業暫停(即開始作業后的某時間段內分配給船舶的岸橋數為0).雖然這樣可以最大限度地利用已有岸橋資源，加快整個碼頭作業，但是岸橋頻繁移動會導致岸橋使用效率降低.為避免這種現象，在M1基礎上加入限制岸橋頻繁移動的約束條件，同時考慮由于岸橋頻繁移動引起的效率下降的成本，建立基于岸橋移動約束的泊位和岸橋集成調度模型(M2),其目標函數及式(1)～(19).

式(20)為以偏離偏好位置靠泊成本f1,延遲離港處罰成本f2,等待泊位時間處罰成本f3及岸橋移動成本f4最小定義的港口運營成本目標函數；式(21)和(22)表示通過控制Wi,j*的值提高岸橋使用率.

2 算例與分析

表1 船舶參數

根據表1中數據，運用Cplex軟件分別求解模型M1和M2，得到這兩個模型在每個時間段的岸橋使用數量,見圖2；表2為分別采用這兩個模型所得到的最優解中的成本，其中f為總成本.

在港口碼頭，船舶上的岸橋作業時間基本是固定的，一艘船舶作業時間只與作業的岸橋數有關.從圖2可以看出,除在第8,15,24,34,35,39,40個時間段內岸橋使用數不一致外，其他時間段的岸橋使用數都是一致的.這說明這兩個模型的岸橋使用數在各時間段是基本一致的，岸橋總的作業時間基本沒有變化，對作業效率沒有太大影響，由此可知兩個模型中岸橋作業時間和作業效率在整個港口作業過程中沒有太大區別.另外，由表2列出的成本明細可知，在兩個模型計算出的最優解中f1,f2和f3相同，不同的是f4，這說明新模型在加入限制岸橋頻繁移動條件后，并沒有增加不考慮岸橋移動模型的成本.

圖2 模型M1和M2在各時間段內的岸橋使用數對比

表2模型M1和M2的成本明細對比

成本M1M2f1900900f254005400f300f4-30790f630037090

圖3 優化前岸橋移動次數示例

圖4 優化后岸橋移動次數示例

在岸橋作業時，移動過于頻繁會使其使用效率大大降低，岸橋調度也會更加繁瑣和復雜.岸橋移動分為軌道式和輪胎式，其移動路線基本固定或變化非常小，岸橋移動過于頻繁會極大地增強岸橋之間的相互干擾，增加管理成本.當干擾較大時往往會帶來更多的人工成本和其他管理成本，同時增加船舶靠泊成本.如圖3所示，服務船舶1的岸橋最初是6個岸橋，后變為2個、5個、3個和2個，導致岸橋要離開船舶1，這就涉及岸橋的頻繁移動.假設服務船舶k的岸橋因作業而移動的總次數為Qk(第一次和最后一次岸橋移動不計算在內)，以圖3中船舶1,2,3為例，Q1=|2-6|+|5-2|+|3-5|+|2-3|=10，同理Q2=1，Q3=3.

在有預見性的情況下，可以通過模型M2優化后，達到類似圖4的調度策略，在不增加運營成本的前提下極大地減少岸橋移動次數和岸橋利用率.此時Q1=1，Q2=1，Q3=0.

對Cplex軟件得出的數據進行進一步整理計算可得，模型M1中所有岸橋移動總次數為34次，而在模型M2中所有岸橋移動總次數為19次.由此可見，加入限制岸橋頻繁移動約束條件能大大降低岸橋移動次數，提高岸橋使用效率，降低岸橋調度難度并簡化岸橋移動計劃，從某種程度上會減少岸橋移動中出現混亂或其他干擾因素的機會，避免多船舶出現時大幅度岸橋調度或沒有岸橋為船舶服務的現象.在算例中，模型M1中出現在船舶連續的時間段內岸橋變化為4→1→4，移動次數為6次，變化幅度很大，甚至出現5→0→5，移動次數為10次，這表示在中間那一時刻沒有岸橋為船舶服務，經過對模型優化，加入限制岸橋頻繁移動條件，相關船舶岸橋調度變為4→4→1，5→5→5，岸橋移動次數分別為3次和0次，減少岸橋移動次數，使得調度更加合理.為充分說明加入限制岸橋頻繁移動約束的合理性與正確性，分別計算5艘船、10艘船、15艘船、20艘船在兩個模型中的結果，見圖5.從圖中可以明顯看出，當船舶數量大于5時，M2模型中岸橋移動次數明顯減少，4種情況下移動次數分別減少0，44.1%，46.2%和47.4%.因此可以合理預見當靠泊船舶數量越多時，M2模型相對于M1模型的優越性會越明顯，減少岸橋頻繁移動的次數會越多.

圖5 采用模型M1和M2岸橋移動次數對比

對不同的船舶數量所得的岸橋調度計劃中，加入限制岸橋頻繁移動約束后，岸橋移動次數一直都相對較小，并且f1，f2和f3在兩個模型中的值沒有變化.這充分說明加入限制岸橋頻繁移動約束的新模型使得岸橋移動次數更少，岸橋利用率更高，岸橋調度更為合理，而且隨著船舶數量增加，限制岸橋頻繁移動效果顯著.

在成本方面，如果不考慮模型M2中的約束條件(21)和(22)，即考慮岸橋移動但對岸橋的移動不加以限制，會增加船舶在港時因岸橋的頻繁移動帶來的額外成本，甚至可能影響到船舶到港后的靠泊和船舶到港、離港時間變化，造成f1，f2和f3的增加.在模型M2中去除約束條件(21)和(22)后分別對5艘船、10艘船、15艘船、20艘船的靠泊計劃進行計算，其結果與有約束條件的結果的對比見表3.

表3 有約束與無約束條件的成本對比

3 結束語

泊位岸橋集成調度是一個同時處理合理泊位分配和岸橋調度的多目標任務，岸橋的作業效率和岸橋利用率是決定岸橋對船舶服務時間的兩個重要因素.針對連續的泊位分配和岸橋調度的動態協調問題，在最大限度利用已有岸橋資源加快整個港口碼頭作業的同時，減少岸橋的頻繁移動以提高岸橋使用效率.本文在研究泊位和岸橋集成調度時以限制岸橋頻繁移動為約束，建立以船舶總在港懲罰成本最小為目標函數的混合整數規劃模型，并通過試驗算例驗證其合理性與正確性.算例分析表明,本文提出的方法可以：(1)在船舶靠泊規模大于5艘時提高岸橋實際使用效率40%以上；(2)減少當多艘船出現時因岸橋頻繁移動造成的岸橋之間的相互干擾；(3)防止出現在船舶未裝卸完之前沒有岸橋為其服務的情況；(4)減少考慮岸橋移動但未限制岸橋頻繁移動而帶來的額外成本；(5)提高港口碼頭對岸橋和船舶的管理效率.本文雖然考慮岸橋頻繁移動帶來的代價，但對該代價并沒有提出具體的計算方法，同時也沒有考慮這個因素與岸橋作業的其他因素之間的耦合關系.通過與港口合作，了解岸橋移動的規律和岸橋移動產生的成本，能夠使這個模型更接近集裝箱碼頭的實際情況，具有更強的實用性.

參考文獻：

[1] BIERWIRTH C, MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminal[J]. Eur J Operational Res, 2010, 202(3): 615-627.

[2] STEENKEN D, VOβ S, STAHLBOCK R. Container terminal operation and operations research: a classification and literature review[J]. OR Spectrum, 2004, 26(1): 3-49.

[3] STAHLBOCK R, VOβ S. Operations research at container terminals: a literature update[J]. OR Spectrum, 2008, 30(1): 1-52.

[4] GUAN Y, CHEUNG R K. The berth allocation problem: models and solution methods[J]. OR Spectrum, 2004, 26(1): 75-92.

[5] AKIO I, ETSUKO N, MASAHIRO H,etal. Berth allocation at indented berths for mega-container vessels[J]. Eur J Operational Res, 2007,179(2): 579-593.

[6] IMAI A, NISHIMURA E, PAPADIMITRIOU S. Berthing ships at a multi-user container terminal with a limited quay capacity[J]. Transportation Res Part E, 2008, 44(1):136-151.

[7] CORDEAU J F, LAPORTE G, LEGATO P,etal. Models and tabu search heuristics for the berth allocation problem[J]. Transportation Sci, 2005, 39(4): 526-538.

[8] 何軍良, 宓為建, 謝塵, 等. 基于分布式混合遺傳算法的動態泊位分配策略與仿真[J]. 上海海事大學學報, 2008, 29(2): 52-57.

[9] 樂美龍, 陳雷雷, 黃有方. 集裝箱港口動態泊位指派仿真優化[J]. 上海海事大學學報, 2013, 34(1): 23-27.

[10] 董良才, 丁以中, 宓為建. 基于時間窗的集裝箱裝卸橋調度[J]. 上海海事大學學報, 2011, 32(1): 1-7.

[11] NISHIMURA E, IMAI A, STRATOS P. Berth allocation planning in the public berth system by genetic algorithms[J]. Eur J Operational Res, 2001, 131(2): 282-292.

[12] IMAI A, NISHIMURA R, STRATOS P. Berth allocation with service priority[J]. Transportation Res Part B, 2003, 37(5): 437-357.

[13] KIM K H, MOON K C. Berth scheduling by simulated annealing[J]. Transportation Res Part B, 2003, 37(6): 541-560.

[14] IMAI A, SUM X, NISHIMURA E,etal. Berth allocation in a container port: using a continuous location space approach[J]. Transportation Res Part B, 2005, 39(3): 179-221.

[15] WANG F, LIM A. A stochastic beam search for the berth allocation problem[J]. Decision Support Systems, 2007, 42(4): 2186-2196.

[16] DAGANZO C F. The crane scheduling problem[J]. Transportation Res Part B, 1989, 23(3): 159-175.

[17] KIM K H, PARK Y M. A crane scheduling method for port container terminals[J]. Eur J Operational Res, 2004, 156(3): 752-768.

[18] LEE D H, WANG H Q, MIAO L. Quay crane scheduling with non-interference constraints in port container terminals[J]. Transportation Res Part E, 2008, 44(1): 124-135.

[19] TAVAKKOLI-MOGHADDAM R, MAKUI A, SALAHI S,etal. An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports[J]. Computers & Ind Eng, 2009, 56(1): 241-248.

[20] GOODCHILD A V, DAGANZO C F. Crane double cycling in container ports: planning methods and evaluation[J]. Transportation Res Part B, 2007, 41(8): 875-891.

[21] PARK Y M, KIM K H. A scheduling method for berth and quay cranes[J]. OR Spectrum, 2003, 25(1): 1-23.

[22] IMAI A, CHEN H C, NISHIMURA E,etal. The simultaneous berth and quay crane allocation problem[J]. Transportation Res Part E: Logistics Transportation Rev, 2008, 44(5): 900-920.

[23] LIANG C, HUANG Y, YANG Y. A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J]. Computers & Ind Eng, 2009, 56(3): 1021-1028.