考慮經(jīng)濟(jì)利益的泊位-岸橋聯(lián)合調(diào)度

牟志為,傅恩圓

(天津大學(xué)管理與經(jīng)濟(jì)學(xué)部,天津 300072)

作為連接國際物流網(wǎng)絡(luò)的重要節(jié)點(diǎn),在過去的數(shù)十年里,世界主要港口的集裝箱吞吐量持續(xù)增長,并有望在接下來的數(shù)年里繼續(xù)保持增長勢頭,即使是在受到新冠疫情強(qiáng)烈沖擊的2020年上半年,我國部分港口的集裝箱吞吐量仍能夠逆勢增長[1]。這種迅猛的發(fā)展勢頭促使碼頭運(yùn)營者為了提高集裝箱碼頭的作業(yè)效率,一方面增加碼頭作業(yè)設(shè)備數(shù)量,另一方面更加重視制定合理的作業(yè)計(jì)劃。作為碼頭的主要稀缺資源,泊位的分配情況和岸橋的調(diào)度情況影響到整個集裝箱碼頭的作業(yè)效率,在很大程度上泊位的分配會影響到岸橋的調(diào)度。因此,考慮將泊位計(jì)劃和岸橋計(jì)劃綜合起來進(jìn)行分析,通過參數(shù)共享來制定聯(lián)合調(diào)度計(jì)劃,以代替之前獨(dú)立地制定作業(yè)計(jì)劃。

已有許多關(guān)于泊位-岸橋聯(lián)合調(diào)度的研究,如Akio等[2]首先針對船舶動態(tài)到港下的泊位-岸橋調(diào)度問題,以船舶在港時(shí)間最小為目標(biāo),給予所有船舶同等的服務(wù)優(yōu)先級并假設(shè)為每艘船舶服務(wù)的岸橋數(shù)固定;Young-Man等[3]最先研究了連續(xù)型泊位的泊位分配和岸橋調(diào)度問題,以集裝箱的裝卸成本加權(quán)總和最小化為優(yōu)化目標(biāo),設(shè)計(jì)了一個兩階段的算法進(jìn)行求解;李娜等[4]以待分配船舶的總在港時(shí)間最小為目標(biāo)建立模型,考慮了岸橋交叉干擾等現(xiàn)實(shí)約束,利用Squeaky Wheel 優(yōu)化方法,設(shè)計(jì)了一個啟發(fā)式算法進(jìn)行求解。

對于船舶公司來說,船舶在港時(shí)間較短有助于降低其自身運(yùn)營成本,提高貨物周轉(zhuǎn)速度。但在泊位-岸橋調(diào)度問題中,船舶的裝卸時(shí)間實(shí)際上取決于岸橋的分配結(jié)果。對于碼頭運(yùn)營者而言,更希望看到其昂貴的碼頭資源得到充分利用,一味致力于減少船舶在港時(shí)間,勢必需要將更多的岸橋調(diào)配給同一艘船只,將會帶來岸橋移動成本的明顯提高以及碼頭泊位利用率的降低。因此,后期的研究者在此基礎(chǔ)上提出了更多優(yōu)化目標(biāo),如Frank等[5]研究了裝卸作業(yè)中岸橋的邊際效率問題,認(rèn)為隨著為船只服務(wù)的岸橋數(shù)量增加,其邊際效率下降,他們以最小化所有到港船舶的總服務(wù)成本為目標(biāo)建立了泊位-岸橋調(diào)度模型;楊華龍等[6]認(rèn)為想要達(dá)到系統(tǒng)最優(yōu),必須考慮岸橋利用率,因此建立了目標(biāo)為船舶在港時(shí)間最小和岸橋利用率最高的模型,并針對該模型使用擠壓算法求解;Yavuz等[7]綜合分析了船舶偏離偏好泊位成本、等待泊位的時(shí)間成本和船舶滯期成本,對不同規(guī)模的問題進(jìn)行求解;楊劼等[8]從為船舶提供的所有服務(wù)的成本入手,致力于減少船舶等待泊位成本、偏離偏好泊位成本、推遲離港的時(shí)間成本和岸橋移動成本。

綜合已有研究分析,早期研究者考慮的因素較為單一,片面追求在港時(shí)間最小化既不符合碼頭方的利益,也無法滿足船舶方多方面的需求。后期的研究者從碼頭服務(wù)質(zhì)量、船舶服務(wù)成本、客戶滿意度等方面入手,但是更多的還是站在船舶公司的角度出發(fā)來尋找最優(yōu)解或滿意解。碼頭運(yùn)營者和船舶公司作為泊位-岸橋調(diào)度問題的利益雙方,均陷入了非零和博弈的狀態(tài)。在雙方都只關(guān)注其自身經(jīng)濟(jì)利益的前提下,船舶公司希望能夠降低其在港時(shí)間和運(yùn)營成本,而碼頭運(yùn)營者則期望從到港船舶身上攫取更多利潤。當(dāng)然,二者可以合作共贏,找到這個合作博弈問題的帕累托解集具有重要現(xiàn)實(shí)意義。研究先從碼頭運(yùn)營者角度出發(fā),在錨地停泊、引航、泊位停泊、裝卸作業(yè)、集卡運(yùn)輸?shù)拳h(huán)節(jié)進(jìn)行分析,厘清船港雙方在各個環(huán)節(jié)上的利益關(guān)系,找到整個系統(tǒng)的痛點(diǎn),再研究如何兼顧雙方,以制定更切合實(shí)際、更合理的泊位-岸橋聯(lián)合調(diào)度計(jì)劃。

1 建立模型

在抵港之前,船舶需要將自身船型、計(jì)劃到港時(shí)間、需要裝卸作業(yè)量等信息報(bào)備給碼頭,根據(jù)這些信息,碼頭在計(jì)劃周期內(nèi)制定作業(yè)計(jì)劃,包括船舶在指定時(shí)間?？?、停靠于指定泊位、由指定岸橋進(jìn)行裝卸作業(yè)等。船舶到港后的作業(yè)流程如圖1所示。

圖1 到港船舶作業(yè)流程Fig.1 Operation flow chart of the arriving ships

港口經(jīng)營服務(wù)性費(fèi)用參考我國2019年修訂的《港口收費(fèi)計(jì)費(fèi)辦法》,因?yàn)樵阱^地停泊費(fèi)用遠(yuǎn)小于在港內(nèi)停泊費(fèi)用,因而設(shè)定船舶到港后,假如為其分配的泊位或岸橋不可用,船舶將在錨地等待,港口按照停泊時(shí)間和船舶噸位收取錨地停泊費(fèi)。在確認(rèn)分配的泊位和岸橋均可用后,進(jìn)行引航作業(yè),需要移動的岸橋向預(yù)?？坎次灰苿?船舶進(jìn)入港口并停泊在指定泊位。在這個過程中,港口按照船舶噸位和引航距離收取引航費(fèi)用。靠泊之后,由分配的岸橋?qū)Υ霞b箱進(jìn)行裝卸作業(yè),港口按照船舶停泊時(shí)間和噸位收取停泊費(fèi),并按照自定標(biāo)準(zhǔn)(一般包括作業(yè)量、使用岸橋數(shù)量等)收取港口作業(yè)包干費(fèi),集裝箱從船上卸下后由集卡運(yùn)送至堆場堆存,港口按照自定標(biāo)準(zhǔn)收取庫場使用費(fèi);港口還將根據(jù)集裝箱型號和數(shù)量收取港務(wù)費(fèi)及港口設(shè)施保安費(fèi),但貨物信息確定后二者相當(dāng)于固定費(fèi)用,因此模型中不再考慮。同理,庫場使用費(fèi)也根據(jù)集裝箱型號和數(shù)量收取,模型僅考慮碼頭方因未安排船舶進(jìn)入偏好泊位而額外付出的運(yùn)輸成本。經(jīng)過分析,各環(huán)節(jié)產(chǎn)生費(fèi)用及影響因素如表1所列。

表1 港口停泊各環(huán)節(jié)費(fèi)用及影響因素

1.1 模型假設(shè)

該模型建立在離散型泊位布局的碼頭上,即一定長度岸線被劃分為若干個大小各異的泊位,每個泊位擁有不同的長度和水深,能夠滿足不同類型船只的需要。模型假設(shè)如下:(1)所有船舶在時(shí)間和空間上不能重疊;(2)所有岸橋在不同時(shí)段的工作效率相等,但當(dāng)多臺岸橋同時(shí)在一艘船作業(yè)時(shí),相互之間會有影響;(3)所有岸橋直線分布于岸線上,不能交叉跨越作業(yè),默認(rèn)岸橋移動在引航時(shí)間內(nèi)完成;(4)分配給所有船舶的岸橋數(shù)量在作業(yè)過程中保持不變;(5)每艘船舶能靠泊一次且必須靠泊一次,并且不能移泊;(6)每艘船舶都有偏好泊位,使得泊位與該船貨物應(yīng)當(dāng)儲存的堆場之間距離最短;(7)每艘船舶都有固定的安全水深、安全船長以及最小和最大的可分配岸橋數(shù)量;(8)所有船舶從錨地到特定泊位的引航時(shí)間都是已知和固定的,不考慮潮汐、船只大小的影響因素;(9)碼頭必須在計(jì)劃周期內(nèi)完成所有到港船舶的裝卸作業(yè)。

假設(shè)(1)是離散型泊位碼頭的基本要求;假設(shè)(2)參考了文獻(xiàn)[5]中的研究,在模型中設(shè)定多臺岸橋共同工作的相互影響系數(shù);假設(shè)(3)保證為船舶分配的岸橋必須相鄰,滿足客觀實(shí)際條件;假設(shè)(4)被證明[9]能夠?yàn)閷?shí)際操作提供保守的時(shí)間表,因?yàn)榛趧討B(tài)岸橋數(shù)量的理論分析往往帶來大量的岸橋移動,在實(shí)際中會很快偏離理論計(jì)算;假設(shè)(5)保證船舶必須靠泊且只能靠泊一次,模型不考慮移泊;假設(shè)(6)規(guī)定船舶擁有偏好泊位,停靠在偏好泊位能夠提高集卡運(yùn)行速度,相較于偏好泊位,碼頭將集裝箱從其他泊位運(yùn)輸?shù)蕉褕?需要付出額外運(yùn)輸成本;假設(shè)(7)和假設(shè)(8)規(guī)定模型中考慮到的參數(shù)已知且固定;假設(shè)(9)對碼頭制定作業(yè)計(jì)劃施加限制,相應(yīng)地在算例實(shí)驗(yàn)時(shí)會減少計(jì)劃周期后期到船概率,最后數(shù)個小時(shí)不再到船。

1.2 參數(shù)符號

模型中涉及的符號表示如下:

1.3 決策變量

模型中的決策變量為:

pi為船舶i的開始引航時(shí)間,整數(shù);bi為船舶i的靠泊時(shí)間,整數(shù);li為船舶i的離港時(shí)間,整數(shù);Bi為船舶i的停泊泊位,整數(shù);Qi為分配給船舶i的岸橋數(shù)量,整數(shù);Uijqt∈{0,1},當(dāng)船舶i在泊位j在時(shí)間t被q臺岸橋服務(wù)時(shí),取值為1,否則為0;σij∈{0,1},當(dāng)船舶i在泊位j被服務(wù)時(shí),取值為1,否則為0。

為了方便在模型中表示,定義了一些變量,它們都可以輕易用決策變量Uijqt表示出來,變量如下:

θit∈{0,1},當(dāng)船舶i在時(shí)間t被服務(wù)時(shí),取值為1,否則為0;δijt∈{0,1},當(dāng)船舶i在時(shí)間t在泊位j被服務(wù)時(shí),取值為1,否則為0。

1.4 目標(biāo)函數(shù)

最大化碼頭經(jīng)濟(jì)利益的目標(biāo)函數(shù)為

α3vi(li-bi)+α4wi-α5Qi(li-bi)+

α6wiDBiPi),

(1)

1.5 約束條件

模型中的約束條件為

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(t+1)·θit≤li, ?i,t

(11)

t·θit+H·(1-θit)≥bi, ?i,t

(12)

pi,bi,li∈{ai,…,H}, ?i

(13)

(14)

(15)

Uijqt,σij,θit,δijt∈{0,1}, ?i,j,q,t

(16)

式(2)定義了船舶靠泊時(shí)刻和引航時(shí)刻的關(guān)系,表示船舶經(jīng)過引航作業(yè)后靠泊;式(3)引入多臺岸橋在同一艘船上工作時(shí)的影響指數(shù),表示必須滿足船舶裝卸作業(yè)所需臺時(shí)數(shù);式(4)表示對于所有船舶來說,有且只有一次靠泊機(jī)會且必須靠泊一次;式(5)和式(6)表示泊位要滿足船舶的安全水深和安全船長;式(7)表示岸橋數(shù)量約束;式(8)表示為每艘船分配的岸橋數(shù)量要大于等于其最小岸橋數(shù)量且不超過其最大岸橋數(shù)量;式(9)表示所有船舶在時(shí)間和空間上不能重疊;式(10)～(12)定義了船舶的靠泊時(shí)間和離港時(shí)間;式(13)表示所有環(huán)節(jié)均在計(jì)劃周期內(nèi)完成;式(14)～(16)定義了決策變量的相互關(guān)系和取值范圍。

2 求解算法

泊位-岸橋聯(lián)合調(diào)度問題屬于NP-hard問題,已有多項(xiàng)研究針對它提出了包括精確解算法和啟發(fā)式算法的不同算法進(jìn)行求解。Salhi等[10]在研究中同時(shí)使用了商業(yè)化求解軟件CPLEX和遺傳算法,證明對于較大型實(shí)例只有使用啟發(fā)式算法才能在合理的時(shí)間內(nèi)找到最優(yōu)或者接近最優(yōu)的解決方案。為了更加貼近實(shí)際情況,研究采用了改進(jìn)的遺傳算法[11]對模型進(jìn)行求解,包括采用改進(jìn)的錦標(biāo)賽選擇算子對種群進(jìn)行選擇,基于sigmoid函數(shù)的交叉和變異率來使算法獲得更好的收斂性以及跳出局部最優(yōu)解的能力。算法的具體流程如下:

(1) 根據(jù)編碼規(guī)則初始化Nind個個體的種群;

(2) 若滿足停止條件,則算法結(jié)束,輸出最終結(jié)果,否則繼續(xù)執(zhí)行;

(3) 對當(dāng)前種群進(jìn)行統(tǒng)計(jì)分析,記錄其最優(yōu)個體、平均適應(yīng)度等,并計(jì)算當(dāng)前交叉率和變異率;

(4) 按照當(dāng)前交叉率對當(dāng)前種群的Nind個母體進(jìn)行交叉操作;

(5) 按照當(dāng)前變異率對這Nind個交叉后的個體進(jìn)行變異;

(6) 將父代種群和交叉變異得到的種群進(jìn)行合并,得到規(guī)模為2Nind的種群;

(7) 從合并的種群中根據(jù)選擇算法選擇出Nind個個體,得到新一代種群;

(8) 回到(2)。

2.1 編碼方式

對于決策變量Uijqt來說,有3個決定因素,分別是靠泊位置Bi、分配的岸橋數(shù)量Qi和開始引航作業(yè)時(shí)刻pi。因此針對模型中這3個決定因素,使用3條染色體進(jìn)行編碼,如圖2所示。圖2中船舶2停泊在4號泊位,分配給它的岸橋數(shù)為2臺,在時(shí)間3進(jìn)行引航作業(yè)。

圖2 染色體編碼方式示例Fig.2 Example of the chromosome coding method

在編寫代碼實(shí)現(xiàn)算法時(shí),先對輸入的船舶信息進(jìn)行分析,根據(jù)約束條件(2)(5)(6)(8)(13)得到所有船舶能夠?？康牟次环秶⒖山邮艿陌稑驍?shù)量范圍以及可以進(jìn)行靠泊的時(shí)間范圍等數(shù)據(jù),以此對每個基因位置的取值范圍設(shè)定限制,避免產(chǎn)生大量不可行解。在執(zhí)行交叉和變異操作后也對每個基因位置進(jìn)行檢查,修復(fù)不可行的染色體。

2.2 適應(yīng)度函數(shù)

該模型是為了找到計(jì)劃周期內(nèi)每艘到港船舶的最佳停泊位置、最佳停泊時(shí)間以及最佳分配岸橋數(shù)量,使碼頭運(yùn)營者得到經(jīng)濟(jì)利潤的最大化。因此,將模型的目標(biāo)函數(shù)設(shè)定為遺傳算法的適應(yīng)度函數(shù):

α3vi(li-bi)+α4wi-α5Qi(li-bi)+

α6wiDBiPi)。

(17)

2.3 選擇算子

研究采用了改進(jìn)的錦標(biāo)賽選擇法,選擇算子的具體步驟如下:

(ⅰ)首先從父代種群和交叉變異得到的種群合并的種群中(規(guī)模為2Nind),按照適應(yīng)度大小進(jìn)行排序,將位于優(yōu)勢位置的前1/4的個體直接選擇進(jìn)入下一代種群;

(ⅱ)在剩余的個體中隨機(jī)選擇n個個體,將其中適應(yīng)度最好的個體選擇進(jìn)入下一代種群;

(ⅲ)重復(fù)步驟(ⅱ),直到新種群的規(guī)模達(dá)到Nind。

2.4 交叉和變異操作

遺傳算法中的交叉概率Pc和變異概率Pm對算法的收斂性影響重大。對于增強(qiáng)的精英保留算法來說,在算法的初期,種群適應(yīng)度的方差較大,而在算法后期種群適應(yīng)度的方差變小,甚至產(chǎn)生多個相同個體。因此,參照文獻(xiàn)[11]中的方法,基于sigmoid函數(shù)設(shè)計(jì)了交叉概率Pc和變異概率Pm,其公式分別為

(18)

(19)

其中:k1、k2是參數(shù),可以根據(jù)實(shí)際問題進(jìn)行取值;Dx為種群適應(yīng)度方差;Pcmax、Pcmin分別為種群的最大、最小交叉概率;Pmmax、Pmmin分別為種群的最大、最小變異概率。按照式(18)和式(19),在進(jìn)化初期,種群的適應(yīng)度方差較大,相應(yīng)地Pc也會較大,而Pm則較小,在進(jìn)化后期反之。利用種群適應(yīng)度方差進(jìn)化過程中的變化特點(diǎn),滿足了算法前后期對交叉、變異概率值的不同要求。sigmoid函數(shù)圖像如圖3所示。

圖3 sigmoid函數(shù)圖像Fig.3 Graph of sigmoid function

3 數(shù)值實(shí)驗(yàn)

參考某集裝箱碼頭數(shù)據(jù),該碼頭岸線長1 700 m,擁有6個泊位,20臺岸橋,其中200 m泊位2個,300 m泊位3個,400 m泊位1個。將到港船舶按照安全船長分為3個等級:小型、中型和大型,假定所有泊位水深能夠滿足所有船舶的?？恳蟆４皡?shù)設(shè)置如表2所列,其中小型船舶參數(shù)參考3 000TEU集裝箱船,中型船舶參數(shù)參考標(biāo)準(zhǔn)巴拿馬型集裝箱船,大型船舶參數(shù)參考12 000TEU集裝箱船。按照中型船舶占60%,其他2種船舶各占20%的比例隨機(jī)生成分別包含20、25、30艘船的算例。

表2 船舶參數(shù)設(shè)置

所有集裝箱均折算成裝載一般貨物的20英尺標(biāo)準(zhǔn)TEU計(jì)算,所有船只按照國際航線船舶收費(fèi)基準(zhǔn)費(fèi)率收費(fèi)。計(jì)劃周期為72 h,設(shè)置船舶只在前60 h到港,之后不再有船舶到港。參考《港口收費(fèi)計(jì)費(fèi)辦法》和某港口收費(fèi)標(biāo)準(zhǔn)設(shè)置參數(shù)如下:α1=2.1,α2=1.8,α3=10,α4=500,α5=20 000,α6=10。單個岸橋單獨(dú)作業(yè)下的工作效率η=300箱/h,β=0.9,Pcmax=1,Pcmin=0.5,Pmmax=0.3,Pmmin=0.001,Dsg根據(jù)泊位之間的距離確定。算法采用Python語言編程,在英特爾Core i5-8400 2.80 GHz六核處理器、8 GB內(nèi)存和Win 10操作系統(tǒng)下完成實(shí)驗(yàn)。通過實(shí)驗(yàn)選取算法參數(shù)分別為種群個數(shù)Nind=100,最大進(jìn)化代數(shù)為500代。為了進(jìn)行對照,在模型的基礎(chǔ)上增加以最小化所有船舶總在港時(shí)間為目標(biāo)的目標(biāo)函數(shù)作為對照,其函數(shù)表示為

(20)

再分別以最大化碼頭運(yùn)營者經(jīng)濟(jì)利益、最小化碼頭運(yùn)營者利益、最大化所有船舶總在港時(shí)間和最小化所有船舶總在港時(shí)間為目標(biāo)進(jìn)行實(shí)驗(yàn),各算例及各目標(biāo)結(jié)果如表3所列。

表3 數(shù)值實(shí)驗(yàn)求解結(jié)果Table 3 The results of numerical experiment

從表3中可知,針對實(shí)驗(yàn)生成的3個算例,當(dāng)以最大化碼頭運(yùn)營者的經(jīng)濟(jì)利益為優(yōu)化目標(biāo)時(shí),船舶在港時(shí)間大幅變長,但還是明顯小于以最大化在港時(shí)間為目標(biāo)時(shí)得到的解。而當(dāng)以最小化經(jīng)濟(jì)利益為目標(biāo)時(shí),得到的結(jié)果基本與目標(biāo)為最小化船舶總在港時(shí)間無異,甚至有時(shí)能得到使船舶在港時(shí)間更小的解。

4 結(jié)語

對離散型泊位布局的集裝箱碼頭進(jìn)行了泊位-岸橋聯(lián)合調(diào)度問題的研究,在目標(biāo)函數(shù)中考慮了船舶在錨地停泊、引航作業(yè)、裝卸作業(yè)等環(huán)節(jié)產(chǎn)生的費(fèi)用以及碼頭運(yùn)營者因此付出的成本。在假設(shè)船舶裝卸作業(yè)中岸橋數(shù)量不變以及考慮多臺岸橋一起工作時(shí)使其效率邊際遞減的情況下,以碼頭運(yùn)營者經(jīng)濟(jì)利益為判斷參考建立整數(shù)規(guī)劃模型并設(shè)計(jì)算法求解。為了對照,同時(shí)以船舶在港時(shí)間為判斷參考,分別對2種目標(biāo)函數(shù)進(jìn)行最大化和最小化求解。通過數(shù)值實(shí)驗(yàn)證明了模型和算法的有效性,數(shù)值實(shí)驗(yàn)表明,一味延長船舶總在港時(shí)間并不能使碼頭運(yùn)營者實(shí)現(xiàn)經(jīng)濟(jì)利益最大化,但以最小化船舶在港時(shí)間為目標(biāo)進(jìn)行優(yōu)化,基本上意味著碼頭運(yùn)營者同時(shí)也最小化了自己的當(dāng)前經(jīng)濟(jì)利益,這顯然是碼頭方不能接受的。然而,一味追逐當(dāng)前經(jīng)濟(jì)利益的最大化,會使船舶在港時(shí)間大幅增加,這是船方不能接受的。因此,應(yīng)該將碼頭方經(jīng)濟(jì)利益和船舶在港時(shí)間或者其他標(biāo)準(zhǔn)聯(lián)合起來考慮,通過設(shè)置權(quán)重來尋找雙方比較滿意的解,這需要進(jìn)一步的研究。