考慮時間窗的集裝箱港口場橋全局調度優(yōu)化

梁承姬，黃 帥

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

1 引言

隨著經濟全球化以及信息技術的不斷發(fā)展，特別是中國持續(xù)推進對外開放以及“一帶一路”倡議使得貨物貿易需求迅速提升，中國港口得到了快速發(fā)展。但伴隨著激烈的市場競爭，高效率運作對于港口的作用越來越突顯。場橋作為港口的昂貴資源，對堆場物流系統(tǒng)甚至是整個港口物流系統(tǒng)都起著推動作用[1]。高效的場橋調度計劃能夠使得場橋與其他機械設備資源更好地協(xié)調工作，在滿足實際約束的情況下盡可能地縮短船舶的在港裝卸時間，加快貨物的運轉周期。

在前期研究中，為了簡化問題難度，大多數學者針對單個場橋進行調度優(yōu)化研究。Ng W C等[2]考慮集裝箱任務準備時間不同情況下的場橋調度問題，通過分支界定法對模型求解。Huang等[3]針對單場橋調度問題提出了兩種改進最小成本的啟發(fā)式算法。韓曉龍等[4]分別運用啟發(fā)式算法和模擬退火算法對單箱區(qū)單場橋調度問題進行研究，通過結果對比分析得出模擬退火算法在運算時間和路徑優(yōu)化方面都優(yōu)于啟發(fā)式算法。

隨著航運業(yè)的發(fā)展以及信息化技術水平的提高，專家學者開始研究多場橋并行調度問題，考慮了場橋同時作業(yè)的安全距離等限制條件。Li Wenkai 等[5]利用滾動時域算法研究單個箱區(qū)內多場橋調度問題。Wu Yong等[6]則在文獻[5]的基礎上，將提箱延遲任務數考慮到目標函數中并用啟發(fā)式算法進行求解。劉志雄等[7]設計了一種三維坐標表示方法來確定場橋移動過程中的位置，從而利用混合演化算法求解得到最優(yōu)的場橋轉場次數及作業(yè)完工時間。梁承姬等[8]研究單個箱區(qū)中多臺場橋在干擾情況下基于混堆模式的存取箱同時進行的調度問題。邵乾虔等[9]將進口箱場橋作業(yè)調度問題分解成場橋路徑優(yōu)化問題和貝內翻箱作業(yè)優(yōu)化問題，建立動態(tài)優(yōu)化模型。Speer等[10]通過仿真模型詳細討論了場橋移動干涉等約束，并提出用分支定界法求解場橋的實時調度問題。初良勇等[11]研究在外集卡預約模式下的多箱區(qū)多場橋調度，利用模擬退火算法進行求解，并與實際人工操作對比，從而驗證算法的有效性。曹朋亮等[12]考慮了集卡作業(yè)面模式下的場橋與集卡聯(lián)合調度，利用改進遺傳算法確定場橋作業(yè)量，進而得到優(yōu)化后的場橋最短行駛路徑。初良勇等[13]在文獻[11]的基礎上設計了基于遺傳算法的模型，并與文獻[11]的結果對比，驗證該方法可以大幅度降低成本。

綜上，現(xiàn)有關于場橋調度的文獻大部分都是以場橋路徑最短或者場橋完工時間最小化為目標。但隨著港口信息化水平的不斷提高，集裝箱港口開始采用外集卡預約模式，這也意味著可以提前確定集卡運輸集裝箱任務的到達時間和總任務量，集卡與場橋之間的匹配度可以進一步優(yōu)化，從而提高場橋的作業(yè)效率。但是當前很少有文獻考慮到了這一因素。因此本文針對多箱區(qū)多場橋調度問題，考慮到場橋在箱區(qū)內與箱區(qū)間作業(yè)的干涉約束，根據集卡到達時間（即準備時間），提出了計劃時間段和基于集裝箱任務組的時間窗，并采用遺傳算法求解以場橋移動成本及延誤成本最小化為目標的模型。

2 問題描述

后方堆場作為存儲或者中轉集裝箱的場地，在整個碼頭中處于核心地位。而場橋是堆場中進行集裝箱堆取作業(yè)的機械設備，其工作效率的高低直接影響到堆場乃至整個港口的服務水平。由于堆場內集裝箱裝卸任務工作量分布不均勻，場橋需要在箱區(qū)間頻繁進行移動。而場橋在箱區(qū)間的移動和轉彎會占用大量的時間和空間，容易導致堆場通道堵塞，進而增加場橋與集裝箱任務組之間的相互等待時間。

因此本文提出了計劃時間段和時間窗的概念，在考慮場橋移動成本最小的基礎上最小化兩者相互等待成本，同時考慮到多箱區(qū)多場橋作業(yè)過程中不可跨越和保持安全距離等現(xiàn)實約束。根據上海某集裝箱港口的實際數據，研究在某一個計劃時間域內（本文選取4 h）按照各個集裝箱任務組的準備時間劃分成四個計劃時間段：0～60，60～120，120～180，180～240，各個任務組要在其對應的計劃時間段內分開完成調度。在每個計劃時間段再按各個集裝箱任務組的準備時間設計一個時間范圍（即時間窗），若場橋在這個時間窗外作業(yè)則給予一定的單位時間成本處罰。如圖1所示，集裝箱任務組最早能被服務的時刻即為其準備時間，最晚被服務時刻是任務組等待時間上限。但集裝箱任務組實際開始操作時間則為任務組最早能被服務時刻與場橋到達時刻兩者之間的較大值。

圖1 集裝箱任務組時間窗示意圖

3 模型的建立

3.1 模型假設

（1）本文研究的堆場區(qū)域如圖2所示。

（2）堆場上場橋操作的集裝箱都是20 英尺標準集裝箱，且按照不同類型不同目的地將同一箱區(qū)同一貝位的集裝箱作為一個任務組來處理。

（3）所有場橋的工作參數都是相同的，包括移動速度，進行轉場作業(yè)時的轉彎時間，操作集裝箱的時間都是固定值。

（4）不考慮由于設備新舊程度不同而可能導致的能耗不同，每臺場橋的移動成本相同。

圖2 集裝箱港口堆場示意圖

（5）規(guī)定每臺場橋初始時刻位于要操作的第一個集裝箱任務組貝位，結束所有分配任務后位于最后一個集裝箱任務組貝位。

（6）場橋操作完集裝箱任務組i 后隨即按最短路徑移動到下一個任務組j 所處的貝位。

（7）設定場橋在水平方向箱區(qū)間的移動距離按貝位差進行計算，在垂直方向箱區(qū)間的移動距離按箱區(qū)通道和箱區(qū)寬度計算。

（8）集裝箱任務組的準備時間根據集卡預約時間轉變而來，假定其在堆場所處位置都是已知且固定不變的。

（9）本文不考慮每個計劃時間段內有未完成的任務情況，即在每個時間段結束時場橋必須完成當前時間段內的所有任務。

（10）每個計劃時間段被分配的集裝箱數量不能超過任一場橋在該時間段的總工作能力（即每小時場橋最多可處理20個集裝箱任務的裝卸）。

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

（1）參數

c,c′：場橋，c,c′∈C；

b：箱區(qū)，b ∈B；

k：計劃時間段，k ∈K ；

i,j,o：集裝箱任務組，i,j,o ∈M ；

pi：集裝箱任務組i 包含的集裝箱數；

TGk：k 計劃時間段內集裝箱任務組總數；

Bp：垂直方向中間通道寬度；

Bw：單個箱區(qū)的寬度；

l：單個貝位的長度；

u：單個箱區(qū)的貝位數；

mi：集裝箱任務組i 所對應的貝位；

ni：集裝箱任務組i 所對應的箱區(qū)；

Tturn：場橋轉場作業(yè)時2次轉彎90°的總時間；

q：場橋操作單個集裝箱的時間；

v：場橋移動速度；

W1：場橋移動成本；

W2：場橋到達時間早于集裝箱任務組準備時間的單位時間懲罰金額；

W3：超過集裝箱任務組等待時間上限的單位時間懲罰金額；

ETi：集裝箱任務組i 的準備時間（即集裝箱任務組i 最早被服務時刻）；

LTi：集裝箱任務組i 最晚被服務的時間上限；

Sic：場橋c 操作集裝箱任務組i 的開始時刻；

OTi：集裝箱任務組i 的操作時間；

FTi：集裝箱任務組i 的操作完成時刻；

MTij：場橋從集裝箱任務組i 移動到任務組j 的時間；

dij：場橋從集裝箱任務組i 移動到任務組j 的距離；

（2）集合

C：堆場箱區(qū)內可工作的場橋集合；

B：堆場箱區(qū)集合；

K ：計劃域內計劃時間段集合；

M ：集裝箱任務組集合；

Mk：k 計劃時間段內集裝箱任務組集合；

Mkb：k 計劃時間段內b 箱區(qū)的集裝箱任務組集合；

Nc：場橋c 操作的集裝箱任務組集合；

（3）決策變量

Vcibk：0-1，若在b 箱區(qū)k 計劃時間段內場橋c 操作集裝箱任務組i 則為1，否則為0；

Uijbk：0-1，判斷在b 箱區(qū)k 計劃時間段內的集裝箱任務組i,j 是否同時被處理，當FTj≥FTi-OTi且FTi≥FTj-OTi時則為0，否則為1；

xijc：0-1，若場橋c 操作集裝箱任務組i,j 且操作順序為i →j 時則為1，否則為0。

ωic：0-1，若場橋c 操作集裝箱任務組i 時則為1，否則為0。

3.3 目標函數和約束條件

其中：

其中：

式（1）借鑒了文獻[11]的目標函數，其中第1部分表示最小化場橋的移動成本，第2 部分在第1 部分基礎上最小化場橋與集裝箱任務組之間的相互等待成本。

本文將集裝箱任務組按計劃時間段分批次分批量進行作業(yè)從而減少場橋在箱區(qū)間頻繁進行轉場作業(yè)：約束條件（2）表示在任一時間段內場橋處理的集裝箱任務組數；約束條件（3）保證在任一計劃時間段內任意一個集裝箱任務組只能分配給一臺場橋進行作業(yè)；約束條件（4）保證任一計劃時間段內一臺場橋只能同時操作一個集裝箱任務組；約束條件（5）保證在任意時刻不同場橋間須保持一定的安全作業(yè)距離；約束條件（6）保證任一計劃時間段內每個箱區(qū)至多有2 臺場橋同時工作。在每個計劃時間段內再采用時間窗對場橋作業(yè)進行約束：約束條件（7）和（8）表示任一場橋進行作業(yè)時至多有一個緊前作業(yè)和緊后作業(yè)；約束條件（9）表示任一場橋進行作業(yè)時至少有一個緊前作業(yè)或緊后作業(yè)；約束條件（10）定義了相關變量之間的關系；約束條件（11）定義了同一場橋處理前后兩個集裝箱任務組的作業(yè)時間關系；約束條件（12）保證任一集裝箱任務組等待被操作的時間不能超過等待上限。

4 遺傳算法的實現(xiàn)

由于場橋全局調度問題是一個NP 難的問題，在以往的研究中通常采用智能優(yōu)化算法求解。而針對本文模型特點，遺傳算法不僅能將約束條件嵌入算法結構中，解決其高復雜度性，而且能提高在解的空間中的搜索次數，增加搜索到最優(yōu)解的概率，縮短優(yōu)化時間。并且根據參考文獻[13]有專家學者采用遺傳算法進行求解并獲得了較好的結果。因此本文考慮使用遺傳算法來解決這個問題。

4.1 染色體編碼

首先對集裝箱任務組和場橋進行編號，根據不同計劃時間段劃分集裝箱任務組，然后將不同時間段的任務組分配給相應的場橋并按照一定的順序進行場橋調度作業(yè)。如圖3 所示，本文采用二維整數形式編碼，分別用來表示集裝箱任務組以及場橋的作業(yè)順序。其中染色體中非0的基因值表示集裝箱任務組和場橋的編號，而染色體中的間隔符“0”則將染色體分為4 個部分，從左往右分別表示第1～4 個計劃時間段的場橋調度計劃。例如第一段染色體表示在第一個計劃時間段內場橋1 做任務組9，場橋2 做任務組3，場橋3 做任務組16和5，場橋4 做任務組13，其中場橋3 先做任務組16，再做任務組5。

圖3 染色體編碼示意圖

4.2 生成初始種群

初始種群的產生和選擇對算法的實現(xiàn)有很大的影響。通常會采取兩種方式生成初始種群：（1）啟發(fā)式方法；（2）隨機生成法。前者雖然能生成更高質量的初始個體，但是容易陷入局部最優(yōu)解，而后者則有利于初始種群的多樣性。因此本文采用隨機生成法在滿足基本約束條件的情況下生成初始種群，并且規(guī)定可行解只是初始種群的一部分，具體規(guī)則如下：

（1）對于染色體中集裝箱任務組的優(yōu)先級部分，首先根據每個計劃時間段劃分集裝箱任務組數確定間隔符號“0”的基因位，然后在每個時間段內隨機排列被分配的集裝箱任務組編號，并且要滿足約束條件（3）。

（2）場橋部分則按照各個時間段內的集裝箱任務組隨機產生可工作的場橋編號，但要保證在該計劃時間段內分配給場橋的任務數不能超過場橋的工作能力。

4.3 適應度計算

遺傳算法中適應度函數值來評價一個個體（解）的好壞，其直接關系到最終解的質量和搜索效率。本文選取目標函數的值作為適應度值，在計算適應度值時，需要判斷是否滿足模型中的約束條件：（1）通過設定時間步長，每隔一定的時間間隔確定堆場內場橋所處的貝位，再計算場橋之間是否處于同一箱區(qū)以及是否保持一定的安全距離；（2）利用拉格朗日松弛法引入一個很大的正數作為懲罰項來限制每個計劃時間段結束時場橋必須完成該時間段內的所有任務組，而對于場橋提前到達或者延誤的情況，則分別設置相應的單位時間懲罰金額。

4.4 遺傳操作

4.4.1 選擇操作

本文采用輪盤賭法進行選擇運算，其主要思想是根據每個染色體的適值比例確定該個體的選擇概率或者生存概率[14]，將父代染色體和子代染色體按適應度值大小進行排序，從中選擇適應度好的個體組成新的種群。

4.4.2 交叉操作

本文采用雙切點交叉法，具體步驟如圖4所示。其中未交換的染色體片段按映射關系恢復合法性時只針對集裝箱任務組，而場橋部分不變更。

4.4.3 變異操作

圖4 交叉操作示意圖

變異運算是產生新個體的輔助方法，它有助于提高局部搜素能力，同時保持種群的多樣性，防止發(fā)生早熟現(xiàn)象。本文采用逆轉變異法[15]，即在染色體場橋部分中隨機選擇兩點，將其基因值進行對換，這也用于解決染色體中出現(xiàn)場橋之間相互跨越現(xiàn)象。如圖5所示，場橋3在去往任務組16作業(yè)的移動過程中會與場橋1前往任務組9的途中發(fā)生場橋跨越，此時若在保證在該計劃時間段內完成所有任務組的前提下，將其換成其他可工作的場橋4，則可把上面的不可行解轉化成可行解，從而在一定程度上保持了種群的多樣性。但由于染色體中的間隔符“0”沒有實際意義，所以規(guī)定在變異操作中不能選擇“0”基因位進行交換。

圖5 變異操作示意圖

4.4.4 基因修復

在經過交叉和變異操作以后，可能會產生一些不符合約束條件的染色體，因此需要進行基因修復：

步驟1 在交叉后，若交換的染色體片段正好是“0”基因位，則意味著交叉無意義。因此需要重新生成新的切點。同理在變異操作中若交換的兩基因位值相等，也需要重新隨機生成交換點。若不存在這種情況則轉到步驟2。

步驟2 在交叉變異后，需要判斷相鄰兩個“0”基因位之間的染色體片段中是否滿足假設條件（10）。若不滿足，則需要將超出場橋工作能力的集裝箱任務分配給這個時間段相對任務最少的場橋。

4.5 結束規(guī)則

通過以上操作產生的新個體將會替代原先種群中適應度較差的染色體，這個迭代過程持續(xù)到最大迭代次數時停止。

5 算例與結果分析

本文采用上海某集裝箱港口的實際運營數據進行研究，通過與實際作業(yè)情況以及其他算法的優(yōu)化結果進行對比進而驗證上述所提模型和算法的有效性和適用性。運行環(huán)境為Intel?CoreTMi5處理器、內存8 GB、硬盤128 GB的個人計算機，使用Matlab2016a運行本文的遺傳算法來求解算例。

5.1 輸入數據

本文選取該港口堆場中某塊區(qū)域的6 個箱區(qū)進行研究，數據規(guī)模為：每個箱區(qū)由60 個貝位組成，每個貝位又由6 列組成。為了便于后續(xù)計算場橋在箱區(qū)間作業(yè)的移動距離，本文設定水平方向的中間過道為3個貝位距離，垂直方向的中間過道為2個貝位距離。在計劃時間4 小時內處理200 個集裝箱任務數量，可用的場橋數量為4 臺，每臺場橋處理單個集裝箱的操作時間為3 min，假定集裝箱任務組要在其準備時間后的30 min內被服務[13]，場橋移動成本、場橋與任務組相互等待的懲罰金額等數據在算法主程序中給出，其他輸入數據見表1～6。

表1 箱區(qū)1任務量數據

表2 箱區(qū)2任務量數據

表3 箱區(qū)3任務量數據

表4 箱區(qū)4任務量數據

表5 箱區(qū)5任務量數據

表6 箱區(qū)6任務量數據

5.2 結果分析

針對本文模型，在算法中設置了相應的參數：種群大小N=300，迭代次數G=500，交叉概率PC=0.85，變異概率PM=0.2。通過Matlab運行求解，得到遺傳算法的結果收斂圖，如圖6所示。由算法收斂圖中可以看到，大約迭代到130 代時得到最終的收斂結果，避免了前期陷入局部解。

圖6 GA收斂圖

根據本文模型和所設計的算法得到計劃時間域內的作業(yè)任務分配以及場橋的作業(yè)順序。如圖7 是各個計劃時間段內場橋調度甘特圖，可以看出該結果既滿足模型中分配給場橋的任務數不超過其工作能力的要求，也滿足每個集裝箱任務組在計劃時間段結束的約束。

為了更加清楚直觀地看到場橋的作業(yè)任務順序，如圖8～11所示為各個計劃時間段內分配給各個場橋作業(yè)的集裝箱任務組及其開始時刻和結束時刻，圖中的數字分別對應算例中的任務組編號，灰色空白部分則為場橋與集裝箱任務組之間的相互等待時間。其中選取集裝箱任務組準備時間和場橋到達任務組對應貝位時間這兩者中較大的值作為每個任務組開始操作的時間，從而得到每個集裝箱任務組的開始時刻，再根據表格里任務組對應的數量得到場橋操作時間和結束時刻。

圖7 計劃時間域內場橋調度甘特圖

圖8 計劃時間段1內各場橋調度方案圖

圖9 計劃時間段2內各場橋調度方案圖

圖10 計劃時間段3內各場橋調度方案圖

圖11 計劃時間段4內各場橋調方案圖

為了進一步驗證本文所提模型與算法的有效性，將遺傳算法所得結果與實際運營操作進行對比，結果見表7所示。從表7 中可以看出不論是在作業(yè)時間還是目標函數值方面，本文采用的遺傳算法都使得結果更優(yōu)化，不僅縮短了場橋作業(yè)時間，而且大幅度降低了運營成本。

表7 運算結果對比表

為了驗證模型與算法的適用性和穩(wěn)定性，選取了8個試驗腳本，采用遺傳算法和粒子群算法分別針對不同規(guī)模大小的算例進行試驗對比，每個腳本下的目標函數值均采取試驗10 次取最優(yōu)值的方法，CPU 時間取值則為10 次試驗結果的平均值，具體結果如表8 所示，其中S 為箱區(qū)數，Y 為場橋數，T 為總集裝箱任務數。

表8 GA與PSO試驗結果對比

從表8 中可以看到，對于場橋全局調度問題，結果表明這兩種算法的結果幾乎一致。在這八組試驗腳本中，每組遺傳算法求解得到的解和粒子群算法的解都相差不大，但遺傳算法的運行時間相對較快些，并且其收斂速度更快，從而驗證了遺傳算法在求解本文所提出的場橋全局調度模型時的穩(wěn)定性和有效性。

6 結語

本文針對某計劃時間域內集裝箱港口的全局場橋調度問題進行了研究?？紤]到場橋作業(yè)過程的不可相互跨越和保持一定的安全距離等約束，引入計劃時間段和時間窗的概念，以場橋移動成本和場橋與集裝箱任務組之間相互等待成本最小化為目標建立了優(yōu)化模型，并設計遺傳算法進行求解，結果表明該模型和算法可以有效解決多箱區(qū)多場橋調度中場橋相互干擾和安全距離等問題，并且有效減少了不必要的等待時間，為解決大規(guī)模的場橋調度問題提供了科學合理的決策依據。但在實際操作中，場橋的工作效率還受眾多不確定因素的影響，例如機械設備故障或者船舶提前進港等情況，因此未來可以考慮不確定因素影響下的集卡與場橋聯(lián)合調度，從而更加優(yōu)化集裝箱港口的堆場操作。