基于網絡流的自動化集裝箱碼頭堆場空間分配

梁承姬 賈 茹 盛 揚

(上海海事大學物流研究中心 上海 201306)

0 引 言

隨著經濟的發展，碼頭的集裝箱處理量大幅增長，但堆場的面積卻相對有限。同時，由于人工成本快速上漲、船舶大型化加速，碼頭自動化成為業界關心的話題。由于船邊作業的干擾因素較多，堆場的自動化就成為自動化碼頭重點關注的領域。本文以2017年試運營的洋山港四期全自動化集裝箱碼頭為背景，對自動化集裝箱碼頭的堆場堆存問題進行研究。

國內外對堆存計劃的研究大多是針對傳統集裝箱碼頭的。李建忠等[1]為平衡堆場的集裝箱數量和最小化集卡的運輸作業距離，建立堆場空間動態分配模型，并應用數學規劃法求解。王孟昌[2]將堆場箱位動態分配問題分為箱區分配和箱位選擇。在計算箱區分配時，建立平衡箱區間作業量模型和最小化箱區泊位間距模型。接著，以翻箱量最少為目標建立了箱位選擇模型，并采用啟發式算法和模擬退火算法求解。Jo?rg Wiese 等[3]分別研究了平行分布和垂直分布的箱區運輸通道的資源優化問題，提出了關于堆場布局的整數線性規劃問題，并用一種啟發式算法求解。Nils[4]研究了自動化軌道吊對堆場箱區作業效率的影響，使用仿真的方法模擬了堆場箱區的作業情況，并評估比較了四種具有不同自動化軌道吊的堆場箱區對集裝箱碼頭性能的影響。Yu等[5]針對進場集裝箱的空間分配問題提出了一個優化方法，提高檢索進場集裝箱的操作效率，減少預期的外部集卡的等待時間。周鵬飛等[6]為優化卸船箱箱位分配，減少翻箱率，考慮客戶提箱順序的隨機和不確定性，建立船舶卸載箱位整數規劃模型，采用啟發式算法來求解。結果表明能有效減少翻箱率。對于網絡流問題，趙禮峰等[7]給出了一種求解網絡最小費用最大流的新方法，令該算法易于理解，且能夠避免最小費用路算法需要對剩余網絡進行增廣的不足之處，提升了算法效率。Han等[8]提出基于不確定性理論框架去解決一個不確定網絡中的最大流問題。

目前國內外將自動化集裝箱碼頭的堆存問題按其特點轉化為網絡流問題進行研究的較少。自動化集裝箱碼頭的箱區呈垂岸式分布，進出口箱混堆模式。從箱區的布局圖1中可以看出，按兩臺起重機的作業范圍可分為海側，交換和陸側作業區域。由于集裝箱只能從箱區兩端進出，在這三個區域流入與流出的集裝箱量均相等。因此在制定堆存計劃時需要考慮所有箱區之間的作業量和單個箱區作業的進出口箱量的平衡，以滿足箱區海側起重機作業的重進重出。本文提出基于網絡流的自動化集裝箱碼頭堆場空間動態分配的模型，并用禁忌搜索算法來求解，突出了自動化集裝箱碼頭堆場的布局特征以及在制定堆存計劃時的特點。

圖1 箱區示意圖

1 問題描述

自動化集裝箱碼頭的堆場堆存計劃可以視為一個具有時間和空間維度的網絡優化問題。如圖2所示，本文將具有相同屬性的集裝箱歸并為一個集裝箱組k。這里的相同屬性可以是箱子重量、箱子種類和箱子的目的港等。起始節點和結束節點分別標注為Sk和Tk。集裝箱組k在時間點ak到達碼頭，并在時間點bk離開堆場。它的停留期間是從ak到bk，每一個時段都有m個備選的堆場箱區來存儲這一組集裝箱。從起始節點到結束節點的路徑對應這組集裝箱到達泊位以后在堆場的堆存計劃。泊位和堆場之間的弧形虛線箭頭代表碼頭和堆場之間的移動，堆場箱區之間的弧形虛線箭頭代表連續時間段內的集裝箱組的再分配。弧形的成本取決于兩個節點之間的作業距離與作業成本。圖2中實線箭頭表示的路徑顯示了一組集裝箱的一個可行的泊位配置和堆存計劃。如圖2所示，集裝箱組k到達泊位1，從進港船舶上卸載后分配給堆場1，然后停留在堆場1中直到時間點bk-1被重新分配給堆場2，最后一直停留在堆場2直到時間點bk被分配到虛擬節點2，即被外集卡裝走。

圖2 箱區網絡節點示意圖

2 模型建立

本模型意在實現集裝箱組在泊位-箱區間、箱區-箱區間的運輸總成本最小以及集裝箱組在堆場箱區的合理分散。

2.1 模型假設

(1) 已知某一天進港船舶預靠的泊位；

(2) 已知船舶各時間段要完成的進口箱組數量和出口箱量組數量；

(3) 時間段t內裝卸移動的集裝箱組均在該時段完成作業；

(4) 已知每個集裝箱組包含的集裝箱數量；

(5) 所有集裝箱組包含的集裝箱不分類型，統一尺寸定為20尺。

2.2 符號說明

參數：M：箱區

N：泊位

T：時間周期

K：集裝箱組

ak：集裝箱組的到達時間，ak∈T

bk：集裝箱組的離開時間，bk∈T

qk：集裝箱組k包含的集裝箱數量

ok：卸載集裝箱組k的進口船

dk：卸載集裝箱組k的進口船

rk：集裝箱組k允許在堆場箱區間重新分配的最大次數

αkl：如果集裝箱組k和l從相同的進口船被卸載則為1，反之則為0，k,l∈K

βkl：如果集裝箱組k和l衩裝卸到相同的進口船則為1，反之則為0，k,l∈K

γkl：如果集裝箱組k的進口船和l的進口船相同則為1，反之則為0，k,l∈K

δ：岸邊和箱區之間允許行駛的最大行駛成本

ω1：箱區重進重出的權重系數

ω2：箱區作業量平衡的權重系數

h：平衡箱區作業成本和箱量的權重系數

決策變量：

2.3 目標函數及約束條件

目標函數：

Z=min(Z1+h×Z2)

(1)

約束：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

式(1)的目標函數表示的是最小化泊位和箱區，箱區和箱區之間的運輸成本;平衡單個箱區和所有箱區的進出口箱量。

式(2)約束了開始節點的流出需求。式(3)約束了結束節點的流入需求。式(4)表示箱區之間的流量守恒。式(5)、式(6)定義了決策變量Z、U、V之間的關系以及箱區里進、出口箱量的定義。式(7)、式(8)定義了決策變量U、V、X之間的關系，表明從泊位i到箱區j的集裝箱組必然從箱區j移動到箱區i。從箱區i到泊位j的集裝箱組在前一個時段必然從箱區j移動到箱區i。式(9)、式(10)指定了泊位和箱區之間的行駛成本要求，確保堆存的箱區離船舶的距離不會過遠。式(11)、式(12)、式(13)定義了代表集裝箱位置的決策變量W，箱區之間的位置；出口箱在離開時的位置；在泊位作業的進口箱和出口箱。式(14)表示同一時段內所有集裝箱組需要的存儲空間不能超出箱區存儲能力。式(15)表示同一時段內所有集裝箱組需要的處理量不能超出泊位處理能力。式(16)表示同一時段內所有集裝箱組需要的處理量不能超出箱區處理能力。式(17)定義了集裝箱組的重新分配次數不能超過最大允許重新分配次數。式(18)定義了有相同進口船或出口船的集裝箱組的泊位分配約束。式(19)定義了決策變量的范圍。

3 基于禁忌搜索算法模型求解

禁忌搜索算法通過采用禁忌表來記錄被禁止的對象，避開局部最優解從而找到總體最優解。被放入禁忌表的是屬于被禁止的局部最優解。進入禁忌表的對象在接下來的若干個迭代次數內被禁止，從而避免陷入局部最優解的循環。本文的禁忌長度數值為一個常數，具體數值根據問題的規模大小來確定。

3.1 禁忌搜索算法的使用

將自動化集裝箱碼頭堆場的堆存計劃轉化為網絡流問題，得到泊位與箱區之間、箱區與箱區之間的集裝箱堆存總成本以及堆場箱區的“重進重出”和作業量均衡。

禁忌算法的初始解可以通過隨機生成得到，但是通過改進初始解的生成可以提高搜索效率。在堆存策略制定的初始階段，本文采用指派模型來生成初始解，通過該方法生成的初始解來進行搜索可以提高整體的運算效率。堆存計劃的集裝箱組分配的初始解采用貪婪算法獲得，在貪婪算法中，按次序將待分配的集裝箱組依次分配到滿足容量的距離最近的堆場箱區。

圖3展現了一個在三個時間段中兩個集裝箱組分配到兩個箱區的例子。堆場容量被假設為是相同的，都為Q。在網絡容量充足的情況下，集裝箱組1首先被裝載到網絡，它的最小成本路徑：S1→(2,1)→(2,2)→(1,3)→T1，如圖3(a)中實線箭頭所示。然后，網絡的裝載能力被更新，如圖3(b)所示，集裝箱組2被裝載到網絡中。由于裝載能力有限，集裝箱組只有一個可行路徑：S2→(1,2)→(2,3)→T2。最后，網絡剩余量如圖3(c)所示，并且通過相加兩個路徑的成本，可以得到目標函數值。必須注意的是：對集裝箱不同的裝載次序會導致不同的解決方案和目標值。

圖3 網絡節點示意圖

如何選擇一個好的次序將集裝箱裝載到網絡中去是一個非常關鍵的問題，通過這樣可以得到一個近似最佳方案。在這一階段中，禁忌搜索方法被用作去尋找好的裝載次序。一個裝載次序可以影響集裝箱裝載到網絡中的次序。越先被運輸的集裝箱組就會有越大的網絡容量。這表明越先裝載的集裝箱組，其優先級就越大。在每一次鄰域搜索循環中產生鄰域方案，并且在循環中評估它。

3.2 編碼方式

L=(p1,p2,…,p|k|)，集裝箱組pi是第i個被裝載到網絡中的。例如：L=(2,3,1)，表示集裝箱組2是在網絡裝載能力充足時第一個被裝載到網絡中的，集裝箱組3是第2個被裝載的，集裝箱組1是最后一個。

3.3 鄰域結構

禁忌搜索算法是一種基于鄰域搜索技術的算法，本文采用兩兩交換來實施操作。這種方法是通過隨機選擇任意兩個對象并交換其數值的操作方式。具體的操作方式如圖4所示。

圖4 交叉操作示意圖

3.4 適應度評價

根據集裝箱組被裝載到網絡中的次序，采用表1的方法來計算適應度。在該算法中，最重要的一個步驟就是去尋找集裝箱組的一個最小成本路徑。由于節點的容量有限，所允許的再分配的次數會限制到路徑的選擇。

表1 適應度評價方

階段變量：時間t∈T

階段變量：節點(i,t)

最優值：L(n,i,t):從源點Sk經過幾次再分配到達節點(i,t)的最小成本，P(i,t)：t時段在節點i的重進重出最優值。

遞歸函數：

L(n,i,t+1)=

λ2minP(i,t) ?i∈N∪M,t∈T,ak≤t

邊界條件：

L(n,ok,ak)=0 ?n=0,…,rk,P(i,t)=0

最優解：

min{L(n,dk,bk) ?n=0,…,rk},minP(i,t)=0

上述遞歸函數表示：如果沒有進行重新分配，節點(i，t)與節點(i，t-1)的成本是一樣的，因為沒有操作成本的產生。但是，當重新分配必須進行時，后一節點的成本是前邊在同一路徑的所有節點成本的總和。在我們結算當前節點成本之前，應該對約束限制進行檢查。只有滿足能力需求時，節點的成本才能被遞歸函數計算。式中的P(i,t)則是用來評價堆場箱區中堆存集裝箱的重進重出，即節點中進出口集裝箱數量關系的一個評價標準。

當迭代次數達到預先設定的最大迭代次數時，進行終止操作。

4 算例分析

在本文中會展現算例實驗的設計和結果，分別采用CPLEX求解器和禁忌搜索算法對模型進行求解，然后會對CPLEX和禁忌搜索算法結果的區別進行比較。

4.1 算例實驗

自動化集裝箱碼頭堆場的布局與傳統集裝箱碼頭差異較大，并且上海洋山深水港四期自動化集裝箱碼頭仍在建設階段，無法獲得現實數據，因此算例的數據主要來自于實際項目研究的結果以及國外自動化集裝箱碼頭現實情況的數據。

在選取算例數據時，本文采用3個泊位，9個箱區的碼頭布局來進行實驗計算，然后通過改變時間周期的長短以及集裝箱組數量的大小來產生不同的實驗數據。在一臺裝有Intel 雙核P8600@2.6 GHz處理器和2 GB內存的個人電腦上用MATLAB軟件編寫本文提出的禁忌搜索算法來求解算例。

具體的輸入數據的信息如船舶信息，集裝箱信息，泊位到箱區的距離等等如表2-表6所示。

表2 船舶相關信息

表3 t=1時船舶進口箱信息

表4 t=1時船舶出口箱信息

表5 泊位與箱區的距離

表6 各箱區其他信息

4.2 計算結果

通過使用禁忌搜索算法對問題進行求解，運算20次得到的平均最優值為4 131。t=1時的堆場箱區分配結果如圖5所示，各箱區堆存的集裝箱量如表7所示。進口集裝箱和出口箱進入堆場到離開堆場的分配結果如表8和表9所示。禁忌搜索算法的收斂結果如圖6所示，各時間段各箱區工作量如圖7所示，t=1時堆場箱區作業的進出口箱量比例如圖8所示。

圖5 時間段t=1時堆場箱區分配圖

船號進口箱出口箱11(2W)、2(2E)、3(1W)、4(2W)1(1L)、2(2L)、3(3L)、4(3E)21(5W)、2(5W)、3(6W)、4(4W)、5(3W)1(3L)、2(4L)、3(5L)、4(6L)31(4W)、2(5E)、3(4E)、4(3W)1(5E)、2(4L)、3(6L)、4(6E)41(7W)、2(7E)、3(8W)、4(8E)1(7L)、2(8E)、3(7E)、4(8L)51(9W)、2(8W)、3(7E)1(9E)、2(9L)、3(8L)、4(7L)注:W表示箱區的海側區域,E表示箱區的交換區域,L表示箱區的陸側區域;1(2W)表示箱區2的海側區域堆存了船舶的1號進口/出口集裝箱組

表8 進口箱組分配結果

續表8

表9 出口箱組分配結果

圖6 TS的收斂圖

圖7 各時間段各箱區工作量折線圖

圖8 t=1時堆場箱區作業的進出口箱量比例

為了驗證禁忌搜索算法的有效性，本文設計了10個算例，如表10所示，船舶數量從5到40，集裝箱組數量從40到240，分別采用3個泊位9個箱區和5個泊位15個箱區的碼頭布局。用CPLEX和禁忌搜索算法進行計算，計算結果如表11所示，比較可以看出，禁忌搜索算法可以在更短的時間內找到一個較優的解，算例1-8中的最優值與增均值的平均差距小于5%，而在算例9-10中，由于算例規模較大，CPLEX不能找到可行解，而禁忌搜索算法可以找到較優的解。

表10 算例數據

表11 CPLEX和禁忌搜索算法計算結果的比較

續表11

4.3 結果分析

從圖5和圖7可以看出，在同個時間段內作業的進口箱和出口箱均衡地分配在堆場的箱區中，雖然集裝箱的運輸距離較長，但是各個箱區之間的作業量差距比較平緩，且每個箱區都盡量做到了讓同一時間段內作業的進口箱和出口箱數量的差值最小化，從而滿足堆場箱區的“重進重出”。從圖8可以看到在時間段t=1時堆場各個箱區作業的進口箱和出口箱量的比例，當比例數值越相近時則表明該時間段內箱區起重機的利用率越高，空載率越少，即最大化的滿足了“重進重出”這一要求。最后分別采用CPLEX方法和禁忌搜索算法對相同算例進行求解，實驗結果表明，禁忌搜索算法在求解速度上較為占優。雖然與CPLEX求得的最優解平均有5%左右的差距，但是在較大規模的問題上，CPLEX無法找到可行解而禁忌搜索算法可以實現。

5 結 語

本文主要研究自動化集裝箱碼頭的實際堆場空間分配問題，以上海洋山深水港四期在建的自動化集裝箱碼頭項目為研究背景進行研究，提出了一個基于網絡流的自動化集裝箱碼頭堆場空間動態分配模型，通過網絡流的形式體現一個個集裝箱組在堆場和堆場箱區中的移動狀態來反映堆場實際的作業過程。通過將集裝箱按某些共同屬性歸為一組進行統一作業可以更好地管理碼頭堆場的堆存作業。通過考慮“重進重出”可以更好地利用堆場箱區起重機，減少起重機的作業負擔，達到最大化的利用率。

[1] 李建忠,丁以中,王斌.集裝箱堆場空間動態配置模型[J].交通運輸工程學報,2007,7(3):50-55.

[2] 王孟昌.集裝箱碼頭堆場箱位動態分配優化策略研究[D].武漢:武漢理工大學,2007.

[3] Wiese J,Suhl L,Kliewer N.Mathematical models and solution methods for optimal container terminal yard layouts[J].OR Spectrum,2010,32(3):427-452.

[4] Kemme N.Effects of storage block layout and automated yard crane systems on the performance of seaport container terminals[J].OR Spectrum,2012,34(3):563-591.

[5] Yu Mingzhu,Qi Xiangtong.Storage space allocation models for inbound containers in an automatic container terminal[J].European Journal of Operational Research,2013,226(1):32-45.

[6] 周鵬飛,李丕安.集裝箱堆場不確定提箱次序與卸船箱位分配[J].哈爾濱工程大學學報,2013,34(9):1119-1123.

[7] 趙禮峰,白睿,宋常城.求解最小費用最大流的新方法[J].計算機技術與發展,2012,22(5):94-96.

[8] Han Shengwei,Peng Zixiong,Wang Shunqin.The maximum flow problem of uncertain network[J].Information Sciences,2014,265(5):167-175.

[9] Lee B K,Kim K H.Optimizing the yard layout in container terminals[J].OR Spectrum,2013,35(2):363-398.

[10] 陳宇.集裝箱碼頭基于作業路的堆場空間分配策略研究[D].上海:上海海事大學,2010.

[11] 毛鈞,李娜,靳志宏.基于混堆模式的集裝箱碼頭堆場空間資源配置優化[J].大連海事大學學報,2014,40(1):117-122.

[12] Kim K H,Lee J S.Satisfying Constraints for Locating Export Containers in Port Container Terminals[C]//International Conference on Computational Science and Its Applications,2006:564-573.

[13] Fu Z,Li Y,Lim A.Port Space Allocation with a Time Dimension[J].Journal of the Operational Research Society,2007,58(6):797-807.

[14] Gao Y.Uncertain models for single facility location problems on networks[J].Applied Mathematical Modelling,2012,36(6):2592-2599.

[15] Gao Y.Shortest path problem with uncertain arc lengths[J].Computers & Mathematics with Applications,2011,62(6):2591-2600.

[16] Myung Y S,Moon I.A network flow model for the optimal allocation of both foldable and standard containers[J].Operations Research Letters,2014,42(6):484-488.