分布式?jīng)Q策下的集裝箱碼頭泊位分配研究

張恒 全雄文 徐亞 陳增強(qiáng)

[摘要]為減少船舶廢氣排放和優(yōu)化集裝箱碼頭資源配置，建立了分布式?jīng)Q策環(huán)境下的泊位和岸橋聯(lián)合調(diào)度模型，將船舶和碼頭看作相互獨(dú)立的決策主體，船舶優(yōu)化航速及抵港時刻，碼頭則優(yōu)化自身泊位及岸橋分配。采用多回合組合拍賣方法，將泊位服務(wù)時段看作特殊商品，港航雙方就泊位分配反復(fù)協(xié)商達(dá)成一致，相比于以碼頭作為集中決策者的集中式?jīng)Q策方案更易于被船舶方接受。數(shù)值實(shí)驗(yàn)表明，分布式?jīng)Q策模型求得的分配方案相比于傳統(tǒng)固定抵港時問策略能夠有效減少船舶燃油消耗及在港等待時問，降低船舶廢氣排放。

[關(guān)鍵詞]水路運(yùn)輸；泊位分配；組合拍賣；集裝箱碼頭；分布式?jīng)Q策

[中圖分類號]U656.1+35；N945.12 [文獻(xiàn)標(biāo)識碼]A [文章編號]1005-152X（2018）02-0034-07

1 引言

近年來，船舶廢氣排放問題受到社會廣泛關(guān)注，這些廢氣將對港區(qū)環(huán)境和居民健康產(chǎn)生不利影響。以香港為例，2013年水上運(yùn)輸仍是該市最大的S02、NOx、PM10、PM2.5排放源，排放貢獻(xiàn)率分別達(dá)到了50%、31%、36%、42%，在所有船舶中，遠(yuǎn)洋集裝箱船是最大排放源。航運(yùn)減排措施可分為三類：技術(shù)手段、運(yùn)營手段和市場手段，。目前的研究和實(shí)踐多集中于技術(shù)手段，而對后兩者的研究還不多。泊位是港口的稀缺資源，泊位分配不僅影響碼頭自身的運(yùn)營效率，還影響船期可靠性，因此，泊位分配是港航雙方通過協(xié)作來推進(jìn)節(jié)能減排的重要契合點(diǎn)。對此，Golias等采用可變抵港時間（Variable ArrivalTime，VAT）策略，將船舶抵港時間視為決策變量，間接考慮了船舶在港期間的廢氣排放。Lang和Veen-stra等建立了港航合作下的泊位分配模型，使得燃油成本、機(jī)會損失和延誤懲罰之和最小化。Du等采用更加精確的燃油消耗函數(shù)，對燃油消耗量和主要廢氣排放量做了定量分析。這些研究表明，相比于固定抵港時間（ Constant Arrival Time，CAT）策略，通過優(yōu)化抵港時間可以降低船舶燃油消耗與廢氣排放。

但是，這些研究都是以碼頭作為集中決策者來制定泊位分配方案，其存在兩方面的問題：首先，大多數(shù)船舶出于商業(yè)競爭考慮并不愿意將私有信息傳遞給碼頭，如燃油消耗信息；其次，集中式VAT策略要求船舶依照碼頭所指定的航速航行，忽略了船舶方的自主性，降低了船舶參與合作的積極性，不利于策略的推廣實(shí)踐。

為克服以上兩點(diǎn)不足，本文將碼頭和船舶看作相互獨(dú)立的決策主體，在分布式?jīng)Q策環(huán)境下研究泊位和岸橋聯(lián)合調(diào)度問題。由于每個主體在決策時都從自身利益出發(fā)，經(jīng)常存在相互沖突的情況，所以需要協(xié)調(diào)以得到可行方案。組合拍賣作為一種有效的市場機(jī)制，可以保護(hù)好主體的獨(dú)立性和私有信息，被廣泛應(yīng)用于資源分配問題，如機(jī)場跑道分配、分布式火車調(diào)度等。針對問題的特點(diǎn)，本文設(shè)計(jì)了基于多回合組合拍賣的泊位分配機(jī)制，船舶無需在每一回合中對所有可能時段組合進(jìn)行估值，減輕了船舶方的計(jì)算負(fù)擔(dān)，包括投標(biāo)決策、中標(biāo)決策、價格更新、拍賣流程四個方面的設(shè)計(jì)。這樣更有利于VAT策略應(yīng)用于實(shí)踐，豐富節(jié)能減排運(yùn)營手段和市場手段的研究。

2 問題描述

在分布式?jīng)Q策環(huán)境下，船舶自主決策航速及抵港時間，碼頭優(yōu)化泊位及岸橋分配。船舶決策時主要考慮船期可靠性和航次成本，其中航次成本除去固定成本外主要包括燃油費(fèi)及港口費(fèi)用，因此，可將港口費(fèi)用作為中間量用于雙方協(xié)商。本文將泊位使用時段（Time Slot）看作一種特殊商品，碼頭作為資源主體向各船拍賣使用時段并制定中標(biāo)決策，船舶則競拍所需時段并支付相應(yīng)費(fèi)用（即港口費(fèi)用）。同時，碼頭可根據(jù)投標(biāo)情況及時調(diào)整時段價格，從而引導(dǎo)船舶避開高峰期。考慮到使用時段的互補(bǔ)性，即船舶需獲得一段連續(xù)的使用時段，本文采用多回合組合拍賣的方法，雙方通過協(xié)商達(dá)成一致意見。希望通過港航間的這種協(xié)商機(jī)制來降低船舶燃油消耗和廢氣排放，提高碼頭服務(wù)水平。

為便于建模，基于以下假設(shè)進(jìn)行研究：

（1）泊位為同質(zhì)離散泊位，且物理?xiàng)l件滿足任一來港船舶停泊要求；

（2）船舶一旦開始裝卸作業(yè)，不允許中斷；

（3）船舶在投標(biāo)時采用最佳近似投標(biāo)策略nu；

（4）不考慮船舶對泊位位置的偏好及岸橋移動約束限制。

3 模型建立

3.1 數(shù)學(xué)符號

對本文中出現(xiàn)的數(shù)學(xué)符號定義如下：

H—計(jì)劃期長度；

T一泊位使用時段集合，T={1，2，…，H）；

V-船舶集合，共n艘船，V={1，2，…，n）；

B-泊位集合，共m個泊位，B={1，2，…，m）；

li—初始時刻，船i距離碼頭的距離，i∈V，單位：海里；

a0i—船i預(yù)計(jì)抵港時刻，i∈V；

di一船i要求最晚離港時刻，i∈V：

hi—船i裝卸作業(yè)量，i∈V，單位：岸橋工時；

p—燃油價格，單位：美元/t；

Q—碼頭可用岸橋總數(shù)；

rmini，rmaxi—每時段至少和最多為船i分配的岸橋數(shù)，i∈V；

qi一碼頭每時段為船i預(yù)計(jì)分配的岸橋數(shù)，qi= （rmini+rmaxi）/2，i∈V；v0i—船i計(jì)劃服務(wù)航速，i∈V，單位：節(jié)；vmini，vmaxi一船i最小和最大航速，i∈V，單位：節(jié)；ai，ai—依離港距離和航速范圍計(jì)算出的船i最早和最晚抵港時刻，i∈V；Ai—船i可能抵港時刻的集合，i∈V，Ai=

Faii一船i以時刻ai抵港時對應(yīng)的燃油消耗量，i∈V，ai∈Ai，單位：t；

λit一對船i，第t時段的價格，i∈V，t∈T，單位：美元；

Ci—船i港口費(fèi)用預(yù)算，i∈V，單位：美元；

M—足夠大的正數(shù)。

3.2 投標(biāo)決策

基于最佳近似投標(biāo)策略，船舶在每回合競拍時選擇使自身成本最小的時段組合進(jìn)行投標(biāo)。在計(jì)算燃油成本時，采用的單位時間燃油消耗函數(shù)為：

其中，c0，c1為回歸系數(shù)，v為航速。考慮到燃油消耗函數(shù)非線性帶來的求解困難，本文采用離散化方法進(jìn)行處理，計(jì)算出不同抵港時刻對應(yīng)的燃油消耗量。

對船i，i∈V，其投標(biāo)決策模型如下：

決策變量：

yi一船i靠泊時刻；

zit—0-1變量，若占用t時段則取1，否則取0，t∈T：

Uaii—0-1變量，若以時刻ai抵港則取1，否則取0，a∈Ai。

輔助決策變量：

ei—船i離港時刻；

其中，目標(biāo)函數(shù)為最小化航行成本（燃油成本和港口費(fèi)用）與離港延誤時間加權(quán)和，Ni1和Ni2為標(biāo)準(zhǔn)化因子，用于消除量綱影響，（ei-di）+=max{ei-di，0}；式（4）表示需選擇一個抵港時刻；式（5）表示靠泊時刻不得早于抵港時刻；式（6）表示裝卸作業(yè)完成后才能離港，依預(yù)計(jì)分配岸橋數(shù)來計(jì)算；式（7）定義了所需時段的數(shù)目；式（8）和（9）要求所占用時段是連續(xù)的；式（10）表示所支付港口費(fèi)用不能超過預(yù)算。

求解模型后，船i將（i，yi，hi，si，bi，wi）發(fā)給碼頭進(jìn)行投標(biāo)，其中，yi為最早靠泊時刻；hi為裝卸作業(yè)量；si= max{ei，di}為該標(biāo)要求最晚裝卸完工時間；bi=表示船舶支付的費(fèi)用；wi為狀態(tài)變量，若ei≤di則取1，否則取-1。

3.3 中標(biāo)決策

碼頭得到本回合所有投標(biāo)后，通過求解競勝標(biāo)模型來確定中標(biāo)船舶及分配方案。碼頭可通過調(diào)整岸橋分配來影響船舶實(shí)際裝卸作業(yè)時間，可看作一個加工時間可控的調(diào)度問題。

決策變量：

θ-0-1變量，若船i中標(biāo)則取1，否則取0，i∈V：

xy—0-1變量，若船i停靠泊位j則取1，否則取0，i∈V，j∈B；

Rit一在t時段為船i分配的岸橋數(shù)，i∈V，v∈T：

σii'—0-1變量，等于1時表示船i'在船i離開后才靠泊，i，i'∈V，i≠i'；yi一由碼頭決策的船i實(shí)際靠泊時刻，i∈V。輔助決策變量：rit—0-1變量，在t時段，若安排岸橋?yàn)榇琲服務(wù)則取1，否則取0，i∈V，t∈T；

ei一由碼頭決策的船i實(shí)際離港時刻，i∈V。

其中，目標(biāo)函數(shù)第一項(xiàng)表示最大化港口收益，第二項(xiàng)是為了優(yōu)化船舶離港時刻，對中標(biāo)船舶i，若wi=1，則可使e盡量接近si，若wi=-1，則表示若在s，離港將產(chǎn)生延誤，因此需盡量早點(diǎn)離港；式（ 14）-式（15）表示僅對中標(biāo)船舶分配泊位及岸橋；式（16）表示安排在同一泊位的船舶不應(yīng)有時間沖突；式（17）表示分配的岸橋數(shù)不能超過碼頭所擁有的岸橋數(shù)；式（18）表示每時段為船舶分配的岸橋數(shù)限制；式（19）—式（21）表示裝卸作業(yè)不能中斷；式（22）表示需完成中標(biāo)船舶的裝卸作業(yè)；式（23）—式（24）表示實(shí)際靠泊和離港時刻應(yīng)在船舶所投標(biāo)的時段區(qū)間內(nèi)；式（25）表示當(dāng)σ長城ii'=1時，ei≤yi'成立。

3.4 價格更新機(jī)制

為促使船舶投標(biāo)時段分布更加均勻，減少沖突現(xiàn)象發(fā)生，碼頭采用基于拉格朗日松弛算法的價格更新機(jī)制來引導(dǎo)船舶投標(biāo)，具體如下：其中，為第k+1回合船i第t時段的價格，為拍賣開始時船i每時段的保留價格，勾時段t能力約束的次梯度，sk為步長。

其中，α是一個常數(shù)，UB和LB分別為第k回合碼頭目標(biāo)函數(shù)的上下界。

3.5 拍賣機(jī)制設(shè)計(jì)

拍賣機(jī)制步驟如下：

Step 1：初始化。碼頭向?qū)⒃谟?jì)劃期內(nèi)抵港船舶公布時段初始價格，由于碼頭通常會根據(jù)船舶大小不同安排不同數(shù)量岸橋進(jìn)行裝卸作業(yè)，所以初始價格采取了差異化定價方式，并置回合計(jì)算器k=0。

Step 2：投標(biāo)決策。在回合k，每艘船先判斷自己在上一回合是否中標(biāo)，如果中標(biāo)，則無需投標(biāo)；否則，根據(jù)當(dāng)前時段價格求解投標(biāo)模型再次投標(biāo)。

Step 3：碼頭決策。碼頭收集當(dāng)前回合所有投標(biāo)，結(jié)合上一回合的中標(biāo)結(jié)果，求解競勝標(biāo)模型，得到本回合臨時分配結(jié)果，若所有船舶均中標(biāo)則拍賣結(jié)束；否則，轉(zhuǎn)Step 4。

Step 4：價格更新。依照式（30）更新時段價格，置k=k+l，轉(zhuǎn)Step2。

3.6 CAT策略模型

本文以傳統(tǒng)CAT策略為對照組，碼頭計(jì)劃人員將抵港時間看作一個常量，以最小化離港延誤時間之和為目標(biāo)制定集中式分配方案。約束條件同式（ 16）-式（21），式（25）-式（28）

4 數(shù)值買驗(yàn)

為分析分布式?jīng)Q策模型（ Decentralized Decision-making Model，DDM）性能，進(jìn)行數(shù)值實(shí)驗(yàn)。以72h為計(jì)劃期，單位時間為1h，碼頭共有4個泊位和12臺岸橋，船舶分為Feeder、Medium、Jumbo三種類型，比例為4：5：1。按船舶數(shù)目不同，設(shè)計(jì)了5個測試問題。對每個測試問題，按如下方式隨機(jī)生成15個實(shí)例：（1）基本參數(shù)按表1所給區(qū)間均勻分布產(chǎn)生；（2）船舶其它參數(shù)，a0i～U[1，60]，li=a0iv0i，di=a0i+hi/qi·U[1，1.5]最小航速取經(jīng)濟(jì)航速vmini=[c0i//（μi-1））]1/μ，最大航速分別為vmaxi=24，26，28，ai=li/vmaxi，ai=li/vmini；（3）價格參數(shù)，Ci=λ0ihi/qi·U[1.5，3]，p=400，對于λ0i，主要考慮裝卸費(fèi)用，假設(shè)每臺岸橋裝卸效率77= 30 TEU/h，集裝箱裝卸費(fèi)c= 60 USD/TEU，對于這三種船舶，每時段預(yù)計(jì)分配岸橋數(shù)qi= 1.5，3，5，所以相應(yīng)λ0i=2700，5 400，9000 USD；（4）其它參數(shù)，Ni1=pFa0ii+cηhi，Ni2=1，α=2。

在MATLAB環(huán)境下采用YALMIP建模，調(diào)用CPLEX 12.6求解，電腦配置為2.93GJHz CPU和4GB內(nèi)存。

4.1 經(jīng)濟(jì)和環(huán)境效益分析

為比較DDM策略與CAT策略在經(jīng)濟(jì)和環(huán)境效益上的表現(xiàn)，將總等待時間、總離港延誤時間、船舶總油耗三項(xiàng)主要指標(biāo)匯總，見表2，表中數(shù)值為15個測試實(shí)例的平均值。可見，在DDM策略下，（1）經(jīng)濟(jì)效益方面，燃油消耗明顯下降，可省油14.0%-16.4%，平均每艘船省油20.3-26.Ot，而且在港等待時間減少78%以上；（2）環(huán)境效益方面，由于燃油消耗的降低及在港等待時間的減少，船舶航行及在港期間的廢氣排放可以大大減少；（3）延誤時間有所增加，這主要是因?yàn)樵诜植际經(jīng)Q策環(huán)境下，船舶參與決策，碼頭不再作為決策主導(dǎo)者擁有所有信息并以總延誤時間最小為唯一目標(biāo)，另外，設(shè)置的港口費(fèi)用預(yù)算約束對此也有一定影響。

為進(jìn)一步分析燃油節(jié)省效果，將DDM策略與集中式VAT策略結(jié)果對比，如圖1所示。在集中式VAT策略下，碼頭以總?cè)加拖暮脱诱`時間加權(quán)和最小化為目標(biāo)制定集中式?jīng)Q策。DDM策略下的船舶節(jié)油量達(dá)到集中式VAT策略下節(jié)油量的90%左右，因此，DDM策略的節(jié)油效果十分明顯。

下面對港航雙方收支情況進(jìn)行分析，如圖2所示。相比于CAT策略，在DDM策略下，對船舶而言，一方面燃油費(fèi)用會有所減少；另一方面由于船舶首次投標(biāo)時的競標(biāo)價約等于CAT策略下的港口費(fèi)用，隨著拍賣的進(jìn)行，港口費(fèi)用會有所增加，也就意味著碼頭收益會增長。不過將兩者相減，船舶總成本仍然降低了3.1%-7.3%。這對實(shí)際運(yùn)營有一定指導(dǎo)意義，首先，通過拍賣方式對時段進(jìn)行定價，可以更好地反映不同時段的市場價格和供求關(guān)系；其次，通過制定合適的初始時段價格可以取得雙贏的效果，一方面降低船舶總成本，同時增加碼頭收益，有利于策略的實(shí)行。

4.2 拍賣效率分析

圖3為拍賣所需回合數(shù)的統(tǒng)計(jì)，碼頭可通過優(yōu)化岸橋分配調(diào)節(jié)船舶實(shí)際裝卸所需時問，從而優(yōu)化配置，使得港航雙方能夠通過較少回合便得到最終分配方案。

需指出的是，僅通過一同合便結(jié)束拍賣并不代表首輪投標(biāo)沒有沖突，而是碼頭通過優(yōu)化泊位和岸橋分配予以解決。以實(shí)例65為例，該例有20艘船，表3為各船首輪投標(biāo)情況。統(tǒng)計(jì)各時段需求次數(shù)，如圖4所示，即便不考慮岸橋是否充足，仍有多個時段的需求次數(shù)大于碼頭所擁有的泊位數(shù)，因而存在沖突。另外，對于船15，通過求解投標(biāo)模型，得到離港時刻為23，投標(biāo)時卻取28，這樣做的日的除了給予碼頭更大的自由度外，更主要的原因是船舶自身希望能夠在不延誤的情況下晚點(diǎn)離港，從而以更低航速航行，進(jìn)一步節(jié)省燃油費(fèi)用，而不必增加港口費(fèi)用。

通過求解競勝標(biāo)模型，該例分配方案如圖5所示。由于模型目標(biāo)函數(shù)第二項(xiàng)所起的作用，船15實(shí)際靠泊時刻為16，有利于進(jìn)一步降低油耗；而對于船11，碼頭則通過分配使其提前離港，避免了產(chǎn)生延誤，這正是船舶所希望得到的。

5 結(jié)語

本文研究了分布式?jīng)Q策環(huán)境下的集裝箱碼頭泊位和岸橋聯(lián)合調(diào)度問題，將船舶和碼頭看作相互獨(dú)立的決策主體，設(shè)計(jì)了基于多回合組合拍賣的分配機(jī)制，這樣更有利于VAT策略應(yīng)用于實(shí)踐。數(shù)值實(shí)驗(yàn)表明，相比于CAT策略，DDM策略能夠有效降低船舶燃油消耗及在港等待時間，從而降低廢氣排放。并且，通過拍賣泊位服務(wù)時段，在降低船舶運(yùn)營成本的同時也可以增加碼頭收入，取得雙贏的效果。本文的研究還可進(jìn)一步深入和完善，第一，對拍賣機(jī)制進(jìn)行改進(jìn)，研究如何進(jìn)一步減少離港延誤時間；第二，設(shè)計(jì)相應(yīng)算法，提高求解速度。