馬孫豫 楊勇生 梁承姬

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

0 引 言

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

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

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

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

1 問題描述

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

圖1 自動(dòng)化集裝箱碼頭布局圖

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

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

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

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

2.1 模型假設(shè)

根據(jù)自動(dòng)化碼頭實(shí)際情況，對(duì)相關(guān)問題進(jìn)行簡(jiǎn)化：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

M：一個(gè)較大的整數(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)

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

3 PSO求解

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

3.1 編 碼

為驗(yàn)證PSO的有效性，在設(shè)計(jì)算法時(shí)，采用多層編碼粒子的方法來表示自動(dòng)化碼頭的調(diào)度問題，以求得全局最優(yōu)解。假設(shè)有3臺(tái)岸橋，15個(gè)裝卸任務(wù)，使用3輛AGV進(jìn)行運(yùn)輸，隨機(jī)運(yùn)載到4個(gè)箱區(qū)中,其中箱區(qū)編號(hào)為RMG編號(hào)，則第i個(gè)任務(wù)的編碼表示為：編號(hào)為第v輛AGV將第i個(gè)任務(wù)運(yùn)送到并由第b個(gè)RMG運(yùn)輸?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é)粒子飛向最好位置方向的步長(zhǎng)，c2則是調(diào)節(jié)粒子飛向全局最好位置方向的步長(zhǎng)[19]。在本文中，設(shè)置c1=c2=1.494 45。

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

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

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

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

4 算例驗(yàn)證

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

表1 PSO與CPLEX、GA對(duì)比

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

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

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

圖4 PSO收斂圖

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

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

可以看出：

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

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

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

5 結(jié) 語

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

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