自動化碼頭堆場穿越式雙ASC調(diào)度

2021-01-22 06:00:28周亞民楊勇生仲美穌王宇生許學謙

計算機工程與應(yīng)用 2021年2期

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

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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

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

圖3 可穿越式雙ASC俯視圖

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

2 模型

（1）模型假設(shè)

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

②每個ASC在同一時間段內(nèi)有相同的工作能力。

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

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

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

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

（2）符號

K={1,2}：堆場內(nèi)ASC的集合，k ∈K 。

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

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

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

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

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

M ：表示無限大的數(shù)。

（3）參數(shù)

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

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

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

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

（4）變量

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

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

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

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

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

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

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

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

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

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

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

目標函數(shù)[M]

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

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

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

式（28）～（33）為模型中相關(guān)參數(shù)的約束范圍和條件。

3 算例

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

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

4 實驗分析

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

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

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

表1 測試數(shù)據(jù)集合

表2 ASC耗能和速度

圖4 雙ASC的最優(yōu)作業(yè)順序圖

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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