基于集裝箱簇的場橋調度模型與算法

梁承姬，周 聰,魯 渤

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

基于集裝箱簇的場橋調度模型與算法

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

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

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

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

0 引 言

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

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

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

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

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

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

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

1 問題描述

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

到集裝箱堆場指定位置，然后堆場中的場橋對到達的集裝箱進行堆垛作業；船舶裝載過程與之相反。3種機械設備的操作具有緊密的相關性，相互協調完成船舶的裝卸作業。由此可見，合理的場橋作業調度直接影響整個碼頭的作業效率。圖1為集裝箱碼頭作業流程示意圖。

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

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

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

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

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

2 場橋調度模型

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

2.1 模型假設

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

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

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

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

2.2 數學模型

目標函數

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)

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

3 遺傳算法求解

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

3.1 染色體編碼

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

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

3.2 初始種群的生成

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

3.3 適應值函數

算法中個體的適應值函數用個體的目標函數變化而成。為滿足約束條件(12)，當個體對應方案出現跨越或者干擾時，該個體的適應值將被區分，如下式(17)：

Fitness[f(xi)]=

(17)

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

3.4 選擇操作

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

Step1 在當前種群任意選擇一個個體，撥一次輪盤產生一個隨機數；

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

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

3.5 交叉操作

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

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

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

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

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

當場橋的數量多于兩臺時，染色體中有多個“0”出現，此時可能會刪除過多的“0”導致個體不一樣長。因此筆者規定只刪除首次重復基因。

3.6 變異操作

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

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

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

4 數值案例

結合某碼頭的實際數據進行算例設計，該碼頭集裝箱堆場某條場橋通道有5個箱區，共有250個貝位，其中各箱區通道均以4個貝位表示。2個小時內有100個集裝箱要進行裝卸，各集裝箱任務在堆場指定的位置、對應集卡到達時間及相關實驗數據如表1、表2。

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

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

表2 模型中相關參數取值Table 2 The parameter values of the model

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

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

場橋集裝箱簇作業順序集裝箱任務作業順序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臺場橋實時行走路徑Fig.6 Real-time paths of 8 yard cranes

5 結 語

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

[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] 王展,陸志強,潘爾順.堆區混貝的堆場場吊調度模型與算法[J].系統工程理論與實踐,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] 鄭紅星,于凱.基于混合遺傳算法的混堆箱區內場橋調度研究[J].交通運輸系統工程與信息,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] 樂美龍,林艷艷,范志強.基于兩階段啟發式算法的多場橋作業調度研究[J].武漢理工大學學報,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] 靳志宏,毛鈞,徐奇,等.基于混合遺傳算法的集裝箱堆場裝卸作業調度優化[J].大連海事大學學報, 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] 李麗麗.集裝箱堆場布局與場橋調度優化研究[D].大連:大連海事大學,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

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

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

U693

A

1674-0696(2016)04-152-06