基于PSO的自動化集裝箱碼頭雙小車岸橋和AGV的協(xié)同調(diào)度

馬孫豫 楊勇生 梁承姬

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

0 引 言

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

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

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

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

1 問題描述

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

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

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

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

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

2 數(shù)學(xué)模型

2.1 模型假設(shè)

根據(jù)自動化碼頭實際情況，對相關(guān)問題進(jìn)行簡化：

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

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

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

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

(5) 每個箱區(qū)使用一個RMG進(jìn)行裝卸作業(yè)。

2.2 參數(shù)及決策變量

(1) 參數(shù)變量:

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

F：一個虛擬任務(wù)的結(jié)束，OF=D∪F；

D：集裝箱數(shù)量集合，i,j∈D；

K：岸橋數(shù)量集合，k,l∈K；

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

B：箱區(qū)數(shù)量集合，b,a∈B；

V：AGV數(shù)量集合；

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

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

Nk：岸橋k卸載的集裝箱數(shù)量；

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

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

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

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

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

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

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

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

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

M：一個較大的整數(shù)。

(2) 決策變量:

2.3 基本模型

(1) 目標(biāo)函數(shù):

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)

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

3 PSO求解

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

3.1 編 碼

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

圖2 初始種群

3.2 控制參數(shù)的選擇

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

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

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

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

式中:wmax=0.9，wmin=0.4，g為進(jìn)化代數(shù)，Tmax為最大迭代數(shù)，Tmax=200。

4 算例驗證

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

表1 PSO與CPLEX、GA對比

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

以算例12為例，基于PSO對模型進(jìn)行求解所得的甘特圖如圖3所示。該甘特圖中包含了岸橋作業(yè)時間、AGV 時間和箱區(qū)RMG作業(yè)時間，并每個任務(wù)編號作業(yè)區(qū)上標(biāo)注了岸橋、AGV和箱區(qū)RMG編號。在本文中未設(shè)置交接區(qū)，因此運行過程中，出現(xiàn)了AGV運輸?shù)较鋮^(qū)時等待RMG這種情況。以任務(wù)編號25為例，1號岸橋?qū)⒓b箱運輸?shù)?號AGV，而后運輸?shù)?號箱區(qū)，所求得收斂情況如圖4所示，最終得到的最優(yōu)值為1 277 s。

圖3 調(diào)度甘特圖

圖4 PSO收斂圖

下面討論不同任務(wù)數(shù)量下雙小車岸橋和AGV數(shù)量對最優(yōu)值的影響。數(shù)據(jù)均來源于運行多次結(jié)果的均值，如圖5所示。

圖5 不同岸橋及AGV數(shù)量變化下目標(biāo)值的變化

可以看出：

(1) 不同雙小車岸橋數(shù)量下，最優(yōu)適應(yīng)度值達(dá)到最低值時的AGV數(shù)量不同。當(dāng)雙小車岸橋數(shù)量為2時，AGV數(shù)量為6時適應(yīng)度值最??；當(dāng)雙小車岸橋數(shù)量為3時，AGV數(shù)量為9。雙小車岸橋的數(shù)量和AGV的數(shù)量應(yīng)相互配合。

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

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

5 結(jié) 語

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

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