秦 琴，梁承姬

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

1 引言

港口作為集裝箱運(yùn)輸?shù)慕煌屑~，主要起到集裝箱的中轉(zhuǎn)作用。集裝箱碼頭作為港口的重要部分，其作業(yè)效率直接影響著港口運(yùn)營(yíng)效益。近年來(lái)，隨著集裝箱港口的設(shè)備升級(jí)，碼頭的自動(dòng)化程度有了很大提升，甚至出現(xiàn)了全自動(dòng)化的集裝箱碼頭，使碼頭作業(yè)效率實(shí)現(xiàn)了質(zhì)的飛躍。根據(jù)主要的自動(dòng)化設(shè)備可以將碼頭作業(yè)系統(tǒng)分為雙小車(chē)岸橋作業(yè)子系統(tǒng)，AGV（自動(dòng)導(dǎo)引車(chē)，Auto‐mated Guided Vehicle）作業(yè)子系統(tǒng)和ARMG（自動(dòng)化軌道吊，Automated Rail Mounted Gantry Crane）作業(yè)子系統(tǒng)，三個(gè)子系統(tǒng)之間環(huán)環(huán)相扣，協(xié)同作業(yè)。集裝箱碼頭運(yùn)作成本和運(yùn)行效率很大程度上取決于碼頭作業(yè)系統(tǒng)各環(huán)節(jié)之間的協(xié)調(diào)調(diào)度，研究這三種設(shè)備的協(xié)調(diào)調(diào)度對(duì)于自動(dòng)化集裝箱港口運(yùn)作優(yōu)化有著重要意義。

關(guān)于碼頭作業(yè)系統(tǒng)的優(yōu)化研究，國(guó)內(nèi)外相關(guān)專(zhuān)家學(xué)者做出了重要貢獻(xiàn)，目前主要分為兩個(gè)子系統(tǒng)之間的協(xié)同調(diào)度優(yōu)化[1-3]以及三個(gè)子系統(tǒng)之間的集成調(diào)度優(yōu)化[4-5]。Niu 等[1]在考慮準(zhǔn)備時(shí)間的前提下研究了集卡調(diào)度與堆存問(wèn)題，并使用粒子群算法和細(xì)菌部落優(yōu)化算法求解問(wèn)題。周靜嫻等[2]研究了自動(dòng)升降車(chē)與岸橋的協(xié)同調(diào)度問(wèn)題，針對(duì)自動(dòng)升降車(chē)的任務(wù)序列進(jìn)行優(yōu)化，并得出不同情況下的最優(yōu)作業(yè)順序和作業(yè)成本。曹朋亮等[3]綜合考慮場(chǎng)橋安全距離，任務(wù)優(yōu)先級(jí)等現(xiàn)實(shí)約束，建立了裝船時(shí)間最小化的場(chǎng)橋與集卡的聯(lián)合調(diào)度模型，通過(guò)遺傳算法求解以及實(shí)證分析，證明在集卡數(shù)量較少時(shí)，作業(yè)面模式能有效減少裝船時(shí)間。欒晨等[4]將雙循環(huán)模式下的岸橋，AGV 與場(chǎng)橋集成調(diào)度問(wèn)題抽象為混合整數(shù)規(guī)劃模型，以基于啟發(fā)式的自適應(yīng)遺傳算法作為求解方法對(duì)任務(wù)完成時(shí)間進(jìn)行了優(yōu)化。Xin 等[5]研究了岸橋、AGV 和ASC（自動(dòng)堆垛機(jī)，Automated Stacking Crane）三者之間的協(xié)調(diào)調(diào)度，在AGV 路徑規(guī)劃上利用分層控制構(gòu)架，提出一種生成AGV 自由無(wú)碰撞路徑的方法以避免AGV之間的碰撞。

隨著對(duì)自動(dòng)化集裝箱碼頭裝卸設(shè)備調(diào)度優(yōu)化的不斷深入，緩沖區(qū)也越來(lái)越受到相關(guān)學(xué)者的關(guān)注，分別為雙小車(chē)岸橋的緩沖區(qū)（中轉(zhuǎn)平臺(tái)）[6-8]和堆場(chǎng)中的緩沖區(qū)（緩沖支架或AGV 伴侶）[9-10]。丁一等[6]在考慮雙小車(chē)岸橋中轉(zhuǎn)平臺(tái)的情況下，對(duì)后小車(chē)進(jìn)行作業(yè)時(shí)間窗約束，通過(guò)Cplex求解驗(yàn)證了帶有中轉(zhuǎn)平臺(tái)的雙小車(chē)岸橋?qū)τ贏GV 調(diào)度的優(yōu)越性。唐世科等[7]以最小化完工時(shí)間為目標(biāo)，建立了帶有時(shí)間窗約束的雙小車(chē)岸橋與AGV 協(xié)調(diào)調(diào)度模型，為集裝箱任務(wù)在中轉(zhuǎn)平臺(tái)上設(shè)置了時(shí)間窗，利用遺傳算法對(duì)實(shí)際算例進(jìn)行了求解分析。梁承姬等[8]在考慮中轉(zhuǎn)平臺(tái)及其容量限制的情況下，以門(mén)架小車(chē)時(shí)間窗為約束建立AGV 與雙小車(chē)岸橋的調(diào)度模型，并用遺傳算法得出AGV 與岸橋兩大設(shè)備的調(diào)度方案。程聰聰?shù)萚9]將AGV伴侶的容量約束轉(zhuǎn)化為時(shí)間窗約束，以啟發(fā)式算法求得AGV 伴侶的時(shí)間窗，粒子群算法得到AGV調(diào)度方案，結(jié)果表明AGV伴侶能有效提高AGV與場(chǎng)橋之間的協(xié)調(diào)性。添玉等[10]針對(duì)自動(dòng)化集裝箱碼頭一種自帶提升功能的AGV（L-AGV）和緩沖支架系統(tǒng)，提出了新的設(shè)備集成調(diào)度框架，并設(shè)計(jì)了雙層遺傳算法對(duì)模型進(jìn)行求解。

綜合以上所述研究現(xiàn)狀，關(guān)于自動(dòng)化集裝箱碼頭緩沖區(qū)的研究基本集中在岸橋緩沖區(qū)與水平運(yùn)輸設(shè)備AGV 或ALV 的集成調(diào)度方面，少數(shù)文獻(xiàn)對(duì)于堆場(chǎng)海側(cè)交接區(qū)設(shè)置固定的集裝箱緩沖支架進(jìn)行了考慮，但同時(shí)考慮岸橋緩沖區(qū)與堆場(chǎng)緩沖區(qū)的設(shè)備集成調(diào)度問(wèn)題尚未見(jiàn)到。本文的創(chuàng)新在于研究雙小車(chē)岸橋，AGV和ARMG三種設(shè)備集成調(diào)度的同時(shí)，充分考慮岸橋中轉(zhuǎn)平臺(tái)和緩沖支架的緩存作用，并應(yīng)用緩存有限的柔性流水車(chē)間調(diào)度理論（Limited-Buffer Flexible Flow-shop Scheduling Problem，LBFFSP）[11-13]將緩沖區(qū)和裝卸搬運(yùn)設(shè)備作為整體進(jìn)行調(diào)度優(yōu)化，這對(duì)增強(qiáng)設(shè)備間的協(xié)調(diào)性，提高AGV的使用效率有著重要作用。

2 問(wèn)題描述

圖1展示了一種自動(dòng)化碼頭“雙小車(chē)岸橋+AGV+緩沖支架+ARMG”的裝卸工藝。以進(jìn)口集裝箱為例，其作業(yè)流程主要包括雙小車(chē)岸橋操作，AGV 水平運(yùn)輸以及ARMG堆存三個(gè)階段，相鄰兩階段之間均設(shè)置有容量有限的緩沖區(qū)。第一階段，雙小車(chē)岸橋作業(yè)階段，岸橋主小車(chē)從集裝箱船上抓取集裝箱放置到岸橋中轉(zhuǎn)平臺(tái)處，岸橋門(mén)架小車(chē)將中轉(zhuǎn)平臺(tái)處的集裝箱抓取放置到岸橋下方的AGV 上；第二階段，AGV 水平運(yùn)輸階段，AGV 在基于作業(yè)面的作業(yè)模式下將集裝箱運(yùn)輸?shù)街付ㄏ鋮^(qū)，并將其放置到箱區(qū)前方的緩沖支架上，而后即可離去執(zhí)行下一個(gè)任務(wù)；第三階段，ARMG 堆存階段，ARMG 從緩沖支架上抓取集裝箱，按照堆存計(jì)劃將其放到箱區(qū)指定位置上。在這種裝卸工藝下，雙小車(chē)岸橋的中轉(zhuǎn)平臺(tái)以及堆場(chǎng)箱區(qū)海側(cè)的緩沖支架充當(dāng)容量有限的中間緩沖區(qū)，有利于提升AGV 水平運(yùn)輸與岸橋裝卸和ARMG 裝卸作業(yè)間的協(xié)調(diào)性，減少了設(shè)備間的相互等待時(shí)間。

圖1 一種帶有緩沖區(qū)的自動(dòng)化碼頭示意圖

針對(duì)以上所述裝卸工藝，本文通過(guò)引入一種帶有限中間緩存的柔性流水車(chē)間調(diào)度理論（LBFFSP）來(lái)綜合考慮雙小車(chē)岸橋、AGV、緩沖支架和ARMG 的三階段集成調(diào)度問(wèn)題?？蓪⒆詣?dòng)化碼頭作業(yè)系統(tǒng)抽象為：如圖2，n個(gè)待加工工件在車(chē)間等待進(jìn)行m 道工序的加工，m 道工序中每道工序均具有多個(gè)并行工位，每個(gè)工件只需在每道工序的其中一個(gè)工位上加工即可。相鄰兩道工序間存在容量有限的緩沖區(qū)，工件完成前一道工序即可進(jìn)入緩沖區(qū)等待下一道工序的開(kāi)始，若緩沖區(qū)容量已滿，則產(chǎn)生阻塞，直到該緩沖區(qū)有存放空間。

圖2 帶有有限緩沖區(qū)的柔性流水車(chē)間模型

由于碼頭作業(yè)的特殊性，其區(qū)別之處主要在于：

（1）集裝箱任務(wù)之間的預(yù)定義順序約束，如卸船時(shí)，靠岸側(cè)任務(wù)優(yōu)先于靠海側(cè)任務(wù)。

（2）多臺(tái)岸橋同時(shí)作業(yè)，避免交叉碰撞。

（3）設(shè)備必須移動(dòng)到指定位置才能進(jìn)行作業(yè)。

3 自動(dòng)化設(shè)備的集成調(diào)度模型

3.1 模型假設(shè)

（1）所有待作業(yè)的集裝箱均為20英尺標(biāo)準(zhǔn)箱。

（2）船舶配載計(jì)劃與堆場(chǎng)堆存計(jì)劃均已知。

（3）不考慮翻箱問(wèn)題。

（4）設(shè)備作業(yè)時(shí)間包含設(shè)備調(diào)整時(shí)間和操作時(shí)間。

（5）同一階段的并行設(shè)備作業(yè)能力相同。

3.2 模型參數(shù)及決策變量

（1）參數(shù)

J：集裝箱任務(wù)集合J={1 ,2 ,…,j}，虛擬任務(wù)j=0 為所有設(shè)備的第一個(gè)任務(wù)。

JP：預(yù)定義順序約束集合，如( j,j′ )∈Jp表示任務(wù)j必須在任務(wù)j′之前開(kāi)始作業(yè)。

M：設(shè)備集合，i ∈M 為所有設(shè)備索引，Mk表示第k階段的設(shè)備集合，k ∈{ }1,2,3。

Bj：集裝箱j在船上的所在貝位號(hào)。

Li,( i ∈ M3)：表示該ARMG 所在箱區(qū)的最大堆存容量。

Buk：表示第k階段前的緩沖區(qū)，k ∈{2 ,3}。

bck：表示Buk的容量，k ∈{2 ,3}。

buk,l：表示Buk中的緩沖工位l,l ∈{1 ,2 ,…,bck}。

Tej,k,l：集裝箱進(jìn)入緩沖工位buk,l的時(shí)間。

WAk(t)：表示t時(shí)刻緩沖區(qū)Buk中等待作業(yè)的隊(duì)列。

H：一個(gè)足夠大的正數(shù)。

（2）決策變量

uj,j′,k,i：第k 階段，集裝箱j在j′之前由設(shè)備i操作（連續(xù)）時(shí)為1，否則為0。

OAj,k(t)：t 時(shí)刻，集裝箱任務(wù)j 在WAk(t )隊(duì)列中為1，否則為0。

3.3 目標(biāo)函數(shù)及約束

式（1）為目標(biāo)函數(shù)，即最小化最大完工時(shí)間；式（2）定義作業(yè)系統(tǒng)的makespanCmax；式（3）規(guī)定操作Oj,k在第k 階段有且僅有一臺(tái)設(shè)備i 處理；式（4）表明每個(gè)操作的完成時(shí)間和作業(yè)時(shí)間之間的關(guān)系；式（5）規(guī)定虛擬任務(wù)n在第k 階段的完工時(shí)間為0；式（6）～（8）定義yj,j′,k,i，當(dāng)xj,k,i=xj′,k,i=1 時(shí)，yj,j′,k,i=yj′,j,k,i=1；式（9）和（10）規(guī)定了zj,j′,k,i和uj,j′,k,i；式（11）和（12）表明所有任務(wù)j ∈J 在JP上都有一個(gè)緊前和緊后任務(wù)；式（13）和（14）確定xj,k,i與uj,j′,k,i和uj′,j,k,i之間的關(guān)系；式（15）明確同一設(shè)備的兩個(gè)連續(xù)任務(wù)之間的順序關(guān)系；式（16）明確同一任務(wù)在連續(xù)兩個(gè)階段的操作順序約束；式（17）和（18）定義vj,j′；式（19）為岸橋避碰約束，式（20）為堆場(chǎng)容量約束；式（21）規(guī)定任務(wù)進(jìn)入緩沖區(qū)的時(shí)間要大于等于其在上一階段的完工時(shí)間；式（22）表明在t 時(shí)刻緩沖區(qū)中等待處理的隊(duì)列中包含的所有任務(wù)；式（23）是緩沖區(qū)容量有限約束，任意時(shí)刻WAk(t )中的任務(wù)總數(shù)要小于等于該緩沖區(qū)最大容量bck。

4 基于遺傳算法的調(diào)度算法

上述模型描述的調(diào)度問(wèn)題屬于NP-hard 問(wèn)題，隨著問(wèn)題規(guī)模的增大，計(jì)算復(fù)雜度將呈指數(shù)增長(zhǎng)，而遺傳算法（Genetic Algorithm，GA）以其簡(jiǎn)單通用、魯棒性強(qiáng)、并行處理廣等特點(diǎn)在求解此類(lèi)NP-hard 問(wèn)題上優(yōu)勢(shì)明顯，其良好的全局優(yōu)化能力使得其在求解大規(guī)模復(fù)雜問(wèn)題方面快速高效，在設(shè)備調(diào)度問(wèn)題和柔性流水車(chē)間調(diào)度問(wèn)題上都具有重要的應(yīng)用價(jià)值。NEH 啟發(fā)式算法是由Nawaz、Enscore 以及Ham 于1983 年提出的高效性構(gòu)造型算法[14]，具有很強(qiáng)的局部搜索能力。綜合GA 的全局優(yōu)化特點(diǎn)和NEH 的局部尋優(yōu)特點(diǎn)，本文采用NEH 啟發(fā)式算法產(chǎn)生初始解，加入到GA 中，以提高算法性能，算法流程如圖3所示。

圖3 算法流程圖

4.1 染色體編碼與解碼

本文采用基于操作的編碼方式，取所有集裝箱任務(wù)序號(hào)的一種排列組合作為一個(gè)染色體，集裝箱編號(hào)即是構(gòu)成染色體的基因值。例如：有10 個(gè)待處理的集裝箱，對(duì)于這10 個(gè)任務(wù)可以取P1=[ ]2 9 6 3 7 8 2 4 1 5 10 作為一個(gè)染色體個(gè)體，集裝箱編號(hào)在染色體中的位置即為集裝箱任務(wù)的優(yōu)先級(jí)順序，這種編碼方式搜索空間較小，易于操作。

本文采用NEH啟發(fā)式算法來(lái)生成初始解，使得生成的個(gè)體更接近最優(yōu)解，進(jìn)化效果更好，其基本原理如下：

步驟1由于已知船舶配載計(jì)劃與堆場(chǎng)堆存計(jì)劃，可以估算出每個(gè)待卸集裝箱完成三個(gè)階段所有操作所需的總加工時(shí)間，并按降序排列。

步驟2單獨(dú)考慮該序列中加工時(shí)間最大的兩個(gè)集裝箱，以最小化完工時(shí)間為目標(biāo)對(duì)它們進(jìn)行排序，形成新的序列。

步驟3依次選取剩下的集裝箱任務(wù)，插入到新的序列中，遍歷新序列中每一個(gè)可插入的位置，確定總完工時(shí)間最小的排序，直到所有任務(wù)都被選取過(guò)，即可得到一個(gè)染色體個(gè)體。

重復(fù)執(zhí)行以上所有步驟Psize遍，生成規(guī)模為Psize的初始種群。

解碼方法：

圖4 染色體交叉操作示意圖

將一個(gè)染色體的基因序列按照一定的設(shè)備分配規(guī)則依次分配到各級(jí)設(shè)備上，形成一個(gè)可行的調(diào)度方案的過(guò)程稱(chēng)為解碼。

最先空閑設(shè)備分配規(guī)則（FAM）是一種非常有效的設(shè)備分配規(guī)則，在分配時(shí)只要有設(shè)備可用，并且緩沖區(qū)內(nèi)有待處理的集裝箱任務(wù)，就可以使用FAM 規(guī)則將緩沖區(qū)中優(yōu)先級(jí)最高的任務(wù)分配給最先可用的設(shè)備，當(dāng)有多個(gè)設(shè)備可用時(shí)，隨機(jī)選擇一臺(tái)設(shè)備。由于第二階段集裝箱被AGV 運(yùn)輸?shù)讲煌南鋮^(qū)，作業(yè)時(shí)間差別較大，可能會(huì)產(chǎn)生空閑時(shí)間，在設(shè)備分配時(shí)考慮在可能的情況下，將任務(wù)插入到這些空閑時(shí)間內(nèi)，從而減少總完工時(shí)間。

步驟1判斷任務(wù)在各階段各設(shè)備上最早允許作業(yè)時(shí)間，零時(shí)刻到該設(shè)備的釋放時(shí)刻間的空隙能否插入該任務(wù)。

步驟2根據(jù)各設(shè)備的最早允許作業(yè)時(shí)間，選擇時(shí)間最早的設(shè)備i對(duì)任務(wù)j進(jìn)行加工，并更新設(shè)備i上的任務(wù)隊(duì)列，如果沒(méi)有進(jìn)行任務(wù)插入則更新設(shè)備i 的釋放時(shí)間Cj,k。

步驟3判斷所有任務(wù)是否在每個(gè)階段都進(jìn)行了設(shè)備選擇，是則結(jié)束，更新工件在各階段各設(shè)備上的Cj,k；否則返回步驟1。

任務(wù)j能否插入空閑時(shí)段[ ]

a,b 的條件為：

4.2 適應(yīng)度函數(shù)設(shè)置

fitness=1/Cmax其中，Cmax表示所有集裝箱任務(wù)的一個(gè)調(diào)度方案的最大完工時(shí)間。

4.3 遺傳操作

選擇復(fù)制：精英保留，每個(gè)染色體個(gè)體被保留的概率與其適應(yīng)度函數(shù)值大小成正比，優(yōu)先選擇適應(yīng)度大的個(gè)體，最終選取10%的父代最優(yōu)個(gè)體和90%的新生個(gè)體形成新種群。

交叉算子：部分映射交叉（Partial Mapped Crossover，PMX），根據(jù)交叉概率從種群中選取兩個(gè)父代個(gè)體，隨機(jī)選取兩個(gè)交叉點(diǎn)，將兩個(gè)交叉點(diǎn)之間的基因片段根據(jù)映射關(guān)系進(jìn)行替換，即可得到新個(gè)體，交叉操作如圖4所示。

變異算子：兩點(diǎn)交換，如圖5，根據(jù)變異概率選取一個(gè)父代染色體，隨機(jī)選取該染色體上兩個(gè)不同基因位置，交換這兩個(gè)位置上的基因，即能變異得到新染色體。

圖5 染色體變異操作示意圖

5 數(shù)值分析

5.1 GA的參數(shù)設(shè)置與初始解對(duì)比

參數(shù)設(shè)置對(duì)GA 算法性能有重要影響，問(wèn)題類(lèi)型的不同導(dǎo)致算法參數(shù)的選取存在差異。為找到適當(dāng)?shù)膮?shù)，基于算法的收斂性和算法運(yùn)行時(shí)間進(jìn)行了同一問(wèn)題的多次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1 所示，在所有備選參數(shù)中，當(dāng)交叉概率Pc=0.9，變異概率Pm=0.2時(shí)算法性能最佳。

優(yōu)質(zhì)的初始種群能夠提高GA 的全局收斂性，使其更快地到達(dá)最優(yōu)解。為驗(yàn)證NEH 啟發(fā)式算法產(chǎn)生初始種群的遺傳算法相較于傳統(tǒng)遺傳算法的優(yōu)越性，進(jìn)行了初始解對(duì)比實(shí)驗(yàn)，將NEH 產(chǎn)生初始種群解的質(zhì)量與隨機(jī)產(chǎn)生的初始種群解的質(zhì)量進(jìn)行對(duì)比，作為NEH 啟發(fā)式算法產(chǎn)生初始解的質(zhì)量的客觀依據(jù)。每個(gè)實(shí)驗(yàn)重復(fù)10 次，分別記錄初始種群最優(yōu)解和解的均值，實(shí)驗(yàn)結(jié)果如表2 所示，A 表示NEH 初始種群最優(yōu)解，B 表示隨機(jī)初始種群最優(yōu)解，C 表示NEH 初始種群解的均值，D 表示隨機(jī)初始種群解的均值。

相同條件下的10 次實(shí)驗(yàn)中，采用NEH 產(chǎn)生的初始種群最優(yōu)解的平均值為35.75 min，解均值的平均值為42.1 min；隨機(jī)產(chǎn)生的初始種群的最優(yōu)解的平均值為40.78 min，解均值的平均值為49.55 min，由此可知，NEH 產(chǎn)生的初始種群解的質(zhì)量明顯優(yōu)于隨機(jī)產(chǎn)生的初始種群解的質(zhì)量，很大程度地提升GA 性能，使其更符合本文的計(jì)算要求。

表1 GA參數(shù)設(shè)置

表2 初始種群對(duì)比實(shí)驗(yàn) min

5.2 有限緩沖區(qū)情況下的算例分析

某集裝箱港口的自動(dòng)化碼頭現(xiàn)需使用6 臺(tái)雙小車(chē)岸橋，20 輛AGV，對(duì)某艘集裝箱船上的300 個(gè)進(jìn)口集裝箱進(jìn)行卸載作業(yè)，根據(jù)堆場(chǎng)堆存計(jì)劃已知這300 個(gè)進(jìn)口集裝箱分布在堆場(chǎng)的15 個(gè)不同的箱區(qū)中，即需要使用15 臺(tái)ARMG 對(duì)其進(jìn)行堆存作業(yè)。其中，雙小車(chē)岸橋主小車(chē)卸載一個(gè)標(biāo)準(zhǔn)箱的時(shí)間固定為110 s，門(mén)架小車(chē)卸載一個(gè)標(biāo)準(zhǔn)箱的時(shí)間固定為60 s，AGV 的行駛速度為8 m/s，AGV 到達(dá)指定位置后處理集裝箱的時(shí)間為20 s，ARMG 處理一個(gè)標(biāo)準(zhǔn)箱的時(shí)間固定為80 s。雙小車(chē)岸橋中轉(zhuǎn)平臺(tái)緩存容量為2 個(gè)標(biāo)準(zhǔn)集裝箱，堆場(chǎng)箱區(qū)海測(cè)的緩沖支架容量為5 個(gè)標(biāo)準(zhǔn)集裝箱。集裝箱船到堆場(chǎng)各箱區(qū)的距離矩陣如表3所示。

GA 相關(guān)參數(shù)設(shè)置如下：種群規(guī)模Psize=100 迭代次數(shù)gen=500,交叉概率Pc=0.9,變異概率Pm=0.2。NEH啟發(fā)式算法以及GA 的程序均是通過(guò)Matlab2016b 仿真軟件實(shí)現(xiàn)，運(yùn)行于Windows 8 操作系統(tǒng)，處理器為In‐tel?CoreTMi3，CPU2.50 GHz，內(nèi)存為4.0 GB 的PC 機(jī)上。

通過(guò)程序運(yùn)行，得到GA 的收斂情況如圖6所示，最終得到的最優(yōu)完工時(shí)間約為9 847.3 s，雙小車(chē)岸橋的調(diào)度方案以及任務(wù)排序如表4 所示，表5 為ARMG 的堆存作業(yè)調(diào)度方案，AGV 的指派結(jié)果如表6 所示，表7 為優(yōu)化前（無(wú)緩沖區(qū)）與優(yōu)化后（有緩沖區(qū)）的完工時(shí)間的對(duì)比。

表3 船舶到各箱區(qū)的距離 m

表4 雙小車(chē)岸橋作業(yè)調(diào)度結(jié)果

表5 ARMG作業(yè)調(diào)度

圖6 遺傳算法收斂圖

表6 AGV指派結(jié)果

表7 優(yōu)化前后完工時(shí)間比較

由表7 的優(yōu)化前后完工時(shí)間的對(duì)比結(jié)果可以看出，在船舶配載計(jì)劃與堆場(chǎng)堆存計(jì)劃均已知的情況下，緩沖區(qū)的設(shè)置能顯著減少完工時(shí)間，表4～6 的調(diào)度結(jié)果也可以看出，設(shè)置緩沖區(qū)不僅使各階段的各臺(tái)設(shè)備間的運(yùn)作銜接更加流暢，也使每臺(tái)設(shè)備在整體作業(yè)中被分配的任務(wù)更加均衡，一定程度上避免了某臺(tái)設(shè)備長(zhǎng)時(shí)間被閑置或某些設(shè)備高負(fù)荷作業(yè)所產(chǎn)生的資源浪費(fèi)以及完工時(shí)間延長(zhǎng)等現(xiàn)象。

5.3 算法比較

前文利用改進(jìn)遺傳算法得到了較大規(guī)模算例的調(diào)度結(jié)果，本節(jié)為進(jìn)一步驗(yàn)證本文提出的集成調(diào)度模型與算法的合理有效性，引入粒子群算法（Particle Swarm Optimization，PSO），將其運(yùn)算結(jié)果與GA 的結(jié)果進(jìn)行對(duì)比分析。PSO 的種群規(guī)模Psize=100，最大迭代次數(shù)gen=500，采用Eberhart 等[15]推薦的參數(shù)，慣性權(quán)重ω=0.729 8，加速常數(shù)c1=c2=1.496 18，GA 的實(shí)驗(yàn)參數(shù)延續(xù)前文的設(shè)置，兩種算法中緩沖區(qū)容量設(shè)置情況相同。根據(jù)所需處理的集裝箱量的多少以及所需裝卸設(shè)備的數(shù)量的大小，分別設(shè)計(jì)9 組小規(guī)模算例實(shí)驗(yàn)和9 組大規(guī)模算例實(shí)驗(yàn)，通過(guò)對(duì)比不同規(guī)模下的算例實(shí)驗(yàn)來(lái)比較GA 與PSO 在實(shí)驗(yàn)結(jié)果上的差異，包括算法得出的完工時(shí)間與算法運(yùn)行所需的時(shí)間，每組實(shí)驗(yàn)均運(yùn)行5 次，實(shí)驗(yàn)結(jié)果取平均值。

兩種算法的對(duì)比結(jié)果如表8，表9 所示，T、Q、R、V 分別表示集裝箱、雙小車(chē)岸橋、ARMG與AGV的數(shù)量。小規(guī)模算例實(shí)驗(yàn)下，PSO的運(yùn)行時(shí)間普遍比GA長(zhǎng)，但是兩種算法得到的完工時(shí)間都相差不大，GA的優(yōu)勢(shì)不明顯；相較于小型問(wèn)題，大規(guī)模問(wèn)題下遺傳算法的高效性更加明顯，9組大規(guī)模算例中，不論是完工時(shí)間還是算法運(yùn)行時(shí)間，GA都明顯優(yōu)于PSO。綜合以上分析可以說(shuō)明，就本文所研究的問(wèn)題而言，遺傳算法是一種高效可行的求解方法，通過(guò)與PSO的結(jié)果對(duì)比也證明了本文提出的包括緩沖區(qū)在內(nèi)的多設(shè)備集成調(diào)度模型與算法能有效滿足自動(dòng)化碼頭集成調(diào)度的要求。

5.4 緩沖區(qū)容量對(duì)完工時(shí)間的影響分析

為了評(píng)估不同任務(wù)規(guī)模下隨AGV 數(shù)量的增多，緩沖區(qū)容量的設(shè)置對(duì)于整個(gè)調(diào)度的完工時(shí)間的影響，分別進(jìn)行以下兩組實(shí)驗(yàn)，較小任務(wù)規(guī)模實(shí)驗(yàn)與較大任務(wù)規(guī)模實(shí)驗(yàn)，每組包含3 個(gè)緩沖區(qū)容量設(shè)置不同的實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)在Matlab 中分別運(yùn)行10 次，取最大完工時(shí)間的平均值作為評(píng)價(jià)指標(biāo)，其中bc2表示岸橋中轉(zhuǎn)平臺(tái)容量，bc3表示緩沖支架容量。

表8 小規(guī)模問(wèn)題算法求解結(jié)果對(duì)比

表9 大規(guī)模問(wèn)題算法求解結(jié)果對(duì)比

小規(guī)模實(shí)驗(yàn)：60 個(gè)標(biāo)準(zhǔn)箱，2 臺(tái)雙小車(chē)岸橋，5 臺(tái)ARMG，AGV 數(shù)量為3～10 輛；大規(guī)模實(shí)驗(yàn)：400 個(gè)標(biāo)準(zhǔn)箱，8 臺(tái)雙小車(chē)岸橋，14 臺(tái)ARMG，AGV 數(shù)量設(shè)置為10～20輛。

圖7 不同緩沖容量的比較（小規(guī)模）

圖7 為小規(guī)模實(shí)驗(yàn)結(jié)果，從橫向看，當(dāng)緩沖區(qū)容量固定時(shí)，隨著AGV 數(shù)量的增多，完工時(shí)間逐漸減少，但當(dāng)AGV 數(shù)量達(dá)到6 輛時(shí)，不論緩沖區(qū)容量是多少，平均最大完工時(shí)間不變或變化甚微，因?yàn)榇藭r(shí)的AGV 數(shù)量足夠多，可以通過(guò)AGV 調(diào)度滿足岸橋與ARMG 的作業(yè)需求。此后，完工時(shí)間隨AGV 數(shù)量增大反而逐漸上升，但是增加幅度較小，這是因?yàn)锳GV 數(shù)量過(guò)多時(shí)，受雙小車(chē)岸橋和ARMG 裝卸能力的限制以及緩沖區(qū)容量的限制，AGV 到達(dá)中轉(zhuǎn)平臺(tái)下方時(shí)需要等待岸橋卸載集裝箱，AGV 運(yùn)輸集裝箱到達(dá)指定箱區(qū)時(shí)，需要等待ARMG可用或緩沖支架可用，其中造成的等待時(shí)間增加了整體作業(yè)的完工時(shí)間。縱向來(lái)看，當(dāng)AGV 數(shù)量固定時(shí)，隨著緩沖區(qū)容量的增大，平均完工時(shí)間得到有效減少，當(dāng)AGV 數(shù)量較少時(shí)這種現(xiàn)象尤為明顯，因?yàn)榫彌_區(qū)容量越大暫存的集裝箱越多，AGV 到達(dá)時(shí)不必等待雙小車(chē)岸橋與ARMG，直接取走或放下集裝箱即可，減少了設(shè)備之間的等待時(shí)間。

從圖8 中可以更加清晰地看出，當(dāng)作業(yè)量達(dá)到一定規(guī)模時(shí)，緩沖區(qū)及其容量的設(shè)置對(duì)于完工時(shí)間的優(yōu)化效果更為明顯。AGV 數(shù)量為17 輛時(shí)，緩沖區(qū)設(shè)置為bc2=3,bc3=6 的實(shí)驗(yàn)的完工時(shí)間達(dá)到最優(yōu)，11 450 s 左右，相比緩沖區(qū)為bc2=0,bc3=0 的實(shí)驗(yàn)結(jié)果，優(yōu)化了1 120 s 左右，相比緩沖區(qū)為bc2=2,bc3=4 的實(shí)驗(yàn)結(jié)果，優(yōu)化了約456 s。但由于緩沖區(qū)容量有限，AGV 數(shù)量超過(guò)17輛后，設(shè)備等待時(shí)間增多導(dǎo)致完工時(shí)間增大。

圖8 不緩沖區(qū)容量的比較（大規(guī)模）

綜合兩組實(shí)驗(yàn)的結(jié)果可以說(shuō)明，緩沖區(qū)的合理設(shè)置使得集裝箱碼頭各種設(shè)備資源間的協(xié)調(diào)性增強(qiáng)，有效減少了船舶在港作業(yè)的完工時(shí)間，提高了AGV 的使用率，減少AGV 的使用量，從而在一定程度上降低了碼頭擁堵的可能性。

6 結(jié)語(yǔ)

本文主要研究了自動(dòng)化碼頭帶有緩沖設(shè)置的多設(shè)備集成調(diào)度問(wèn)題，以緩沖有限的柔性流水車(chē)間為基礎(chǔ)建立了混合整數(shù)規(guī)劃模型，使用改進(jìn)的遺傳算法進(jìn)行求解，算例分析與算法對(duì)比的結(jié)果表明，本文的模型與算法能夠有效提高碼頭運(yùn)作效益：（1）相較于普通裝卸工藝，“雙小車(chē)岸橋+AGV+緩沖支架+ARMG”這種帶有緩沖區(qū)的裝卸工藝能有效減少完工時(shí)間；（2）緩沖區(qū)的合理設(shè)置不僅能提高設(shè)備間的協(xié)調(diào)性，還能減少AGV 的使用數(shù)量，為集裝箱碼頭降本增效。

自動(dòng)化碼頭存在各種復(fù)雜多變的不確定性，這些不確定因素都會(huì)對(duì)作業(yè)效率產(chǎn)生影響，本文的研究未能將這些隨機(jī)因素考慮在內(nèi)，例如堆場(chǎng)內(nèi)的交通擁堵，AGV的速度變化等。未來(lái)關(guān)于自動(dòng)化碼頭新型設(shè)備的調(diào)度研究可以將這些不確定因素柔性化，利用柔性調(diào)度理論考慮碼頭的動(dòng)態(tài)性，不確定性和復(fù)雜性，可以使研究更具現(xiàn)實(shí)意義。