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

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

1 引言

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

2 研究現(xiàn)狀

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

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

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

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

3 問(wèn)題描述

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

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

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

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

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

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

變量：

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

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

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

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

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

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

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

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

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

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

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

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

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

5 算法求解

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

5.1 啟發(fā)式算法

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

5.2 遺傳算法

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

開(kāi)始

步驟1 g ←0；

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

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

步驟4 While 終止條件沒(méi)有滿足時(shí)，do

循環(huán)開(kāi)始

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

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

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

F( g )；

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

擇下一代個(gè)體；

步驟9 g ←g+1；

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

結(jié)束

5.2.1 編碼

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

5.2.2 解碼

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

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

5.2.3 適應(yīng)度計(jì)算

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

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

輸出：f步驟

1 j ←1

2 如果j=1，則

圖2 編碼過(guò)程

圖3 解碼過(guò)程

否則

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

否則

否則

3.2 dk=0

4 j=j+1

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

7 輸出f

5.2.4 遺傳算子

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

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

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

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

開(kāi)始

步驟1 i ←1

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

步驟4 計(jì)算種群中每個(gè)個(gè)體的累計(jì)概率，染色體xi的累計(jì)概率記為

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

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

步驟7 i ←i+1

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

結(jié)束

6 實(shí)驗(yàn)

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

6.1 算法性能實(shí)驗(yàn)

圖4 兩點(diǎn)交叉

圖5 均勻變異

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

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

6.2 實(shí)驗(yàn)結(jié)果

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

圖6 ASC作業(yè)

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

6.3 靈敏度實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)論

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