自動化碼頭堆場穿越式雙ASC調度

周亞民，楊勇生，仲美穌，王宇生，許學謙

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

自動化集裝箱碼頭是將原本的集裝箱碼頭的場橋、岸橋、起重機等設備換成與之相對應的自動化的設備，從而更加高效地完成岸邊和堆場之間的運輸作業、堆場內的作業以及進出道口的作業[1-2]。

現有的集裝箱裝卸設備（吊兩箱、三箱岸橋）和裝卸條件（挖入式港池、浮動裝卸作業平臺）極大地提高了岸邊的裝卸效率問題，無人集卡、AGV（Automated Guided Vehicle）和ALV（Automated Lifted Vehicle）也能夠實現邊裝邊卸的要求[3-4]。堆場內AGV 排隊等待、設備利用率低等問題，迫使大部分研究人員將研究方向轉移到陸側的堆場裝卸方面[5]。

目前，自動化集裝箱碼頭的陸側堆場區域布局多采用垂直式的布局和多場橋運作[6-7]。場橋一般采用自動堆垛起重機（Automated Stacking Crane，ASC），用于連接堆場和堆場兩側（海側和陸側）。場橋運作中，根據ASC 的數量可以分為單ASC、雙ASC 和多ASC。而雙ASC最常見的在堆場的場橋布局[8]，其中關于雙ASC可以根據兩個ASC之間是否可以相互穿越分為不可穿越式雙ASC 和可穿越式雙ASC（具體見圖1、2）[9-10]。前者是兩臺大小一樣的ASC 在同一軌道上運行，兩臺ASC在箱區的兩側與AGV和集卡進行交接工作。后者是兩臺大小不一的ASC 分別在兩臺軌道上運行，并且兩臺ASC 均可以在箱區的兩端與AGV 和集卡進行交接工作。不可穿越式雙ASC的堆垛層高比可穿越式雙ASC的堆垛層高更高，ASC 的占地面積更?。坏强纱┰绞诫pASC 可以兩端作業，減少了因為不可穿越式等原因造成的等待時間，提高了自動化碼頭的堆場工作效率。

圖1 不可穿越式雙ASC堆場布局

圖2 可穿越式雙ASC堆場布局

關于堆場作業已經有一定的研究基礎，例如Carlo等人[11]研究包括所使用的物料搬運設備的堆場作業，提出了倉庫作業分類方案，其對研究自動化集裝箱碼頭具有重要借鑒。為了有效地裝卸集裝箱，Cao 等人[12]研究了亞洲布局中堆場堆存問題，設計了貪婪啟發式算法，模擬退火（SA）算法和組合式堆場調度啟發式算法來解決該問題。Stahlbock 等人[13]為了提高集裝箱碼頭的工作效率，研究了歐洲布局中堆場堆存問題，并設計了三個程序和一個基于SA 的啟發式算法，并根據德國漢堡港的集裝箱碼頭進行仿真，結果SA 在高工作負載情況下優于基于規則的其他算法。Vis等人[14]針對場橋的最小化完工時間，提出了一種基于模擬退火算法的啟發式算法，通過分支界定法求解場橋的調度模型，并且提出雙場橋的避讓方法。

隨著近年來，自動化碼頭更多使用雙場橋進行作業來提高作業效率，Ng[15]針對不同準備時間的雙場橋調度問題，建立了整數規劃模型，提出了一種基于動態規劃的啟發式算法，能夠有效解決雙場橋的調度問題。隨后，Ng等人[16]又提出了以最小化總作業時間為目標，優化堆場內雙向行車道的場橋調度問題，并利用啟發式算法來求解并證明算法有效性。但是，其模型只考慮了單一箱區中一種類型的任務，并且沒有考慮場橋的移動時間。對于歐洲布局中使用單個箱區中雙場橋問題，Zhou等人[17]提出了一種根據給定的日期對作業序列和交換點進行排序的方法，并且運用最優化算法最大限度地減少最大遲到、遲到作業的數量和完工時間。魏晨和胡志華[18]以最小化作業總完成時間為目標，建立了雙場橋混合整數規劃模型，提出了啟發式遺傳算法，表明大規模算例中遺傳算法優于CPLEX算法。

然而在自動化碼頭中，尤其是雙場橋作業時存在諸多不確定性和限制性因素，比如Li等人[19]以任務的提前和延誤時間最小化為目標，考慮了場橋之間的干擾和安全作業距離，建立了離散時間整數規劃模型，提出滾動周期算法在短時間內產生近似最優的解決方案。Li 等人[20]在考慮碼頭實際操作環境中的設備數量限制問題的情況下，改進了上述模型，建立了一個連續時間MILP模型，其所提出的啟發式算法與滾動周期算法相結合更優于離散時間模型的結果。Wu等人[21]考慮到非交叉場橋的安全距離等約束限制，建立了基于連續時間的混合整數線性規劃模型，提出了一種再分配算法，為實時調度中的提供近似最優解作為作業方案。

隨著對雙場橋調度問題的研究，其可穿越式雙ASC具有高效性和靈活性等特點，成為了國內外研究的重點，例如周靜嫻和胡志華[22]針對穿越式雙ASC的調度問題，以ASC的最小化空載時間為目標，建立多目標混合整數規劃模型，分析其運行速度、裝卸量和存取比例對作業效率的影響。景貞文和韓曉龍[23]針對雙ASC 的互相干擾問題，以雙ASC的完工時間最小化為目標，提出9條優先權分配規則和兩種避讓方案（直接避讓和動態暫存區），并進行調度仿真實驗驗證了所提方案的合理性。李敏和韓曉龍[24]為了縮減完工時間，根據優先權規則建立多目標混合整數規劃模型，并針對可穿越式雙ASC的參數設計了三組實驗，證明了該模型可以提高堆場作業效率。

上述文獻關于雙場橋和可穿越式雙ASC的研究都為本文的研究奠定了基礎，其通常以最小化完工時間為目標，同時場橋的調度并沒有考慮到場橋垂直方向的運行距離等不確定性因素。本文所研究的雙ASC的調度問題，其目標函數中引入能耗這一系數，并且根據場橋裝載和空載的情況，以及場橋規格大小設置不同的能耗系數，根據堆場集裝箱位置設立三維坐標點，同時考慮到場橋作業的不同垂直高度問題，其更符合碼頭作業的實際情況。

1 問題描述

堆場內雙ASC既可以與連接海陸兩側的AGV協調作業，也可以與外部集卡（集裝箱卡車）一起協調作業。此外，堆場內的存箱作業和取箱作業也由ASC承擔，如果堆場內雙ASC 調度安排不合理或效率低下，會造成AGV 和外集卡的等待時間過長。同時，雙ASC 空載和重載作業、不同作業速度都直接影響其能耗水平，其反過來直接影響ASC 的作業效率水平，所以合理的ASC調度優化顯得尤為重要。

堆場內包含多個箱區（Block），而每個箱區內又包含多個貝（Bay）。在同一箱區的情況下，穿越式ASC可同時進行存箱和取箱作業，當目標集裝箱作業的位置不在同一貝位時，兩個ASC之間可以相互穿越；當目標集裝箱作業的位置處于同一貝位時，兩個ASC 之間可能會存在沖突。

如圖3所示，穿越式雙ASC配備一大一小兩臺ASC，并且兩臺ASC 始末位置已規定（橫縱坐標箱區區塊位置已用數字進行標注和設定）。從開始位置坐標出發，完成所有集裝箱任務后返回初始位置坐標。

圖3 可穿越式雙ASC俯視圖

將堆場內的可穿越式雙ASC的存取箱作業分為四個步驟：（1）ASC 從上一個集裝箱任務結束的終止位置到達隨后的集裝箱任務的開始位置，將這個過程稱為空載過程，所需要的時間成為空載時間，用字母T 表示；（2）ASC 在目標集裝箱任務的開始位置，對集裝箱進行抓取作業，這個過程所需要的時間用th表示；（3）ASC從集裝箱任務的開始位置將集裝箱送達集裝箱任務的終止位置，將這個過程稱為裝載過程，所需要的時間稱為裝載時間，用字母S 表示；（4）ASC在集裝箱任務的終止位置，對集裝箱進行釋放作業，這個過程所需要的時間也用th表示。

2 模型

（1）模型假設

①只考慮一種標準箱型在同一箱區的情況。

②每個ASC在同一時間段內有相同的工作能力。

③在水平和垂直方向均作勻速運動Vk，不考慮其加速和減速。

④忽略集卡或AGV堵塞等因素造成的對場橋調配策略的影響。

⑤在不考慮自動化集裝箱碼頭堆場箱區的堆存能力限制的條件下。

⑥忽略翻箱操作（由于配載安排與堆場堆存順序不匹配所造成集裝箱的移動）[25]。

（2）符號

K={1,2}：堆場內ASC的集合，k ∈K 。

C ∈{1,2,…,NC}：穿越式雙ASC 的集裝箱裝卸任務集合，其中i,j ∈C,i,j ＞0。

OK：假設ASC 在初始位置為一個虛擬集裝箱任務，且=C ?{OK}。

DK：假設ASC 在終止位置為一個虛擬集裝箱任務，且=C ?{DK}。

HK：ASCK吊具的高度，HK=(5,6),即H1=5,H2=6。

VK：表示ASCK水平和垂直移動的速度，其中較小ASC 運行速度V1，較大ASC 運行速度V2。

M ：表示無限大的數。

（3）參數

COi=()表示集裝箱任務i 的初始位置。

CDi=()表示集裝箱任務i 的終止位置。

ROK=()表示ASCK的初始位置。

RDK=()表示ASCK的終止位置。

（4）變量

Ui∈{0,1}：表示集裝箱任務i 的存取屬性。Ui=1表示集裝箱任務i 為存箱作業，否則為取箱作業，Ui=0。

xk,i,j∈{0,1}：xk,i,j=1 表示ASCK依次完成集裝箱任務i 和集裝箱任務j，否則xk,i,j=0。

xk,i∈{0,1}：xk,i=1 表示集裝箱任務i 由ASCK完成，否則xk,i=0。

ak,i：表示ASCK完成集裝箱任務i 的初始時間，且ak,i≥0。

dk,i：表示ASCK完成集裝箱任務i 的終止時間，且dk,i≥0。

yk：表示ASCK完成最后一個集裝箱任務后到達終點位置的時間。

w：表示完成所有集裝箱任務的時間，且w ≥0。

sk,i：表示ASCK完成集裝箱任務i 所需要的時間。

Tk,i,j：表示ASCK完成集裝箱任務i 后到達集裝箱任務j 的初始位置所需要的時間。

Tk,Ok,j：表示ASCK從初始位置到第一個集裝箱任務所需要的時間。

Tk,j,Dk：表示ASCK完成最后一個集裝箱任務后到達終點位置所需要的時間。

目標函數[M]

本文建立了混合整數線性模型[M]，式（6）、（7）表示ASC 的裝載時間和耗能情況。式（8）、（9）表示ASCK從初始位置出發，依次完成任務i 和j ，回到終止位置。式（10）～（12）表示每一個集裝箱任務只能被執行一次。式（15）表示ASCK完成集裝箱任務i 的初始時間加上操作時間不能超過其終止時間。式（16）表示ASCK完成最后一個集裝箱任務j 的終止時間加上運行到整個最后點的時間不能超虛擬任務的完成時間。式（17）表示任意兩個任務，前一個任務的完成時間加上運行到下一個任務的時間不能超過下一個任務的初始時間。式（18）表示所有集裝箱任務的完成時間不小于任意一個集裝箱任務的時間。式（19）表示ASC 不能為降低耗能而無限延長集裝箱任務的完成時間。

穿越式雙ASC 同時處理同一貝位的集裝箱任務時，假設ψ1表示終止位置在同一貝位的存箱任務；ψ2表示初始位置在同一貝位的取箱任務；ψ3表示取箱任務的初始位置和存箱任務的終止位置在同一貝位；ψ4表示存箱任務的初始位置和取箱任務的終止位置在同一貝位。

式（20）和（24）表示當集裝箱任務i 和j 同為存箱作業且終止位置在同一貝位上，任務i 的完成時間早于任務j。同理，式（21）和（25）、式（22）和（26）和式（23）和（27）。

式（28）～（33）為模型中相關參數的約束范圍和條件。

3 算例

以穿越式雙ASC 的20 個集裝箱任務為例，根據自動化碼頭的實際情況建立坐標，驗證模型的實用性。目前已經知道的20個集裝箱任務，如表1、表2所示。

本文使用Matlab進行求解，并且調用Yamlp工具箱和Gurobi 求解器。求解出ASC 的最優序列、最小時間和最小總耗能。即在20 個集裝箱工作任務的情況下ASC的總耗能為626.25，具體路線如圖4所示。

4 實驗分析

為了進一步分析參數變化對結果的影響，本文分別從集裝箱任務數量、速度，還有耗能系數的角度設計了三組不同的對比實驗。

實驗1 分析了不同數量集裝箱任務條件下，雙ASC總時間和總耗能的變化，如圖5 所示，可以看出隨著集裝箱數量的增加，其總能耗呈線性增長。

實驗2 比較1#ASC 與2#ASC 之間速度比值不同，即比較不同大小的V1/V2，對雙ASC 總時間和總耗能的影響，具體情況如表3 所示（其他影響因素保持不變）。其不同雙ASC速度之比下，其總作業時間和耗能的變化如圖6所示。

表1 測試數據集合

表2 ASC耗能和速度

圖4 雙ASC的最優作業順序圖

圖5 雙ASC總時間和總耗能的隨集裝箱數量的變化

表3 雙ASC速度、總時間和耗能

圖6 不同雙ASC速度之比下總時間和耗能的變化

由圖6 可知，當V1/V2 處于（6/10，1）的范圍時，總耗能隨著比值的增大而減小。當V1/V2=9/10 時，雙ASC的總作業時間最大，并且其總耗能是處于一個比較低的數值，整體上符合六階多項式的關系。所以，進一步說明當雙ASC 對同一箱區的集裝箱進行任務時，可以合理調整兩個ASC 的速度之比，使其耗能的增加速度達到最小，從而以最小的能耗作業更多的集裝箱任務。

實驗3 比較1#ASC和2#ASC裝載和空載的耗能系數不同，對雙ASC總時間和總耗能的影響結果（其他影響因素保持不變，例如：集裝箱任務數量和速度），具體情況如表4所示。

由圖7可知，當α/β=1/2 時，即當1#ASC與2#ASC之間的能耗系數比為1/2 時，在不同條件的情況下其總作業時間總是保持最小。并且當α1/α2 處于（1/3，1）時，其總耗能的增長速度也隨著增加，當α1/α2 處于（1/4，1/3）時，其總耗能的增長速度隨之減小。

圖7 不同耗能系數下總時間和耗能的變化

表4 雙ASC裝載與空載耗能系數、總時間和總耗能

綜上所述，三組實驗從整體上表明：當雙ASC對同一箱區的集裝箱進行任務時，可以通過合理地調整兩個ASC在不同狀態下的耗能系數之比，從而達到耗能的增加速度最小，來提高雙ASC的作業效率。

5 結束語

隨著信息技術的發展，自動化的集裝箱碼頭成為國內外發展的趨勢。越來越多的傳統碼頭正在進行自動化改造。本文研究自動化集裝箱碼頭為在穿越式雙ASC作業的單個箱區內，給予其作業一定數量集裝箱任務下不同的耗能系數，以最小化集裝箱任務的總完成時間和總耗能為目標，建立了混合整數規劃模型。并且通過設計了三組基于集裝箱任務，雙ASC 總時間和總耗能的對比實驗。實驗結果表明：（1）在不同能耗系數條件下，當雙ASC的耗能系數達到一定值，能夠保證其耗能的增加速度最小化，能夠以最小的能耗作業集裝箱任務，來降低碼頭作業成本。（2）當兩個ASC（可穿越式）的耗能系數達到一定的數值時，能夠保證其作業并完成集裝箱任務的總時間最小。所以，自動化碼頭可以通過不斷改進和優化雙ASC 的耗能水平（通過改變其作業速度），使得作業集裝箱任務的總時間和總耗能達到最小或最優的情況。（3）在自動化碼頭的堆場作業中，可以通過調整其作業的集裝箱任務數量和雙ASC 的作業速度，來減少總時間和總耗能，從而提高碼頭堆場的作業效率，節約自動化碼頭作業成本。

在自動化碼頭的復雜的實際作業環境中（岸橋、水平運輸和場橋），堆場作業作為配合水平運輸和岸橋作業的重要環節，直接制約著其他作業環節和流程的運行，其雙ASC 的作業決定著水平運輸和岸橋的作業效率。減少堆場中ASC的能耗水平，提高其作業效率，對整個自動化碼頭的作業效率都具有重要意義。本文對雙ASC的考慮中并沒有考慮其諸多的限制因素和其與水平運輸的協同調度等問題，可以在未來研究中進行進一步的探討。