岸橋移動(dòng)約束的連續(xù)泊位和岸橋集成調(diào)度

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

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

0 引 言

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

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

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

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

1 模型建立

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

模型采用連續(xù)型泊位分配，用“泊位-時(shí)間”[11]表示泊位分配方案；分配給船舶的岸橋數(shù)有最小值和最大值約束；服務(wù)某一船舶的岸橋可以在該作業(yè)未完成之前退出而轉(zhuǎn)向其他相鄰船舶的作業(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 泊位-時(shí)間時(shí)空?qǐng)D示例

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

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

2 算例與分析

表1 船舶參數(shù)

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

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

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

表2模型M1和M2的成本明細(xì)對(duì)比

成本M1M2f1900900f254005400f300f4-30790f630037090

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

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

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

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

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

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

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

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

表3 有約束與無約束條件的成本對(duì)比

3 結(jié)束語

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

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

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

[10] 董良才, 丁以中, 宓為建. 基于時(shí)間窗的集裝箱裝卸橋調(diào)度[J]. 上海海事大學(xué)學(xué)報(bào), 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.