自動(dòng)化碼頭堆場(chǎng)穿越式雙ASC調(diào)度

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

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

周亞民，楊勇生，仲美穌，王宇生，許學(xué)謙

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

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

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

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

圖1 不可穿越式雙ASC堆場(chǎng)布局

圖2 可穿越式雙ASC堆場(chǎng)布局

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

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

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

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

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

1 問題描述

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

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

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

圖3 可穿越式雙ASC俯視圖

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

2 模型

（1）模型假設(shè)

①只考慮一種標(biāo)準(zhǔn)箱型在同一箱區(qū)的情況。

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

③在水平和垂直方向均作勻速運(yùn)動(dòng)Vk，不考慮其加速和減速。

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

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

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

（2）符號(hào)

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

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

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

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

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

VK：表示ASCK水平和垂直移動(dòng)的速度，其中較小ASC 運(yùn)行速度V1，較大ASC 運(yùn)行速度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 的初始時(shí)間，且ak,i≥0。

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

yk：表示ASCK完成最后一個(gè)集裝箱任務(wù)后到達(dá)終點(diǎn)位置的時(shí)間。

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

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

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

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

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

目標(biāo)函數(shù)[M]

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

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

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

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

3 算例

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

表2 ASC耗能和速度

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

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

表3 雙ASC速度、總時(shí)間和耗能

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

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

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

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

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

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

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

5 結(jié)束語

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