基于混合演化策略算法的多場橋調度優化

劉志雄　李　俊　張　煜　東經偉

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

?

基于混合演化策略算法的多場橋調度優化

劉志雄1李俊1張煜2東經偉3

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

摘要針對集裝箱堆場多場橋調度問題，構建調度模型，提出一種混合演化策略算法。采用基于實數的四維個體編碼方法，設計了基于三點交叉互換的重組算子以及基于兩點互換的變異算子，并采用三種不同的局部搜索策略來優化算法的性能。通過算例分析證明混合演化策略算法在優化多場橋調度問題時的有效性。在三種不同的局部搜索策略中，基于互換操作的局部搜索策略要優于其他兩種，能明顯改善演化策略算法的優化性能。最后，通過一組對比試驗對局部搜索的次數進行了分析。

關鍵詞多場橋調度演化策略算法局部搜索

0引言

集裝箱運輸的迅猛發展給港口的作業能力帶來了巨大的挑戰。由于集裝箱碼頭的改建和設備投入都需要大量的資金注入，因此如何充分利用現有資源來提升碼頭裝卸作業效率成為了當下的研究熱點。堆場作為堆存集裝箱的重要場地，在整個碼頭作業中起到緩沖作用，對整個碼頭的裝卸作業效率、吞吐能力以及船舶在港時間等都有很大的影響。在現有的岸邊作業系統和水平運輸系統一定的情況下，堆場作業效率成為了制約碼頭吞吐能力的瓶頸，而場橋作為堆場作業中的核心設備，是提高堆場作業效率的關鍵。如何對場橋進行有效地調度，從而保障整個堆場的作業效率是亟需解決的問題。

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

本文將在考慮最短路的前提下，以減少場橋的轉向次數和最小化場橋的最大作業完工時間為目標，構建多目標的多場橋優化調度模型。針對構建的模型，設計一種混合演化策略算法進行優化求解。最后，根據天津港集裝箱碼頭堆場的實際情況，設置幾種規模不同的作業場景來驗證模型以及算法的有效性。

1多場橋調度問題

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

多場橋調度問題是指針對堆場內某一時間段內的堆箱作業任務，安排多臺場橋來共同完成，這時就需要在保證堆箱順序的前提下，考慮場橋移動的最短距離，對多個場橋進行移動，確定每臺場橋的行走路徑，明確場橋每次作業的貝位位置以及在該貝位位置上的作業箱量，最后在該時間段的堆箱作業任務全部完成時，在保證參與作業的所有場橋的轉向次數盡量小的同時，使所有場橋的最大作業完工時間最小化。

1.1貝位的坐標表示

圖1　貝位位置坐標的說明示意圖

由于集裝箱碼頭堆場的布局一般都很規整，為了確定每個時刻場橋所在的貝位(bay)位置，現采用一種三維坐標的形式(x，y，z)來對堆場內的貝位進行編碼。其中第一維x表示箱區(block)所在的列，第二維y表示箱區所在的行，第三維z表示箱區內的貝位號。如圖1所示，圖中標“1”的貝位位置可以表示為(1，1，4)，標“2”的貝位位置可以表示為(2，1，6)，標“3”的貝位位置可以表示為(3，1，10)，標“4”的貝位位置可以表示為(1，2，3)，標“5”的貝位位置可以表示為(1，3，7)，標“6”的貝位位置可以表示為(3，3，4)。這樣每個貝位位置就可以用唯一的坐標來表示，方便調度模型的求解。

1.2模型假設

針對天津港集裝箱碼頭堆場的實際情況，對構建的模型做出以下幾點假設：

(1) 堆場內所有場橋的作業能力等基本參數相同；

(2) 不存在多臺場橋處于同一貝位產生沖突的情況；

(3) 忽略堆場中集卡阻塞對場橋調度的影響；

(4) 每個箱區在任意時刻至多只有2臺場橋；

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

(6) 不考慮場橋作業的等待時間。

1.3參數定義

M：堆場內的場橋總數(單位：臺)

N：堆場內的箱區數(單位：個)

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

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

LXi：箱區i的長度(i=1，2，…，N)(單位：米)

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

Bi：箱區i內的貝位數(i=1，2，…，N)(單位：個)

LB：單個貝位的長度(沿箱區長度方向)(單位：米)

q：場橋的作業效率(單位：TEU/分)

v：場橋的水平移動速度(單位：米/秒)

tr：場橋完成一次90°轉彎所需的時間(單位：秒)

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

Q：需要進行堆存的總作業箱量(單位：TEU)

ni：場橋i的總作業次數(i=1，2，…，M)(單位：次)

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

DTij：場橋i到達第j次作業貝位位置所需要的移動時間(i=1，2，…，M；j=1，2，…，ni)(單位：秒)

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

1.4調度模型

調度模型的優化目標是在考慮最短路的前提下，減少場橋轉向次數的同時，最小化場橋的最大作業完工時間。其中，場橋i的第j次作業完工時間由上次作業完工時間與本次堆箱作業時間以及到達本次作業貝位的移動時間，可以表示為：

(1)

其中場橋移動時間DTij需要分以下三種情況來進行確定：

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

假設某集裝箱堆場的平面示意圖如圖2所示，場橋i的第j次作業的貝位位置在圖中標“2”位置，上一次作業貝位位置在圖中標“1”位置。那么場橋在從位置“1”到達位置“2”時，既可以向左移動后經過兩次90°轉向后再到達，也可以向右移動后經過兩次90°轉向后再到達。這時就需要對這兩條場橋的行走路徑進行最短路的判斷，讓場橋選擇最短路徑進行轉場作業。

圖2　場橋前后作業貝位位于同一列路徑選擇示意圖

通過上述分析可以得出此時的DTij可以表示為：

DTij=Aij×2tr+

(2)

其中，min{}表示需要進行場橋最短路的判斷。

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

此時，需要考慮場橋向左移動和向右移動兩種情況：

① 場橋i的第j次作業的貝位位置位于上次作業位置左側，則場橋需要向左移動。假設場橋前后兩次作業的貝位位置如圖3所示，場橋i的第j次作業的貝位位置在圖中標“2”位置，上一次作業貝位位置在圖中標“1”位置。那么場橋在從位置“1”到達位置“2”時，按照最短路的原則，場橋會按圖中箭頭所示的方向進行移動。

圖3　場橋前后作業貝位位于相鄰兩列向左移動路徑示意圖

因此在此種情況下，若場橋向左移動，則DTij可以表示為：

(3)

② 場橋i的第j次作業的貝位位置位于上次作業位置右側，則場橋需要向右移動。假設場橋前后兩次作業的貝位位置如圖4所示，場橋i的第j次作業的貝位位置在圖中標“2”位置，上一次作業貝位位置在圖中標“1”位置。那么場橋在從位置“1”到達位置“2”時，按照最短路的原則，場橋會按圖中箭頭所示的方向進行移動。

圖4　場橋前后作業貝位位于相鄰兩列向右移動路徑示意圖

因此在此種情況下，若場橋向右移動，則DTij可以表示為：

(4)

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

此時，需要考慮場橋向左移動和向右移動兩種情況：

① 場橋i的第j次作業的貝位位置位于上次作業位置左側，則場橋需要向左移動。

假設場橋前后兩次作業的貝位位置如圖5所示，場橋i的第j次作業的貝位位置在圖中標“2”位置，上一次作業貝位位置在圖中標“1”位置。那么場橋從位置“1”到達位置“2”時，按照最短路的原則，場橋可以按圖中箭頭所示的方向任意選擇一條路徑進行移動。這是因為若前后兩位作業貝位之間不在同一行，則場橋會有多條行走路徑，但是每條路徑的所需的行走時間都是一樣的，這時場橋可以根據堆場的實時情況，選擇一條不與其他場橋產生作業干涉的路徑進行移動。

圖5　場橋前后作業貝位位于不相鄰兩列向左移動路徑示意圖

因此在此種情況下，若場橋向左移動，則DTij可以表示為：

(5)

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

② 場橋i的第j次作業的貝位位置位于上次作業位置右側，則場橋需要向右移動。

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

圖6　場橋前后作業貝位位于不相鄰兩列向移動路徑示意圖

因此在此種情況下，若場橋向右移動，則DTij可以表示為：

(6)

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

根據式(1)—式(6)可以求出每臺場橋i的作業完工時間Tini：

(7)

則目標函數可以表示為：

(8)

(9)

式(8)表示最小化所有場橋的總轉場次數，式(9)表示最小化所有場橋的最大作業完工時間。

約束條件：

(10)

(11)

Cxij yij zij≥Qij

(12)

0≤i≤M

(13)

0≤j≤ni

(14)

式(10)表示所有場橋的作業量之和等于需要進行堆存的總作業箱量；式(11)表示所有場橋作業貝位的空箱位應該不小于需要進行堆存的總作業箱量；式(12)表示場橋在某一貝位的作業時，該貝位的空箱位應該不小于其作業箱量；式(13)與式(14)表示對循環變量的約束。

2多場橋調度優化的演化策略算法設計

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

2.1個體編碼

(1) 個體編碼方法

采用基于實數的四維個體編碼方法，第一維表示貝位序號，第二維表示個體位置，在[0，2]區間內隨機生成來對貝位加工順序進行排序，第三維表示每個貝位的作業箱量，第四維用來確定到每個貝位作業的場橋編號。

假設有m臺場橋到n個貝位去進行堆箱作業，每個貝位的個體位置分別為Xi(i=1，2，…，n)，每個貝位的作業箱量分別為Ci(i=1，2，…，n)，每個貝位作業的場橋編號為Qi∈[1，m](i=1，2，…，n)，則一個完整的四維粒子可以如表1所示來表示。

表1　基于實數的四維個體編碼方法

(2) 個體解碼

首先，按照第二維個體位置Xi的大小對第一維貝位序號進行從新排序，得到所有貝位的作業先后順序，同時需要相應地調整第三維和第四維的位置。然后，根據第四維場橋編號Qi來得到每個貝位的作業場橋，從而得到每個場橋的作業貝位集合，根據每個場橋的作業貝位集合以及貝位的先后作業順序，就可以得到每個場橋的行走路徑，從而就可以計算出場橋的轉向次數及其對應的作業完工時間。

2.2重組算子

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

圖7　基于三點交叉互換的重組算子

2.3變異算子

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

圖8　基于兩點互換的變異算子

2.4局部搜索策略

在進行了(μ+λ)選擇策略以后，針對新產生的μ個父代個體進行局部搜索。局部搜索用來實現對每個父代個體在其鄰域內進行局部最優解的搜索過程。采用三種基于鄰域操作的局部搜索策略：基于互換操作、基于逆序操作以及基于插入操作的局部搜索策略[12]。

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

依次針對父代個體的第二維和第四維個體編碼進行互換操作。基于互換的局部搜索方法按以下步驟來實現：① 對于每一個父代個體，隨機選擇其第二維(或第四維)個體編碼中的兩個不同位置p、q(p

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

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

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

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

3試驗結果與分析

3.1算例求解

目前，北方某集裝箱碼頭堆場用來進行普通箱堆存的區域主要有31～38場、41～48場、51～56場以及71～74場，一共26個場。這26個場在堆場中的分布情況如圖9所示。

圖9　堆場分布實際情況圖

(1) 2臺場橋到10個貝位作業的算例

假設現在有2臺場橋來完成180個箱的堆存任務，這180個箱需要堆存到10個貝位上。隨機生成2臺場橋的初始位置和10個貝位的位置以及各貝位上的作業箱量如表2所示。

表2　算例1原始數據表

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

表3　算例1不同算法優化結果表

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

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

(2) 4臺場橋到10個貝位作業的算例

假設現在有4臺場橋來完成180個箱的堆存任務，這180個箱需要堆存到10個貝位上。這4臺場橋的初始位置和10個貝位的位置以及各貝位上的作業箱量如表4所示。

表4　算例2原始數據表

同樣在考慮最短路的前提下，以場橋轉向次數最少和最小化最大作業完工時間為目標，其中以優化場橋轉向次數為主，采用ES、HES、PSO、SA來進行優化求解。為了保證算法的求解性能，對某些算法的相關參數做以下調整：SA的Metropolis鏈長調整為L=300，其他參數與上一算例保持一致；ES和HES的最大迭代次數調整為300次，其他參數與上一算例保持一致；PSO的參數與上一算例保持一致。所有的算法均連續優化20次，優化結果表5所示。

表5　算例2不同算法優化結果表

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

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

(3) 4臺場橋到20個貝位作業的算例

假設現在有4臺場橋來完成360個箱的堆存任務，這360個箱需要堆存到20個貝位上。這4臺場橋的初始位置和20個貝位的位置以及各貝位上的作業箱量如表6所示。

表6　算例3原始數據表

同樣在考慮最短路的前提下，以場橋轉向次數最少和最小化最大作業完工時間為目標，其中以優化場橋轉向次數為主，采用ES、HES、PSO、SA來進行優化求解。為了保證算法的求解性能，對某些算法的相關參數做以下調整：PSO的最大迭代次數調整為2000次，其他參數與上一算例保持一致；ES和HES的最大迭代次數調整為500次，其他參數與上一算例保持一致；SA的參數與上一算例保持一致。所有的算法均連續優化20次，優化結果表7所示。

表7　算例3不同算法優化結果表

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

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

3.2局部搜索次數分析

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

表8　不同局部搜索次數算法優化結果表

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

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

圖10　算法平均轉向次數折線圖

圖11　算法平均最大作業完工時間折線圖

圖12　算法平均求解時間折線圖

從表8和圖10、圖11中可以看出，算法的求解結果與局部搜索次數之間并沒有明顯的規律可循，它并不是隨著局部搜索次數的增加而越來越優，而是呈現出波動的情況。而從圖12可以看出算法的平均求解時間卻是隨著局部搜索次數的增加而直線增加。所以必須設置一個合適的局部搜索次數在保障算法求解結果的同時提高算法的求解效率，縮短求解時間。

從表8中可以看出，當局部搜索次數設置為3次、4次、6次、8次時，算法求得的最優解更好。但是為了保障算法的穩定性和求解效率，從平均解和平均求解時間的角度出發，將局部搜索次數設置為3次更為合理。

4結語

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

參考文獻

[1] 陳歡．集裝箱場橋調度及其仿真研究[D]．武漢：武漢理工大學，2011．

[2] 王巖．集裝箱堆場多橋路徑優化研究[D]．大連：大連海事大學，2012．

[3] 賈志剛．集裝箱碼頭箱區間場橋調度研究[D]．大連：大連海事大學，2013．

[4] 牟蓮芝．集裝箱碼頭閘口-場橋合理配置的仿真優化研究[D]．大連：大連海事大學，2011．

[5] 張琪．考慮作業干涉的多場橋存取箱優化問題研究[D]．大連：大連海事大學，2011．

[6] 樂美龍，林艷艷，范志強．基于兩階段啟發式算法的多場橋作業調度研究[J]．武漢理工大學學報，2012，34(1)：60-65．

[7] 趙磊，胡志華，李淑琴．基于作業均衡的集裝箱堆場箱區場橋作業調度[J]．武漢理工大學學報，2013，35(1)：69-74．

[8] 何軍良，宓為建，嚴偉．基于爬山算法的集裝箱堆場場橋調度[J]．上海海事大學學報，2007，28(4)：11-15．

[9] 嚴偉，宓為建，萇道方，等．一種基于最佳優先搜索算法的集裝箱堆場場橋調度策略[J]．中國工程機械學報，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] 劉志雄．調度問題中的粒子群優化方法及其應用研究[D]．武漢：武漢理工大學，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。國家自然科學基金項目(70801047,71372202)；中央高校基本科研專項基金項目(2013-IV-057)。劉志雄，教授，主研領域：生產計劃與調度、智能優化方法。李俊，碩士生。張煜，教授。東經偉，碩士生。

中圖分類號TP3

文獻標識碼A

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