自動(dòng)化碼頭多資源協(xié)同調(diào)度優(yōu)化模型與算法

初良勇， 周于佩， 姚藝飛， 許小衛(wèi)

(1.集美大學(xué) 航海學(xué)院，福建 廈門 361021； 2.福建航運(yùn)研究院，福建 廈門 361021； 3.大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116024)

自動(dòng)化碼頭作為一個(gè)復(fù)雜的整體系統(tǒng)，單獨(dú)研究單一或者2個(gè)子系統(tǒng)的協(xié)同對(duì)整個(gè)自動(dòng)化碼頭效能的提升并不顯著，也不符合自動(dòng)化碼頭作業(yè)的實(shí)際情況，在自動(dòng)化集裝箱碼頭裝卸任務(wù)的過程中，由于岸橋、自動(dòng)導(dǎo)引車(automated guided vehicle, AGV)、場(chǎng)橋這3種裝卸設(shè)備的工作范圍是靈活可變的，集裝箱在三者之間的流轉(zhuǎn)分配成為了一個(gè)復(fù)雜的問題，因此越來越多的研究學(xué)者逐漸轉(zhuǎn)移到對(duì)岸橋，AGV和場(chǎng)橋三者的協(xié)同調(diào)度研究上來。AGV作為自動(dòng)化集裝箱碼頭水平運(yùn)輸和連接場(chǎng)橋岸橋之間的重要工具，其運(yùn)輸時(shí)間也會(huì)對(duì)集裝箱整體的裝卸效率帶來影響。

在3個(gè)設(shè)備資源協(xié)同調(diào)度方面，Meersmans等[1]采用以完工時(shí)間最小為目標(biāo)的分支定界算法來解決自動(dòng)化集裝箱碼頭設(shè)備調(diào)度問題，這是AGV、岸橋、場(chǎng)橋綜合調(diào)度的首次嘗試；Homayouni等[2]將提出的遺傳算法性能和Meersmans等提出的最優(yōu)解進(jìn)行比較，得出Homayouni所提出的遺傳算法更接近最優(yōu)解。欒晨等[3]以總運(yùn)輸時(shí)間最小化為目標(biāo)，利用基于啟發(fā)式的自適應(yīng)遺傳算法進(jìn)行求解；Sadeghian等[4]對(duì)自動(dòng)化集裝箱碼頭裝卸作業(yè)的質(zhì)量控制以及裝卸作業(yè)的綜合調(diào)度進(jìn)行了研究;Yang等[5]研究比較了滾動(dòng)時(shí)域算法和基于擁堵預(yù)防規(guī)則的雙層遺傳算法，結(jié)果表明基于擁堵預(yù)防規(guī)則的雙層遺傳算法是有效的；Luo等[6]在研究裝載過程中船舶停泊時(shí)間最小化的問題中，采用自適應(yīng)啟發(fā)式算法來進(jìn)行求解。

除此之外，對(duì)于AGV的避碰問題，泰應(yīng)鵬[7]通過對(duì)時(shí)間窗的排布和賦予小車優(yōu)先級(jí)別來處理碰撞問題；凌忠奇[8]提出在AGV節(jié)點(diǎn)間發(fā)生沖突時(shí)，采用等待策略，優(yōu)先級(jí)高的AGV先通過。

由此可見，在國內(nèi)外對(duì)集裝箱碼頭多資源協(xié)同調(diào)度問題的研究中，考慮岸橋、AGV和自動(dòng)化軌道吊(automated rail mounted gantry crane，ARMG)等多資源的協(xié)同的研究較多，但考慮3種設(shè)備資源協(xié)同調(diào)度的同時(shí)加入對(duì)AGV行駛過程中碰撞問題的研究較少，且現(xiàn)有的文獻(xiàn)都是考慮在任意時(shí)間只能通過一輛AGV來減少等待時(shí)間，忽視了多個(gè)AGV同時(shí)運(yùn)行的情況。本文在研究3種設(shè)備協(xié)同調(diào)度時(shí)，考慮了多個(gè)AGV運(yùn)輸情況下可能會(huì)產(chǎn)生的路徑?jīng)_突問題。通過設(shè)計(jì)3種智能優(yōu)化算法的對(duì)比研究，從資源配置和調(diào)度執(zhí)行2個(gè)方面給出了設(shè)備資源的協(xié)同調(diào)度方案。

1 多資源協(xié)同調(diào)度問題描述

本文將水平運(yùn)輸與垂直運(yùn)輸車道根據(jù)車道方向分別進(jìn)行標(biāo)記，見圖1，其中i′與j′車道的方向?yàn)橹剌d小車從岸橋駛向堆場(chǎng)，i′′與j′′車道表示空載小車從堆場(chǎng)向岸橋的行駛車道。同時(shí)引用楊雅潔等[9]的路徑選擇方法，創(chuàng)新點(diǎn)在于將岸橋q與箱區(qū)b之間的AGV路線上水平運(yùn)輸區(qū)與堆場(chǎng)作業(yè)區(qū)的不同車道的不同組合定義為該岸橋到該箱區(qū)的不同路徑，如“Q2L→H2L→3→H1L→2→P2E→P2M→箱區(qū)2”為岸橋q到箱區(qū)b的一條路徑。如果重載AGVn在沖突點(diǎn)H2L選擇車道3，其沖突車道集合Dpnt={1，2，3}，見圖2。即AGVn在t時(shí)刻行駛到?jīng)_突點(diǎn)的3車道時(shí)，其他小車在同一時(shí)刻選擇沖突車道集合中的任意一條都會(huì)發(fā)生碰撞，不能同時(shí)經(jīng)過沖突點(diǎn)。如果選不出避碰車道，即選擇默認(rèn)車道1或6，以此達(dá)到減少AGV沖突的效果。

圖1 改建自動(dòng)化碼頭AGV路徑分布

圖2 沖突點(diǎn)的路徑分布

2 協(xié)同調(diào)度優(yōu)化模型構(gòu)建

2.1 模型假設(shè)

1)岸橋的每個(gè)小車作業(yè)時(shí)間固定；

2)ARMG作業(yè)時(shí)間固定；

3)AGV行駛狀態(tài)分為重載、空載與轉(zhuǎn)彎3種，每種狀態(tài)下均為勻速行駛。

2.2 模型參數(shù)

2.2.1 集合

Q： 岸橋的集合，(1,2,…,q)∈Q；

C：集裝箱的集合，(1,2,…,i)∈C；

V：AGVs的集合，(1,2,…,n)∈V；

B：堆場(chǎng)箱區(qū)的集合，(1,2,…,b)∈B；

BL：空載AGV出發(fā)的箱區(qū)集合；

BU：重載AGV到達(dá)的箱區(qū)集合；

Ckp(t):t時(shí)刻岸橋k的轉(zhuǎn)運(yùn)平臺(tái)緩存集裝箱的集合；

Dpnt：AGVn在t時(shí)刻的車道位置上的沖突車道集合；

S：沖突點(diǎn)集合；

L：路徑集合。

2.2.2 模型參數(shù)

TQSkj：岸橋k開始處理任務(wù)集裝箱j的時(shí)刻；

TAFjb：箱區(qū)b處理完任務(wù)集裝箱j的時(shí)刻；

TQS2kj：岸橋k的門架小車開始處理集裝箱j的時(shí)刻；

TQFkj：岸橋k將集裝箱j裝載到AGV的時(shí)刻；

TBLib：運(yùn)送集裝箱i的AGV空載離開箱區(qū)b的時(shí)刻；

TBRjl：AGV運(yùn)送集裝箱j的到達(dá)箱區(qū)l的時(shí)刻；

V1Dj：運(yùn)送任務(wù)j的AGV作業(yè)空載階段的等待時(shí)間；

V2Dj：運(yùn)送任務(wù)j的AGV作業(yè)重載階段的等待時(shí)間；

TASjl：集裝箱j到達(dá)箱區(qū)l后場(chǎng)橋開始的時(shí)刻；

TAFjl：集裝箱j到達(dá)箱區(qū)l后場(chǎng)橋結(jié)束的時(shí)刻；

ADjl：箱區(qū)l的場(chǎng)橋處理集裝箱j中的等待時(shí)間；

QDj：岸橋處理任務(wù)集裝箱j時(shí)的等待時(shí)間；

v1：空載AGV的行駛速度；

v2：重載AGV的行駛速度；

xnjr：重載AGVn運(yùn)送任務(wù)集裝箱j是否經(jīng)過路徑r；

ynjr：空載AGVn駛向任務(wù)集裝箱j所在岸橋是否經(jīng)過路徑r；

M：表示一個(gè)足夠大的正數(shù)；

a：AGV小車的車長(zhǎng)；

e：AGV小車的車寬。

2.3 協(xié)同調(diào)度優(yōu)化模型

2.3.1 目標(biāo)函數(shù)

最小化所有任務(wù)的最大完工時(shí)間如式(1)所示，為全局目標(biāo)函數(shù)，目的是為了使AGV空載運(yùn)輸過程耗時(shí)最少：

(1)

最小化每一個(gè)任務(wù)作業(yè)時(shí)間如式(2)所示，為局部目標(biāo)函數(shù)：

(2)

2.3.2 決策變量

決策變量如下所示：

βkjl：岸橋k的集裝箱j存放在箱區(qū)l時(shí)為1，否則為0；

γkjn：由岸橋k處理的集裝箱j分配給小車n時(shí)為1，否則為0；

λsr：沖突點(diǎn)s與路徑r有交集時(shí)為1，否則為0；

xnjr：重載AGVn運(yùn)送集裝箱j經(jīng)過路徑r時(shí)為1，否則為0；

ynjr：空載AGVn駛向集裝箱j所在岸橋經(jīng)過路徑r時(shí)為1，否則為0；

φn′ntir：pn′t∈Dpnt時(shí)為1，否則為0。

2.3.3 約束條件

約束條件如下所示：

(3)

(4)

其中，式(3)與式(4)表示AGV連續(xù)作業(yè)。

(5)

(6)

式(5)與式(6)表示每一個(gè)任務(wù)都有唯一的作業(yè)岸橋與存放箱區(qū)。

(7)

式(7)表示每一個(gè)任務(wù)都有唯一的AGV運(yùn)輸。

(8)

(9)

式(8)與式(9)分別表示從岸邊到箱區(qū)與箱區(qū)到岸邊選擇的AGV路徑?jīng)]有沖突點(diǎn)。

?k∈Q,?j∈C

(10)

式(10)表示岸橋前后小車多任務(wù)操作，并保證單個(gè)任務(wù)等待時(shí)間最少。

(11)

(12)

式(11)與式(12)表示AGV 2個(gè)作業(yè)階段的等待時(shí)間。

(13)

式(13)表示AGV在岸橋任務(wù)箱作業(yè)結(jié)束之前到達(dá)任務(wù)岸橋。

(14)

式(14)表示在岸橋主小車作業(yè)結(jié)束后輔小車開始作業(yè)。

TBRjl+M·(βkjl-1)≤TASjl，

?j∈C，?l∈B,?k∈Q

(15)

式(15)表示AGV在ARMG抓箱之前到達(dá)任務(wù)箱區(qū)。

?j∈C，?k∈Q

(16)

(17)

式(16)與式(17)分別表示岸橋與ARMG作業(yè)過程中的等待時(shí)間。

TQFkj-TQFk(j-1)≥2(TQSkj-TQSk(j-1))，

?j∈C，k∈Q

(18)

式(18)表示連續(xù)的2個(gè)任務(wù)的時(shí)間銜接。

3 算法設(shè)計(jì)

3.1 算法思想

通過研究初良勇等[10-12]的文獻(xiàn)，模擬退火(simulated annealing，SA)算法與粒子群優(yōu)化(particle swarm optimization，PSO)算法的應(yīng)用能夠得到：SA算法可以混合群智能算法以提高算法性能；單一優(yōu)化算法中，SA算法求解的目標(biāo)函數(shù)值較遺傳算法(genetic algorithm，GA)與PSO算法更優(yōu)，在大規(guī)模算例中表現(xiàn)尤為明顯；HGA-PSO(hybrid genetic algorithm-particle swarm optimization)算法求解的目標(biāo)函數(shù)值與SA算法求解所得目標(biāo)函數(shù)值相差較小，可混合PSO與SA算法進(jìn)行實(shí)驗(yàn)。因此本文設(shè)計(jì)SA-PSO作為模型的求解算法，該算法在PSO算法框架下混合模擬退火思想，彌補(bǔ)了PSO算法在高維復(fù)雜問題中會(huì)遇到早熟收斂的缺點(diǎn)，提升算法的全局搜索能力，同時(shí)具備較強(qiáng)的收斂能力。

1)初始化種群設(shè)定。

選擇合適的種群規(guī)模，將每次實(shí)驗(yàn)的任務(wù)數(shù)量設(shè)置為粒子群維度，設(shè)定粒子的位置邊界與最大移動(dòng)速度，在位置邊界內(nèi)隨機(jī)產(chǎn)生種群初始位置，并在速度約束內(nèi)隨機(jī)產(chǎn)生相應(yīng)的初始速度。

2)速度與位置更新公式。

采用標(biāo)準(zhǔn)粒子群算法的速度與位置更新公式：

v(2)=ω·v(1)+c1·rand·(xLocalbest-x(1))+

c2·rand·(xGbest-x(1))

(19)

x(2)=x(1)+v(2)

(20)

式中：v(1)、x(1)表示當(dāng)前粒子速度與位置；v(2)、x(2)表示更新后的粒子速度與位置；xLocalbest為局部最優(yōu)位置；xGbest為全局最優(yōu)位置；ω為慣性權(quán)重；c1、c2為學(xué)習(xí)因子。

3)適應(yīng)度函數(shù)。

以全部任務(wù)的最大完工時(shí)間為函數(shù)值設(shè)計(jì)適應(yīng)度函數(shù)，計(jì)算全部任務(wù)在最優(yōu)化的協(xié)調(diào)配置下的總時(shí)間消耗，便于實(shí)驗(yàn)結(jié)果對(duì)比。

4)退火策略。

以初始種群全局最優(yōu)適應(yīng)度值的2倍作為初始溫度，選取適當(dāng)?shù)耐嘶鹣禂?shù)，根據(jù)Metropolis準(zhǔn)則，計(jì)算當(dāng)前溫度下每個(gè)粒子的適配值，并做歸一化處理，再找出全局最優(yōu)解，通過PSO算法更新尋優(yōu)，最后以適應(yīng)度值絕對(duì)值的平均數(shù)的0.01倍為最終溫度。

5)參數(shù)設(shè)定。

根據(jù)本文模型特點(diǎn)與研究問題的特點(diǎn)，設(shè)定種群規(guī)模N為60，維度D為任務(wù)數(shù)，粒子位置上下界xmax與xmin分別為200、-200，粒子移動(dòng)最大速度vmax為400，學(xué)習(xí)因子為1.2，退火系數(shù)c為0.99。

3.2 算法步驟

本文所設(shè)計(jì)的SA-PSO算法步驟如下, 具體流程如圖3所示。

圖3 SA-PSO算法流程

1)初始化參數(shù)，在約束條件下隨機(jī)生成初始位置x與速度v，評(píng)價(jià)適應(yīng)度函數(shù)，找到全局最優(yōu)位置xGbest；

2)進(jìn)行交叉變異操作；

3)根據(jù)Metropolis準(zhǔn)則，計(jì)算當(dāng)前溫度下每個(gè)粒子的適配值，并做歸一化處理，再找出全局最優(yōu)解；

4)更新位置與速度，計(jì)算適應(yīng)度值，更新全局最優(yōu)位置xGbest；

5)溫度判斷，若當(dāng)前溫度大于最終溫度，降溫處理后進(jìn)行3)，否則，直接進(jìn)行6)；

6)若滿足終止條件，輸出最優(yōu)解；否則，返回2)。

4 多資源協(xié)同調(diào)度算例分析

本文中假設(shè)3臺(tái)岸橋同時(shí)對(duì)一艘靠泊集裝箱船進(jìn)行卸貨作業(yè)，8個(gè)箱區(qū)均有任務(wù)集裝箱存放。為了方便求解，對(duì)任務(wù)集裝箱和AGV分別進(jìn)行順序編號(hào)。實(shí)驗(yàn)參數(shù)來自遠(yuǎn)海自動(dòng)化碼頭，具體數(shù)據(jù)見表1。實(shí)驗(yàn)所用計(jì)算機(jī)為Windows10系統(tǒng)，i5處理器，8 GB內(nèi)存，并采用MATLAB 2016a軟件運(yùn)行程序。

表1 實(shí)驗(yàn)參數(shù)

4.1 資源配置分析

當(dāng)任務(wù)數(shù)量相同時(shí)，配備AGV數(shù)量越多，最大完工時(shí)間越小，如實(shí)驗(yàn)1、2、3，實(shí)驗(yàn)12、13等；實(shí)驗(yàn)3、6、9、11的適應(yīng)度值變化較小，對(duì)比實(shí)驗(yàn)13、15、17，在岸橋與AGV配比為1∶6時(shí)的實(shí)驗(yàn)中，當(dāng)任務(wù)數(shù)量大于120時(shí)，3個(gè)算法求得的最優(yōu)適應(yīng)度值變化較大；以實(shí)驗(yàn)12為分界點(diǎn)，對(duì)比岸橋與AGV配比為1∶4的實(shí)驗(yàn)與1∶6的實(shí)驗(yàn)，可以發(fā)現(xiàn)，當(dāng)任務(wù)數(shù)量大于120時(shí)，岸橋與AGV最優(yōu)配比為1∶6。當(dāng)任務(wù)數(shù)量小于120，岸橋與AGV配比在1∶4時(shí)，既能完成任務(wù)，也可節(jié)省成本投入，這對(duì)于自動(dòng)化碼頭協(xié)同調(diào)度安排具有實(shí)際意義；實(shí)驗(yàn)18前后對(duì)比，可以看出，當(dāng)任務(wù)數(shù)量達(dá)到320之后，隨著任務(wù)集裝箱數(shù)量增加，問題的復(fù)雜度增加，算法運(yùn)行時(shí)間與碼頭最大完工時(shí)間都會(huì)較大程度增加，具體情況見表2。

表2 不同數(shù)量設(shè)備資源配置實(shí)驗(yàn)結(jié)果

4.2 算法對(duì)比分析

1)算法收斂對(duì)比分析。以實(shí)驗(yàn)11和實(shí)驗(yàn)23這2組實(shí)驗(yàn)的算法收斂情況為例，如圖4所示，SA-PSO算法都表現(xiàn)出最優(yōu)的收斂結(jié)果。SA-PSO算法在兩組實(shí)驗(yàn)中表現(xiàn)在10代、70代左右收斂，在收斂效率方面只有實(shí)驗(yàn)11優(yōu)于PSO與AGPSO算法，表明SA-PSO算法收斂結(jié)果較優(yōu)，其綜合收斂能力優(yōu)于其他算法，但是其收斂效率穩(wěn)定性有待提升。

圖4 算法收斂對(duì)比

2)算法表現(xiàn)與運(yùn)行時(shí)間對(duì)比分析。每組實(shí)驗(yàn)中PSO、AGPSO與SA-PSO算法求得最優(yōu)適應(yīng)度值為模型目標(biāo)函數(shù)值，整合23組實(shí)驗(yàn)數(shù)據(jù)得到算法表現(xiàn)分析圖5；對(duì)比3個(gè)算法在每組實(shí)驗(yàn)中的運(yùn)行時(shí)間，繪制對(duì)比結(jié)果于圖6。在最優(yōu)適應(yīng)度值求解能力方面，SA-PSO算法優(yōu)于PSO算法與AGPSO算法，以PSO算法能力最弱，尤其在任務(wù)數(shù)量大于320的大規(guī)模實(shí)驗(yàn)中，SA-PSO算法優(yōu)勢(shì)更加明顯，如圖5所示；從算法運(yùn)行時(shí)間上看，PSO算法與AGPSO算法的運(yùn)行時(shí)間基本一致，說明AGPSO算法在提升PSO算法的運(yùn)行效率方面能力較弱，而SA-PSO算法運(yùn)算時(shí)間較短，提高了PSO算法運(yùn)行效率，如圖6所示。

圖5 算法表現(xiàn)分析

圖6 算法運(yùn)行時(shí)間對(duì)比

4.3 算法任務(wù)調(diào)度求解對(duì)比分析

以實(shí)驗(yàn)15為例，如圖7所示，SA-PSO算法求解得到的作業(yè)時(shí)間在2 500 s左右，比其他2個(gè)算法求解結(jié)果少300 s左右；PSO與AGPSO算法求解的任務(wù)調(diào)度總時(shí)間決定于最后單任務(wù)作業(yè)時(shí)間，整體任務(wù)調(diào)度安排沒有SA-PSO算法結(jié)果集中；SA-PSO算法整體任務(wù)調(diào)度安排集中，說明作業(yè)銜接表現(xiàn)較好。綜上所述，可以得到結(jié)論：SA-PSO在求解任務(wù)調(diào)度效率方面明顯優(yōu)于PSO與AGPSO算法，同時(shí)，其整體任務(wù)調(diào)度安排分配集中，任務(wù)作業(yè)銜接表現(xiàn)優(yōu)異，設(shè)備等待時(shí)間較少，算法求解得到的任務(wù)調(diào)度合理性明顯優(yōu)于其他算法。

圖7 算法求得的最佳任務(wù)調(diào)度時(shí)間甘特圖(實(shí)驗(yàn)15)

4.4 實(shí)驗(yàn)結(jié)論

1)任務(wù)調(diào)度安排的合理分配方式。當(dāng)任務(wù)數(shù)量相同時(shí)，在岸橋、AGV與堆場(chǎng)箱區(qū)具有最佳合理配置以內(nèi)，配備AGV數(shù)量越多，最大完工時(shí)間越??；在岸橋與任務(wù)數(shù)量相同的情況下，AGV與箱區(qū)數(shù)量配比大的作業(yè)效率高；在AGV與箱區(qū)數(shù)量配比適當(dāng)?shù)那闆r下，合理配備岸橋數(shù)量對(duì)于提升碼頭作業(yè)效率影響較大。

2)本文設(shè)計(jì)的SA-PSO算法性能綜合表現(xiàn)優(yōu)異。主要體現(xiàn)在SA-PSO算法具有較強(qiáng)的適應(yīng)度求解能力，運(yùn)行時(shí)間快、運(yùn)行效率高，綜合收斂能力強(qiáng)；在求解任務(wù)調(diào)度效率方面整體任務(wù)調(diào)度安排分配集中，任務(wù)作業(yè)銜接表現(xiàn)優(yōu)異，設(shè)備等待時(shí)間較少。

5 結(jié)論

1)本文創(chuàng)新性地考慮了AGV路徑的選擇、3種設(shè)備資源的協(xié)同調(diào)度問題，得出了從資源配置和調(diào)度執(zhí)行2個(gè)方面進(jìn)行設(shè)備資源配置的協(xié)同調(diào)度方案。

2)本文設(shè)計(jì)的混合整數(shù)規(guī)劃模型和模擬退火粒子群算法可以更好地適用于解決自動(dòng)化集裝箱碼頭設(shè)備資源協(xié)同調(diào)度優(yōu)化問題。

本文的分析結(jié)果為自動(dòng)化集裝箱碼頭多資源調(diào)度的實(shí)踐提供方法參考。未來可以對(duì)不確定環(huán)境下的多設(shè)備資源協(xié)同調(diào)度優(yōu)化問題進(jìn)行進(jìn)一步的研究。