劉志雄　李　俊　張　煜　東經(jīng)偉

1(武漢科技大學(xué)汽車與交通工程學(xué)院　湖北 武漢 430081)2(武漢理工大學(xué)物流工程學(xué)院　湖北 武漢 430063)3(天津港集裝箱碼頭有限公司　天津 300456)

?

基于混合演化策略算法的多場(chǎng)橋調(diào)度優(yōu)化

劉志雄1李俊1張煜2東經(jīng)偉3

1(武漢科技大學(xué)汽車與交通工程學(xué)院湖北 武漢 430081)2(武漢理工大學(xué)物流工程學(xué)院湖北 武漢 430063)3(天津港集裝箱碼頭有限公司天津 300456)

摘要針對(duì)集裝箱堆場(chǎng)多場(chǎng)橋調(diào)度問(wèn)題，構(gòu)建調(diào)度模型，提出一種混合演化策略算法。采用基于實(shí)數(shù)的四維個(gè)體編碼方法，設(shè)計(jì)了基于三點(diǎn)交叉互換的重組算子以及基于兩點(diǎn)互換的變異算子，并采用三種不同的局部搜索策略來(lái)優(yōu)化算法的性能。通過(guò)算例分析證明混合演化策略算法在優(yōu)化多場(chǎng)橋調(diào)度問(wèn)題時(shí)的有效性。在三種不同的局部搜索策略中，基于互換操作的局部搜索策略要優(yōu)于其他兩種，能明顯改善演化策略算法的優(yōu)化性能。最后，通過(guò)一組對(duì)比試驗(yàn)對(duì)局部搜索的次數(shù)進(jìn)行了分析。

關(guān)鍵詞多場(chǎng)橋調(diào)度演化策略算法局部搜索

0引言

集裝箱運(yùn)輸?shù)难该桶l(fā)展給港口的作業(yè)能力帶來(lái)了巨大的挑戰(zhàn)。由于集裝箱碼頭的改建和設(shè)備投入都需要大量的資金注入，因此如何充分利用現(xiàn)有資源來(lái)提升碼頭裝卸作業(yè)效率成為了當(dāng)下的研究熱點(diǎn)。堆場(chǎng)作為堆存集裝箱的重要場(chǎng)地，在整個(gè)碼頭作業(yè)中起到緩沖作用，對(duì)整個(gè)碼頭的裝卸作業(yè)效率、吞吐能力以及船舶在港時(shí)間等都有很大的影響。在現(xiàn)有的岸邊作業(yè)系統(tǒng)和水平運(yùn)輸系統(tǒng)一定的情況下，堆場(chǎng)作業(yè)效率成為了制約碼頭吞吐能力的瓶頸，而場(chǎng)橋作為堆場(chǎng)作業(yè)中的核心設(shè)備，是提高堆場(chǎng)作業(yè)效率的關(guān)鍵。如何對(duì)場(chǎng)橋進(jìn)行有效地調(diào)度，從而保障整個(gè)堆場(chǎng)的作業(yè)效率是亟需解決的問(wèn)題。

目前，針對(duì)集裝箱堆場(chǎng)場(chǎng)橋調(diào)度問(wèn)題，國(guó)內(nèi)外學(xué)者分別設(shè)置不同的規(guī)則，采用算法求解或是仿真建模的方法進(jìn)行了優(yōu)化研究。陳歡[1]建立了多臺(tái)場(chǎng)橋作業(yè)動(dòng)態(tài)調(diào)度的模型，采用貪婪算法進(jìn)行優(yōu)化求解，并基于AnyLogic軟件構(gòu)建了仿真模型。王巖[2]以完成裝箱任務(wù)時(shí)場(chǎng)橋最大移動(dòng)時(shí)間最短為目標(biāo)建立了多臺(tái)場(chǎng)橋的路徑優(yōu)化模型，設(shè)計(jì)了進(jìn)化規(guī)劃算法進(jìn)行優(yōu)化求解。賈志剛[3]以延遲任務(wù)量、轉(zhuǎn)場(chǎng)總時(shí)間與空閑總時(shí)間三者最小化為目標(biāo)構(gòu)建了場(chǎng)橋的調(diào)度模型，將啟發(fā)式算法和遺傳算法結(jié)合來(lái)優(yōu)化求解。牟蓮芝[4]構(gòu)建了場(chǎng)橋的優(yōu)化調(diào)度模型，設(shè)計(jì)了蟻群算法進(jìn)行優(yōu)化求解。張琪[5]構(gòu)建了考慮干涉的多場(chǎng)橋調(diào)度優(yōu)化模型，設(shè)計(jì)了一些調(diào)度規(guī)則進(jìn)行編程求解。樂(lè)美龍等[6]考慮場(chǎng)橋在實(shí)際作業(yè)中不可相互跨越與安全距離等約束，建立了場(chǎng)橋作業(yè)調(diào)度模型，設(shè)計(jì)了兩階段啟發(fā)式算法進(jìn)行求解。趙磊等[7]以堆場(chǎng)箱區(qū)作業(yè)箱量均衡和作業(yè)時(shí)間均衡為目標(biāo)建立了場(chǎng)橋均衡調(diào)度模型，并設(shè)計(jì)遺傳算法求解。何軍良等[8]將場(chǎng)橋調(diào)度和堆存空間分配作為整體考慮，構(gòu)建了場(chǎng)橋的動(dòng)態(tài)調(diào)度模型，設(shè)計(jì)了基于整數(shù)規(guī)劃模型和啟發(fā)式算法來(lái)進(jìn)行求解。嚴(yán)偉等[9]以到各時(shí)段中剩余總工作量最小為目標(biāo)構(gòu)建了基于整數(shù)規(guī)劃的場(chǎng)橋動(dòng)態(tài)調(diào)度模型，采用最佳優(yōu)先搜索算法進(jìn)行優(yōu)化求解。K．L．Mak等[10]通過(guò)遺傳算法和禁忌搜索的混合算法，求解帶有機(jī)器干涉約束的場(chǎng)橋調(diào)度問(wèn)題。H.Javanshir等[11]考慮場(chǎng)橋的干涉約束，構(gòu)建了混合整數(shù)規(guī)劃模型，采用遺傳算法進(jìn)行模型的優(yōu)化求解。這些文獻(xiàn)大多都沒(méi)考慮場(chǎng)橋轉(zhuǎn)向次數(shù)過(guò)多的問(wèn)題，而在實(shí)際作業(yè)中場(chǎng)橋的轉(zhuǎn)向次數(shù)過(guò)多將直接影響整個(gè)堆場(chǎng)的作業(yè)效率。

本文將在考慮最短路的前提下，以減少場(chǎng)橋的轉(zhuǎn)向次數(shù)和最小化場(chǎng)橋的最大作業(yè)完工時(shí)間為目標(biāo)，構(gòu)建多目標(biāo)的多場(chǎng)橋優(yōu)化調(diào)度模型。針對(duì)構(gòu)建的模型，設(shè)計(jì)一種混合演化策略算法進(jìn)行優(yōu)化求解。最后，根據(jù)天津港集裝箱碼頭堆場(chǎng)的實(shí)際情況，設(shè)置幾種規(guī)模不同的作業(yè)場(chǎng)景來(lái)驗(yàn)證模型以及算法的有效性。

1多場(chǎng)橋調(diào)度問(wèn)題

對(duì)進(jìn)口箱作業(yè)而言，當(dāng)岸橋把集裝箱從船舶上卸載下來(lái)以后，放到集卡上，然后由集卡水平運(yùn)輸?shù)蕉褕?chǎng)進(jìn)行堆存。由于具有空箱位的貝位往往在不同的箱區(qū)內(nèi)，為了保證場(chǎng)橋作業(yè)的均衡，場(chǎng)橋往往需要進(jìn)行轉(zhuǎn)場(chǎng)作業(yè)，同時(shí)在轉(zhuǎn)場(chǎng)時(shí)，若前后作業(yè)的兩個(gè)箱區(qū)不在同一條直線上，場(chǎng)橋還需要進(jìn)行轉(zhuǎn)向。由于場(chǎng)橋胎壓較高，轉(zhuǎn)向時(shí)對(duì)輪胎會(huì)有一定程度的磨損，同時(shí)場(chǎng)橋在轉(zhuǎn)向時(shí)會(huì)在通道上花費(fèi)大量時(shí)間，導(dǎo)致道路的擁堵，影響集卡和其他場(chǎng)橋的通行，因而場(chǎng)橋的轉(zhuǎn)向不僅會(huì)增加設(shè)備的使用成本，也會(huì)降低堆場(chǎng)的整體作業(yè)效率。

多場(chǎng)橋調(diào)度問(wèn)題是指針對(duì)堆場(chǎng)內(nèi)某一時(shí)間段內(nèi)的堆箱作業(yè)任務(wù)，安排多臺(tái)場(chǎng)橋來(lái)共同完成，這時(shí)就需要在保證堆箱順序的前提下，考慮場(chǎng)橋移動(dòng)的最短距離，對(duì)多個(gè)場(chǎng)橋進(jìn)行移動(dòng)，確定每臺(tái)場(chǎng)橋的行走路徑，明確場(chǎng)橋每次作業(yè)的貝位位置以及在該貝位位置上的作業(yè)箱量，最后在該時(shí)間段的堆箱作業(yè)任務(wù)全部完成時(shí)，在保證參與作業(yè)的所有場(chǎng)橋的轉(zhuǎn)向次數(shù)盡量小的同時(shí)，使所有場(chǎng)橋的最大作業(yè)完工時(shí)間最小化。

1.1貝位的坐標(biāo)表示

圖1　貝位位置坐標(biāo)的說(shuō)明示意圖

由于集裝箱碼頭堆場(chǎng)的布局一般都很規(guī)整，為了確定每個(gè)時(shí)刻場(chǎng)橋所在的貝位(bay)位置，現(xiàn)采用一種三維坐標(biāo)的形式(x，y，z)來(lái)對(duì)堆場(chǎng)內(nèi)的貝位進(jìn)行編碼。其中第一維x表示箱區(qū)(block)所在的列，第二維y表示箱區(qū)所在的行，第三維z表示箱區(qū)內(nèi)的貝位號(hào)。如圖1所示，圖中標(biāo)“1”的貝位位置可以表示為(1，1，4)，標(biāo)“2”的貝位位置可以表示為(2，1，6)，標(biāo)“3”的貝位位置可以表示為(3，1，10)，標(biāo)“4”的貝位位置可以表示為(1，2，3)，標(biāo)“5”的貝位位置可以表示為(1，3，7)，標(biāo)“6”的貝位位置可以表示為(3，3，4)。這樣每個(gè)貝位位置就可以用唯一的坐標(biāo)來(lái)表示，方便調(diào)度模型的求解。

1.2模型假設(shè)

針對(duì)天津港集裝箱碼頭堆場(chǎng)的實(shí)際情況，對(duì)構(gòu)建的模型做出以下幾點(diǎn)假設(shè)：

(1) 堆場(chǎng)內(nèi)所有場(chǎng)橋的作業(yè)能力等基本參數(shù)相同；

(2) 不存在多臺(tái)場(chǎng)橋處于同一貝位產(chǎn)生沖突的情況；

(3) 忽略堆場(chǎng)中集卡阻塞對(duì)場(chǎng)橋調(diào)度的影響；

(4) 每個(gè)箱區(qū)在任意時(shí)刻至多只有2臺(tái)場(chǎng)橋；

(5) 只考慮普通箱的堆存情況；

(6) 不考慮場(chǎng)橋作業(yè)的等待時(shí)間。

1.3參數(shù)定義

M：堆場(chǎng)內(nèi)的場(chǎng)橋總數(shù)(單位：臺(tái))

N：堆場(chǎng)內(nèi)的箱區(qū)數(shù)(單位：個(gè))

Dx：兩水平相鄰箱區(qū)間的水平距離(單位：米)

Dy：兩垂直相鄰箱區(qū)間的垂直距離(單位：米)

LXi：箱區(qū)i的長(zhǎng)度(i=1，2，…，N)(單位：米)

WX：箱區(qū)的寬度(單位：米)

Bi：箱區(qū)i內(nèi)的貝位數(shù)(i=1，2，…，N)(單位：個(gè))

LB：?jiǎn)蝹€(gè)貝位的長(zhǎng)度(沿箱區(qū)長(zhǎng)度方向)(單位：米)

q：場(chǎng)橋的作業(yè)效率(單位：TEU/分)

v：場(chǎng)橋的水平移動(dòng)速度(單位：米/秒)

tr：場(chǎng)橋完成一次90°轉(zhuǎn)彎所需的時(shí)間(單位：秒)

Cxyz：貝位(x，y，z)的空箱位(單位：個(gè))

Q：需要進(jìn)行堆存的總作業(yè)箱量(單位：TEU)

ni：場(chǎng)橋i的總作業(yè)次數(shù)(i=1，2，…，M)(單位：次)

Qij：場(chǎng)橋i的第j次作業(yè)的作業(yè)箱量(i=1，2，…，M；j=1，2，…，ni)(單位：TEU)

DTij：場(chǎng)橋i到達(dá)第j次作業(yè)貝位位置所需要的移動(dòng)時(shí)間(i=1，2，…，M；j=1，2，…，ni)(單位：秒)

Aij：場(chǎng)橋i到達(dá)第j次作業(yè)貝位位置是否需要90°轉(zhuǎn)向的決策變量，若需要90°轉(zhuǎn)向，則Aij的值為1，否則為0(i=1，2，…，M；j=1，2，…，ni)

1.4調(diào)度模型

調(diào)度模型的優(yōu)化目標(biāo)是在考慮最短路的前提下，減少場(chǎng)橋轉(zhuǎn)向次數(shù)的同時(shí)，最小化場(chǎng)橋的最大作業(yè)完工時(shí)間。其中，場(chǎng)橋i的第j次作業(yè)完工時(shí)間由上次作業(yè)完工時(shí)間與本次堆箱作業(yè)時(shí)間以及到達(dá)本次作業(yè)貝位的移動(dòng)時(shí)間，可以表示為：

(1)

其中場(chǎng)橋移動(dòng)時(shí)間DTij需要分以下三種情況來(lái)進(jìn)行確定：

(1) 場(chǎng)橋i的第j次作業(yè)的貝位位置與上次作業(yè)位置位于同一列

假設(shè)某集裝箱堆場(chǎng)的平面示意圖如圖2所示，場(chǎng)橋i的第j次作業(yè)的貝位位置在圖中標(biāo)“2”位置，上一次作業(yè)貝位位置在圖中標(biāo)“1”位置。那么場(chǎng)橋在從位置“1”到達(dá)位置“2”時(shí)，既可以向左移動(dòng)后經(jīng)過(guò)兩次90°轉(zhuǎn)向后再到達(dá)，也可以向右移動(dòng)后經(jīng)過(guò)兩次90°轉(zhuǎn)向后再到達(dá)。這時(shí)就需要對(duì)這兩條場(chǎng)橋的行走路徑進(jìn)行最短路的判斷，讓場(chǎng)橋選擇最短路徑進(jìn)行轉(zhuǎn)場(chǎng)作業(yè)。

圖2　場(chǎng)橋前后作業(yè)貝位位于同一列路徑選擇示意圖

通過(guò)上述分析可以得出此時(shí)的DTij可以表示為：

DTij=Aij×2tr+

(2)

其中，min{}表示需要進(jìn)行場(chǎng)橋最短路的判斷。

(2) 場(chǎng)橋i的第j次作業(yè)的貝位位置與上次作業(yè)位置位于相鄰兩列

此時(shí)，需要考慮場(chǎng)橋向左移動(dòng)和向右移動(dòng)兩種情況：

① 場(chǎng)橋i的第j次作業(yè)的貝位位置位于上次作業(yè)位置左側(cè)，則場(chǎng)橋需要向左移動(dòng)。假設(shè)場(chǎng)橋前后兩次作業(yè)的貝位位置如圖3所示，場(chǎng)橋i的第j次作業(yè)的貝位位置在圖中標(biāo)“2”位置，上一次作業(yè)貝位位置在圖中標(biāo)“1”位置。那么場(chǎng)橋在從位置“1”到達(dá)位置“2”時(shí)，按照最短路的原則，場(chǎng)橋會(huì)按圖中箭頭所示的方向進(jìn)行移動(dòng)。

圖3　場(chǎng)橋前后作業(yè)貝位位于相鄰兩列向左移動(dòng)路徑示意圖

因此在此種情況下，若場(chǎng)橋向左移動(dòng)，則DTij可以表示為：

(3)

② 場(chǎng)橋i的第j次作業(yè)的貝位位置位于上次作業(yè)位置右側(cè)，則場(chǎng)橋需要向右移動(dòng)。假設(shè)場(chǎng)橋前后兩次作業(yè)的貝位位置如圖4所示，場(chǎng)橋i的第j次作業(yè)的貝位位置在圖中標(biāo)“2”位置，上一次作業(yè)貝位位置在圖中標(biāo)“1”位置。那么場(chǎng)橋在從位置“1”到達(dá)位置“2”時(shí)，按照最短路的原則，場(chǎng)橋會(huì)按圖中箭頭所示的方向進(jìn)行移動(dòng)。

圖4　場(chǎng)橋前后作業(yè)貝位位于相鄰兩列向右移動(dòng)路徑示意圖

因此在此種情況下，若場(chǎng)橋向右移動(dòng)，則DTij可以表示為：

(4)

(3) 場(chǎng)橋i的第j次作業(yè)的貝位位置與上次作業(yè)位置位于不相鄰兩列

此時(shí)，需要考慮場(chǎng)橋向左移動(dòng)和向右移動(dòng)兩種情況：

① 場(chǎng)橋i的第j次作業(yè)的貝位位置位于上次作業(yè)位置左側(cè)，則場(chǎng)橋需要向左移動(dòng)。

假設(shè)場(chǎng)橋前后兩次作業(yè)的貝位位置如圖5所示，場(chǎng)橋i的第j次作業(yè)的貝位位置在圖中標(biāo)“2”位置，上一次作業(yè)貝位位置在圖中標(biāo)“1”位置。那么場(chǎng)橋從位置“1”到達(dá)位置“2”時(shí)，按照最短路的原則，場(chǎng)橋可以按圖中箭頭所示的方向任意選擇一條路徑進(jìn)行移動(dòng)。這是因?yàn)槿羟昂髢晌蛔鳂I(yè)貝位之間不在同一行，則場(chǎng)橋會(huì)有多條行走路徑，但是每條路徑的所需的行走時(shí)間都是一樣的，這時(shí)場(chǎng)橋可以根據(jù)堆場(chǎng)的實(shí)時(shí)情況，選擇一條不與其他場(chǎng)橋產(chǎn)生作業(yè)干涉的路徑進(jìn)行移動(dòng)。

圖5　場(chǎng)橋前后作業(yè)貝位位于不相鄰兩列向左移動(dòng)路徑示意圖

因此在此種情況下，若場(chǎng)橋向左移動(dòng)，則DTij可以表示為：

(5)

其中，k={xi(j-1)，xi(j-1)+1，…，xij-1}，∑LXk表示需要加上中間所有箱區(qū)的長(zhǎng)度。

② 場(chǎng)橋i的第j次作業(yè)的貝位位置位于上次作業(yè)位置右側(cè)，則場(chǎng)橋需要向右移動(dòng)。

假設(shè)場(chǎng)橋前后兩次作業(yè)的貝位位置如圖6所示，場(chǎng)橋i的第j次作業(yè)的貝位位置在圖中標(biāo)“2”位置，上一次作業(yè)貝位位置在圖中標(biāo)“1”位置。那么場(chǎng)橋在從位置“1”到達(dá)位置“2”時(shí)，按照最短路的原則，與上面場(chǎng)橋向左移動(dòng)的情況一樣，場(chǎng)橋同樣有多條行走路徑可以來(lái)選擇，這時(shí)場(chǎng)橋可以按圖中箭頭所示的方向任意選擇一條不與其他場(chǎng)橋產(chǎn)生作業(yè)干涉的路徑進(jìn)行移動(dòng)。

圖6　場(chǎng)橋前后作業(yè)貝位位于不相鄰兩列向移動(dòng)路徑示意圖

因此在此種情況下，若場(chǎng)橋向右移動(dòng)，則DTij可以表示為：

(6)

其中，k={xi(j-1)，xi(j-1)+1，…，xij-1}，∑LXk表示需要加上中間所有箱區(qū)長(zhǎng)度。

根據(jù)式(1)—式(6)可以求出每臺(tái)場(chǎng)橋i的作業(yè)完工時(shí)間Tini：

(7)

則目標(biāo)函數(shù)可以表示為：

(8)

(9)

式(8)表示最小化所有場(chǎng)橋的總轉(zhuǎn)場(chǎng)次數(shù)，式(9)表示最小化所有場(chǎng)橋的最大作業(yè)完工時(shí)間。

約束條件：

(10)

(11)

Cxij yij zij≥Qij

(12)

0≤i≤M

(13)

0≤j≤ni

(14)

式(10)表示所有場(chǎng)橋的作業(yè)量之和等于需要進(jìn)行堆存的總作業(yè)箱量；式(11)表示所有場(chǎng)橋作業(yè)貝位的空箱位應(yīng)該不小于需要進(jìn)行堆存的總作業(yè)箱量；式(12)表示場(chǎng)橋在某一貝位的作業(yè)時(shí)，該貝位的空箱位應(yīng)該不小于其作業(yè)箱量；式(13)與式(14)表示對(duì)循環(huán)變量的約束。

2多場(chǎng)橋調(diào)度優(yōu)化的演化策略算法設(shè)計(jì)

演化策略算法主要包含了選擇策略、重組算子和變異算子三大部分，其中選擇策略存在(1+1)、(μ+1)、(μ+λ)和(μ，λ)等幾種不同的形式。本文采用基于(μ+λ)選擇策略的演化策略算法，考慮加入幾種不同的局部搜索策略來(lái)優(yōu)化算法的求解性能，設(shè)計(jì)一種混合演化策略算法來(lái)對(duì)多場(chǎng)橋調(diào)度問(wèn)題進(jìn)行優(yōu)化。

2.1個(gè)體編碼

(1) 個(gè)體編碼方法

采用基于實(shí)數(shù)的四維個(gè)體編碼方法，第一維表示貝位序號(hào)，第二維表示個(gè)體位置，在[0，2]區(qū)間內(nèi)隨機(jī)生成來(lái)對(duì)貝位加工順序進(jìn)行排序，第三維表示每個(gè)貝位的作業(yè)箱量，第四維用來(lái)確定到每個(gè)貝位作業(yè)的場(chǎng)橋編號(hào)。

假設(shè)有m臺(tái)場(chǎng)橋到n個(gè)貝位去進(jìn)行堆箱作業(yè)，每個(gè)貝位的個(gè)體位置分別為Xi(i=1，2，…，n)，每個(gè)貝位的作業(yè)箱量分別為Ci(i=1，2，…，n)，每個(gè)貝位作業(yè)的場(chǎng)橋編號(hào)為Qi∈[1，m](i=1，2，…，n)，則一個(gè)完整的四維粒子可以如表1所示來(lái)表示。

表1　基于實(shí)數(shù)的四維個(gè)體編碼方法

(2) 個(gè)體解碼

首先，按照第二維個(gè)體位置Xi的大小對(duì)第一維貝位序號(hào)進(jìn)行從新排序，得到所有貝位的作業(yè)先后順序，同時(shí)需要相應(yīng)地調(diào)整第三維和第四維的位置。然后，根據(jù)第四維場(chǎng)橋編號(hào)Qi來(lái)得到每個(gè)貝位的作業(yè)場(chǎng)橋，從而得到每個(gè)場(chǎng)橋的作業(yè)貝位集合，根據(jù)每個(gè)場(chǎng)橋的作業(yè)貝位集合以及貝位的先后作業(yè)順序，就可以得到每個(gè)場(chǎng)橋的行走路徑，從而就可以計(jì)算出場(chǎng)橋的轉(zhuǎn)向次數(shù)及其對(duì)應(yīng)的作業(yè)完工時(shí)間。

2.2重組算子

采用基于三點(diǎn)交叉互換的重組算子，依次針對(duì)個(gè)體的第二維和第四維個(gè)體編碼進(jìn)行重組，其實(shí)現(xiàn)過(guò)程如下：首先隨機(jī)選取兩個(gè)父代個(gè)體，然后在它們的第二維(或第四維)個(gè)體編碼中隨機(jī)選擇三個(gè)交叉點(diǎn)，從而將其分成了四段，然后采取隔段互換的方式進(jìn)行基因值的互換，從而產(chǎn)生了兩個(gè)子代個(gè)體，如圖7所示。

圖7　基于三點(diǎn)交叉互換的重組算子

2.3變異算子

在生成的子代個(gè)體中，采用基于個(gè)體內(nèi)部基因兩點(diǎn)互換的變異算子，依次針對(duì)其第二維和第四維個(gè)體編碼進(jìn)行變異，其實(shí)現(xiàn)過(guò)程如下：在子代個(gè)體中，隨機(jī)選擇兩個(gè)不同的位置，交換這兩個(gè)位置上第二維(或第四維)個(gè)體編碼的基因值，從而生成新的子代個(gè)體，如圖8所示。

圖8　基于兩點(diǎn)互換的變異算子

2.4局部搜索策略

在進(jìn)行了(μ+λ)選擇策略以后，針對(duì)新產(chǎn)生的μ個(gè)父代個(gè)體進(jìn)行局部搜索。局部搜索用來(lái)實(shí)現(xiàn)對(duì)每個(gè)父代個(gè)體在其鄰域內(nèi)進(jìn)行局部最優(yōu)解的搜索過(guò)程。采用三種基于鄰域操作的局部搜索策略：基于互換操作、基于逆序操作以及基于插入操作的局部搜索策略[12]。

(1) 基于互換的局部搜索方法

依次針對(duì)父代個(gè)體的第二維和第四維個(gè)體編碼進(jìn)行互換操作?；诨Q的局部搜索方法按以下步驟來(lái)實(shí)現(xiàn)：① 對(duì)于每一個(gè)父代個(gè)體，隨機(jī)選擇其第二維(或第四維)個(gè)體編碼中的兩個(gè)不同位置p、q(p

(2) 基于逆序的局部搜索方法

依次針對(duì)父代個(gè)體的第二維和第四維個(gè)體編碼進(jìn)行逆序操作。基于逆序的局部搜索方法按以下步驟來(lái)實(shí)現(xiàn)：① 對(duì)于每一個(gè)父代個(gè)體，隨機(jī)選擇其第二維(或第四維)個(gè)體編碼中的兩個(gè)不同位置p、q(p

(3) 基于插入的局部搜索方法

依次針對(duì)父代個(gè)體的第二維和第四維個(gè)體編碼進(jìn)行插入操作。基于插入的局部搜索方法按以下步驟來(lái)實(shí)現(xiàn)：① 對(duì)于每一個(gè)父代個(gè)體，隨機(jī)選擇其第二維(或第四維)個(gè)體編碼中的兩個(gè)不同位置p、q(p

3試驗(yàn)結(jié)果與分析

3.1算例求解

目前，北方某集裝箱碼頭堆場(chǎng)用來(lái)進(jìn)行普通箱堆存的區(qū)域主要有31～38場(chǎng)、41～48場(chǎng)、51～56場(chǎng)以及71～74場(chǎng)，一共26個(gè)場(chǎng)。這26個(gè)場(chǎng)在堆場(chǎng)中的分布情況如圖9所示。

圖9　堆場(chǎng)分布實(shí)際情況圖

(1) 2臺(tái)場(chǎng)橋到10個(gè)貝位作業(yè)的算例

假設(shè)現(xiàn)在有2臺(tái)場(chǎng)橋來(lái)完成180個(gè)箱的堆存任務(wù)，這180個(gè)箱需要堆存到10個(gè)貝位上。隨機(jī)生成2臺(tái)場(chǎng)橋的初始位置和10個(gè)貝位的位置以及各貝位上的作業(yè)箱量如表2所示。

表2　算例1原始數(shù)據(jù)表

在考慮最短路的前提下，以場(chǎng)橋轉(zhuǎn)向次數(shù)最少和最小化最大作業(yè)完工時(shí)間為目標(biāo)，其中以優(yōu)化場(chǎng)橋轉(zhuǎn)向次數(shù)為主，分別采用演化策略算法(ES)和混合演化策略算法(HES)對(duì)上述算例進(jìn)行優(yōu)化求解，其中，ES和HES的基本參數(shù)設(shè)置均為μ=40、λ=30，最大迭代次數(shù)100次，HES采用每種局部搜索策略的次數(shù)均為3次。同時(shí)，采用常見(jiàn)的粒子群算法(PSO)和模擬退火算法(SA)來(lái)進(jìn)行結(jié)果對(duì)比分析。為了使這兩種算法的求解性能更優(yōu)，將PSO的參數(shù)設(shè)置為種群數(shù)量為50，學(xué)習(xí)因子均為2，采用線性遞減的慣性權(quán)重(從0.9線性遞減至0.4)，最大迭代次數(shù)為1000次；將SA的參數(shù)設(shè)置為初始溫度T0=1000，結(jié)束溫度Te=0.001，Metropolis鏈長(zhǎng)L=200，降溫速率q=0.98。所有的算法均連續(xù)優(yōu)化20次，優(yōu)化結(jié)果如表3所示。

表3　算例1不同算法優(yōu)化結(jié)果表

注：表中每種算法下第一列表示轉(zhuǎn)向次數(shù)(單位：次)，第二列表示最大作業(yè)完工時(shí)間(單位：min)

從表3的結(jié)果中可以看出，ES和HES在迭代次數(shù)更少的前提下，具有更高的求解效率和更好的求解結(jié)果，它們優(yōu)化性能要明顯好于PSO和SA。由于算例較為簡(jiǎn)單，采用局部搜索策略對(duì)HES求解性能的優(yōu)化效果并不十分明顯。

(2) 4臺(tái)場(chǎng)橋到10個(gè)貝位作業(yè)的算例

假設(shè)現(xiàn)在有4臺(tái)場(chǎng)橋來(lái)完成180個(gè)箱的堆存任務(wù)，這180個(gè)箱需要堆存到10個(gè)貝位上。這4臺(tái)場(chǎng)橋的初始位置和10個(gè)貝位的位置以及各貝位上的作業(yè)箱量如表4所示。

表4　算例2原始數(shù)據(jù)表

同樣在考慮最短路的前提下，以場(chǎng)橋轉(zhuǎn)向次數(shù)最少和最小化最大作業(yè)完工時(shí)間為目標(biāo)，其中以優(yōu)化場(chǎng)橋轉(zhuǎn)向次數(shù)為主，采用ES、HES、PSO、SA來(lái)進(jìn)行優(yōu)化求解。為了保證算法的求解性能，對(duì)某些算法的相關(guān)參數(shù)做以下調(diào)整：SA的Metropolis鏈長(zhǎng)調(diào)整為L(zhǎng)=300，其他參數(shù)與上一算例保持一致；ES和HES的最大迭代次數(shù)調(diào)整為300次，其他參數(shù)與上一算例保持一致；PSO的參數(shù)與上一算例保持一致。所有的算法均連續(xù)優(yōu)化20次，優(yōu)化結(jié)果表5所示。

表5　算例2不同算法優(yōu)化結(jié)果表

注：表中每種算法下第一列表示轉(zhuǎn)向次數(shù)(單位：次)，第二列表示最大作業(yè)完工時(shí)間(單位：min)

從表5的結(jié)果中可以看出，雖然PSO的求解時(shí)間是最短的，但是在迭代次數(shù)更少的前提下，ES和HES的求解結(jié)果要明顯優(yōu)于PSO和SA，且求解時(shí)間的差異不大。同時(shí)，隨著場(chǎng)橋數(shù)量的增加，ES和HES均找到了最優(yōu)解，但是采用局部搜索策略的HES的求解結(jié)果在穩(wěn)定性方面要優(yōu)于ES。且在三種不同的局部搜索策略中，采用基于互換操作的局部搜索策略的HES具有更好的求解效果。

(3) 4臺(tái)場(chǎng)橋到20個(gè)貝位作業(yè)的算例

假設(shè)現(xiàn)在有4臺(tái)場(chǎng)橋來(lái)完成360個(gè)箱的堆存任務(wù)，這360個(gè)箱需要堆存到20個(gè)貝位上。這4臺(tái)場(chǎng)橋的初始位置和20個(gè)貝位的位置以及各貝位上的作業(yè)箱量如表6所示。

表6　算例3原始數(shù)據(jù)表

同樣在考慮最短路的前提下，以場(chǎng)橋轉(zhuǎn)向次數(shù)最少和最小化最大作業(yè)完工時(shí)間為目標(biāo)，其中以優(yōu)化場(chǎng)橋轉(zhuǎn)向次數(shù)為主，采用ES、HES、PSO、SA來(lái)進(jìn)行優(yōu)化求解。為了保證算法的求解性能，對(duì)某些算法的相關(guān)參數(shù)做以下調(diào)整：PSO的最大迭代次數(shù)調(diào)整為2000次，其他參數(shù)與上一算例保持一致；ES和HES的最大迭代次數(shù)調(diào)整為500次，其他參數(shù)與上一算例保持一致；SA的參數(shù)與上一算例保持一致。所有的算法均連續(xù)優(yōu)化20次，優(yōu)化結(jié)果表7所示。

表7　算例3不同算法優(yōu)化結(jié)果表

注：表中每種算法下第一列表示轉(zhuǎn)向次數(shù)(單位：次)，第二列表示最大作業(yè)完工時(shí)間(單位：min)

從表7的結(jié)果中可以進(jìn)一步看出，在迭代次數(shù)更少的前提下，ES和HES的求解結(jié)果要明顯優(yōu)于PSO和SA。同時(shí)，隨著算例規(guī)模的增大，與ES相比，采用了局部搜索策略的HES具有更好的求解性能，且在三種不同的局部搜索策略中，基于互換操作的局部搜索策略對(duì)HES求解性能的優(yōu)化效果更為理想。

3.2局部搜索次數(shù)分析

在局部搜索策略中，局部操作次數(shù)的設(shè)置是一個(gè)很重要的參數(shù)。局部搜索次數(shù)過(guò)少，則局部搜索對(duì)算法性能的優(yōu)化效果不明顯，無(wú)法體現(xiàn)局部搜索的作用；局部搜索次數(shù)過(guò)多，則會(huì)加大算法的搜索空間，對(duì)算法的求解效率產(chǎn)生影響。以算例3為例，設(shè)置幾組不同的局部搜索次數(shù)，采用基于互換操作的混合演化策略算法(HES)來(lái)進(jìn)行優(yōu)化，通過(guò)對(duì)比試驗(yàn)來(lái)確定合適的局部搜索次數(shù)。其中，HES的基本參數(shù)設(shè)置為μ=40、λ=30，最大迭代次數(shù)500次。連續(xù)優(yōu)化20次，優(yōu)化結(jié)果如表8所示。

表8　不同局部搜索次數(shù)算法優(yōu)化結(jié)果表

注：表中每組互換次數(shù)下第一列表示轉(zhuǎn)向次數(shù)(單位：次)，第二列表示最大作業(yè)完工時(shí)間(單位：min)

設(shè)置不同局部搜索次數(shù)時(shí)，算法取得的平均轉(zhuǎn)向次數(shù)以及平均最大作業(yè)完工時(shí)間如圖10、圖11所示，算法的平均求解時(shí)間如圖12所示。

圖10　算法平均轉(zhuǎn)向次數(shù)折線圖

圖11　算法平均最大作業(yè)完工時(shí)間折線圖

圖12　算法平均求解時(shí)間折線圖

從表8和圖10、圖11中可以看出，算法的求解結(jié)果與局部搜索次數(shù)之間并沒(méi)有明顯的規(guī)律可循，它并不是隨著局部搜索次數(shù)的增加而越來(lái)越優(yōu)，而是呈現(xiàn)出波動(dòng)的情況。而從圖12可以看出算法的平均求解時(shí)間卻是隨著局部搜索次數(shù)的增加而直線增加。所以必須設(shè)置一個(gè)合適的局部搜索次數(shù)在保障算法求解結(jié)果的同時(shí)提高算法的求解效率，縮短求解時(shí)間。

從表8中可以看出，當(dāng)局部搜索次數(shù)設(shè)置為3次、4次、6次、8次時(shí)，算法求得的最優(yōu)解更好。但是為了保障算法的穩(wěn)定性和求解效率，從平均解和平均求解時(shí)間的角度出發(fā)，將局部搜索次數(shù)設(shè)置為3次更為合理。

4結(jié)語(yǔ)

首先針對(duì)集裝箱堆場(chǎng)布局規(guī)整的特點(diǎn)設(shè)計(jì)了一種三維坐標(biāo)表示方法來(lái)確定堆場(chǎng)中的貝位位置。然后，從考慮場(chǎng)橋最短路的角度出發(fā)，構(gòu)建了多場(chǎng)橋調(diào)度的優(yōu)化模型，該模型在優(yōu)化場(chǎng)橋轉(zhuǎn)向次數(shù)的前提下，對(duì)場(chǎng)橋的最大作業(yè)完工時(shí)間進(jìn)行優(yōu)化。針對(duì)構(gòu)建的多場(chǎng)橋調(diào)度模型，采用基于局部搜索策略的混合演化策略算法(HES)來(lái)優(yōu)化求解。通過(guò)幾個(gè)算例的試驗(yàn)說(shuō)明，HES比傳統(tǒng)的演化策略算法(ES)和常見(jiàn)的粒子群算法(PSO)、模擬退火算法(SA)具有更好的優(yōu)化性能，且在采用基于互換操作的局部搜索策略時(shí)，對(duì)算法的性能優(yōu)化效果更加理想。最后，通過(guò)一組對(duì)比實(shí)驗(yàn)對(duì)局部搜索的次數(shù)進(jìn)行了分析，得出了將局部搜索次數(shù)設(shè)置為3次較為合理。

參考文獻(xiàn)

[1] 陳歡．集裝箱場(chǎng)橋調(diào)度及其仿真研究[D]．武漢：武漢理工大學(xué)，2011．

[2] 王巖．集裝箱堆場(chǎng)多橋路徑優(yōu)化研究[D]．大連：大連海事大學(xué)，2012．

[3] 賈志剛．集裝箱碼頭箱區(qū)間場(chǎng)橋調(diào)度研究[D]．大連：大連海事大學(xué)，2013．

[4] 牟蓮芝．集裝箱碼頭閘口-場(chǎng)橋合理配置的仿真優(yōu)化研究[D]．大連：大連海事大學(xué)，2011．

[5] 張琪．考慮作業(yè)干涉的多場(chǎng)橋存取箱優(yōu)化問(wèn)題研究[D]．大連：大連海事大學(xué)，2011．

[6] 樂(lè)美龍，林艷艷，范志強(qiáng)．基于兩階段啟發(fā)式算法的多場(chǎng)橋作業(yè)調(diào)度研究[J]．武漢理工大學(xué)學(xué)報(bào)，2012，34(1)：60-65．

[7] 趙磊，胡志華，李淑琴．基于作業(yè)均衡的集裝箱堆場(chǎng)箱區(qū)場(chǎng)橋作業(yè)調(diào)度[J]．武漢理工大學(xué)學(xué)報(bào)，2013，35(1)：69-74．

[8] 何軍良，宓為建，嚴(yán)偉．基于爬山算法的集裝箱堆場(chǎng)場(chǎng)橋調(diào)度[J]．上海海事大學(xué)學(xué)報(bào)，2007，28(4)：11-15．

[9] 嚴(yán)偉，宓為建，萇道方，等．一種基于最佳優(yōu)先搜索算法的集裝箱堆場(chǎng)場(chǎng)橋調(diào)度策略[J]．中國(guó)工程機(jī)械學(xué)報(bào)，2008，6(1)：95-100．

[10] Mak K L，Sun D．A new hybrid genetic algorithm and tabu search method for yard cranes scheduling with inter-crane interference[C] //Proceedings of the World Congress on Engineering 2009，London，U．K，2009：978-988．

[11] Javanshir H，Seyedalizadeh Ganji S R．Yard crane scheduling in port container terminals using genetic algorithm[J]．International Journal of Industrial Engineering，2010，6(11)：39-50．

[12] 劉志雄．調(diào)度問(wèn)題中的粒子群優(yōu)化方法及其應(yīng)用研究[D]．武漢：武漢理工大學(xué)，2005．

YARD CRANES SCHEDULING OPTIMISATION BASED ON HYBRID EVOLUTIONARY STRATEGY ALGORITHM

Liu Zhixiong1Li Jun1Zhang Yu2Dong Jingwei3

1(SchoolofAutomobileandTrafficEngineering,WuhanUniversityofScienceandTechnology,Wuhan430081,Hubei,China)2(CollegeofLogisticsEngineering,WuhanUniversityofTechnology,Wuhan430063,Hubei,China)3(TianjinPortContainerTerminalCo.,Ltd.,Tianjin300456,China)

AbstractWe built the scheduling model and proposed a hybrid evolutionary strategy algorithm for the problem of container yard cranes scheduling.We adopted the real number-based four-dimension individual coding method,and designed the recombination operator,which is based on three-point crossover interchange,and the mutation operator which is based on two-point swap,as well as used three different local search strategies to optimise the performance of the algorithm.Through example analysis we proved the effectiveness of hybrid evolutionary strategy algorithm in optimising yard cranes scheduling problem.Among three different local search strategies,the local search strategy based on swap operation was better than the other two,it could obviously improve the optimisation performance of evolutionary strategy algorithm.At last,we analysed the local search times through a series of contrast tests.

KeywordsYard cranes schedulingEvolutionary strategy algorithmLocal search

收稿日期：2014-12-08。國(guó)家自然科學(xué)基金項(xiàng)目(70801047,71372202)；中央高?；究蒲袑ｍ?xiàng)基金項(xiàng)目(2013-IV-057)。劉志雄，教授，主研領(lǐng)域：生產(chǎn)計(jì)劃與調(diào)度、智能優(yōu)化方法。李俊，碩士生。張煜，教授。東經(jīng)偉，碩士生。

中圖分類號(hào)TP3

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.05.061