考慮泊位偏好和岸橋移動的泊位岸橋聯(lián)合調(diào)度

梅益群，韓曉龍

上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306

近幾十年來，各國間的貿(mào)易量瘋狂增長，帶動了全球運(yùn)輸業(yè)的快速發(fā)展。據(jù)統(tǒng)計，目前有60%以上的貨物采用集裝箱運(yùn)輸，在一些發(fā)達(dá)國家甚至近100%的占額，集裝箱運(yùn)輸?shù)难该驮鲩L對集裝箱碼頭的運(yùn)作效率提出了更高的要求。

泊位是碼頭沿岸線劃分的一系列海面區(qū)域，用以船舶停靠，以便進(jìn)行后續(xù)的船舶在港工作。岸橋負(fù)責(zé)進(jìn)出口集裝箱的裝卸工作。泊位和岸橋作為集裝箱碼頭的重要資源，如何準(zhǔn)確地為到港船只分配泊位以及調(diào)用岸橋?qū)⒅苯佑绊懙秸麄€碼頭的作業(yè)效率。

目前對泊位和岸橋的研究主要分為兩種，一種是分開獨(dú)立研究，包括泊位分配問題（berth allocation problem，BAP）、岸橋分配問題（quay crane assignment problem，QCAP）和岸橋調(diào)度問題（quay crane scheduling problem，QCSP）等。第二種是兩者結(jié)合研究，即泊位和岸橋聯(lián)合調(diào)度問題（berth allocation and quay crane assignment problem，BACAP）。

關(guān)于第一種分開獨(dú)立研究，Guan等[1]研究BAP時，考慮船舶等待時間，將時間和泊位離散化，以船舶在港時間之和最小為目標(biāo)，用樹搜索算法進(jìn)行求解。韓曉龍等[2]在對BAP建模過程中，加入船舶服務(wù)時間價值權(quán)重，目標(biāo)求最小化船舶停靠的加權(quán)等待時間。Kim等[3]以船舶偏離偏好泊位成本和延遲離港成本之和最低為目標(biāo)，構(gòu)建了一種混合整數(shù)線性規(guī)劃模型并求解。Correcher等[4]考慮了碼頭復(fù)雜的空間約束，提出了一種混合整數(shù)線性規(guī)劃公式和一種啟發(fā)式算法，得到關(guān)于引入新變量的BAP最優(yōu)解。Liu等[5]研究不確定性條件下的泊位分配問題，采用兩階段的魯棒性優(yōu)化方法，構(gòu)建了三個兩階段的魯棒模型。Jakub等[6]研究了運(yùn)行時間限制下的BAP算法選擇，通過使用一個最小化解決方案質(zhì)量損失的線性程序，提出一種新的算法選擇方式。吳凌霄等[7]首次提出岸橋調(diào)度的時間-成本均衡的混合整數(shù)優(yōu)化模型，設(shè)計改進(jìn)的遺傳算法用以求解該模型。樂美龍等[8]以岸橋作業(yè)量和作業(yè)時間均衡調(diào)度為目標(biāo)，建立岸橋調(diào)度優(yōu)化模型，并設(shè)計遺傳算法求解QCSP。鄭紅星等[9]考慮岸橋突發(fā)故障對岸橋調(diào)度方案的影響，構(gòu)建以岸橋最大完工時間最小為目標(biāo)的線性規(guī)劃模型，設(shè)計改進(jìn)的差分進(jìn)化算法求解。陸書翔等[10]考慮岸橋閑置對碼頭運(yùn)作效率的影響，建立最小化岸橋完工時間和閑置時間的多目標(biāo)規(guī)劃模型，基于不同的完工時間下界設(shè)計不同算法求解。

關(guān)于第二種將兩者結(jié)合研究的方式，趙虎等[11]綜合考慮泊位和岸橋?qū)嶋H作業(yè)過程，構(gòu)建考慮能耗的泊位-岸橋聯(lián)合調(diào)度模型，設(shè)計遺傳算法進(jìn)行求解。楊劼等[12]在離散泊位的情況下，建立了以總服務(wù)成本最小為目標(biāo)的動態(tài)泊位岸橋協(xié)調(diào)調(diào)度模型，設(shè)計遺傳算法進(jìn)行求解。吳迪等[13]以平均在港時間和作業(yè)成本最小為目標(biāo)，構(gòu)建泊位-岸橋多目標(biāo)聯(lián)合優(yōu)化模型，并設(shè)計模擬植物生長交替進(jìn)化算法求解。Türkogullar?等[14]考慮連續(xù)泊位分配并且采用時不變的岸橋分配策略，建立了混合整數(shù)規(guī)劃模型，利用后處理算法進(jìn)行求解。彭麗姣等[15]研究連續(xù)泊位下的BACAP，建立了以最小化延遲完工任務(wù)量、偏離偏好泊位和岸橋移動懲罰成本為目標(biāo)的整數(shù)規(guī)劃模型。毛敏俐等[16]以最小化船舶在港總服務(wù)成本為目標(biāo)，基于船時效率的岸橋配置的調(diào)整規(guī)則，設(shè)計啟發(fā)式算法進(jìn)行求解。田星等[17]同時考慮泊位、岸橋和集卡三種資源的協(xié)同調(diào)度，以總物流作業(yè)成本最小為目標(biāo)，構(gòu)建了協(xié)同調(diào)度的整數(shù)線性規(guī)劃模型。Hsu[18]將泊位離散化，考慮岸橋工作前的移動和設(shè)置時間并設(shè)置懲罰成本，以總成本最小為目標(biāo)，建立混合整數(shù)規(guī)劃模型并使用改進(jìn)的粒子群算法求解。Wang等[19]研究BACAP時考慮碳排放稅，以最小化所有任務(wù)的總完成延遲和總岸橋運(yùn)營成本為目標(biāo)，建立了多目標(biāo)模型并設(shè)計算法求解。胡鴻濤等[20]研究考慮岸橋維護(hù)的泊位岸橋聯(lián)合調(diào)度問題，以最小化船在港時間為目標(biāo)，設(shè)計粒子群算法對模型求解。孫彬等[21]考慮碼頭作業(yè)過程中的不確定因素，分別采用ASAP和MAS的策略調(diào)度泊位和岸橋，設(shè)計了基于CNP協(xié)商機(jī)制的調(diào)度模型，有效提高系統(tǒng)魯棒性。

綜合以上研究發(fā)現(xiàn)，現(xiàn)有的文獻(xiàn)大多是把船舶到港時間作為已知參數(shù)來考慮，優(yōu)化船舶延期到港時間和船舶延期離港時間等。而本文把船舶到港時間看作變量，考慮船舶抵港后偏離偏好泊位的距離和岸橋移動頻數(shù)對碼頭作業(yè)效率影響。本文構(gòu)建了考慮船舶偏離距離的動態(tài)泊位-岸橋分配模型和考慮岸橋移動頻數(shù)的動態(tài)岸橋調(diào)度模型，求解可得出具體的泊位-岸橋分配計劃和岸橋調(diào)度方案。

1 問題描述

集裝箱港口布局如圖1，船舶進(jìn)港后工作流程如圖2，船舶抵港后，港口為其安排泊位，若暫無可用泊位則需等待，產(chǎn)生等待成本。同時需要注意的是，由于堆場存在多個箱區(qū)，各船舶的集裝箱需要運(yùn)往不同的箱區(qū)，因此各船都有其偏好泊位，若船舶偏離偏好泊位同樣也會造成裝卸效率的降低。岸橋作為裝卸集裝箱船的主要工具，需要根據(jù)實時工作情況而調(diào)動，以滿足資源的最大化利用，但同時也要盡量降低移動頻數(shù)，減少損耗。

圖1 集裝箱港口布局圖Fig.1 Container port layout

圖2 船舶進(jìn)港作業(yè)流程Fig.2 Operation flow of inbound ship

本文考慮的是基于連續(xù)泊位布局的動態(tài)泊位-岸橋聯(lián)合調(diào)度問題。動態(tài)泊位分配即船舶的到達(dá)時間是可變的。碼頭和船公司共享運(yùn)營信息，在船舶到港之前，碼頭向船公司提供泊位信息，船公司根據(jù)船舶的航速（最大最小航速）以及船舶與港口之間距離可預(yù)測該船的抵港時間范圍。

本文問題分為兩階段進(jìn)行，第一階段根據(jù)船舶到港的偏好泊位以及船舶的待裝卸工作量，對船舶實際靠泊位置與偏好泊位的偏離距離、船舶延遲離港時間以及船舶抵港至靠泊的等待時間設(shè)置了懲罰成本，并在約束條件中引入泊位偏離因子表示船舶偏離偏好泊位對船工作量的間接影響，構(gòu)建以最小化泊位偏離成本、延遲離港成本以及等待成本之和為目標(biāo)的混合整數(shù)規(guī)劃模型。第二階段在第一階段的基礎(chǔ)上加入岸橋干擾約束，建立以最小化岸橋移動頻數(shù)為目標(biāo)的整數(shù)規(guī)劃模型。結(jié)合兩模型求解結(jié)果可以得到最佳泊位-岸橋聯(lián)合調(diào)度計劃。

模型構(gòu)建基于以下假設(shè)：

（1）岸線水深滿足所有即將到港船舶的吃水需求。

（2）所有岸橋工作效率、移動速度都相同。

（3）所有到港船舶能在計劃期內(nèi)完成裝卸工作。

（4）船舶在抵港之前根據(jù)所在位置距離港口遠(yuǎn)近程度進(jìn)行抵港時間預(yù)報。

（5）船舶預(yù)計離港時間已知。

2 模型建立

2.1 第一階段模型構(gòu)建

（1）集合和參數(shù)

約束條件（4）保證船i工作的連續(xù)性；約束條件（5）保證船i在完成所有工作之后才能離港；約束條件（6）表示船i的工作時間范圍。

約束條件（7）～（9）表示當(dāng)船i的實際離港時間超過預(yù)期離港時間時，計算超出預(yù)期時間的延遲離港時間成本，當(dāng)船i實際離港時間不超過預(yù)期離港時間時，延遲時間成本為0。

2.2 第二階段模型構(gòu)建

第一階段模型的求解可得出各船舶的靠泊情況，第二階段模型在第一階段模型的基礎(chǔ)上，加入岸橋干擾約束，為各時間段在不同泊位工作的船舶調(diào)配岸橋，目標(biāo)是盡可能少的岸橋移動頻數(shù)。模型如下。

（1）集合和參數(shù)

約束條件（30）～（32）表示船i在t時段的服務(wù)岸橋數(shù)限制，當(dāng)船i在t時段不是工作狀態(tài)則沒有岸橋為其服務(wù)。

約束條件（35）～（37）表示岸橋q在t時段和t-1時段的對船i服務(wù)狀態(tài)的不同導(dǎo)致的yiqt的變化。

3 算法設(shè)計

本文問題為NP-Hard問題，此類問題多采用群智能算法，粒子群算法（PSO）作為一種群智能算法，特點(diǎn)是有記憶性，求解過程中會保留好的解，在分配問題方面具有良好表現(xiàn)，因此針對本文模型設(shè)計了改進(jìn)自適應(yīng)變異的粒子群算法，在編碼過程中，為了保持種群多樣性，增加了粒子的自適應(yīng)變異操作，避免陷入局部最優(yōu)解。根據(jù)種群的適應(yīng)度方差σ2計算變異概率P，公式如下：

其中，N表示種群規(guī)模，Pmax和Pmin分別表示最大和最小變異概率，分別設(shè)置為0.4和0.1。

本文算法流程如下：

步驟1設(shè)置種群參數(shù)（空間維數(shù)、種群規(guī)模、迭代次數(shù)、位置及速度上下界、慣性權(quán)重及學(xué)習(xí)因子），給出適應(yīng)度函數(shù)。

步驟2初始化粒子的位置和速度。

步驟3判斷是否滿足約束條件，若滿足則轉(zhuǎn)至步驟4；否則，轉(zhuǎn)至步驟2。

步驟4計算每個粒子的適應(yīng)度值，將每個粒子的適應(yīng)度值與它的個體極值gbest比較，若較優(yōu)，則替換gbest。將此時的gbest與群體最優(yōu)zbest比較，若較優(yōu)，則替換zbest。

步驟5進(jìn)入迭代，更新粒子的速度和位置，對部分粒子進(jìn)行自適應(yīng)變異。

步驟6計算新粒子的適應(yīng)度值，并更新gbest和zbest。

步驟7若達(dá)到最大迭代次數(shù)，則算法終止，否則回到步驟5。

3.1 編碼方式

一共有n艘船(i=1,2,…,n)，t個時間段，每艘船都有4+t個待求變量。因此，本文粒子群算法的自變量是( 4+t)·n維矩陣，粒子的搜索空間維度為( 4+t)·n。

自變量表示如下：

其中前4行分別表示為每艘船的靠泊位置bi、離港時間td、靠泊時間tb、到港時間ta，后t行表示為每艘船每個時段內(nèi)的岸橋數(shù)。

3.2 種群初始化

粒子群算法所需參數(shù)較少，易于實現(xiàn)，主要參數(shù)包括：種群規(guī)模N、迭代次數(shù)G、慣性權(quán)重w、個體學(xué)習(xí)因子c1、群體學(xué)習(xí)因子c2、位置參數(shù)Xmax和Xmin以及速度參數(shù)Vmax和Vmin，其中需要注意的是位置參數(shù)和速度參數(shù)。

位置參數(shù)Xmax和Xmin：自變量x的上下限，本文位置參數(shù)上限表示為：

1～4行分別表示各船舶的靠泊位置、離開時間、靠泊時間和到港時間的上限，后t行表示每艘船每時間段內(nèi)岸橋數(shù)上限。位置參數(shù)下限的表示則與上限相反。粒子位置初始化公式為：

3.3 適應(yīng)度函數(shù)及約束

結(jié)合本文模型給出適應(yīng)度函數(shù)：

關(guān)于船舶工作量的約束條件：

用泊位偏離因子β來表示船舶偏離對船工作量的影響。

3.4 迭代和變異

在計算完每個粒子的初始適應(yīng)度值并得到初始的gbest和zbest之后，對每個粒子速度和位置進(jìn)行迭代更新。在每一次迭代過程中計算群體適應(yīng)度方差σ2，群體適應(yīng)度方差的值越小，說明粒子群越聚集，根據(jù)式（44）計算P，生成隨機(jī)數(shù)rand∈[ ]0,1，若rand≥P，則對粒子群進(jìn)行自適應(yīng)變異。

4 算例分析

為驗證本文提出的模型和算法的可行性，結(jié)合相關(guān)文獻(xiàn)以及上海某港的相關(guān)運(yùn)營數(shù)據(jù)設(shè)計算例進(jìn)行研究。

4.1 算例參數(shù)

設(shè)集裝箱碼頭連續(xù)岸線長1 200 m，岸邊共有12臺岸橋順序編號1～12，每臺岸橋工作效率相同，均為40 TEU/h，偏離成本按0.1元/(TEU·m-1)。計劃期為1天，1天內(nèi)有8艘船到港。具體參數(shù)見表1。

表1 算例參數(shù)Table 1 Data of example

4.2 算法性能分析

針對本文提出的模型及算例，設(shè)置相關(guān)的算法參數(shù)：種群規(guī)模N=300、迭代次數(shù)G=100、慣性權(quán)重w=0.729 8、個體學(xué)習(xí)因子c1=1.490 5、群體學(xué)習(xí)因子c2=1.490 5。根據(jù)算例，船舶數(shù)量n=8、時間段按半小時劃分t=48，位置參數(shù)Xmax和Xmin表示如下：

在不考慮泊位偏離對船工作量影響的前提下（即泊位偏離因子β=0），設(shè)置5組不同規(guī)模的算例，并分別使用CPLEX和MATLAB編碼的粒子群算法求解，來驗證算法的有效性。結(jié)果如表2，其中，算法求解結(jié)果為10次求解的平均值。

表2 CPLEX與本文算法求解結(jié)果對比表Table 2 Result comparison of CPLEX and proposed algorithm

當(dāng)船舶數(shù)量為8時，算法收斂圖如圖3。

圖3 算法結(jié)果收斂圖Fig.3 Convergence diagram of algorithm results

從表2可看出，當(dāng)船舶數(shù)量相同時，CPLEX求解結(jié)果和本文算法求解結(jié)果誤差較小，說明本文設(shè)計的改進(jìn)自適應(yīng)變異的粒子群算法是可行的。而且隨著算例規(guī)模的增大，可以發(fā)現(xiàn)，CPLEX耗費(fèi)時間明顯比算法所需時間多，由此驗證了該算法的高效性。

將該算法求解結(jié)果與傳統(tǒng)粒子群算法求解結(jié)果比較，如表3。

表3 傳統(tǒng)粒子群算法與本文算法求解結(jié)果對比表Table 3 Result comparison of traditional PSO and proposed algorithm

由表3可看出，不同規(guī)模的算例下，本文算法求解結(jié)果均優(yōu)于傳統(tǒng)粒子群算法求解結(jié)果，證明本文算法求解該問題效果更好。

4.3 算例結(jié)果分析

泊位偏離因子β表示船舶偏離給船裝卸工作帶來的間接影響，本文表現(xiàn)為對船工作量的間接增加。為了更直觀地發(fā)現(xiàn)β變化對總成本的影響，將總成本分成三部分表示，船舶數(shù)量不同時，β值變化對各部分成本的影響如表4所示。

表4 不同泊位偏離因子下的求解結(jié)果Tab.4 Results of different berth deviation factors

為了更清楚地反映以上數(shù)據(jù)的變化，將表4表示為折線圖，如圖4所示。

從圖4可以看出，隨著泊位偏離因子β的增加，船舶在港總成本也是不斷增大的，其中，β值的變化主要影響船舶的延遲離港成本，這是因為當(dāng)泊位偏離因子變大，船舶對岸橋的工作量需求增多，而岸橋的工作效率是一定的，因此船舶的在港工作時間就會被延長，從而導(dǎo)致延遲離港。

圖4 求解結(jié)果走勢圖Fig.4 Line graph of solution results

觀察圖4還能發(fā)現(xiàn)，當(dāng)β值從0.15增加到0.2時，規(guī)模為12艘船的成本變化幅度比規(guī)模為6艘船的大，這是因為規(guī)模為6艘時，所有船舶總的裝卸工作量較小，遠(yuǎn)低于所有岸橋的總工作負(fù)荷，β值變化所帶來的額外工作量可以輕松被各岸橋分擔(dān)。而當(dāng)規(guī)模增大至12艘時，所有船的總工作量較大，β值變化所帶來的額外工作量較大，岸橋資源不變，從而導(dǎo)致等待成本的降低（在港等待時間縮短）和延遲成本的激增（離港時間延長），以充分利用有限的岸橋資源。因此，在實際碼頭工作中，β值應(yīng)隨著計劃期內(nèi)到港的所有船舶總工作量變化而變化，當(dāng)總工作量較大時，應(yīng)當(dāng)采用較大的β值，以充分利用岸橋資源。

5 結(jié)語

相比于其他研究，本文考慮船舶到港時間可變的到港策略，通過船公司與集裝箱碼頭相互間的信息共享，在船舶到港之前，碼頭及時告知船公司泊位資源情況，船公司再根據(jù)泊位信息調(diào)整船舶航速控制船舶到港時間，達(dá)到節(jié)約資源的目的。考慮岸橋干擾約束，同時引入泊位偏離因子β表示船舶偏離間接給碼頭帶來的額外工作量，建立了泊位-岸橋聯(lián)合調(diào)度兩階段模型。使用MATLAB軟件設(shè)計改進(jìn)的自適應(yīng)變異粒子群算法，并設(shè)計算例將算法求解結(jié)果與CPLEX求解結(jié)果比較，證明算法的可行性和優(yōu)越性。模型求解結(jié)果表明，在一定計劃期內(nèi)，岸橋資源不變，船舶偏離偏好泊位會影響碼頭的總運(yùn)作成本。預(yù)計到港船舶的總工作量較大時，取較大的β值能夠縮短船舶的在港等待時間，提高岸橋作業(yè)效率，因此在解決該問題時考慮泊位偏離因子β能夠幫助碼頭工作者權(quán)衡資源利用和作業(yè)成本，做出合理的決策。

通過本文模型的求解，可以得出給定計劃期內(nèi)的泊位-岸橋聯(lián)合調(diào)度計劃。然而在實際碼頭作業(yè)過程中，當(dāng)計劃期較長時，泊位和岸橋的實際工作情況會與計劃的有所出入。未來的研究可以考慮采用滾動計劃法，對于計劃期較長的情況，先按照原計劃實行一段時間觀察成效，若與原計劃產(chǎn)生偏差，則取下一個新的計劃期進(jìn)行新的泊位-岸橋聯(lián)合調(diào)度計劃。