楊 劼，高 紅，劉 巍

1.大連海事大學 交通運輸管理學院，遼寧 大連 116026

2.大連海事大學 數(shù)學系，遼寧 大連 116026

1 引言

泊位和岸橋作為集裝箱碼頭的主要稀缺資源，其調度問題直接影響著顧客滿意度和碼頭的運營成本。泊位計劃和岸橋計劃的制定相互依賴、相互影響。合理的岸橋計劃能夠保證泊位計劃的順利實施，避免因岸橋調配不合理而導致的船舶滯港、壓船、壓貨等現(xiàn)象；另一方面，合理的泊位計劃能夠充分利用岸橋資源，避免岸橋資源的閑置或浪費。因此，充分考慮泊位調度和岸橋分配之間的相互關系，協(xié)調調度碼頭資源，符合碼頭作業(yè)的實際情況，具有十分重要的實踐意義。

泊位調度問題按照碼頭泊位布局的空間屬性可以分為連續(xù)泊位調度、離散泊位調度和混合泊位調度；按照船舶抵港的時間屬性可以分為動態(tài)調度和靜態(tài)調度。Bierwirth和Meisel[1-2]綜述了這兩種屬性任意組合下的泊位和岸橋調度的研究成果。本文研究基于離散泊位布局的泊位岸橋動態(tài)協(xié)調調度，具體是針對離散泊位，在一個計劃周期內，為動態(tài)到港的船舶安排停泊時間和停泊泊位，并為每艘船舶分配一定數(shù)量的岸橋以完成船舶裝卸任務。國內外學者對離散泊位布局下的泊位岸橋協(xié)調調度進行了大量研究。Liang等[3-4]以最小化船舶總的在港時間與延遲時間之和為目標建立數(shù)學模型。船到船的直接轉運能夠減少堆場的使用，從而加快船舶的處理速度，Liang等[5]考慮了船舶之間貨物的轉運，建立了以船舶在港時間、延遲時間及等待轉運時間之和最小為目標的模型，并設計了分階段求解算法確定泊位和岸橋調度計劃。以上是從操作層面考慮泊位岸橋調度問題，Giallombardo等[6]從戰(zhàn)術層面上進行資源調度，旨在一個較長的計劃周期內均衡碼頭收益和顧客滿意度，為碼頭管理者在與船公司的協(xié)商談判中提供決策支持，同時提出了兩階段啟發(fā)式算法對模型求解，第一階段采用禁忌搜索算法安排泊位計劃，第二階段用數(shù)學規(guī)劃方法更新岸橋計劃。Lalla-Ruiz等[7]繼續(xù)從戰(zhàn)術層面解決集裝箱碼頭泊位岸橋調度問題，并設計了偏隨機密鑰遺傳算法求解模型。楊春霞等[8]以最小化船舶在港時間和碼頭生產成本為目標建立了碼頭資源調度優(yōu)化模型，但模型沒有考慮時間與岸橋資源之間的約束，并且在建模中假設船舶裝卸時間是固定的。李明偉等[9]假設船舶裝卸時間與分配的岸橋數(shù)相關，以平均集卡運距和所有船舶平均在港時間最小為目標建立了雙目標協(xié)調調度模型，并采用混沌云粒子群算法尋求模型的滿意解。

以上研究大多立于碼頭管理者的角度，以最小化船舶在港時間為目標建立模型。然而對于船公司來說，船舶到港后在完成裝卸任務的同時應使生產成本最小。本文從船公司的角度出發(fā)，以最小化船舶總的服務成本為目標提出泊位岸橋動態(tài)協(xié)調調度模型。

泊位岸橋調度問題的求解是個NP難題，目前常用的求解方法主要是進化算法和啟發(fā)式算法，包括遺傳算法[10-12]、粒子群算法[13]、禁忌搜索算法[14]、文化基因算法[15]等。采用進化算法求解能夠找到理論最優(yōu)解，然而搜索空間將隨著船舶和泊位數(shù)量的增加迅速膨脹，從而出現(xiàn)組合爆炸問題。啟發(fā)式算法的設計則依賴于具體的問題，容易陷入局部最優(yōu)。本文基于具體的問題設計了改進遺傳算法對模型求解。

2 泊位岸橋動態(tài)協(xié)調調度模型

2.1 問題描述與模型假設

通常情況下，船舶在抵港前就將相關信息（包括船型、即將到港時間、載箱量和預計離港時間等）預報給即將掛靠的碼頭，碼頭工作人員依據(jù)這些信息以及碼頭設備狀態(tài)為船舶制定泊位和岸橋計劃，船舶抵港后便依據(jù)該計劃進行裝卸作業(yè)直至船舶離港。如圖1給出了集裝箱船舶在碼頭作業(yè)的流程圖。船舶抵港后，若為其分配的泊位空閑，則船舶進入泊位等待為其分配岸橋，否則需在錨地等待泊位空閑；船舶靠泊后，若為其分配的岸橋可用，則開始船舶裝卸作業(yè)，否則需在泊位等待岸橋可用；船舶裝卸作業(yè)完成后，則立即離港。顯然，泊位計劃和岸橋計劃共同影響著整個碼頭生產作業(yè)的效率，任一計劃的單獨最優(yōu)往往會因另一計劃未能與其完美對接而無法順利實施。泊位岸橋協(xié)調調度就是充分考慮泊位調度和岸橋分配之間相互關聯(lián)、相互影響的關系，使二者共享參數(shù)和變量，確定到港船舶的最優(yōu)停泊泊位、停泊順序以及分配給船舶的岸橋數(shù)，從而達到系統(tǒng)整體最優(yōu)狀態(tài)。

本文基于離散型泊位布局進行研究，即整個岸線被分割成若干個泊位，同一時刻每個泊位最多可?？恳凰掖埃颐克掖荒芡２丛谝粋€泊位內。由于各泊位的長度及其前沿水深不盡相同，因此，在制定船舶泊位計劃時要充分考慮船舶的安全船長和安全水深因素。

具體模型是基于以下假設建立的：（1）每艘船都必須且只能靠泊一次；（2）每艘船都有一個偏好泊位，當船舶停泊在偏好泊位時集卡的運輸距離最短；（3）船舶裝卸時間與分配給該船的岸橋數(shù)成反比；（4）在船舶裝卸過程中作業(yè)的岸橋數(shù)以及具體的岸橋不變；（5）岸橋開始作業(yè)后，在裝卸任務結束前不能中途停止；（6）不考慮多個岸橋同時作業(yè)時相互干擾對岸橋工作效率的影響。

假設（1）和（2）是泊位調度的基本假設。本文并不考慮半集裝箱船舶，因此船舶抵港后沒有移泊的必要性，而從船公司的角度，移泊會增加移泊費用和拖輪費用，為了使成本最小化，船方并不希望船舶移泊?？紤]碼頭工作人員預先制定的堆場計劃以及船舶可停泊的泊位，每艘船必然都至少有一個偏好泊位，當船舶停泊在偏好泊位時，泊位到堆場的集卡運輸距離最短。假設（3）和（6）體現(xiàn)了岸橋資源對泊位決策的影響，是模型的理想假設。對船舶裝卸時間的假設大致可分為三類：船舶裝卸時間是固定的、船舶裝卸時間與?？课恢孟嚓P、船舶裝卸時間與岸橋（數(shù)量或效率）相關。本文假設船舶裝卸時間與分配的岸橋數(shù)成反比，能夠在一定程度上更接近碼頭實際生產情況。假設（4）和（5）避免了碼頭生產作業(yè)中岸橋頻繁調度，有利于減少岸橋作業(yè)相互干擾。由于很難對岸橋間的干擾進行量化，因此假設（6）排除了干擾對模型的影響。

2.2 模型建立

圖1 集裝箱船舶在碼頭作業(yè)流程圖

模型涉及的參數(shù)：V為計劃周期內到港的船舶總數(shù)；B為碼頭可用的泊位數(shù)；T為計劃周期；Q為碼頭可用的岸橋數(shù)；ai為船舶i的預計到港時間；bi為船舶i的偏好泊位；di為船舶i的預計離港時間；VLi為船舶i的安全船長（含橫向安全預留距離）；VDi為船舶i的安全水深（含縱向安全預留距離）；BLj為泊位j的長度；BDj為泊位j的前沿水深；wi為裝卸船舶i所需的岸橋總臺時數(shù)為裝卸船舶i所需的最小岸橋數(shù)為裝卸船舶i所需的最大岸橋數(shù)；c1為船舶到港后等待靠泊的單位時間成本；c2為船舶停泊位置遠離偏好泊位的單位距離成本；c3為船舶推遲離港的單位時間成本；c4為單位岸橋單位時間裝卸成本；M為極大正數(shù)。

涉及的決策變量：Bi為船舶i的停泊泊位；Oi為船舶i的停泊順序；qi為分配給船舶i的岸橋數(shù)。

涉及的從屬變量：Ei為船舶i的停泊時間；Di為船舶i的離港時間；Uit=1表示船舶i在t時刻被服務，否則Uit=0；Uijk=1表示船舶i在j泊位按次序k被服務，否則Uijk=0。

基于以上模型假設及變量設置，本文建立泊位岸橋動態(tài)協(xié)調調度模型如下：

其中，目標函數(shù)（*）表示最小化船舶總的服務成本。式（1）表示船舶到港后才能靠泊；式（2）和式（3）表示船舶只能停泊在滿足其安全船長和安全水深的泊位；式（4）表示每艘船有且只有一次靠泊機會；式（5）表示一個泊位至多只能同時服務一艘船；式（6）定義了船舶的服務順序；式（7）避免了同一泊位服務的船舶在服務時間上的沖突；式（8）表示任意時刻作業(yè)的岸橋數(shù)不超過碼頭岸橋總數(shù)；式（9）表示必須滿足每艘船舶裝卸所需的岸橋臺時數(shù)；式（10）限制了分配給每艘船舶的岸橋數(shù)；式（11）保證了連續(xù)的船舶裝卸作業(yè)；式（12）定義了船舶離港時間；式（13）定義了船舶推遲離港的時間；式（14）～（16）定義了決策變量和從屬變量的取值范圍。

3 模型求解

鑒于模型約束較多，在算法設計中盡可能地將約束條件嵌入算法結構，從而降低模型求解難度。本文結合具體問題，設計遺傳算法對模型求解，具體步驟如下。

3.1 個體編碼及種群初始化

每個種群個體用3組染色體表示，分別對應于模型中的3個決策變量，即船舶停泊泊位、停泊順序以及分配給船舶的岸橋數(shù)。3組染色體均采用自然數(shù)編碼。例如，圖2中，船舶4停泊在2號泊位，停泊順序為4，分配的岸橋數(shù)為4臺。

圖2 種群個體編碼

個體子染色體1的每個基因值分別從滿足各個船舶安全船長和安全水深的泊位中產生，這滿足了約束條件（2）、（3）；子染色體2的基因值是自然數(shù)1到V以任意順序排成的一個序列，子染色體3的每個基因值分別從滿足各船舶岸橋數(shù)量約束的區(qū)間中產生，這兩組子染色體的生成規(guī)則滿足了約束條件（4）、（5）、（10）。這樣生成的初始種群雖然就單個基因而言都是合理的，但是組合起來幾乎不可能組成可行解，尤其是隨著問題規(guī)模的擴大，必然出現(xiàn)大量的約束沖突。因此，有必要對生成的種群個體進行基因調整以滿足所有的約束條件。

逐時刻基因調整：

為了更直觀地顯示各船舶的資源調度情況，通常采用如圖3所示的示意圖表示模型的解，其中矩形表示船舶，矩形中的數(shù)字表示船舶編號及分配給船舶的岸橋數(shù)，矩形的位置表示船舶的靠泊順序。矩形的長表示船舶的安全船長，寬表示船舶裝卸時間。考慮到離散泊位布局的特點，這些矩形塊的排列結果與矩形的長無關，因此圖3中的矩形均設置為等長。矩形的寬（船舶裝卸時間）由約束條件（9）、（11）、（12）確定，即：

于是泊位岸橋調度問題可以形象地看作矩形塊在

圖3 離散泊位下泊位岸橋調度結果示意圖

泊位-時刻空間內的排隊問題。對于生成的個體，用式（18）計算出各船舶具體的靠泊時間和離港時間，這滿足了約束條件（1）、（6）、（7）。

這樣生成的初始解只需要滿足約束條件（8）即為可行解，否則為不可行解。因此有必要對初始解進行基因調整，使得個體滿足時間T和岸橋Q之間的關系。具體采用逐時刻基因調整策略來突破T-Q關系沖突，步驟如下：

步驟1對所有船舶按照由公式（18）計算得到的靠泊時間（升序排列）重新編號。

步驟2依次對每一艘船舶構建與其有T-Q關系沖突的船舶集合，并對最晚靠泊的船舶以及與其共享泊位單元的后來船舶進行逐時刻后移，重復這一過程使得任意時刻總服務岸橋數(shù)量不超過碼頭岸橋總數(shù)。

步驟3依據(jù)新的船舶靠泊時刻更新船舶靠泊順序。

通過逐時刻基因調整方法，能夠保證個體的可行性。因此在種群的迭代過程中，也采用該方法對不可行解進行修復。

3.2 適應度函數(shù)

遺傳算法在進化搜索中基本不利用外部信息，僅以適應度函數(shù)為依據(jù)，利用種群個體的適應度來進行搜索。適應度函數(shù)的構建要能夠反映一個解的優(yōu)劣?；诒疚哪Ｐ偷哪繕撕瘮?shù)以及適應度函數(shù)非負性要求，建立適應度函數(shù)如下：

其中，f(x)為模型的目標函數(shù)，fmax為種群個體中的目標函數(shù)值最大值。

3.3 選擇操作

本文采用精英選擇+輪盤賭的策略對種群個體進行選擇。首先，對種群個體依據(jù)其適應度值降序排列；其次，選擇精英個體，根據(jù)預設的精英數(shù)量EN，選擇前EN個個體直接放入交配池中；最后，采用輪盤賭選擇策略從整個種群中選擇個體補齊交配池中的種群數(shù)量。

該選擇策略能夠有效的避免最優(yōu)個體丟失，加快種群收斂速度。

3.4 交叉和變異操作

由于種群個體由3組染色體共同表示，且3組染色體分別表示的決策變量需滿足不同的要求。因此有必要對3組染色體分別進行交叉和變異操作。

（1）子染色體1和子染色體3

子染色體1和子染色體3分別表示船舶的停泊泊位及分配給船舶的岸橋數(shù)，各基因的取值相互獨立，因此采用單點交叉法對這兩組染色體分別進行基因重組，即在染色體中隨機選擇一個交叉點，交換兩個父代染色體中的部分基因。對兩組染色體的基因變異采用單點變異法，隨機選擇一個變異點，重新生成新的基因值。

（2）子染色體2

子染色體2表示船舶的停泊順序，各基因的取值為1到V的自然數(shù)且不能重復，采用兩點交叉對該染色體進行基因重組，即在染色體中隨機選擇兩個交叉點，兩個交叉點之間的區(qū)域即為交叉區(qū)域，交換兩個父代染色體交叉區(qū)域的基因。由于各基因之間的相互關系，交叉后的子代往往會不滿足約束條件（4）、（5），需要進一步調整基因的取值。如圖4所示，兩個父代交叉后得到兩個中間代，均不符合船舶靠泊要求，其中中間代1中，O1=O3=1，O5=O7=6，中間代2中，O1=O5=2,O2=O4=4。具體的基因調整策略分為3步：（1）對比中間代與其相應父代的交叉區(qū)域的基因值，確定中間代缺失的基因和重復的基因；（2）在中間代交叉區(qū)域外，查找重復基因并確定其位置；（3）依次用中間代缺失的基因去替代上一步確定的基因。圖4中，在交叉過程中，父代1交叉區(qū)域的基因用1、5、6替換了原來的5、4、2，于是中間代1中缺失了基因4、2，重復了1、6，通過調整策略，用基因4、2分別替換交叉區(qū)域外的基因1、6，最終得到子代1，對中間代2的基因調整同理。

圖4 兩點交叉規(guī)則

表2 兩種算法求解結果對比

同樣為了保證子染色體2的變異子代符合靠泊要求，采用兩點變異，即隨機選擇兩個變異點，交換兩點處的基因值。

對于交叉和變異操作過程中產生的不可行解采用逐時刻基因調整策略（見3.1節(jié)）進行修復。依次對種群個體進行選擇、交叉和變異操作，并不斷迭代至迭代次數(shù)達到預先設定的值，算法結束。

4 數(shù)值實驗

基于某集裝箱碼頭的基礎數(shù)據(jù)設計案例，以驗證本文模型及算法的可行性和有效性。該碼頭具有離散型泊位布局，岸線長1 200 m，擁有4個泊位，12臺岸橋，1#～4#泊位長度分別為200 m、300 m、400 m、400 m，到港船舶按照船舶等級分為小船、中船和大船，船舶可靠泊泊位依據(jù)船舶等級確定，即小船可?？?#～4#泊位，中船可?？?#～4#泊位，大船可?？?#～4#泊位。以72 h為一個計劃周期隨機生成6個算例（包含的船舶數(shù)分別為10、12、14、16、18、20），且每個算例中包含不同等級船舶的比例分別為小船30%，中船50%，大船20%，船舶到港時間ai～U[1,60]，船舶服務成本參數(shù)設為c1=150,c2=100,c3=200,c4=150。其他相關參數(shù)設置如表1所示。本文算法采用MATLAB R2009a，m腳本語言編程，在英特爾Core i3 2.53 GHz雙核處理器，2 GB內存和Win 7操作系統(tǒng)下完成實驗。算法基本參數(shù)通過實驗選?。悍N群規(guī)模為200，迭代次數(shù)為1 000次，交叉和變異概率分別為0.8和0.2，精英數(shù)為40。

表1 船舶參數(shù)設置

港口工作人員在資源調度過程中通常依據(jù)先到先服務原則，采用人工貪婪算法為船舶分配泊位及岸橋。貪婪算法又叫步步最優(yōu)算法，即最先到達的船靠泊在最先可用的泊位，并在船舶裝卸要求等約束條件下分配最多的岸橋。表2給出了每個算例下本文算法與貪婪算法求解結果的對比情況。

由表2可知，針對隨機生成的6個算例，本文提出的模型和算法在船舶在港時間及船舶服務成本方面均比人工貪婪算法下獲得的結果更優(yōu)，并且隨著船舶數(shù)量的增加，本文模型及算法的優(yōu)勢更加明顯。當船舶數(shù)量為20時，本文算法較人工貪婪算法在船舶在港時間上改善了39.60%，在船舶服務成本方面改善了29.18%。

5 結論

隨著集裝箱碼頭運輸需求的日益增長，港口間的競爭越發(fā)激烈，合理配置港口稀缺資源以提高港口競爭力成為推動港口未來發(fā)展的重要手段。本文對離散泊位布局下的泊位岸橋協(xié)調調度問題進行了研究，建立了基于非線性整數(shù)規(guī)劃的泊位岸橋協(xié)調調度優(yōu)化模型，并設計了改進的遺傳算法對模型求解。運用本文算法不僅能夠簡化模型求解難度，而且較人工貪婪算法更好地改善了船舶在港時間和船舶服務成本，能夠為集裝箱碼頭的資源調度優(yōu)化提供科學合理的解決方案和決策依據(jù)。

[1]Bierwirth C，Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research，2010，202（3）：615-627.

[2]Bierwirth C，Meisel F.A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research，2015，244（3）：675-689.

[3]Liang C，Lin L，Jo J.Multiobjective hybrid genetic algorithm for quay crane scheduling in berth allocation planning[J].International Journal of Manufacturing Technology and Management，2009，16（1/2）：127-146.

[4]Liang C，Guo J，Yang Y.Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning[J].Journal of Intelligent Manufacturing，2011，22（3）：471-479.

[5]Liang C，Hwang H，Gen M.A berth allocation planning problem with direct transshipment consideration[J].Journal of Intelligent Manufacturing，2012，23（6）：2207-2214.

[6]Giallombardo G，Moccia L，Salani M，et al.Modeling and solving the tactical berth allocation problem[J].Transportation Research Part B：Methodological，2010，44（2）：232-245.

[7]Lalla-Ruiz E，González-Velarde J L，Melián-Batista B，et al.Biased random key genetic algorithm for the tactical berth allocation problem[J].Applied Soft Computing，2014，22：60-76.

[8]楊春霞，王諾.基于多目標遺傳算法的集裝箱碼頭泊位—岸橋分配問題研究[J].計算機應用研究，2010，27（5）：1720-1722.

[9]李明偉，康海貴，耿靜，等.基于多目標混沌云粒子群算法的泊位-岸橋分配研究[J].水運工程，2014（1）：90-96.

[10]Imai A，Chen H C，Nishimura E，et al.The simultaneous berth and quay crane allocation problem[J].Transportation Research：Part E Logistics&Transportation Review，2008，44（5）：900-920.

[11]Lee D，Wang H Q.Integrated discrete berth allocation and quay crane scheduling in port container terminals[J].Engineering Optimization，2010，42（8）：747-761.

[12]畢婭，李文鋒.集裝箱港口集群下多港口多泊位聯(lián)合調度方法[J].計算機應用，2012，32（2）：448-451.

[13]張紅菊，樂美龍.基于多目標粒子群算法的泊位-岸橋分配研究[J].武漢理工大學學報，2012，34（2）：59-64.

[14]Sammarra M，Cordeau J F，Laporte G，et al.A tabu search heuristic for the quay crane scheduling problem[J].Journal of Scheduling，2007，10（4）：327-336.

[15]He J.Berth allocation and quay crane assignment in a container terminal for the trade-off between time-saving and energy-saving[J].Advanced Engineering Informatics，2016，30（3）：390-405.