許波桅，接德培，李軍軍，楊勇生

(1.上海海事大學 物流科學與工程研究院，上海 201306；2.上海海事大學 商船學院，上海 201306)

1 問題的提出

自動化集裝箱碼頭(簡稱自動化碼頭)的高速發(fā)展提升了港口的運作效率[1]，但是現(xiàn)有自動化碼頭中場橋需要長距離的往復行駛、能源消耗高；場外集卡司機倒車進入交互區(qū)作業(yè)時，容易影響其他車道正常通行，在總結(jié)現(xiàn)有自動化碼頭的不足后，上海振華重工提出一種全新U型工藝的自動化碼頭，如圖1所示。U型碼頭高效經(jīng)濟是未來自動化碼頭改造的方向[2]。岸橋、自動導引車(Automated Guided Vehicle, AGV)、雙懸臂軌道吊(簡稱軌道吊)和外集卡是U型自動化碼頭的主要裝卸設備，四者相互關(guān)聯(lián)，相互影響，如何使得岸橋、AGV、軌道吊和外集卡高效協(xié)同作業(yè)，保證以最少的時間完成所有裝卸任務，是亟待解決的關(guān)鍵科學問題。

關(guān)于自動化碼頭的集成調(diào)度問題，國內(nèi)外眾多學者對此進行了研究，LUO等[3]整合自動化碼頭裝卸設備的各個組成部分，以最小化船舶靠泊時間為目標，建立了混合整數(shù)規(guī)劃模型;常祎妹等[4]考慮龍門吊間的干擾和安全距離等現(xiàn)實約束，建立了龍門吊、集卡和場橋的協(xié)同調(diào)度模型;田宇等[5]研究了自動化碼頭雙循環(huán)AGV和場橋協(xié)同調(diào)度問題;張振毓等[6]研究了岸側(cè)泊位和岸橋資源的協(xié)同調(diào)度問題，建立了不確定環(huán)境下連續(xù)型泊位岸橋集成調(diào)度的數(shù)學模型，采用雙層決策結(jié)構(gòu)的優(yōu)化算法對模型進行求解;鄭紅星等[7]研究了傳統(tǒng)集裝箱碼頭的場橋和內(nèi)外集卡的集成調(diào)度問題，提出一個多場橋調(diào)度整數(shù)規(guī)劃模型，設計新的變異操作來提高遺傳算法的全局尋優(yōu)能力。隨著自動化碼頭建設的加快，如何減少大型自動化裝備運作的能耗是另一個重要的科學問題。YU等[8]考慮了工作量的不確定性，研究了集裝箱碼頭中電動輪胎式龍門起重機的碳配置問題，建立了兩階段隨機模型;LIU等[9]利用排隊論對AGV的運輸方式進行建模，通過優(yōu)化岸橋的數(shù)量，使集裝箱從岸橋到AGV卸載過程中的碳排放量最小。實際運作中的不確定因素影響著碼頭的裝卸效率，宋云婷等[10]根據(jù)集裝箱班輪靠泊規(guī)則，構(gòu)建了基于運行時間不確定的集裝箱碼頭靠泊計劃優(yōu)化模型;常祎妹等[11]考慮了集裝箱碼頭岸橋、集卡的速度變化等不確定因素，建立了船舶和集卡裝卸作業(yè)集成調(diào)度模型，并設計了改進的多層遺傳算法求解模型;韓笑樂等[12]研究了泊位和堆場資源聯(lián)合分配問題，考慮了船舶到港時間的不確定性，提出了基于松弛時間的啟發(fā)式調(diào)整規(guī)則用來優(yōu)化啟發(fā)式算法，為集裝箱碼頭多資源協(xié)同分配提供了有效的決策思路。然而，現(xiàn)有自動化碼頭集成調(diào)度研究中，大部分都是建立在確定的理想情況下，較少考慮外集卡；關(guān)于集裝箱碼頭節(jié)能減排的研究大多數(shù)集中在傳統(tǒng)碼頭上，缺乏對自動化碼頭集成調(diào)度情況下的節(jié)能減排研究。因此，研究不確定環(huán)境下U型自動化碼頭綠色集成調(diào)度有助于促進我國集裝箱港口的高質(zhì)量轉(zhuǎn)型發(fā)展。

2 問題描述與建模

2.1 問題描述

本文研究U型自動化碼頭邊裝邊卸模式，即AGV完成一個集裝箱裝船任務后接著完成一個卸船任務，完成一個卸船任務后接著完成一個裝船任務。在U型自動化碼頭中，外集卡可以進入堆場與軌道吊進行交互，因此可以將外集卡的任務穿插在AGV任務中，減少外集卡的等待時間，即當外集卡到達時，軌道吊完成當前AGV裝卸任務后立即執(zhí)行外集卡的任務。為了減少軌道吊的行駛距離，降低能耗。本文提出一種綠色等待策略，即當外集卡任務與船舶任務在堆場的貝位一致時，運輸該船舶任務的AGV將等待該外集卡到達，之后軌道吊完成外集卡任務裝卸后立即對船舶任務進行裝卸，可充分減少軌道吊的行駛距離和停駐次數(shù)，減少軌道吊的碳排放量。

本文的優(yōu)化目標為在外集卡到達時間不確定的情況下合理分配作業(yè)任務實現(xiàn)岸橋、AGV、軌道吊和外集卡之間集成調(diào)度的總時間最小以及3種裝卸設備的碳排放最低。

2.2 數(shù)學模型

(1)假設

①碼頭設備之間不存在沖突和擁堵。

②岸橋和AGV間不存在相互等待。

③AGV在轉(zhuǎn)彎和直線行駛的速度相同。

④所有集裝箱的大小都為40英尺，外集卡全部為單掛集卡，所運輸?shù)募b箱都為40英尺。

(2)符號說明

本文中的符號定義如表1～表4所示。

表1 集合符號定義

表2 參數(shù)符號定義

表3 非0-1變量符號定義

續(xù)表3

表4 0-1變量符號定義

(3)多目標混合規(guī)劃模型

(1)

f2=min{Esq+Esy+EAGV},

(2)

f=φ1f1+φ2f2。

(3)

其中：式(1)為第1個目標，碼頭設備完成所有任務的時間最小;式(2)為第2個目標，3種設備的碳排放量最少;式(3)為目標函數(shù)，其中φ1為f1的權(quán)重系數(shù)，φ2為f2的權(quán)重系數(shù)。

(4)

(5)

?k∈Y,i∈U,m∈Q,n∈B;

(6)

?k∈Y,i∈U,w∈W;

(7)

?k,l∈Y,i∈U,j∈L,m∈B,n∈B,w∈W。

(8)

其中：式(4)表示卸船任務的開始時刻與AGV到達岸橋時刻之間的關(guān)系;式(5)表示AGV到達岸橋時刻與岸橋?qū)⒓b箱放到AGV上時刻之間的關(guān)系;式(6)表示AGV從岸橋出發(fā)的時刻與AGV到達堆場指定裝卸貝位時刻之間的關(guān)系;式(7)表示軌道吊開始卸載AGV上集裝箱的時刻與該任務結(jié)束時刻之間的關(guān)系;式(8)表示上一個卸船任務結(jié)束時刻與AGV到達下一個裝船任務的堆場指定貝位時刻之間的關(guān)系。

(9)

?l∈Y,j∈L,m∈B,n∈Q;

(10)

(11)

(12)

?k,l∈Y,i∈U,j∈L,m∈Q,n∈Q。

(13)

其中：式(9)表示裝船任務的開始時刻;式(10)表示裝船任務開始時刻與AGV到達岸橋時刻之間的關(guān)系;式(11)表示AGV到達岸橋的時刻與岸橋?qū)⒓b箱從AGV上取走時刻之間的關(guān)系;式(12)表示岸橋從AGV上取走集裝箱的時刻與裝船任務結(jié)束時刻之間的關(guān)系;式(13)表示AGV完成上一個裝船任務時刻與到達下一個卸船任務的岸橋的時刻之間的關(guān)系。

?k∈Y,i∈U∪L,w∈W;

(14)

(15)

(16)

(17)

(18)

(19)

(20)

其中：式(14)表示執(zhí)行與外集卡任務有相同目標貝位的船舶任務的AGV到達目標貝位的時刻與外集卡到達時刻之間的關(guān)系;式(15)表示軌道吊到達任務目標貝位的時刻;式(16)表示表示同一輛AGV完成一個岸橋卸船任務后只能完成一個岸橋的裝船任務;式(17)表示同一輛AGV完成一個岸橋的裝船任務后只能完成一個岸橋的卸船任務;式(18)表示軌道吊一次只能執(zhí)行一個外集卡任務;式(19)表示一個集裝箱只能由一輛AGV運輸;式(20)表示一個集裝箱只能由一個岸橋裝卸。

(21)

C4·ηy2·TN。

(22)

其中：式(21)表示完成所有任務后岸橋總的碳排放量;式(22)表示完成所有任務后軌道吊總的碳排放量。

EAGV=C1·(E1+E2+E3+E4);

(23)

(24)

(25)

(26)

(27)

其中：式(23)表示AGV完成所有任務后總的碳排放量;式(24)表示AGV將集裝箱從岸橋運輸?shù)蕉褕龅哪芎?式(25)表示AGV從堆場行駛到下一個任務堆場的能耗;式(26)表示AGV將集裝箱從堆場運輸?shù)桨稑蛳碌哪芎?式(27)表示AGV從岸橋行駛到下一個任務岸橋的能耗。

(28)

(29)

式(28)～式(29)表示部分參數(shù)和決策變量的取值范圍。

3 改進的混合遺傳布谷鳥算法

3.1 概述

遺傳算法是由美國的HOLLAND[13]于20世紀70年代提出的一種啟發(fā)式算法，由于其通用性強，算法收斂速度快，被大量的學者用于求解自動化集裝箱碼頭的集成調(diào)度模型。LAU等[14]以岸橋、AGV和場橋3種設備為研究對象，建立了最小化岸橋延誤時間、AGV和場橋總運行時間的集成調(diào)度模型，并采用最大匹配遺傳算法進行求解;JI等[15]研究了邊裝邊卸模式下的自動化集裝箱碼頭中岸橋、AGV和場橋的集成調(diào)度問題，以所有集裝箱完成時間最小為目標建立了雙層規(guī)劃模型，并提出基于沖突策略的雙層自適應遺傳算法解決該協(xié)同調(diào)度問題;LUO等[3]整合集裝箱自動化碼頭裝卸設備的各個組成部分，以最小化船舶靠泊時間為目標，建立混合整數(shù)規(guī)劃模型，提出一種自適應遺傳算法。但是遺傳算法易早熟，易陷入局部最優(yōu)解，針對這些缺點，本文引入布谷鳥算法中的萊維飛行搜索方式。布谷鳥算法是于2009年提出的一種新興啟發(fā)式算法，其被證明具有較好的全局搜索能力[16-17]，使得遺傳算法不易陷入局部最優(yōu)解。除遺傳算法以外，李靜等[18]利用灰狼優(yōu)化算法解決自動化集裝箱碼頭AGV的調(diào)度問題。

3.2 編碼

染色體編碼是遺傳算法的關(guān)鍵操作，染色體編碼的好壞直接影響算法的求解結(jié)果以及效率。本文研究U型自動化集裝箱碼頭中4種設備的集成調(diào)度，因為所建立的模型需要區(qū)分岸橋、AGV、軌道吊和外集卡的任務，所以采用任務分配的形式進行染色體編碼。假設現(xiàn)在有裝船任務和卸船任務各4個，2臺雙小車岸橋，2輛AGV，2個堆場區(qū)域，每個堆場區(qū)域配備2臺雙懸臂軌道吊，染色體編碼示意圖如圖2所示。為了區(qū)分卸船和裝船任務，本文在染色體中加入數(shù)字“0”用來區(qū)分，“0”左邊的為卸船任務，右邊的為裝船任務。第1行表示集裝箱任務的編號，第2行表示岸橋的編號，第3行表示AGV的編號，編號為奇數(shù)的AGV先進行卸船任務后進行裝船任務，編號為偶數(shù)的AGV先進行裝船任務后進行卸船任務，第4行表示堆場的編號，第5行表示外集卡隨機到達，其中數(shù)字“1”表示有外集卡到達，“0”表示沒有外集卡到達。

3.3 解碼

對圖2染色體進行解碼操作，1號AGV路徑為：岸橋2→堆場2(卸船任務3)→堆場2→岸橋1(裝船任務1)→岸橋1→堆場2(卸船任務2)→堆場1→岸橋2(裝船任務3);2號AGV的路徑為：堆場1→岸橋2(裝船任務4)→岸橋1→堆場1(卸船任務4)→堆場1→岸橋2(裝船任務2)→岸橋1→堆場2(卸船任務1)。同理可以得到2號AGV的路徑。對于外集卡任務，軌道吊執(zhí)行完當前任務后立即執(zhí)行外集卡任務，例如當外集卡隨機到達為“1”時，堆場2的軌道吊在執(zhí)行完卸船任務3后立即執(zhí)行外集卡任務，外集卡隨機到達為“0”時，軌道吊執(zhí)行完當前任務后繼續(xù)執(zhí)行下一個AGV的任務。

完成任務分配之后，求解目標函數(shù)，求解流程圖如圖3所示。

3.4 基于萊維飛行的交叉

本文的適應度函數(shù)選取目標函數(shù)的倒數(shù)，即F(x)=1/(φ1f1+φ2f2)。選擇操作采用輪盤賭機制，為了防止算法陷入局部最優(yōu)解，本文在選擇操作時保留5%的劣質(zhì)個體。產(chǎn)生下一代可行解采用交叉和變異的方式，其中交叉部分引入萊維飛行的理論，針對染色體第一層任務編號，將染色體中卸船和裝船任務分別進行如下操作，首先對每一個基因按照文獻[17]的萊維飛行公式進行更新，如式(30)～式(31)所示。

(30)

(31)

此操作的結(jié)果會產(chǎn)生不可行解，隨后將不可行解修復成可行解，如圖4所示，具體操作為對每個基因位中的元素進行四舍五入取整的操作，然后將其中相同的元素置0，最后選擇種群中適應度最好的個體與更新后的個體進行比較，將隨機選擇的個體中含有但更新后個體中不含有的元素依次替換掉后者中的“0”元素。針對染色體第二、四和五層，將染色體進行單點交叉，隨機選擇交叉點，將兩條染色體交叉點之前或者之后的所有元素進行交換。針對染色體第三層，由于AGV可以進行任意的任務，不需要對第三層進行操作。

3.5 變異

本文的變異采用逆序操作，該操作不會產(chǎn)生不可行解，在染色體上隨機選擇兩點，將兩點之間的任務進行逆序排列。變異概率采用自適應變異概率[19]，根據(jù)進化代數(shù)自動調(diào)整，如式(32)所示：

(32)

式中：pmax為最大變異概率，pmin為最小變異概率;iter為進化代數(shù)，Maxiter為最大進化代數(shù)。

3.6 算法流程

改進的混合遺傳布谷鳥算法步驟如下：

步驟1初始化。設置參數(shù)，根據(jù)上述3.2節(jié)中的方式生成初始種群。

步驟2計算適應度和選擇。根據(jù)上述3.3節(jié)至3.4節(jié)的方式計算適應度并進行選擇操作，記錄當前最優(yōu)解。

步驟3交叉操作。根據(jù)上述3.4節(jié)的方式進行基于萊維飛行的交叉操作。

步驟4變異操作。根據(jù)上述3.5節(jié)的方式進行變異操作。

步驟5更新當前最優(yōu)解，若滿足停止條件(達到最大進化代數(shù))，輸出最優(yōu)解；否則，轉(zhuǎn)步驟3和步驟4操作產(chǎn)生的下一代種群，轉(zhuǎn)步驟2繼續(xù)尋找最優(yōu)解。

4 數(shù)值實驗及結(jié)果分析

本章對所建立的模型以及提出的算法進行實例驗證，運用MATLAB 2018b，運行環(huán)境為Window10操作系統(tǒng)，Intel(R)Core(TM)i7-8750H CPU @ 2.20 GHz，16 GB內(nèi)存。

4.1 參數(shù)設置

(1)模型參數(shù)

本文以U型自動化碼頭中某次船舶靠港裝卸為例，碼頭的布局如圖1所示，碼頭的水平運輸區(qū)域長300 m，寬120 m，堆場一個貝位的長度為15 m，每個堆場區(qū)域有40個貝位。AGV勻速行駛速度為5 m/s，軌道吊勻速行駛速度為2 m/s。岸橋的前小車從船舶上取箱或者將中轉(zhuǎn)平臺上的箱子放到船舶上的時間服從(20 s，30 s)的均勻分布，岸橋的后小車將集裝箱放到AGV或從AGV上取箱的時間均為20 s，雙懸臂軌道吊將箱子從AGV拿到指定堆存點或者從指定堆存點放到AGV上的時間服從(30 s，50 s)的均勻分布，目標函數(shù)中的φ1和φ2如式(32)所示:

(32)

岸橋、AGV和軌道吊的作業(yè)能耗等相關(guān)參數(shù)[1]如表5所示。關(guān)于碳排放量的計算，本文先計算出裝卸設備的電力能耗，再將能耗根據(jù)碳排放因子折算成碳排放量，其中碳排放因子選取我國南方區(qū)域電網(wǎng)基準線碳排放因子，如表6所示。

表5 設備能耗參數(shù)

表6 中國南方區(qū)域電網(wǎng)基準線碳排放因子

(2)算法參數(shù)

算法參數(shù)取值如表7所示。

表7 算法參數(shù)取值

4.2 結(jié)果分析

為了驗證模型和算法的有效性，本文分別采用自適應遺傳算法(Adaptive Genetic Algorithm, AGA)[3]、遺傳算法(Genetic Algorithm, GA)、灰狼優(yōu)化算法(Grey Wolf Optimizer, GWO)[16]、改進的混合遺傳布谷鳥算法(Hybrid Genetic Algorithm Cuckoo Search, HGACS)進行15組對比實驗，對于每組實驗求解30次，以平均值作為最終的結(jié)果，如表8和表9所示。從實驗結(jié)果可以看出：

表8 平均目標值的對比

表9 CPU平均運行時間(s)的對比

續(xù)表9

(1)提出的改進的混合遺傳布谷鳥算法在求解過程中，能夠穩(wěn)定地獲得大規(guī)模集裝箱計算問題的近似最優(yōu)解。例如表9中的算例12和15，在集裝箱任務為800、AGV數(shù)量為40時，其CPU計算時間大約為15分鐘，表8中可以看出其目標值為12 739。當集裝箱任務為2 000，AGV數(shù)量為50時，其CPU計算時間約為21 min，其目標值為32 210，基本符合現(xiàn)階段自動化碼頭作業(yè)系統(tǒng)調(diào)度的時間和能耗。

(2)當集裝箱任務增多時，碼頭的總裝卸時間也隨之增加；同等任務數(shù)時，AGV的數(shù)量增加會使得總裝卸時間減少，因此在一定程度上增加AGV的數(shù)量可以顯著提高裝卸任務的效率，尤其是在大規(guī)模集裝箱任務時。不同的集裝箱任務數(shù)以及AGV數(shù)量對碼頭總裝卸時間有著顯著的影響。如圖5所示為4種算法分別計算不同任務數(shù)以及不同AGV數(shù)量時的最優(yōu)目標值，比較結(jié)果表明在任務數(shù)量較小時，幾種算法的最優(yōu)值相近，隨著任務數(shù)量的增加，本文所實驗的其他算法目標函數(shù)值與HGACS算法的目標值的差值越來越大。

如圖6～圖7所示分別為針對小規(guī)模算例和大規(guī)模算例兩種策略的結(jié)果對比，從圖中可以看出，當任務規(guī)模較小時，不等待的策略的結(jié)果較好，并且隨著任務量的增多，兩者的差值逐漸減??；當任務規(guī)模較大時，采用等待策略的結(jié)果較好，并且隨著任務量的增多，兩者的差值逐漸增大。產(chǎn)生這種情況的原因是當任務規(guī)模小時，碼頭設備資源利用量較小，碳排放量少，采用等待的策略會導致AGV的運行效率降低，延長任務總完工時間，而目標函數(shù)包括總完工時間和能耗兩方面，此時總完工時間占比較大，最終導致目標函數(shù)值升高。當任務規(guī)模較大時，碼頭資源利用量較大，碳排放量多，采用等待策略可以充分減少軌道吊的行駛距離和停駐次數(shù)，減少碼頭的碳排放量，此時由于碳排放量增多，能耗占比較大，最終導致目標函數(shù)值降低。

為了進一步展示幾種算法性能的整體比較，本文利用4種不同算法在不同規(guī)模下進行對比，如圖8所示。其中圖8a～圖8d分別表示在集裝箱120、200、800、2 000個時的不同算法的收斂情況。從圖中可以觀察到HGACS的收斂時間隨著規(guī)模的增大而增大的，收斂結(jié)果比其余算法要好。從圖8c和圖8d可以看出，大規(guī)模算例下，HGACS算法前期收斂速度比其他算法要好，最終分別在346代和351代收斂到最優(yōu)解。這是因為在交叉操作時引入萊維飛行的更新策略，長短步長相結(jié)合的方式，使得算法向更好的方向搜索，同時采用自適應變異策略使得算法能夠跳出局部最優(yōu)解，所以該算法在求解時間和質(zhì)量上都具有更優(yōu)異的性能表現(xiàn)。而其他算法在大規(guī)模算例下，迭代后期過早收斂易陷入局部最優(yōu)解。綜上可知，本文所設計的算法求解小規(guī)模和大規(guī)模問題的結(jié)果都是比較優(yōu)異的。

5 結(jié)束語

本文通過數(shù)值實驗驗證了所建立的模型能有效的解決U型自動化碼頭的集成調(diào)度優(yōu)化問題，提出的算法能穩(wěn)定地獲得算例的近似最優(yōu)解。兩種調(diào)度策略對比表明，當任務規(guī)模較小時，AGV不等待外集卡的策略的結(jié)果較好，并且隨著任務量的增多，兩者的差值逐漸減??；當任務規(guī)模較大時，采用AGV等待外集卡一同裝卸的策略結(jié)果較好，并且隨著任務量的增多，兩者的差值逐漸增大。該方法能夠在合理的時間內(nèi)獲得有效調(diào)度策略和決策方案，符合U型自動化碼頭高效經(jīng)濟的發(fā)展需求。

然而自動化碼頭的作業(yè)優(yōu)化問題涉及很多方面，是十分復雜的實際工程問題，本文對該問題進行了簡化，對于不確定因素只是考慮了外集卡到達的不確定性，未來可以考慮其他不確定因素，如船舶到達時間的確定性，裝卸設備故障等，還可以考慮AGV和外集卡的擁堵和沖突、外集卡預約系統(tǒng)、外集卡碳排放量等因素，也可以考慮U型自動化碼頭海鐵聯(lián)運的調(diào)度優(yōu)化。