杜衛(wèi)華， 黃有方， 楊斌， 孫瑋珊

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

0 引 言

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

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

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

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

1 模型建立

在IMAI等[14]和LIANG等[23]的基礎上，建立泊位和岸橋集成調(diào)度混合整數(shù)規(guī)劃模型，優(yōu)化船舶的停泊位置、?？繒r間、所分配的岸橋數(shù)和岸橋移動次數(shù)，以達到船舶延誤成本最小和減少岸橋移動成本的目的.

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

1.1 集合與參數(shù)

1.2 決策變量

1.3 模型建立與優(yōu)化

首先，通過式(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 泊位-時間時空圖示例

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

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

2 算例與分析

表1 船舶參數(shù)

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

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

圖2 模型M1和M2在各時間段內(nèi)的岸橋使用數(shù)對比

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

成本M1M2f1900900f254005400f300f4-30790f630037090

圖3 優(yōu)化前岸橋移動次數(shù)示例

圖4 優(yōu)化后岸橋移動次數(shù)示例

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

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

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

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

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

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

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

3 結束語

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

參考文獻：

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

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

[10] 董良才, 丁以中, 宓為建. 基于時間窗的集裝箱裝卸橋調(diào)度[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.