基于集裝箱簇的場橋調(diào)度模型與算法

梁承姬，周 聰,魯 渤

(1.上海海事大學(xué) 科學(xué)研究院物流研究中心，上海201306；2.中國科學(xué)院大學(xué) 管理學(xué)院，北京 100190)

基于集裝箱簇的場橋調(diào)度模型與算法

梁承姬1，周 聰1,魯 渤2

(1.上海海事大學(xué) 科學(xué)研究院物流研究中心，上海201306；2.中國科學(xué)院大學(xué) 管理學(xué)院，北京 100190)

為了提高場橋的作業(yè)效率，針對帶有裝卸順序的集裝箱簇，考慮場橋作業(yè)時的安全距離和互不跨越等約束條件，建立了場橋裝卸完工時間最小為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型。并根據(jù)問題自身的特點，設(shè)計了基于集裝箱簇的染色體，用遺傳算法進行求解。最后通過數(shù)值實驗對模型與算法的有效性進行了驗證。

交通運輸工程；場橋調(diào)度；集裝箱簇；裝卸順序；安全距離；遺傳算法

0 引 言

隨著經(jīng)濟全球化的發(fā)展，集裝箱化運輸逐漸成為世界范圍內(nèi)的主要物流運輸手段。集裝箱的數(shù)量越來越多，對集裝箱碼頭裝卸系統(tǒng)的效率和效益也提出了越來越高的要求。而在集裝箱碼頭的日常運作中，集裝箱堆場場橋的作業(yè)調(diào)度直接影響整個碼頭的效率和成本。因此，優(yōu)化集裝箱碼頭場橋作業(yè)調(diào)度，對提高碼頭整體運作效率和提升港口的競爭力具有十分重要的意義。

近年來，有關(guān)堆場場橋的優(yōu)化調(diào)度的研究很多，如K.Y.KIM等[1]研究了裝船作業(yè)中跨運車的路徑優(yōu)化問題，以確定跨運車提取集裝箱的順序；W.C. NG等[2]采用分枝定界法求解了堆場起重機作業(yè)調(diào)度問題，使作業(yè)等待時間最??；D.H.LEE等[3]研究了兩臺集裝箱吊運車同時服務(wù)一臺岸橋的吊運車調(diào)度問題，以最小化集裝箱裝載時間為目標(biāo)，并設(shè)計了模擬退火算法進行求解，以確定每臺吊運車提取集裝箱的數(shù)量和提取順序；W.LI等[4]考慮了場橋作業(yè)的現(xiàn)實約束條件，以最小化等待時間為目標(biāo)，建立了離散時間模型，并設(shè)計了滾動平面法求解問題；Y.HUANG等[5]首先研究了路徑規(guī)劃在不同領(lǐng)域的各種問題，然后構(gòu)建了場橋路徑規(guī)劃模型，最后采用了基于遺傳算法的路徑優(yōu)化方法求解，從而提高了場橋作業(yè)的效率；X.GUO 等[6]通過預(yù)測提取和運送集裝箱車輛到達時間，研究了動態(tài)場橋調(diào)度問題，目標(biāo)是最小化車輛等待時間，并設(shè)計了基于A*搜索算法和試探算法的算法進行求解，為了減少計算時間，提出了回溯算法，在上述算法的基礎(chǔ)上加入優(yōu)先搜索；王展等[7]研究了堆區(qū)混貝的堆場場橋調(diào)度問題，提出了場橋裝卸時間窗約束和堆場空間約束等，并設(shè)計了改進禁忌搜索算法解決了大規(guī)模場橋調(diào)度問題；鄭紅星等[8]研究了混堆模式下集裝箱箱區(qū)內(nèi)場橋調(diào)度問題，并設(shè)計了基于集裝箱任務(wù)排序的染色體結(jié)構(gòu)，用融入禁忌搜索的混合遺傳算法進行求解；樂美龍等[9]考慮場橋?qū)嶋H作業(yè)約束，建立多場橋混合整數(shù)規(guī)劃模型并設(shè)計了兩階段啟發(fā)式算法求解；靳志宏等[10]以縮短龍門吊作業(yè)時間為目標(biāo)，建立了其裝卸調(diào)度優(yōu)化模型，并將近鄰搜索策略嵌入遺傳算法中進行求解；李麗麗[11]針對場橋調(diào)度問題，提出了最短路法和動態(tài)規(guī)劃法相結(jié)合的算法對場橋路徑進行優(yōu)化，用遺傳算法求解場橋調(diào)配優(yōu)化問題，并用Flexsim仿真軟件仿真評價指標(biāo)和仿真過程。

筆者研究的是某計劃時段內(nèi)，集裝箱堆場同一條場橋通道箱區(qū)各集裝箱任務(wù)在箱區(qū)的指定位置和對應(yīng)集卡到達時刻均已知的場橋調(diào)度優(yōu)化問題?？紤]場橋作業(yè)時須有安全距離和不能相互跨越等約束條件，建立了場橋裝卸完工時間最小為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，并設(shè)計了基于集裝箱簇的遺傳算法求解模型，最后通過實例驗證了模型與算法的有效性。

筆者研究與已有文獻的主要不同之處如下：

1)研究集裝箱堆場同一條場橋通道箱區(qū)的場橋調(diào)度優(yōu)化問題，以往文獻大多針對集裝箱堆場所有箱區(qū)或者單個箱區(qū)；

2)考慮集裝箱任務(wù)對應(yīng)集卡到達堆場指定位置時間的影響，該因素直接影響場橋的調(diào)度方案，而以往文獻大多未考慮；

3)以往文獻大多以集裝箱任務(wù)來考慮，筆者將同一箱區(qū)同一個貝位需要作業(yè)的集裝箱作為一個集裝箱簇考慮。通過確定每臺場橋作業(yè)的集裝箱簇和作業(yè)集裝箱簇的順序，來確定場橋作業(yè)的集裝箱任務(wù)和作業(yè)集裝箱任務(wù)的順序，使研究課題更加符合集裝箱碼頭的實際操作。

1 問題描述

集裝箱碼頭處理集裝箱的機械設(shè)備主要有岸橋，集卡和場橋(筆者采用國內(nèi)最常見的輪胎式場橋)，它們的作業(yè)方式可以概括如下：船舶卸載過程中，岸橋提取船舶上的集裝箱卸載到集卡上，集卡根據(jù)已經(jīng)制定好的堆存計劃將集裝箱從碼頭前沿運送

到集裝箱堆場指定位置，然后堆場中的場橋?qū)Φ竭_的集裝箱進行堆垛作業(yè)；船舶裝載過程與之相反。3種機械設(shè)備的操作具有緊密的相關(guān)性，相互協(xié)調(diào)完成船舶的裝卸作業(yè)。由此可見，合理的場橋作業(yè)調(diào)度直接影響整個碼頭的作業(yè)效率。圖1為集裝箱碼頭作業(yè)流程示意圖。

圖1 集裝箱碼頭作業(yè)流程示意Fig.1 The schematic diagram of operation process in terminal

堆場是存放集裝箱的場地，目的是保證集裝箱裝卸作業(yè)的連續(xù)性。堆場是集裝箱碼頭的主要占地區(qū)域，在整個碼頭處于核心地位。集裝箱堆場由多個箱區(qū)組成，每個箱區(qū)由40～60個貝位組成，每一個貝位又由6～8 列組成。場橋是集裝箱堆場進行堆取集裝箱作業(yè)的專業(yè)機械設(shè)備，可以保持在場橋通道上直線行走，從一個箱區(qū)移動到同一條場橋通道的另一個箱區(qū)，也可以做90°角轉(zhuǎn)向，從一條場橋通道的箱區(qū)移動到另一條場橋通道的箱區(qū)。在不同場橋通道的箱區(qū)間移動時，其輪胎旋轉(zhuǎn)會占用大量的時間和道路空間，增加無效勞動且導(dǎo)致堆場內(nèi)交通堵塞。除非不同場橋通道箱區(qū)的任務(wù)量特別大，一般情況下會盡量避免把場橋調(diào)度到在不同場橋通道的箱區(qū)間作業(yè)。因此筆者不考慮場橋從一條場橋通道移動到另一條場橋通道箱區(qū)進行作業(yè)，從而可以將同一條場橋通道上的箱區(qū)作為整體，對這些箱區(qū)的貝位從左往右依次排序。為了簡化問題，將各箱區(qū)的箱區(qū)通道以貝位表示。圖2為一條場橋通道3個箱區(qū)由3臺場橋作業(yè)的示意圖。此外，為了減少堆場內(nèi)部交通堵塞，通常會規(guī)定集卡在堆場的最大停留時間，即要求場橋盡量在規(guī)定時間內(nèi)完成對集卡的作業(yè)。

圖2 一條場橋通道3個箱區(qū)3臺場橋作業(yè)示意圖Fig.2 The schematic diagram of 3 yard cranes operations in 3 blocks in a yard crane channel

由于同一船舶卸載下來的集裝箱將存放在不同箱區(qū)的不同貝位，集卡到達堆場指定位置時，場橋?qū)⒃诓煌鋮^(qū)以及同一個箱區(qū)的不同貝位間移動。通常港口計劃人員制定船舶配載計劃時，相同目的港和同一箱主的集裝箱會放在一起，而堆存計劃中，這些一定數(shù)量的集裝箱一般會安排在一個箱區(qū)相鄰的幾個貝位中，此時可以將同一箱區(qū)同一貝位需要作業(yè)的集裝箱作為一個集裝箱簇來考慮。由于場橋尺寸大，移動緩慢，為了減少場橋在貝位間的移動，通常場橋作業(yè)完一個貝位所有集裝箱任務(wù)后才移動到下一個貝位作業(yè)。因此，可以將集裝箱任務(wù)的分配和排序轉(zhuǎn)化為集裝箱簇的分配和排序，即先確定每臺場橋需要作業(yè)的集裝箱簇，然后根據(jù)集裝箱任務(wù)對應(yīng)集卡到達貝位的時間來確定每個集裝箱簇中集裝箱任務(wù)的作業(yè)順序，這樣所有集裝箱任務(wù)分配和排序也就確定了。

筆者研究的是某計劃時間段內(nèi)，某條場橋通道箱區(qū)各集裝箱任務(wù)，在箱區(qū)的指定位置和對應(yīng)集卡到達時刻均已知的場橋調(diào)度優(yōu)化問題。為了最大限度地優(yōu)化各場橋的作業(yè)序列，文中構(gòu)建了一個以該計劃時段內(nèi)，該條場橋通道箱區(qū)所有集裝箱任務(wù)的完工時間最小化為目標(biāo)，并保證當(dāng)配有多臺場橋時，場橋間須有安全距離和不能相互跨越的場橋調(diào)度優(yōu)化模型。

2 場橋調(diào)度模型

在某船舶裝卸作業(yè)中，一定數(shù)量的集裝箱任務(wù)，在箱區(qū)指定位置和集裝箱任務(wù)對應(yīng)集卡到達堆場時間已知。通過建立數(shù)學(xué)模型，在滿足場橋作業(yè)的特殊約束下，找出最優(yōu)的集裝箱任務(wù)分配和排序，使場橋完成這些集裝箱任務(wù)的總時間最短。為了方便計算，文中所有時間以時間單位表示，一個時間單位為1 min。

2.1 模型假設(shè)

1)場橋操作的集裝箱都為標(biāo)準集裝箱，且每臺場橋的所有參數(shù)都是相同的，包括場橋的移動速度和工作效率。場橋操作每個集裝箱的時間相等。

2)場橋的初始位置在該場橋處理的第1個集裝箱任務(wù)目的貝位處。

3)場橋之間不能相互穿越且有一定的安全作業(yè)距離。

4)各箱區(qū)通道寬度均相等。

2.2 數(shù)學(xué)模型

目標(biāo)函數(shù)

min{maxC(yim)}, i∈B,m∈{1,2,…,QI}

(1)

約束條件

C(yim)≥R(yim)+ta, i∈B,m∈{1,2,…,Qi}

(2)

C(yim)-ta-R(yim)≤tc, i∈B,m∈{1,2,…,Qi}

(3)

(4)

(5)

(6)

C(yim)=C(yi(m-1))+ta, i∈B,m∈{2,3,…,Qi}

(7)

ta+max{R(yi1),C(yiQi)+tij}-C(yj1)+

(8)

yim≠yin,i∈B，m,n∈{1,2,…,Qi}

(9)

yim≠yjn,i,j∈B,m∈{1,2,…Qi},n∈{1,2,…,Qj}

(10)

(11)

(12)

(13)

yim∈yi, i∈B,m∈{1,2,…,Qi}

(14)

xik∈{0,1}, i∈B,k∈{1,2,…,K}

(15)

zijk∈{0,1}, i,j∈B,k∈{1,2,…,K}

(16)

其中，目標(biāo)函數(shù)(1)表示最小化最大集裝箱任務(wù)完工時間,約束條件(2)保證任一個集裝箱任務(wù)的完成時刻不早于該任務(wù)對應(yīng)集卡到達時刻與裝卸時間之和；式(3)表示集卡的等待時長不能超過等待上限；式(4)表示每個集裝箱任務(wù)分配給一臺且只有一臺場橋；式(5)表示每個集裝箱簇任務(wù)之前或之后的集裝箱簇任務(wù)最多有一個；式(6)定義了場橋在前后兩個集裝箱簇的移動時間；式(7)表示同一個集裝箱簇前后兩個集裝箱任務(wù)完工時間的等式約束；式(8)定義了前一個集裝箱簇最后一個集裝箱任務(wù)的完工時間、場橋從前一個集裝箱簇移動到后一個集裝箱簇的時間、后一個集裝箱簇第一個集裝箱任務(wù)的開始時間及集裝箱簇作業(yè)序列關(guān)系的約束；式(9)～式(11)共同保證了每個集裝箱任務(wù)有且只能作業(yè)一次；式(12)定義了場橋之間的安全作業(yè)距離；式(13)保證在計劃時段內(nèi)任意時刻各場橋均不能離開箱區(qū)；式(14)～式(16)為決策變量的范圍約束。

3 遺傳算法求解

針對模型的特點，筆者設(shè)計了遺傳算法進行求解，具體算法如下所述。

3.1 染色體編碼

采用實數(shù)編碼，一個調(diào)度方案對應(yīng)的染色體長度為(集裝箱簇數(shù)+場橋數(shù)-1)，各基因值為集裝箱簇編號，“0”基因為不同場橋間的間隔符號，“0”基因的個數(shù)為(場橋數(shù)-1)，例如10個集裝箱簇3臺場橋作業(yè)的一個調(diào)度方案對應(yīng)的染色體結(jié)構(gòu)及說明如圖3。

圖3 染色體編碼表示Fig.3 The show of chromosome coding

3.2 初始種群的生成

首先任取(場橋數(shù)-1)個基因，將其基因值設(shè)為“0”，然后將所有集裝箱簇編號任意填滿剩余的基因。種群生成的過程中，需滿足“0”基因不能處于基因鏈的首位或出現(xiàn)兩個“0”相鄰的情況，避免生成的染色體無意義。

3.3 適應(yīng)值函數(shù)

算法中個體的適應(yīng)值函數(shù)用個體的目標(biāo)函數(shù)變化而成。為滿足約束條件(12)，當(dāng)個體對應(yīng)方案出現(xiàn)跨越或者干擾時，該個體的適應(yīng)值將被區(qū)分，如下式(17)：

Fitness[f(xi)]=

(17)

在算法中計算f(xi)時引入一個懲罰規(guī)則來滿足約束(3)。當(dāng)個體對應(yīng)的調(diào)度方案有集卡的等待時長超過等待上限，給該個體的目標(biāo)值加上一個M(一個較大的正數(shù))值作為懲罰。

3.4 選擇操作

考慮到當(dāng)配備多臺場橋作業(yè)時，各代種群中有較多個體對應(yīng)的方案會有跨越或干擾。為了避免選擇該類個體，筆者采用以下選擇流程：

Step1 在當(dāng)前種群任意選擇一個個體，撥一次輪盤產(chǎn)生一個隨機數(shù)；

Step2 若當(dāng)前個體滿足被選條件且該個體對應(yīng)方案無干擾或跨越，則選擇此個體進入交叉池，否則返回Step1 ；

Step3 盤點已選的個體總數(shù)，如果達到種群容量則停止選擇操作，轉(zhuǎn)回Step1 。

3.5 交叉操作

針對染色體編碼特點，筆者采用順序交叉，如圖4，具體步驟如下：

Step1 隨機選擇兩個交叉點X，Y，確定兩父代中將被復(fù)制到子代的基因片段；

圖4 染色體交叉過程Fig.4 The crossover process of chromosomes

Step2 從父代1、父代2的基因碼中分別刪掉父代2、父代1已復(fù)制到子代的基因；

Step3 將父代2剩余的基因按順序填入子代1，父代1剩余的基因按順序填入子代2，完成后得到兩個完整的子個體。

當(dāng)場橋的數(shù)量多于兩臺時，染色體中有多個“0”出現(xiàn)，此時可能會刪除過多的“0”導(dǎo)致個體不一樣長。因此筆者規(guī)定只刪除首次重復(fù)基因。

3.6 變異操作

筆者采用基于位置的變異操作，隨機選擇個體的兩個位置，然后交換它們的基因。由于兩個“0”基因交換沒有意義，因此規(guī)定不能同時選擇個體的兩個“0”基因交換。

由于交叉變異之后個體可能會出現(xiàn)“0”基因處

于基因鏈的首位或兩個“0”基因相鄰的情況，因此交叉變異之后，需要檢驗所有個體是否出現(xiàn)這種情況，出現(xiàn)這種情況的個體刪除。

4 數(shù)值案例

結(jié)合某碼頭的實際數(shù)據(jù)進行算例設(shè)計，該碼頭集裝箱堆場某條場橋通道有5個箱區(qū)，共有250個貝位，其中各箱區(qū)通道均以4個貝位表示。2個小時內(nèi)有100個集裝箱要進行裝卸，各集裝箱任務(wù)在堆場指定的位置、對應(yīng)集卡到達時間及相關(guān)實驗數(shù)據(jù)如表1、表2。

表1 某條場橋通道箱區(qū)任務(wù)情況Table 1 The task condition in blocks in a yard crane channel

注：Ready-time:“1”表示對應(yīng)集卡在第1個時間單位到達作業(yè)位置(初始時刻為0)

表2 模型中相關(guān)參數(shù)取值Table 2 The parameter values of the model

對于GA的染色體編碼、生成初始種群、適應(yīng)值計算、個體的選擇均采用上文提出的方式。運用MATLAB軟件對設(shè)計的遺傳算法進行編程并計算。GA使用的遺傳參數(shù)為：種群規(guī)模M=200，迭代次數(shù)N=500，交叉概率和變異概率分別為0.7和0.1。GA的搜索過程如圖5，GA搜索到400代時，目標(biāo)值收斂于113 min，對應(yīng)的場橋調(diào)度方案如表3。為了直觀看出方案是否出現(xiàn)場橋間跨越或者干擾，繪制了8臺場橋的實時行走路徑，如圖6。從圖中可看出場橋路徑無交叉點，即求得的優(yōu)化調(diào)度方案確實未出現(xiàn)場橋間的干擾或跨越。

圖5 目標(biāo)值收斂過程Fig.5 Convergence process of objective value表3 場橋調(diào)度方案Table 3 Scheduling plans of yard cranes

場橋集裝箱簇作業(yè)順序集裝箱任務(wù)作業(yè)順序YC12—5—7—8—13—161—2—3—7—8—13—14—18—19—23—24—25—31—32YC217—21—44—50—3438—39—43—44—45—48—49—54—55—56—60—61YC352—58—674—5—6—15—16—17—29—30YC475—80—95—98—8836—37—46—47—89—90—96—97—98—68—69—70YC5103—124—1109—10—57—58—59—33—34—35YC6157—142—150—149—133—14140—41—42—79—80—11—12—87—88—94—95—99—100YC7174—176—168—170—180—185—19071—72—81—82—83—50—51—52—53—20—21—22—91—92—93—26—27—28YC8235—239—240—246—216—224—23073—74—75—76—77—78—84—85—86—62—63—64—65—66—67

圖6 8臺場橋?qū)崟r行走路徑Fig.6 Real-time paths of 8 yard cranes

5 結(jié) 語

研究的是某計劃時段內(nèi)，集裝箱碼頭堆場，某條場橋通道箱區(qū)的場橋調(diào)度問題。重點考慮場橋間不可跨越和須有安全距離，以及集卡等待時間上限3個方面。建立了場橋裝卸完工時間最小為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，并設(shè)計了基于集裝箱簇的遺傳算法進行求解。算例結(jié)果表明，提出的場橋調(diào)度模型能確定場橋通道箱區(qū)場橋的作業(yè)序列，使得該計劃時段完成帶有裝卸順序的集裝箱任務(wù)的時間最小，可為場橋的實時調(diào)度提供決策支持。由于集裝箱碼頭堆場計劃本身的復(fù)雜性，雖然在集裝箱碼頭場橋調(diào)度優(yōu)化與求解方法研究方面取得一定進展，但是沒有將堆場空間分配和場橋作業(yè)調(diào)度作為整體考慮，因此，有關(guān)這類問題，將作為未來的研究方向。另外研究中將各任務(wù)需要的裝卸時間視為已知，而實際作業(yè)中由于倒箱的影響，會使某些任務(wù)的裝卸時長有所偏差，因此在筆者研究基礎(chǔ)上，可將倒箱問題加入研究中。

[1] KIM K Y, KIM K H. A routing algorithm for a single straddle carrier to load export containers onto a containership[J].InternationalJournalofProductionEconomics,1999,59(1):425-433.

[2] Ng W C, MAK K L. Yard crane scheduling in port container terminals[J].AppliedMathematicalModelling,2005,29(3):263-276.

[3] LEE D H, CAO Z, MENG Q. Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm[J].InternationalJournalofProductionEconomics,2007,107(1):115-124.

[4] LI W, WU Y, PETERING M E H, et al. Discrete time model and algorithms for container yard crane scheduling[J].EuropeanJournalofOperationalResearch,2009,198(1):165-172.

[5] HUANG Y, LIANG C, YANG Y. The optimum route problem by genetic algorithm for loading/unloading of yard crane[J].Computers&IndustrialEngineering,2009,56(3):993-1001.

[6] GUO X, HUANG S Y, HSU W J, et al. Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information[J].AdvancedEngineeringInformatics,2011,25(3):472-484.

[7] 王展,陸志強,潘爾順.堆區(qū)混貝的堆場場吊調(diào)度模型與算法[J].系統(tǒng)工程理論與實踐,2012,32(1):182-188. WANG Zhan, LU Zhiqiang, PAN Ershun. Model and algorithm for yard crane scheduling problem in a mixed stacking block[J].SystemsEngineering-Theory&Practice,2012,32(1):182-188.

[8] 鄭紅星,于凱.基于混合遺傳算法的混堆箱區(qū)內(nèi)場橋調(diào)度研究[J].交通運輸系統(tǒng)工程與信息,2013,13(5):150-158. ZHENG Hongxing, YU Kai. Yard crane scheduling in the mixture storage block based on hybrid genetic algorithm[J].JournalofTransportationSystemsEngineeringandInformationTechnology,2013,13(5):150-158.

[9] 樂美龍,林艷艷,范志強.基于兩階段啟發(fā)式算法的多場橋作業(yè)調(diào)度研究[J].武漢理工大學(xué)學(xué)報,2012,34(1):60-65. LE Meilong, LIN Yanyan, FAN Zhiqiang. Research on multi-yard-crane scheduling problem based on two-phase heuristic algorithm[J].JournalofWuhanUniversityofTechnology,2012,34(1):60-65.

[10] 靳志宏,毛鈞,徐奇,等.基于混合遺傳算法的集裝箱堆場裝卸作業(yè)調(diào)度優(yōu)化[J].大連海事大學(xué)學(xué)報, 2012,38(1):41-44. JIN Zhihong, MAO Jun, XU Qi, et al. Optimization on the loading/unloading schedules in container yard based on hybrid genetic algorithm[J].JournalofDalianMaritimeUniversity,2012,38(1):41-44.

[11] 李麗麗.集裝箱堆場布局與場橋調(diào)度優(yōu)化研究[D].大連:大連海事大學(xué),2011. LI Lili.AStudyonContainerYard’sLayoutandCraneSchedulingOptimization[D]. Dalian:Dalian Maritime University,2011.

Model and Algorithm for Yard Crane Scheduling Based on Container Groups

LIANG Chengji1, ZHOU Cong1, LU Bo2

(1. Logistics Research Center, Scientific Research Academy, Shanghai Maritime University, Shanghai 201306, P.R.China;2. School of Management, University of Chinese Academy of Sciences, Beijing 100190, P.R.China)

To improve the operation efficiency of yard crane, considering such constraints of compulsory safety distance and forbidden intercrossing in case of the handling of container group, for the purpose of the container group under handling order, a MIP model was established for yard crane scheduling problem in order to minimize the operation time of container groups subject to handling sequence during the fixed span. According to the characteristics of the problem, a genetic algorithm was developed and the chromosome representation was structured on the handling sequence of container groups. Finally, the MIP model and solution algorithm were proved by numerical experiments.

traffic and transportation engineering; yard crane scheduling; container groups; handling sequence; safe distance; genetic algorithm

10.3969/j.issn.1674-0696.2016.04.30

2015-11-13；

2015-12-31

國家自然科學(xué)基金項目(71471110，71301101，2014M550084)

梁承姬(1970—)，女，吉林龍井人，教授，博士，主要從事物流系統(tǒng)運作計劃與優(yōu)化、口岸物流流程模擬與重組等方面的研究。E-mail:liangcj@shmtu.edu.cn。

U693

A

1674-0696(2016)04-152-06