史　立，管明靜，郭金鑫

(上海海事大學 科學研究院物流研究中心，上海 201306)

0　引　言

在經(jīng)濟全球化的背景下，運輸物流正在快速發(fā)展。集裝箱運輸業(yè)已成為運輸和物流的支柱，集裝箱碼頭在多式聯(lián)運網(wǎng)絡中扮演著不可或缺的角色。特別是隨著過去20年世界貿(mào)易的快速發(fā)展，集裝箱碼頭的服務需求在不斷的增加，這樣就需要更高效率完成作業(yè)，以減少船舶在碼頭的逗留時間，從而獲得與其鄰近港口的競爭優(yōu)勢。這種競爭優(yōu)勢將有助于客戶的增加，從而獲得利潤。隨著過去幾十年里集裝箱化的發(fā)展，對集裝箱港口碼頭的研究問題也應運而生，泊位和岸橋的集成分配是目前港口優(yōu)化領域研究的熱點問題。

國內(nèi)外很多學者對泊位分配問題(berth allocation problem，BAP)和岸橋分配問題(QCAP)進行了研究。ZHANG Canrong等[1]最早嘗試研究BA-CASP(berth allocation，quay crane assignment and scheduling problem)，即在數(shù)學優(yōu)化模型中整合BAP，CAP(quay crane assignment problem)和CSP(quay crane scheduling problem)以確定船舶的最佳停泊時間和位置以及岸橋的數(shù)量和調(diào)度方案，C. BIERWIRTH等[2]對相關論文根據(jù)一些特定屬性進行很好的調(diào)查分類。Y. M. PARK等[3]建立了一個動態(tài)到達的連續(xù)的BACAP數(shù)學模型，提出了將模型分為兩個階段解決方案，在第1階段，確定船舶的靠泊時間、位置及分配給每艘船舶的岸橋數(shù)量，運用拉格朗日松弛問題使用子梯度優(yōu)化技術分解成幾個獨立的子問題；在第2階段，使用動態(tài)規(guī)劃確定分配給每艘船舶1組具體的岸橋。蔣大培等[4]基于偏好泊位的泊位和岸橋聯(lián)合分配問題建立0-1混合整數(shù)規(guī)劃模型，并運用了CPLEX 軟件進行編程求解。HAN Xiaolong等[5]將泊位岸橋調(diào)度問題分為兩個階段，第1個階段，根據(jù)船舶之間的時空關系，建立1個連續(xù)泊位分配模型；第2階段，即岸橋分配階段，用到多目標規(guī)劃，考慮到了岸橋的最小最大覆蓋范圍，同時還考慮了岸橋移動的成本，運用PSO和CPLEX進行求解和比較。

在港口業(yè)務的實踐中，對BAP和QCAP集成優(yōu)化研究上會忽略泊位的水深對限制船舶停泊的限制，因此為了避免船舶擱淺，其停泊位置的水深必須滿足船舶的吃水深度要求。泊位水深通常受現(xiàn)實環(huán)境中潮汐的影響，從而使船舶停泊位置的水深隨時間變化而變化。如果船舶在低水位時到達港口且水深不滿足船舶吃水的情況下，則需要在錨地等待下一個高水位的來臨，那么由潮汐引起的等待將會進一步降低碼頭的生產(chǎn)率。孫少文等[6]考慮到潮水水位變化對靠泊計劃的影響，根據(jù)潮汐的運動規(guī)律，建立了船舶總在港時間最小的離散泊位分配模型。A. KARAM等[7]在假設船舶停泊位置不受船的吃水影響條件下，建立了船舶動態(tài)到達的連續(xù)泊位分配模型。T. QIN等[8]考慮到在泊位分配中，受潮汐的影響水深會隨時間變化，對整數(shù)規(guī)劃(IP)和約束規(guī)劃(CP)兩種模型進行比較。Y. DU等[9]研究了船舶進出港口時，量化了潮汐對集裝箱港口海邊作業(yè)的影響，為了減少燃料消耗和污染物排放，建立了采用虛擬到達策略的泊位分配模型，運用了二階錐規(guī)劃方法。A. SHEIKHOLESLAMI等[10]建立了潮汐海港連續(xù)動態(tài)泊位分配模型，考慮到不同泊位的水深也不同，并使用了遺傳算法結(jié)合模式搜索算法進行求解。D. XU等[11]提出了一種集裝箱碼頭的離散泊位分配模型，其中船舶的泊位分配受水深和潮汐條件的限制。在該模型中，時間窗分為兩個時段，即低水位和高水位，并且這兩個時段中的處理集是不同的。V. H. BARROS等[12]通過引入潮汐時間窗(即高潮時期)來建立和分析泊位分配模型，其中船舶只能在這個時間窗內(nèi)才能被服務。這個模型主要講述的是潮汐散貨港口和海運集裝箱碼頭(MCT)管理。

通過上述關于泊位和岸橋調(diào)度問題的研究可以看出，在泊位分配和岸橋調(diào)度過程中考慮潮汐因素局限在離散泊位。在文中不是將潮汐條件分類為兩個或更多，而是將準確的潮汐數(shù)據(jù)應用在連續(xù)的泊位分配問題。

1　問題描述

集裝箱港口使用大量的資源和設備為進港船舶提供服務。泊位和岸橋是集裝箱碼頭最為稀有和最昂貴的資源，集裝箱港口岸邊操作如圖1，因為要提高這兩種資源的生產(chǎn)力需要大量的投資。 因此，通過規(guī)劃實現(xiàn)這兩種資源的最大利用對于實現(xiàn)整個碼頭總體的最大生產(chǎn)率是至關重要的。

因此出現(xiàn)兩個重要的規(guī)劃問題，即泊位分配問題(BAP)和岸橋分配問題(QCAP)。在泊位分配中，確定在給定的規(guī)劃范圍內(nèi)待服務的每艘船舶在碼頭的停泊時間和?？课恢?。在岸橋分配中，分配一組具體的岸橋來為在港船舶服務。在確定船舶靠泊位置時受很多不同的約束，如沿著岸線的水深、岸橋覆蓋范圍等。

圖1　集裝箱港口岸邊操作示意Fig. 1　Diagram of quayside operation of container port

筆者研究連續(xù)泊位及岸橋集成分配問題，同時考慮隨著時間變化的水深對船舶靠泊計劃的影響，建立了混合整數(shù)規(guī)劃模型，優(yōu)化船舶的?？繒r間、離港時間和所分配的具體岸橋。

圖2　潮汐規(guī)律示意Fig. 2　Diagram of tidal regularity

2　模型建立

基本假設條件為：① 岸橋在服務過程中不能發(fā)生中斷；② 每艘船可分配的岸橋數(shù)量都有一定的范圍；③ 岸線上的任意位置至少被一個岸橋覆蓋；④ 船舶左端船頭為船舶的靠泊位置。

2.1　參數(shù)定義

2.2　決策變量

1)ai表示船舶i的停泊時間；di表示船舶i的離開時間；

2)bi表示船舶i的開始靠泊位置；

3)xikt表示0～1變量，船舶i的左端船頭在t時段停在k位置時等于1，否則等于0；

4)φitρ表示0～1變量，ρ個岸橋在第t時間為船舶i服務時等于1，否則等于0；

5)rqit表示0～1變量，岸橋q在第t時間段服務船舶i時等于1，否則等于0；

6)rit表示0～1變量，在第t時間段有岸橋為船舶i服務時等于1，否則等于0；

7)zij表示0～1變量，船舶i任務結(jié)束后船舶j任務開始時等于1，否則等于0；

8)μij表示0～1變量，船舶i的位置在船舶j的下面時等于1，否則等于0。

2.3　目標函數(shù)及約束條件

目標函數(shù)：

(1)

約束條件：

(2)

(3)

(4)

(t+1)·rit≤di?i∈V，t∈T

(5)

t·rit+M·(1-rit)≥ai?i∈V，t∈T

(6)

(7)

(8)

bi+li≤bj+M(1-μij)?i，j∈V，i≠j

(9)

di≤aj+M(1-zij)?i，j∈V，i≠j

(10)

μij+μji+zij+zji≥1?i，j∈V，i≠j

(11)

(12)

Di·xikt≤bkt?i∈V，k∈L，t∈T

(13)

(14)

rq，it+rqjt≤1+μij?q，q′∈Q且q

i，j∈V，t∈T

(15)

xkit，φitρ，rqit，rit，zij，μij∈{0，1}?i，j∈V，

q∈Q，t∈T，k∈L，ρ=1，2，…，Ri

(16)

上述模型的目標函數(shù)為時間成本及岸橋使用成本最小化，通過式(1)～式(16) 定義目標函數(shù)和約束條件。式(1)表示總目標函數(shù)，最小化船舶延遲到港成本、延遲離港處罰成本、岸橋使用成本；式(2)表示任意時刻分配給船的岸橋數(shù)量不能超過碼頭岸橋總數(shù)；式(3)確保變量φitρ和rit的一致性；式(4)確保船舶服務不能中斷。船舶在碼頭停泊，裝卸操作必須完成才能離開碼頭；式(5)為船舶的某一作業(yè)時間與離港時間關系；式(6)表示船舶到港后才能被服務；式(7)表示某一時刻分配給船舶的岸橋數(shù)量與服務船舶的岸橋數(shù)量的關系；式(8)表示任意時刻一個岸橋最多只能為一艘船服務；式(9)～式(11) 保證船舶在時間和空間上不沖突；式(12)表示服務某一艘船的岸橋數(shù)量范圍；式(13)表示船舶作業(yè)期間停泊位置的水深必須滿足船舶的吃水深度；式(14)表示任意一艘船舶只有一個停泊位置；式(15)表示岸橋之間不能穿越；式(16)表示對決策變量的約束。

3　試驗算例

算例(N=6)即6艘船，原始數(shù)據(jù)見表1。

表1　6艘船的原始數(shù)據(jù)Table 1　Original data of 6 ships

3.1　算例分析

在忽略潮汐影響的條件下，表1計算的結(jié)果整理后如圖3。其中，橫坐標表示時間段，縱坐標表示岸線。不同的矩陣表示不同的船舶，矩陣的長表示船舶占用的岸線長度；矩陣的寬表示船舶作業(yè)時間；矩陣中的數(shù)字表示每個時間段分配給船的岸橋，這個岸橋數(shù)量是隨著時間段而變化的。從圖3也可以看到，進港的船舶基本能保證船舶在最遲離港時間之前離港。在第1～5時間段船1和船2分別都是有3臺岸橋服務，船3在第5時間段進港后使得岸橋資源變得緊張，從而分配給船1和船2的岸橋數(shù)量減少，岸橋資源緊張。到第12時間段船1和船2作業(yè)完成，使得船4能有更多的岸橋可以使用。從到第13時間段開始，船5、船6的到來使得船4所分配的岸橋數(shù)量由3臺減少為2臺。到第20時間段，船4的作業(yè)完成，船5和船6所分配到岸橋資源也隨之增加，由原來的2臺岸橋增加到3臺。從圖3也可以看出，服務船舶的岸橋的數(shù)量也在可行的范圍內(nèi)。這種岸橋的動態(tài)分配使港口有限的岸橋資源更能充分利用，提高港口的運營效率。同時可以看到在船1、船2、船3進港靠泊后，泊位資源也變得緊張，所以船4實際進港的時間延遲了1個時間段，船5實際到港時間延遲2個時間段。

3.2　受潮汐干擾的算例分析

在港口的實際作業(yè)中，潮汐規(guī)律通常會對船舶的靠泊計劃產(chǎn)生影響，考慮到船舶吃水與停泊位置水深的關系，由表1計算的結(jié)果整理后如圖4。

從圖4中可以看出，由于船1、船2、船3、船5的吃水不受潮汐影響，所以這3艘船的靠泊計劃不變；根據(jù)圖2中的潮汐規(guī)律圖可以看出，在第12時間段水深為7.6 m，不滿足船4的8 m的吃水，直到第14時間段船4才能進行靠泊作業(yè)，因此船4需延遲2個時間段，同時岸橋資源也需要重新分配，船3和船5有了更多的可用岸橋；第14時間段的水深也不滿足船6的吃水，船6也需要延遲一個時間段到港。因此在集裝箱碼頭的作業(yè)計劃中，考慮到潮汐因素可以使作業(yè)計劃更符合實際。也可從圖4看出，因為岸橋的移動是在一定范圍內(nèi)，在第12時間段到第14時間段之間，船4受潮汐影響需延遲兩個時間段，因此在第14時間段就沒有船舶進行作業(yè)，為了使碼頭資源得到充分的利用，在空閑時段可以安排不受潮汐影響的小型船舶(如船7、船8)進行作業(yè)。這樣將進一步提高碼頭資源的利用率，降低運作成本，同時使文中的模型更加符合港口的實際情況。

表2　算例懲罰費用Table 2　Penalty costs of case studies

由表2中的懲罰費用所知，船舶在受潮汐因素影響的情況下，船4、船5、船6均沒有在期望到達時間到達，各產(chǎn)生了9、8、5的懲罰費用，同時船舶離港時間及岸橋服務數(shù)量也受到了影響。例如船6應在第21時間段離港，最終在第24時間段延遲離港，在第22、23時間段岸橋數(shù)量由原來分配的3臺減少為2臺，船6總的延誤費用為11.8；且船4、船5的延遲離港也產(chǎn)生一部分懲罰費用。

模型中考慮到連續(xù)泊位可以使泊位資源得到更加充分地利用；岸橋分配過程中考慮到岸橋的覆蓋范圍，同時在潮汐因素的約束下研究泊位岸橋集成分配問題，更符合碼頭的實際情況，可以減少因船舶吃水條件不滿足而產(chǎn)生的等待時間進而減少船舶總的時間，降低運營商的運作成本，充分利用碼頭資源，從而提高客戶的滿意度。

4　結(jié)　語

通過構(gòu)造連續(xù)泊位-岸橋聯(lián)合分配模型，建立了一個混合整數(shù)模型，將連續(xù)型泊位與岸橋分配結(jié)合在一起。在泊位計劃中，考慮船舶進出港受到潮汐的影響，以24 h為一個周期，根據(jù)潮汐規(guī)律在不同的時間段設置了不同水深；在岸橋分配過程中，考慮到岸橋覆蓋范圍對岸橋分配的影響，并設置不同的懲罰系數(shù)，從而達到時間延遲成本及岸橋使用成本最低的優(yōu)化目標，到港船舶的停泊位置與進港離港時間及各船舶的具體岸橋分配也比不考慮潮汐因素更符合碼頭的實際情況。

但是，筆者沒有考慮到岸橋移動對總成本的影響以及一些碼頭在同一時間不同位置水深也不同對泊位分配的影響，從而進一步提高港口的服務水平及碼頭資源的利用率。因此，可以使用其他方法完善連續(xù)泊位和岸橋分配模型。

參考文獻(References)：

[1]ZHANG Canrong，ZHENG Li，ZHANG Zhihai，et al.The allocation of berths and quay cranes by using a sub-gradient optimization technique[J].Computers&IndustrialEngineering，2010，58(1)：40-50.

[2]BIERWIRTH C，MEISEL F，MEISEL F.：A survey of berth allocation and quay crane scheduling problems in container terminals.[J].EuropeanJournalofOperationalResearch，2010，202(3)：615-627.

[3]PARK Y M，KIM K H.A scheduling method for Berth and Quay cranes[J].OrSpectrum，2003，25(1)：1-23.

[4]蔣大培，胡志華，胡少龍.考慮偏好泊位的泊位和岸橋集成分派問題[J].廣西大學學報(自然科學版)，2014(3)：663-672.

JIANG Dapei，HU Zhihua，HU Shaolong.Considered berths and quay berths integrated dispatch issue preference[J].GuangxiUniversity(NaturalScience)，2014(3)：663-672.

[5]HAN Xiaolong.A new continuous berth allocation and quay crane assignment model in container terminal[J].Computers&IndustrialEngineering，2015，89(C)：15-22.

[6]孫少文，楊斌，胡志華.潮汐影響下的港口離散泊位分配問題研究[J].合肥工業(yè)大學學報(自然科學版)，2014，37(4)：486-492.

SUN Shaowen，YANG Bin，HU Zhihua.Research on the Dispatch of Discrete Berths under the Influence of Tide[J].JournalofHefeiUniversityofTechnology(NaturalScience)，2014，37(4)：486-492.

[7]KARAM A，ELTAWIL A B.Functional integration approach for the berth allocation，quay crane assignment and specific quay crane assignment problems[J].Computers&IndustrialEngineering，2016.

[8]QIN T，DU Y，SHA M.Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth[J].TransportationResearchPartE，2016，87：167-185.

[9]DU Y，CHEN Q，LAM J S L，et al.Modeling the impacts of tides and the virtual arrival policy in berth allocation[J].TransportationScience，2015，49(4)：939-956.

[10]SHEIKHOLESLAMI A，ILATI G，KOBARI M.The continuous dynamic berth allocation problem at a marine container terminal with tidal constraints in the access channel[J].InternationalJournalofCivilEngineering，2014，12(3)：344-353.

[11]XU D，LI C L，LEUNG Y T.Berth allocation with time-dependent physical limitations on vessels[J].EuropeanJournalofOperationalResearch，2012，216(1)：47-56.

[12]BARROS V H，COSTA T，SOUZA S，et al.Model and heuristic for berth allocation in tidal bulk ports with stock level constraints[J].Computers&IndustrialEngineering，2011，60(4)：606-613.