史　立，管明靜，郭金鑫

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

0　引　言

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

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

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

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

1　問題描述

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

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

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

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

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

2　模型建立

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

2.1　參數(shù)定義

2.2　決策變量

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

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

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

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

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

6)rit表示0～1變量，在第t時(shí)間段有岸橋?yàn)榇癷服務(wù)時(shí)等于1，否則等于0；

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

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

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

目標(biāo)函數(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)

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

3　試驗(yàn)算例

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

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

3.1　算例分析

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

3.2　受潮汐干擾的算例分析

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

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

表2　算例懲罰費(fèi)用Table 2　Penalty costs of case studies

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

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

4　結(jié)　語

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

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

參考文獻(xiàn)(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].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版)，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è)大學(xué)學(xué)報(bào)(自然科學(xué)版)，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.