文家獻(xiàn)，魏 晨，尹宇起，胡志華

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

1 引言

自動化集裝箱碼頭中，堆場由多個箱區(qū)組成，每個箱區(qū)海側(cè)端配備一臺自動化堆垛起重機(jī)（Automated Stacking Crane，ASC），用于搬運(yùn)集裝箱；每個箱區(qū)海側(cè)端設(shè)有自動化導(dǎo)引小車（Automated Guided Vehicle，AGV）緩沖區(qū)，用于AGV與ASC交接集裝箱，緩沖區(qū)與岸邊之間的區(qū)域為AGV 行駛區(qū)。卸船過程中，當(dāng)緩沖區(qū)中集裝箱數(shù)量等于緩沖區(qū)容量時，AGV 無法進(jìn)入緩沖區(qū)作業(yè)，在緩沖區(qū)外等待。因此，考慮緩沖區(qū)容量約束的AGV 調(diào)度是自動化集裝箱中的現(xiàn)實問題，合理安排ASC與AGV的協(xié)同調(diào)度對提高AGV利用率、實現(xiàn)自動化集裝箱碼頭整體效益最優(yōu)具有重要的指導(dǎo)意義。

2 研究現(xiàn)狀

關(guān)于自動化碼頭ASC 的調(diào)度，現(xiàn)有文獻(xiàn)主要考慮雙ASC協(xié)同作業(yè)。胡志華等考慮任務(wù)之間的最小時間間隔，以最小化ASC 完成時間為目標(biāo)盡力混合整數(shù)規(guī)劃模型，設(shè)計啟發(fā)式算法和遺傳算法進(jìn)行求解[1]。魏晨等考慮雙起重機(jī)時空同步約束條件，以最小化作業(yè)總完成時間為目標(biāo)，建立雙起重機(jī)調(diào)度混合整數(shù)規(guī)劃模型，確定起重機(jī)在每個時間點(diǎn)上所處貝位及其作業(yè)狀[2]。Gharehgozli等以最小化總?cè)蝿?wù)時間和ASC等待時間為目標(biāo)，建立混合整數(shù)規(guī)劃模型，并通過實驗驗證不設(shè)置交接區(qū)比設(shè)置交接區(qū)得到更好的結(jié)果[3]。

關(guān)于自動化碼頭AGV 調(diào)度，現(xiàn)有文獻(xiàn)的研究方式多為建立混合整數(shù)規(guī)劃模型、設(shè)計啟發(fā)式算法或遺傳算法進(jìn)行求解，以優(yōu)化AGV 作業(yè)序列。Zaghdoud 等提出迪杰斯特拉算法、遺傳算法和啟發(fā)式算法求解自動化集裝箱碼頭AGV 的調(diào)度問題[4]。Roy 等考慮同時裝卸過程中的動態(tài)調(diào)度，建立混合整數(shù)規(guī)劃模型，優(yōu)化任務(wù)分配[5]。Rashidi等建立最小成本流模型，設(shè)計基于標(biāo)準(zhǔn)網(wǎng)絡(luò)單純形法的啟發(fā)式算法求解自動化集裝箱碼頭中AGV 的調(diào)度問題[6]。Choe 等考慮自動化集裝箱碼頭的不確定性環(huán)境，設(shè)計基于在線偏好學(xué)習(xí)的啟發(fā)式算法求解AGV作業(yè)序列[7]。包曉瓊等考慮集裝箱的不同尺寸，以最小化整體作業(yè)完成時間、空載時間和最大化閑置時間為目標(biāo)，建立多目標(biāo)混合整數(shù)規(guī)劃模型，優(yōu)化車輛配對調(diào)度方案[8]。

緩沖區(qū)容量約束在流水車間中有廣泛的應(yīng)用研究。Engin 等考慮緩沖區(qū)容量，以最小化最大完成時間為目標(biāo)，設(shè)計蟻群算法研究流水車間的調(diào)度問題[9]。鄭永前等考慮到緩沖區(qū)、機(jī)器可用性約束和序列相關(guān)換模時間，以最小化最大完工時間為目標(biāo)建立混合整數(shù)規(guī)劃模型，設(shè)計啟發(fā)式算法研究流水車間調(diào)度問題，并通過實驗驗證算法的有效性和魯棒性[10]。謝展鵬等針對有限緩沖區(qū)流水線調(diào)度問題，設(shè)計基于變鄰域搜索策略的啟發(fā)式算法進(jìn)行研究[11]。曾程寬等提出基于鄰域搜索的兩階段算法對車間調(diào)度問題進(jìn)行求解，算例分析表明，當(dāng)緩沖區(qū)間容量與工件數(shù)量的比例達(dá)到20%，緩沖區(qū)間大小對調(diào)度結(jié)果的影響將會迅速變小[12]。

本文考慮時間窗和緩沖區(qū)容量約束，研究ASC 與AGV 的協(xié)同作業(yè)，以最小化總?cè)蝿?wù)完成時間和最小化總?cè)蝿?wù)延遲時間為目標(biāo)建立混合整數(shù)規(guī)劃模型，確定緩沖位的分配，優(yōu)化ASC的作業(yè)順序，提高碼頭作業(yè)效率。

3 問題描述

卸船作業(yè)中，進(jìn)口集裝箱由岸橋從船舶卸載至AGV上，然后，由AGV沿車道運(yùn)輸至緩沖區(qū)，卸載至指定緩沖位；場橋從箱區(qū)移動至緩沖區(qū)，提取集裝箱，將集裝箱搬運(yùn)至指定位置（如圖1）。在調(diào)度過程中，考慮AGV 勻速行駛且數(shù)量充足，AGV 預(yù)先在岸邊等待，因此，岸橋可連續(xù)作業(yè)。由于緩沖區(qū)容量有限，AGV到達(dá)緩沖區(qū)后，若無空閑緩沖位，則AGV等待。但每個任務(wù)要盡可能在給定的時間窗內(nèi)完成，AGV 的等待將影響任務(wù)的完成時間，因此，如何安排緩沖位與AGV的分配關(guān)系以及ASC 的作業(yè)順序，以減少任務(wù)的延遲時間和總?cè)蝿?wù)完成時間，對提高碼頭作業(yè)效率具有重要意義。

考慮時間窗和緩沖區(qū)容量約束，增加了卸船作業(yè)中ASC與AGV集成調(diào)度的復(fù)雜性。首先，AGV進(jìn)入緩沖區(qū)順序。每個任務(wù)的時間窗不同，當(dāng)某個任務(wù)（用i 表示）要盡快完成時，AGV 在緩沖區(qū)外等待將影響i 的完成時間；若提前為i 預(yù)留緩沖位，AGV 將i 運(yùn)輸?shù)骄彌_區(qū)時即可堆放至緩沖位，無需等待，但預(yù)留緩沖位會增加其他AGV 在緩沖區(qū)的等待時間。再者，任務(wù)與緩沖位分配關(guān)系。AGV到達(dá)緩沖區(qū)后，除了要安排AGV進(jìn)入緩沖區(qū)的順序，還要安排任務(wù)與緩沖位的分配關(guān)系。最后，ASC 作業(yè)順序。安排ASC 作業(yè)時需要考慮緩沖位中任務(wù)的最晚完成時間，讓盡可能多的任務(wù)在規(guī)定時間窗內(nèi)完成。

圖1 集裝箱碼頭示意圖

4 模型

根據(jù)第3 章的描述，建立混合整數(shù)規(guī)劃模型，模型中的集合、參數(shù)和決策變量設(shè)置如下。

集合：

R，任務(wù)的集合，R={1,2,…,r}；

R+，R+=R ?{ }o,d ，虛擬的起始任務(wù)和虛擬的結(jié)束任務(wù)分別為o 和d；

B，緩沖位的集合，B={1,2,…,b}。

參數(shù)：

SY，ASC完成一個任務(wù)所需要的時間；

SA，AGV在緩沖區(qū)卸載一個任務(wù)所需要的時間；

Ci，任務(wù)i 的起點(diǎn)至終點(diǎn)的距離；

V ，AGV的運(yùn)行速度；

Ti，Ti=，AGV將i 從起點(diǎn)運(yùn)輸至終點(diǎn)所需要的時間；

變量：

tF，ASC完成所有任務(wù)的時刻；

di，任務(wù)i 的延遲時間；

yi，ASC的作業(yè)次序；

xij，當(dāng)ASC 完成i 后繼續(xù)作業(yè)j 時，xij=1，否則xij=0；

vib，當(dāng)i 分配給緩沖位b 時，vib=1，否則vib=0；

wijb，當(dāng)i 和j 堆放在緩沖位b 時，wijb=1，否則wijb=0；

uij，當(dāng)i 在j 之前堆放至同一個緩沖位時，uij=1，否則uij=0。

建立混合整數(shù)規(guī)劃模型如下：

目標(biāo)函數(shù)式（1）表示最小化總?cè)蝿?wù)完成時間和最小化總?cè)蝿?wù)延遲時間。

約束（2）～（4）為卸船過程的時刻約束。式（2）表示AGV將i 堆放至緩沖位的時刻約束；式（3）表示ASC開始作業(yè)i 的時刻不小于AGV將i 堆放至緩沖位的時刻；式（4）表示ASC完成i 的時刻約束。

約束（5）～（8）為ASC作業(yè)順序和時刻約束。式（5）表示ASC 的第一個任務(wù)和最后一個任務(wù)分別是o 和d ；式（6）表示i 只有一個前繼任務(wù)和一個后繼任務(wù)；式（7）表示ASC作業(yè)兩個任務(wù)的先后關(guān)系，其中M1= ||R ，|R |表示總?cè)蝿?wù)數(shù)量；式（8）表示如果ASC 先作業(yè)i，緊接著作業(yè)j，則ASC 開始作業(yè)j 的時刻不小于ASC 完成i 的時刻，其中。

約束（9）～（12）為任務(wù)堆放至緩沖位的順序和時間約束。式（9）表示每個任務(wù)都要分配給一個緩沖位；式（10）表示如果i 和j 分配到同一個緩沖位，則vib+vjb≤2，否則vib+vjb≤1；式（11）表示如果i 和j 分配到同一個緩沖位，則要么i 在j 之前堆放到緩沖位，要么j 在i 之前堆放到緩沖位；式（12）表示如果i 在j 之前堆放至同一個緩沖位，則j 堆放到緩沖位的時刻不小于ASC完成i 的時刻。

約束（13）～（15）為目標(biāo)函數(shù)相關(guān)約束。式（13）表示ASC的總?cè)蝿?wù)完成時間不小于ASC完成每個任務(wù)的時刻；式（14）和（15）表示i 的延遲時間約束。

5 算法求解

第4章所建立的混合整數(shù)規(guī)劃模型可通過Cplex等求解器進(jìn)行求解，但求解時間復(fù)雜度較高，難以在有限時間內(nèi)得到理想解。根據(jù)實際調(diào)度過程可設(shè)計啟發(fā)式算法在有限時間進(jìn)行求解，但無法保證解的質(zhì)量。遺傳算法在求解優(yōu)化問題過程中具有求解時間的高效性、尋優(yōu)過程的自適應(yīng)性和解決復(fù)雜問題的魯棒性等特點(diǎn)[13]。因此，本文設(shè)計啟發(fā)式算法和遺傳算法進(jìn)行求解。

5.1 啟發(fā)式算法

根據(jù)AGV 到達(dá)緩沖區(qū)的時間先后，按順序?qū)GV中的集裝箱卸載至緩沖位，如果緩沖位已滿，則AGV等待；然后ASC根據(jù)集裝箱堆放至緩沖位的時間先后，依次作業(yè)。每個任務(wù)的完成時間用tEi表示，則總?cè)蝿?wù)完成時間為，總?cè)蝿?wù)延遲時間為

5.2 遺傳算法

在設(shè)計遺傳算法時，染色體的編碼、解碼、適應(yīng)度計算和遺傳算子（交叉、變異、選擇）應(yīng)該簡單有效。遺傳算法執(zhí)行代數(shù)、交叉概率和變異概率分別記為Pgen、Pc和Pm。此外，解碼方案應(yīng)當(dāng)體現(xiàn)出該問題的特征，AGV 到達(dá)緩沖區(qū)時是否可以立刻開始作業(yè)與緩沖區(qū)容量有關(guān)。遺傳算法流程如下：

開始

步驟1 g ←0；

步驟2 初始化，產(chǎn)生初始種群P( )g（編碼）；

步驟3 解碼，計算P( g )的適應(yīng)度值F( g )；

步驟4 While 終止條件沒有滿足時，do

循環(huán)開始

步驟5 交叉：由P( g )通過交叉算子產(chǎn)生CC( g )；

步驟6 變異：由P( g )通過變異算子產(chǎn)生CM( g )；

步驟7 適應(yīng)度計算：計算CC( g )和CM( g )的適應(yīng)度值

F( g )；

步驟8 選擇：通過選擇算子，從CC( g )和CM( g )中選

擇下一代個體；

步驟9 g ←g+1；

循環(huán)結(jié)束

結(jié)束

5.2.1 編碼

采用實數(shù)優(yōu)先權(quán)編碼[14]。染色體的第一段表示緩沖位與任務(wù)的分配關(guān)系，第二段表示ASC作業(yè)順序；基因位與任務(wù)序號相對應(yīng)，基因值通過U[ ]0,1 產(chǎn)生。以5個任務(wù)為例（如圖2），第一段中，任務(wù)1 的基因值是0.43，任務(wù)5的基因值是0.27；第二段中，任務(wù)1的基因值是0.93，任務(wù)5的基因值是0.46。

5.2.2 解碼

染色體的解碼過程如圖3。第一段的解碼策略為：記染色體p 的第x 個基因位的基因值為px，當(dāng)px∈[ ( b-1) /B,b/B )時，將第x 個基因?qū)?yīng)的任務(wù)分配給緩

沖位b。通過以上計算方式，可以得到分配給緩沖位b的任務(wù)集合Rb。以B=3，R=5 為例，通過第一段的解碼策略，可得到R1={2,5}，R2={1,3}，R3={4}。第二段的解碼策略為：將染色體的基因值從小到大排列，得到基因值序列，排序后基因值序列對應(yīng)的任務(wù)序列即為ASC 的作業(yè)順序，記為Rsort。以R=5 為例，通過第二段的解碼策略，可得到ASC 的作業(yè)順序Rsort=4 →5 →2 →3 →1。

5.2.3 適應(yīng)度計算

遺傳算法進(jìn)行適應(yīng)度計算時，綜合考慮AGV 到達(dá)緩沖區(qū)的時間、AGV進(jìn)入緩沖位的順序、緩沖位的容量和ASC的作業(yè)順序。為方便描述，Rsort的第j 任務(wù)用k表示，則以及目標(biāo)函數(shù)f 的計算過程如下。

輸入：Rsort，，SA，SY，| R |，

輸出：f步驟

1 j ←1

2 如果j=1，則

圖2 編碼過程

圖3 解碼過程

否則

2.2 如果k 到達(dá)緩沖區(qū)時，分配給k 的緩沖位b 處于空閑狀態(tài)，則

否則

否則

3.2 dk=0

4 j=j+1

5 如果j ≤N ，返回步驟2；否則執(zhí)行步驟6；

7 輸出f

5.2.4 遺傳算子

遺傳算子包括交叉算子、變異算子和選擇算子。

交叉算子通過模擬自然界生物的雜交過程對個體進(jìn)行交叉操作，不斷產(chǎn)生新的個體，使得遺傳算法具有較強(qiáng)的搜索能力[15]。本文交叉算子采用兩點(diǎn)交叉：在父代染色體群中依次選取兩條染色體P1P2，隨機(jī)產(chǎn)生兩個不同的點(diǎn)，然后交換P1P2的值，得到兩個子代染色體C1C2，如圖4。

個體的適當(dāng)變異可以保持種群多樣性，防止陷入局部最優(yōu)。本文變異算子采用均勻變異：生成一個與父代染色體長度相同的隨機(jī)數(shù)向量w ，隨機(jī)數(shù)范圍為（0，1）。將向量w 中第x 個位置的值記為w(x)，父代染色體P 中第x 個位置的值記為P(x)，如果w(x)小于變異率pm，則生成一個范圍在(0,1)之間的隨機(jī)數(shù)，替代父代染色體P(x)，形成子代染色體C，如圖5。

選擇算子采用輪盤賭策略，操作流程如下：

開始

步驟1 i ←1

步驟2 計算種群中每個個體的適應(yīng)度值f(xi,i=1,2,…,N)，N 為種群大小

步驟4 計算種群中每個個體的累計概率，染色體xi的累計概率記為

步驟5 隨機(jī)生成s,s ∈[0,1]

步驟6 若k =1 且s ＜qk，則選擇個體1，否則，選擇個體k，使得qk-1＜s ≤qk成立

步驟7 i ←i+1

步驟8 如果i 小于等于N ，則回到步驟5；否則結(jié)束

結(jié)束

6 實驗

本章對混合整數(shù)規(guī)劃模型和遺傳算法進(jìn)行求解，其中，混合整數(shù)規(guī)劃模型使用數(shù)學(xué)規(guī)劃模型求解器Cplex（https：//www.cplex.com）中的分支定界法（Branch-and-Bound，B&B）進(jìn)行求解。程序通過MATLAB R2018a實現(xiàn)，在處理器為Intel?Core?i5-8250U CPU@1.60 GHz 1.80 GHz、RAM為8 GB的電腦上運(yùn)行。設(shè)置：設(shè)置成首項為0，公差為40的等差數(shù)列；=+U(0,3 600)；Ci服從U[5 00,1 500] ；SY=80 s；SA=30 s；V=5 m/s。對于GA，設(shè)置：Pc=0.9，Pm=0.3，Pgen=300。

6.1 算法性能實驗

圖4 兩點(diǎn)交叉

圖5 均勻變異

表1 分支定界法、啟發(fā)式算法與遺傳算法結(jié)果對比

設(shè)置5個算例集，用標(biāo)號1～5表示，對應(yīng)的任務(wù)數(shù)量分別為10，20，30，40，50。每個算例集設(shè)置4個子算例，用字母abcd 表示，包含的緩沖區(qū)容量分別為3，4，5，6。設(shè)置分支定界法的最大運(yùn)行時間為3 600 s；遺傳算法PGen=10 000，當(dāng)500 代內(nèi)結(jié)果無變化時GA 停止運(yùn)算，記錄GA 運(yùn)行10 次目標(biāo)函數(shù)的平均值。計算結(jié)果對比見表1。

6.2 實驗結(jié)果

從表1 可看出：任務(wù)數(shù)量少于20 時，分支定界法求得的目標(biāo)函數(shù)值與遺傳算法基本一致；隨著任務(wù)數(shù)量的增加，遺傳算法的目標(biāo)值逐漸優(yōu)于分支定界法的目標(biāo)函數(shù)值，此外，遺傳算法的求解時間遠(yuǎn)少于分支定界法；啟發(fā)式算法雖然能在極短時間內(nèi)算出結(jié)果，但解的質(zhì)量不如遺傳算法。通過6.1 節(jié)的對比實驗，驗證了模型和遺傳算法算法的有效性。

圖6 ASC作業(yè)

通過GA求解算例2-d（任務(wù)數(shù)量為20，緩沖區(qū)容量為6），得到ASC 作業(yè)順序及時間，如圖6。虛線方框的長度表示任務(wù)在緩沖位的等待時間，方框中的數(shù)字表示任務(wù)序號；實線方框的長度表示ASC 完成任務(wù)所需要的時間。實線方框前沒有虛線方框表示i 堆放至緩沖位時，ASC 立刻開始作業(yè)；實線方框后緊連著虛線方框表示ASC 剛完成緩沖位的任務(wù)，AGV 立刻將下一個任務(wù)堆放至緩沖位；前后兩個方框之間的空白區(qū)域的長度表示緩沖位的空閑時間。

6.3 靈敏度實驗

設(shè)計4個靈敏度實驗，分別研究緩沖區(qū)容量對緩沖區(qū)利用率的影響、ASC 作業(yè)時間對目標(biāo)值的影響、ASC作業(yè)時間對緩沖區(qū)利用率的影響和最大遺傳代數(shù)對目標(biāo)值的影響。采用式（16）計算緩沖區(qū)利用率，其中，表示ASC 完成任務(wù)i 的時刻，表示AGV 將i 堆放至緩沖位的時刻，tF表示ASC 完成所有任務(wù)的時刻， ||B表示緩沖位的數(shù)量。

（1）緩沖區(qū)容量對緩沖區(qū)利用率的影響

設(shè)置： ||R =50， ||B 取值3，4，5，6。GA運(yùn)行10次，記錄目標(biāo)值最小時緩沖區(qū)的利用率，如圖7。從圖中可看出，緩沖區(qū)容量從3 增加到4 時，緩沖區(qū)利用率從82.08%下降到74.38%；但緩沖區(qū)容量繼續(xù)增加時，緩沖區(qū)利用率無明顯變化。

圖7 緩沖區(qū)容量對緩沖區(qū)利用率的影響

（2）ASC作業(yè)時間對目標(biāo)值的影響

設(shè)置：SY取值60，65，…，95，100； ||R =50； ||B =5；記錄GA 運(yùn)行10 次的最小值，如圖8。圖中共有3 條曲線，分別對應(yīng)模型中的目標(biāo)函數(shù)值f 、總?cè)蝿?wù)完成時間tF和總?cè)蝿?wù)延遲時間。從圖中可看出，ASC作業(yè)時間從60增加到90過程中，目標(biāo)函數(shù)值、總?cè)蝿?wù)完成時間和總?cè)蝿?wù)延遲時間均緩慢增長；作業(yè)時間從90 逐漸增加到100 時，總?cè)蝿?wù)完成時間緩慢增長，但目標(biāo)函數(shù)值和總?cè)蝿?wù)延遲時間呈指數(shù)型增長。由f=tF+可知，總?cè)蝿?wù)延遲時間的快速增長引起目標(biāo)函數(shù)值的快速增長。

圖8 ASC作業(yè)時間對目標(biāo)函數(shù)的影響

（3）ASC作業(yè)時間對緩沖區(qū)利用率的影響

設(shè)置：SY取值60，65，…，95，100； ||R =50 ； ||B =5；記錄GA運(yùn)行10次得到的緩沖區(qū)利用率，作箱線圖，如圖9。箱體的上邊緣表示上四分位數(shù)，下邊緣表示下四分位數(shù)，中間的橫線表示中位數(shù)，星號“*”表示平均值；箱體上方的短橫線表示最大值，下方的短橫線表示最小值；遠(yuǎn)離箱體的的加號“+”表示離群值。從圖中可看出，ASC 作業(yè)時間從60 增加到100，緩沖區(qū)利用率的平均值、最小值都呈上升趨勢，表示集裝箱在緩沖位的停留時間增加。

圖9 ASC作業(yè)時間對緩沖區(qū)利用率的影響

（4）最大遺傳代數(shù)對目標(biāo)值的影響

設(shè)置： ||R =50； ||B =5；Pgen=1 000；記錄GA運(yùn)行10次的結(jié)果，如圖10。圖中共有3條曲線，分別表示GA運(yùn)行10 次的最大值、最小值和其中一次運(yùn)行的收斂曲線。GA迭代過程可分為三個階段：第一階段，目標(biāo)函數(shù)值迅速下降；第二階段，目標(biāo)函數(shù)值下降速度較為平緩；第三階段，目標(biāo)函數(shù)值基本維持水平。

圖10 遺傳代數(shù)對目標(biāo)函數(shù)值的影響

7 結(jié)論

本文針對ASC 與AGV 的集成調(diào)度，考慮時間窗和緩沖區(qū)容量，以最小化總?cè)蝿?wù)完成時間和最小化總?cè)蝿?wù)延遲時間為目標(biāo)建立混合整數(shù)規(guī)劃模型，采用分支定界法和遺傳算法進(jìn)行求解，確定任務(wù)與緩沖位的分配關(guān)系以及ASC的作業(yè)順序。通過設(shè)置不同任務(wù)數(shù)量的算例集進(jìn)行算法性能實驗，驗證了模型和算法的有效性。通過靈敏度分析表明，ASC 作業(yè)時間大于90 s 時，增加ASC作業(yè)時間將使得總?cè)蝿?wù)延遲時間呈指數(shù)式增長，進(jìn)而引起目標(biāo)函數(shù)值的迅速增加。