基于PSO的自動化集裝箱碼頭雙小車岸橋和AGV的協同調度

馬孫豫 楊勇生 梁承姬

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

0 引 言

隨著一帶一路的政策逐漸實施，我國沿海港口集裝箱吞吐量逐步增加，船舶逐漸大型化，港口對裝卸效率的要求越來越高，目前建造自動化集裝箱碼頭已經形成一種趨勢。雙小車岸橋和自動導引車(AGV)的運用，是自動化集裝箱碼頭的主要特征，自動化集裝箱碼頭水平運輸系統的效率直接影響了船舶停靠時間。AGV是水平運輸系統的主要設備，而決定水平運輸系統效率的是碼頭各個裝卸設備的調度情況[1]。因此，研究雙小車岸橋和AGV的調度情況，對于提高自動化集裝箱碼頭的整體效率有著巨大的意義。

目前，國內外學者對AGV調度問題已經進行了許多研究[2]。Xin 等[3]針對自由搜索生成無碰撞軌跡的問題，提出了一種多載AGV調度的混合整數規劃模型，以減少自動化碼頭裝卸時間；Angeloudis等[4]針對不確定性環境下的AGV任務分配問題，通過采用滾動時域，減少船舶在港時間，從而提高自動化碼頭的裝卸效率；Danijela等[5]使用數據包絡法對AGV調度進行進一步分析，建立仿真模型和效率評估，通過改變調度及AGV和任務數量來分析卸船集裝箱的作業效率；康志敏等[6]考慮兩種AGV調度方法，提出了基于成本的調度方法，建立了以等待時間最少為目標函數值的調度模型，利用遺傳算法來求解模型；霍凱歌等[7]基于多載AGV，以最小化AGV作業成本為目標函數，并采用GUROBI和遺傳算法對該問題進行求解，與單載AGV結果進行比較，證明該模型的實用性；柯冉絢、任亞東等[8-9]基于兩種AGV調度模式的優缺點，建立了以AGV等待時間為目標函數的整數規劃模型，以Netlogo構建仿真模擬，證明模型的實用性。

國內外學者為解決AGV調度問題提出很多智能方法[10]。Jin等[11]考慮AGV運輸時間和任務的優先順序，設計一種以最小化岸橋裝卸的完成時間和標準差動態多AGV調度模型，利用遺傳算法進行求解；Kim等[12]基于AGV靜態調度，提出了一種多標準的AGV調度策略，以岸橋延誤時間和AGV空駛距離最小化為目標函數，使用多目標進化算法進行求解；李曄等[13]通過改變雙小車岸橋上的中轉平臺容量限制，以岸橋前小車裝卸延遲時間和岸橋后小車與AGV間的等待時間之和最小為目標函數，設計啟發式算法求解后小車時間窗，采用遺傳算法進行求解；宗辰光等[14]采用多層編碼粒子群-遺傳算法融合，對成本優化問題進行了仿真研究，給出了成本變化曲線及AGV調度甘特圖，來證明算法的有效性。

通過上述可知，目前相關文獻的研究主要圍繞時間窗的調度、路徑規劃的調度、任務指派的調度，但是考慮的大都是單一設備裝卸問題，求解算法以遺傳算法為主。隨著AGV數量的增加，水平運輸系統的復雜化，遺傳算法求解的效率和有效性會大大降低。為此，本文采用多層編碼粒子群算法，以AGV調度為主，岸橋等設備為輔，通過改變裝卸任務和AGV的數量進行算法求解，并通過實驗結果進行分析比較，提高自動化碼頭運作效率。

1 問題描述

自動化碼頭與傳統碼頭的最大的區別就是自動化碼頭的布局是垂岸式，所謂垂岸是指堆場的布局垂直于碼頭[15]。自動化集裝箱碼頭如圖1所示。

圖1 自動化集裝箱碼頭布局圖

由于各個設備之間的操作不連貫、不協調，出現岸橋等待AGV或AGV等待時間過長的現象。自動化碼頭作業包括自動化碼頭作業包括岸邊作業、水平運輸作業和堆場作業[16]。雙小車岸橋和軌道吊分別負責岸邊和堆場作業的主要裝卸設備，AGV是負責在岸邊到堆場間水平運輸的主要設備。在卸船過程中，岸橋前小車將船舶上的集裝箱放置于岸橋中轉平臺上，岸橋后小車從中轉平臺上將集裝箱吊起裝載于AGV上，而后AGV選擇路徑運輸至堆場，軌道吊將集裝箱從AGV上取走存放在堆場指定位置[17]。裝船過程與卸船過程相反。

雙小車岸橋按照已知確定的卸船順序依次卸載集裝箱，由于存在中轉平臺的限制，一般中轉平臺只能存放2個集裝箱，當超過2個容量時，前小車不再放置集裝箱至中轉平臺，需等待后小車將中轉平臺中的集裝箱放置于AGV上。在這整個過程中，需要對AGV的任務進行調度分配，來減少AGV的裝載運輸時間和岸橋的等待時間，從而達到縮短船舶停靠時間的目的。因此，該問題實質是AGV的調度問題。

本文針對自動化碼頭新設備，以小型自動化碼頭為例，以AGV為研究對象，已知岸橋卸船作業順序的情況下，建立以岸橋作業時間最短為目標的AGV調度混合整數規劃模型。本文研究的問題主要設備涉及到了雙小車岸橋和AGV，為了保證算法的精確性和完整性，將箱區主要運輸設備軌道吊RMG(Rail-Mounted Gantry Crane)也納入考慮范圍。采用粒子群算法進行求解，CPLEX軟件和GA進行對比分析驗證粒子群算法的有效性,實現整個系統的最優化調度，提高碼頭裝卸運輸效率，減少在港口時間。

2 數學模型

2.1 模型假設

根據自動化碼頭實際情況，對相關問題進行簡化：

(1) 岸橋作業裝卸順序已知且只卸不裝；

(2) 岸橋后小車裝載集裝箱到AGV上的時間已知；

(3) AGV采用作業面裝卸且一次只能運輸一個集裝箱；

(4) AGV勻速行駛，不考慮加減速和運輸過程中沖突死鎖問題；

(5) 每個箱區使用一個RMG進行裝卸作業。

2.2 參數及決策變量

(1) 參數變量:

S：一個虛擬任務的開始，OS=D∪S；

F：一個虛擬任務的結束，OF=D∪F；

D：集裝箱數量集合，i,j∈D；

K：岸橋數量集合，k,l∈K；

P：集裝箱堆存位置集合，(n,b)∈p，(n,b)表示在箱區b的第n個位置；

B：箱區數量集合，b,a∈B；

V：AGV數量集合；

C：軌道吊(RMG)數量集合；

T：岸橋后小車將集裝箱卸載到AGV的時間為固定值；

Nk：岸橋k卸載的集裝箱數量；

(i,k)：岸橋k卸載第i個集裝箱；

h(i,k)：岸橋完成集裝箱i卸載工作的時間；

s(i,k)：岸橋前小車將集裝箱卸載到中轉平臺上的時刻；

r(i,k)：岸橋后小車將集裝箱從中轉平臺卸載的時刻；

d(i,k)：AGV執行岸橋k的第i個任務的時刻；

f(k,b)：AGV在岸橋k和箱區b之間的運行時間；

e(i,k)：RMG開始處理集裝箱i的時刻；

φ(n,b)：RMG運行到箱區b的第n的位置的時間；

u(i,k)：岸橋前小車開始卸載集裝箱i到中轉平臺的時刻；

M：一個較大的整數。

(2) 決策變量:

2.3 基本模型

(1) 目標函數:

MIN=MAX(u(i,k)+h(i,k))

(2) 約束條件:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

s(j+1,l)+r(j,l)-s(j,l)+T≤d(j,l)

?(j,l)∈oF,j=1,2,…,Nk-1

(11)

(14)

u(i,k)≤s(i,k)≤r(i,k)≤d(i,k)≤e(i,k)≤φ(n,b)

?i∈D,?k∈K

(15)

(16)

(17)

u(1,k)=0

(18)

?(i,k)(j,l)∈o,?(n,b)∈p,?b∈B

(19)

上述基本模型是一個混合整數規劃模型，其中目標函數為最小岸橋卸貨操作時間。式(1)表示AGV每個任務都有一個后序任務；式(2)表示AGV每個任務都有一個緊前任務；式(3)保證每個集裝箱在箱區中都有位置；式(4)保證每個箱區的位置只能放少于一個集裝箱；式(5)表示如果集裝箱被分配到了箱區b中，可以放在任意位置；式(6)表示RMG每個任務都有一個后序任務；式(7)表示RMG每個任務有一個緊前任務；式(8)表示AGV將集裝箱運到箱區交接處，RMG才能開始處理該集裝箱任務；式(9)表示只有當AGV完成前一個任務才能開始后一個任務；式(10)表示RMG只能完成前一個任務才能開始后一個任務；式(11)約束岸橋中轉平臺上的集裝箱數量；式(13)表示只有后小車將集裝箱放到AGV上，AGV才能開始任務；式(14)表示參數之間的關系；式(15)為對任務操作時間需要滿足的實際情況；式(16)和式(17)表示對于同一設備，如果(i,k)是(j,l)的前置任務，那么(i,k)就不可能再是(j,l)的后序任務，即任務流向是單向的；式(18)表示設定岸橋卸載第一個集裝箱的時刻為0；式(19)為0-1變量。

3 PSO求解

PSO是進化計算的一種，因其算法簡單，易于實現而常被用來解決非線性連續函數優化、約束優化、多目標優化等問題[18]。利用PSO算法求解AGV調度優化模型的流程是：設計并初始種群粒子，每個粒子是問題的一個可行解，粒子的位置表示一個調度的方案，通過粒子個體間的相互協作逐步在搜索空間中尋找最優解。在每一次迭代的過程中，當前粒子的位置和速度都是由上一代粒子的位置和速度所決定[19]。利用上述模型定義的適應值函數，通過粒子不斷迭代進化尋找全局最優解。

3.1 編 碼

為驗證PSO的有效性，在設計算法時，采用多層編碼粒子的方法來表示自動化碼頭的調度問題，以求得全局最優解。假設有3臺岸橋，15個裝卸任務，使用3輛AGV進行運輸，隨機運載到4個箱區中,其中箱區編號為RMG編號，則第i個任務的編碼表示為：編號為第v輛AGV將第i個任務運送到并由第b個RMG運輸到箱區中。多層編碼即初始種群示例如圖2所示。

圖2 初始種群

3.2 控制參數的選擇

(1) 學習因子 PSO中的粒子無法通過GA中交叉變異來進行更新，粒子只能通過內部速度進行更新。學習因子c1和c2為非負常數，c1調節粒子飛向最好位置方向的步長，c2則是調節粒子飛向全局最好位置方向的步長[19]。在本文中，設置c1=c2=1.494 45。

(2) 初始速度 為了防止算法在迭代過程中粒子離開搜索空間，通常設定最大速度vmax和最小速度vmin，設置種群初始速度vmax= 1，vmin=-1。

(3) 慣性權重w為慣性權重，取較大值時，粒子群具有較強的全局搜索能力，較小時，則傾向局部搜索。本文采取線性遞減的取值方法，其大小變化如下：

w=wmax-(wmax-wmin)×g/Tmax

式中:wmax=0.9，wmin=0.4，g為進化代數，Tmax為最大迭代數，Tmax=200。

4 算例驗證

以圖1的碼頭布局為模型，參照某自動化碼頭實際數據，對參數進行初步設定。假定碼頭有2個箱區，隨著任務數量的改變，雙小車岸橋和AGV的數量也進行改變。為驗證算法解決此問題的有效性，采用MATLAB實現PSO和GA，同時采用CPLEX12.6對約束條件進行求解，對比結果如表1。

表1 PSO與CPLEX、GA對比

從表1中可以看出，通過與其他兩種方法對比，我們提出的PSO算法可以獲得近似最優解。與CPLEX的最優解相比，其運行速度更快，范圍從2.42 s到7.55 s且沒有劇烈波動，GA運行速度從3.53 s到7.32 s，同樣沒有劇烈波動。在運行時間方面，CPLEX所需時間遠遠大于PSO和GA范圍。從11.32 s到11 055.28 s，波動劇烈。隨著任務數量的增加，三者運行時間都逐漸增長，但當任務數量增長到30時，CPLEX無法在合適的時間得出最優解。在運行結果方面，可以看出，隨著任務數量的增加，CPLEX、PSO和GA三者最優解結果差距不大，因此證明了PSO 算法在解決此問題的有效性。從算例6和算例7可以看出，任務數量一定時，增加AGV的數量會提高碼頭效率，使得卸船作業時間減少，提高作業效率。從算例8和算例9可以發現，并不是AGV數量越多則效率越高，數量過多反而會導致效率降低，而影響這類情況有很多原因。

以算例12為例，基于PSO對模型進行求解所得的甘特圖如圖3所示。該甘特圖中包含了岸橋作業時間、AGV 時間和箱區RMG作業時間，并每個任務編號作業區上標注了岸橋、AGV和箱區RMG編號。在本文中未設置交接區，因此運行過程中，出現了AGV運輸到箱區時等待RMG這種情況。以任務編號25為例，1號岸橋將集裝箱運輸到2號AGV，而后運輸到2號箱區，所求得收斂情況如圖4所示，最終得到的最優值為1 277 s。

圖3 調度甘特圖

圖4 PSO收斂圖

下面討論不同任務數量下雙小車岸橋和AGV數量對最優值的影響。數據均來源于運行多次結果的均值，如圖5所示。

圖5 不同岸橋及AGV數量變化下目標值的變化

可以看出：

(1) 不同雙小車岸橋數量下，最優適應度值達到最低值時的AGV數量不同。當雙小車岸橋數量為2時，AGV數量為6時適應度值最小；當雙小車岸橋數量為3時，AGV數量為9。雙小車岸橋的數量和AGV的數量應相互配合。

(2) 當雙小車岸橋數量一定時，隨著AGV數量的增加，岸橋卸載作業時間逐漸減少。這是因為當AGV數量較少時，AGV不能及時將岸橋后小車所卸載的集裝箱運到箱區。此時，岸橋需等待AGV，使得集裝箱堆積在中轉平臺上。當超過2個集裝箱時，岸橋前小車也需等待后小車，但是適應度值并非隨著AGV數量的增加而減少。例如圖3中岸橋數量為2，AGV數量為7時，可以看出最優值開始增加。出現這種情況的原因是AGV數量較多，導致當AGV將上一個集裝箱運輸到指定箱區后返回至岸橋后小車前等待運輸，而岸橋裝載能力有限，不能及時配合AGV運輸作業，造成AGV等待。

(3) 當AGV數量一定時，適應度值隨著雙小車岸橋數量的增加而減少。這是因為隨著雙小車岸橋數量的增加，岸橋前小車將任務卸載至中轉平臺，岸橋后小車將其放置于AGV上，期間任務連續，并沒有造成AGV等待岸橋后小車的情況。但是，當雙小車岸橋的數量較多時，AGV運輸能力的限制會導致后小車需要等待AGV。

5 結 語

本文針對AGV調度，基于任務作業最小化建立數學模型，設計了PSO，從雙小車岸橋作業及箱區RMG作業時間進行優化分析，在任務數量變化的情況下，改變雙小車岸橋數量和AGV數量，進行計算。算例表明，卸船時間隨著任務的數量的增加而增加，隨著AGV的數量的增加而減少，但是增加到一定程度時卸船時間反而增加。通過與CPLEX的對比分析，證明了本文所提模型和算法的有效性，并能減少卸船作業時間，提高碼頭運作效率。

在整個作業過程中，并沒有設置交接區且是在已知卸船作業順序情況下進行雙小車和AGV的調度，AGV等待的時間過長，阻礙了碼頭整體效率，且自動化碼頭調度問題同時還受到岸橋數量、堆場設備數量配置及其他資源分配和調度的影響。此外，碼頭作業裝卸流程和AGV運輸過程所造成的擁堵、沖突和死鎖問題將是以后研究的重點。