干擾約束下集裝箱碼頭全岸線岸橋調度研究

梁承姬，余 健

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

1 引言

近十年以來，全球集裝箱量增長迅速。2017年國內規模以上港口集裝箱吞吐量增速為8.3%，外貿集裝箱規模增長為2.37 億TEU。隨著集裝箱貿易量的不斷增長，自動化碼頭成為未來發展的一大趨勢，而傳統碼頭的改造又是發展自動化碼頭的重要組成部分，在這一過程中碼頭資源的合理利用顯得尤為重要。岸橋作為連接船舶與岸線作業的重要碼頭資源，如何高效合理地利用岸橋，對整個碼頭作業有著較大的影響。岸橋資源計劃分為岸橋分配計劃（Quay Crane Allocation Problem，QCAP）和岸橋調度計劃（Quay Crane Scheduling Problem，QCSP），而岸橋的分配與調度問題（Quay Crane Allocation and Scheduling Problem，QCASP）是對前兩者的綜合考慮，在已知船舶岸橋服務數量前提下，對岸橋進行作業任務順序的優化，使得在滿足相關約束的條件下，實現岸橋的完工時間最短的目標。

針對岸橋調度問題，Kim等[1]在其模型中，通過考慮相鄰貝位間任務的非同時性約束，來確定岸橋間的安全距離，同時提出了分支定界算法進行求解，并將計算結果與貪婪隨機自適應性搜索算法進行比較，得出分支定界法比貪婪隨機自適應性搜索算法性能要好，其缺點是無法解決較大規模的問題。Bierwirth等[2]在充分考慮岸橋干擾因素的限制下，建立了改進的岸橋配置與調度模型，同時提出了一種以分支定界法為核心的啟發式算法，計算得出了更優的解。Chung 等[3]設計了一種改進的遺傳算法，應用于岸橋調度問題，并與其他算法對比得出，該算法的性能更優。丁玲等[4]針對岸橋調度問題的特性，在模型中增加了任務的優先關系約束，并提出一種啟發式算法，結果表明該模型和算法在一定時間內能得到較優的可行解。Diabat 等[5]在考慮岸橋初始作業位置的前提下，設計了一種改進的自適應遺傳算法（Genetic Algorithm，GA），并通過與建立的數學模型計算結果對比，得出算法性能的優越性。Kaveshgar等[6]在傳統岸橋調度問題（QCSP）的基礎上，考慮岸橋作業的時間可用性，提出了帶有時間窗的岸橋調度問題，并設計了一種特殊的遺傳算法進行求解，通過對比，該算法性能更優，所得到的解質量更高。Al-Dhaheri 等[7]在調度方案中考慮了多個貝位間的任務均衡性，使得最終的調度方案更具有現實意義。Al-Dhaheri等[8]以船舶穩定性為基礎，考慮岸橋作業的沖突與移動約束，建立新的MIP模型，同時設計改進的遺傳算法進行求解。Lee 等[9]考慮岸橋調度問題中的岸橋雙循環問題，建立了一種雙機流水車間計劃模型，并通過約翰遜規則進行求解。Zhang 等[10]為岸橋調度問題設計了一種基于分區的算法，并考慮多個岸橋處理速度的不同，為岸橋劃分了相應的任務區間，以達到岸橋總體作業時間最小的目標。Ochoa-Zezzatti 等[11]針對QCSP 問題的算法求解進行了改進，設計了貪婪搜索以及蟻群相結合的啟發式算法，并通過算例驗證了改進算法的有效性。Diabat等[12]將泊位分配與QCSP問題相結合，建立了一種包含多種實際約束的數學模型，該模型更具有實用性。Al-Dhaheri[13]將船舶的穩定性引入QCSP問題中，并建立相應模型及算法，最終得出了岸橋在單貝位內的作業順序。

以上研究大多將岸橋調度與實際貝位任務量分開考慮，而涉及貝位間任務均衡的研究中，岸橋的干擾約束、作業沖突等未被充分考慮。為此，本文將從貝位任務量的角度出發，以貝位為單位將整個岸線劃分為若干區域，針對貝位任務量的動態變化，研究全岸線的多目標岸橋動態調度問題，即要求最小化岸橋最大完工時間的同時，縮短岸橋作業過程中的等待時間與移動時間，最終達到全岸線上岸橋的相互支援，從而得到最佳的岸橋調度方案。

2 問題描述

在全岸線岸橋動態調度問題中，本文從整體出發，將岸線長度和船長以貝位為基礎，劃分為若干個單位（不足一個貝位的按照一個貝位計算），并在此基礎上進行岸橋的配置與調度研究。圖1（a）為岸橋調度的初始方案，4個（臺）岸橋服務兩艘船舶，隨著任務的進行，岸橋在貝位間移動，以完成全部任務，此時岸橋作業順序的不同，會影響總體完工時間。

由于岸橋固定在軌道上，岸橋在作業過程中需考慮干擾因素，其主要為：（1）不可交叉因素，即岸橋不可跨越作業；（2）安全距離因素，即相鄰岸橋間必須保持一定安全距離。由于這些干擾因素的存在，岸橋在作業過程中會產生等待時間，也會影響岸橋總體的完工時間。圖1（b）為岸橋作業過程中存在等待時間的示意圖，QC2在完成Bj+2任務后需移動到Bj+1位置，移動時間為T(j+2)(j+1)，因為安全距離約束（安全距離為2個貝位）及不可交叉約束的存在，QC2 需等待時間為TW，使得整個完工時間延后。

本文提出了一種基于滾動計劃的全岸線岸橋的動態調度方法，以保證在決策周期內岸橋等待時間以及移動時間最小的前提下，最小化岸橋的最大完工時間。

圖1 岸橋調度示意圖

3 模型建立

本文考慮的是全岸線QCSP問題，將整個岸線劃分成若干貝位，不同類型的船舶靠泊時僅考慮所占岸線貝位數量，在船舶靠泊位置及時間已知的前提下，對全岸線岸橋進行動態調度。

3.1 模型假設

（1）岸橋被固定在同一軌道上，不可交叉，即不可跨越作業。

（2）相鄰的兩個岸橋間存在V個貝位的安全距離，即相鄰V個貝位距離內不能同時作業。

（3）兩個岸橋不能在同一時刻處理同一貝位的任務。

（4）岸橋的初始作業時刻已知。

（5）岸橋移動速度恒定，且岸橋的作業效率相同。

（6）岸橋處理每個貝位的任務時間為整數時間單位，即任務量由整數時間單位表示，單位為h。

（7）岸橋的初始位置已知。

（8）每個貝位的任務由不同岸橋在不同時刻處理完成。

3.2 集合、參數及決策變量的定義

集合、參數定義：B表示貝位集合，貝位從左到右依次編號為{1,2,…,i},i,j為貝位編號索引，i,j∈B；Q表示岸橋集合，{1,2,…,k}為岸橋編號，k∈B,岸橋編號方式與貝位編號方式一致；Pi為岸橋處理任務i的時間；li表示貝位i存在任務需要處理；表示岸橋k的初始位置；表示岸橋k在完成分配任務后的終止貝位；rk表示岸橋k開始處理任務的時間；θ表示岸橋在兩個相鄰貝位間的單位移動時間，即岸橋k從任務貝位i移動到任務貝位j所用時間為表示岸橋從初始貝位移動到第一個任務貝位j的時間，表示岸橋k完成最后一個任務貝位j后，移動到終止位置所耗費時間，理論上為0，=；V表示相鄰岸橋k和岸橋k+1 之間的安全距離，通常為1 個貝位；M表示足夠大的整數；α1表示任務最大完工時間分配的權重；α2表示分配給岸橋在岸線上移動時間的權重；α3表示分配給岸橋等待作業的時間的權重。

3.3 目標函數及約束條件

岸橋裝卸作業存在相互協調的問題，本文在各目標間設置相應的權重進行調整。

約束條件為：

式（1）表示最小化岸橋最大完工時間的同時，縮短岸橋的移動時間和等待時間；式（2）表示岸橋任務的最大完工時間為W；式（3）表示單個任務只能由一臺岸橋完成；式（4）和（5）分別說明每個岸橋的初始任務和最終任務有且只有一個；式（6）定義了任務的優先級，即任務i要先于任務j處理；式（7）表示任務j的完成時間，比任務i的完成時間加上任務j的處理時間以及岸橋在貝位i、j的移動時間要大；式（8）說明由于沖突的存在，部分任務無法同時處理；式（9）定義了岸橋作業時不能產生干涉；式（10）說明任務j的完成時間，比任務i的完成時間加上任務j的處理時間要大；式（11）表示岸橋的初始任務完成時間大于岸橋從初始位置移動到任務貝位的時間加上初始任務的處理時間；式（12）表示岸橋的最終完成時間等于最終任務的完成時間加上從該位置移動到最終位置的時間；式（13）定義了岸橋在岸線上總的移動時間；式（14）表示岸橋總的等待時間為岸橋完工時間、岸橋移動時間以及任務處理時間的差值；式（15）和（16）定義了yik和的關系；式（17）說明了岸橋處理任務存在天然的順序要求；式（18）定義了W、m、d三者的權重關系；式（19）確定岸橋在依次作業過程中，相鄰岸橋間保持V個貝位的安全距離；式（20）和（21）確保了決策變量為0-1變量以及模型中的變量均大于0。

4 算法與規則設計

考慮到問題的復雜程度，本文采用遺傳算法進行求解，并結合Meisel 等[14]提出的算法求解方案，對遺傳算法所求解的結果進行了優化。

4.1 染色體編碼

本文采用矩陣式編碼，染色體的每一行代表分配給一臺QC要處理的任務數，染色體每一列代表一個貝位，因此染色體長度與船舶貝位數相等，染色體的基因值表示QCi處理貝位Bj的任務量，0 表示沒有可處理的任務；染色體第j列基因值的和與該貝位需要處理的任務數相等，第i行的和與分配給該岸橋的總任務數相等。圖2為有3臺岸橋、10個貝位的染色體編碼。

圖2 染色體示例

4.2 適應度函數與選擇策略

適應度函數為fitness=1/(minc)，即岸橋最大完工時間、岸橋移動時間和岸橋等待時間的和最小化的倒數。此處使用的染色體僅指定QC到貝位的分配。在評估其適應性之前，必須將一個時間表與染色體關聯起來，以計算適應度值，本文采用50%的精英保留策略，在種群中選擇具有最高適應值的染色體直接保留至下一代，從而保證算法的全局收斂。

通過GA 中的目標函數（適應度函數）確定每個岸橋的初始位置、每個任務的起始和結束時間以及每個岸橋工作的位置，并存儲在矩陣數據結構中。每次岸橋需要開始處理與岸橋當前貝位不同的貝位的新任務時，它將檢查相鄰貝位（在新任務貝位的左側和右側）的任務是否有其他岸橋占用。如果因為不同岸橋執行任務干擾其移動，則檢查這些任務的完成時間。如果這些任務沒有完成，那么目前的岸橋需要等待；否則，它可以繼續移動到下一個任務的貝位并開始卸載或裝載作業。

根據岸橋的當前貝位，可將下一目標貝位與其他岸橋所在貝位，區分為以下四種干擾情況：

（1）岸橋前往其分配的任務并處理該任務；

（2）岸橋需要等待，以避免與另一臺岸橋發生碰撞，然后運行到其下一個任務位置；

（3）岸橋保持閑置狀態，并將停留在當前位置；

（4）岸橋保持閑置狀態，但需要移動以避免與相鄰的岸橋發生碰撞。

4.3 交叉與變異

因為染色體設計的特殊性，本文采用染色體基因值對應比例的組合交叉策略，并參考Tavakkoli-Moghaddam等[15]在2009 年提出的改進遺傳算法中的交叉策略，具體操作如下：

其中δ是在（0.5，1.0）之間隨機生成的常數，表示父代1擁有更好的適應性，在計算過程中采取四舍五入的方式保留基因值。圖3所示為δ=0.6 的操作過程。

圖3 交叉

變異則是采取交換變異的方式，隨機選擇第i行的兩個基因值，最小的基因值與對應的第i+1 行的基因值交換位置，最大的基因值與對應的第i-1 行的基因值交換位置；若所選行為首行或末行，則在此兩者相互為最大值與最小值對應基因位互換。圖4為變異操作過程。

圖4 變異

4.4 結束規則

按照改進的算法步驟，以適應度函數為衡量標準，在初始種群的基礎上產生新的種群，從而保證種群的多樣性，在算法達到最大迭代次數時，算法將終止迭代。

5 算例與結果分析

為了驗證本文所提出的模型及算法的可行性，設計了不同情形及規模的算例。岸橋開始作業時刻在不同算例中不同，相鄰岸橋間存在1 個貝位的安全距離，同時岸橋在相鄰貝位間的移動時間固定為1 個時間單位。模型中設定的目標函數權重分別為α1=0.6，α2=0.2，α3=0.2。

遺傳算法的參數為交叉概率0.9，變異概率0.2，種群大小為150，最大迭代數為300。實驗在Intel?CoreTMi5 的處理器、內存 4 GB 的 PC 上進行，采用 Matlab2018a編程實現。

5.1 小規模算例

岸線作業區域為10 個貝位，岸橋數為3，每個貝位的任務量如表1所示。分別計算遺傳算法與Cplex的結果，并進行比較，如表2所示。

表1 貝位任務數

表2 遺傳算法與Cplex求解結果對比

由上述對比結果可知，兩者的求解結果一致，但Cplex的計算時間要更短。調度方案如圖5，遺傳算法的收斂結果如圖6。由算法收斂圖可知，大約在140 代得到最終收斂結果，避免了前期的局部最優解。最終方案中岸橋1的作業路徑為4-2-1；岸橋2的作業路徑為7-5-4；岸橋3的作業路徑為10-8-7。岸橋最大完工時間為24，船舶1的完工時間為22個時間單位，船舶2的完工時間為24 個時間單位，在整個作業過程中岸橋的等待時間為0，岸橋1、岸橋2和岸橋3的移動時間都是3個單位。

圖5 調度方案示意圖

圖6 算法收斂圖

5.2 大規模算例

岸線長為40個貝位，岸橋數為10臺，表3所示為每個貝位的任務數，表4為船舶計劃，計算結果見表5。

表3 貝位任務數

表4 船舶計劃

表5 岸橋作業路徑及時間

在大規模算例計算中，依據遺傳算法的結果得到調度方案如圖7。最終方案中船舶1的完工時間為22個時間單位，船舶2 的完工時間為24 個時間單位，船舶3 的完工時間為18 個時間單位，船舶4 的完工時間為21 個時間單位，船舶5 的完工時間為16 個時間單位，在整個作業過程中岸橋的等待時間為7個時間單位。

圖7 調度方案示意圖

表5 為岸橋的作業路徑及完工時間表。由表可知岸橋的最大作業時間為26 個單位時間，主要原因為兩艘船舶先后靠泊在20～30 貝位的位置，導致任務量增加；移動時間受到任務貝位數影響，呈現明顯的正相關趨勢；等待時間均處于較低水平。

表6 為全岸線調度與傳統調度方案的結果對比。與傳統方案對比，相同規模的算例下，傳統調度的總完工時間要多于全岸線調度的總完工時間。由圖8可知，隨著算例規模的擴大，全岸線調度方案的優越性越明顯，同時全岸線調度能夠在規定周期內對船舶進行完工作業。

表6 全岸線調度與傳統調度對比

圖8 不同調度方式完工時間比較圖

6 結束語

本文對集裝箱港口的全岸線岸橋調度問題進行了研究，考慮到岸橋作業過程中的安全距離、不可交叉等約束，以減少岸橋的等待時間、移動時間以及最小化岸橋最大完工時間為目標，建立了混合整數規劃模型，同時設計了改進的遺傳算法進行求解。結果表明，該模型可以有效解決岸橋的分配與調度問題，并且隨著問題規模的擴大，算法的優越性越明顯。通過算例驗證了本文研究可以為全岸線岸橋的調度方案提供科學合理的決策依據。另外，由于岸橋裝卸時間受AGV調度的影響，后續將考慮在貝位任務量的基礎上，進行全岸線岸橋與AGV的聯合調度研究。