基于作業均衡的集裝箱碼頭岸橋作業調度優化

樂美龍，徐根龍，文洪蕊

(上海海事大學 物流研究中心，上海 201306)

基于作業均衡的集裝箱碼頭岸橋作業調度優化

樂美龍，徐根龍，文洪蕊

(上海海事大學 物流研究中心，上海 201306)

為了提高集裝箱碼頭資源配置的均衡性，進而提高作業人員任務分配的均衡性以及岸橋設備資源的利用率，提出了基于集裝箱碼頭岸橋作業均衡調度優化問題。以集裝箱碼頭岸橋作業集裝箱量和作業時間兩個均衡調度為目標，建立集裝箱碼頭岸橋作業均衡的岸橋調度優化模型，并設計遺傳算法來求解。通過對3種目標的結果進行比較，得出在岸橋調度過程中考慮岸橋作業量均衡有助于提高岸橋的利用率，減少岸橋無效作業時間，從而提升碼頭整體作業能力。

交通運輸工程；集裝箱碼頭；作業均衡；岸橋；調度優化；遺傳算法

0 引 言

隨著經濟全球化進程加快，集裝箱碼頭在國際物流和國民經濟中的戰略性地位越來越突出，成為了國際物流多式聯運中不可或缺的重要節點。岸橋，作為碼頭前沿岸邊的裝卸設備，由于其設備昂貴且較為稀缺，其裝卸作業能力直接決定了集裝箱貨物的吞吐能力以及碼頭整體作業能力。

近年來，國內外眾多學者針對岸橋調度展開深入研究：C．F．DAGANZO[1]假設岸橋可以自由移動，以船艙為任務單位，研究了多艘船舶岸橋調度問題；K．H．KIM等[2]在考慮岸橋間的安全距離以及任務的優先作業順序等因素下，建立了一個混合整數規劃模型，并采用分支界定方法進行求解；P．LEGATO等[3]在岸橋調度模型考慮了單個岸橋的平均作業速率、準備時間和岸橋的交貨期、安全需求等因素；S．H．CHUNG等[4]基于任務優先級和岸橋互不干涉因素情況下建立模型，并采用改進型遺傳算法進行求解。在岸橋任務重新分配過程中，S．H．CHUNG等[5]提出了在考慮岸橋不同加載條件下工作量平衡分配問題，建立模糊理論控制引導下的數學模型；曾慶成等[6]在岸橋調度模型充分考慮船舶任務優先順序、岸橋作業的安全距離以及岸橋的轉移時間等因素；周鵬飛等[7]針對船舶抵港時間隨機性，建立了面向隨機環境的泊位-岸橋調度模型；曾慶成等[8]在泊位分配-裝卸橋調度中運用干擾管理方法，從船舶等待成本、碼頭作業成本、以及計劃偏離度等3個方面度量擾動；范志強等[9]考慮了岸橋作業不可相互交叉以及安全距離等約束，建立了岸橋調度雙目標混合整數規劃模型；此外，范志強[10]還分析了以箱組為任務對象QCSP 與以整貝為任務對象QCSP 的異同，指出前者更能均衡各岸橋作業負荷；徐遠琴等[11]分析了集裝箱碼頭中的集卡與岸橋、場橋聯合調度問題，建立了以等待岸橋、場橋作業時間與集卡運輸時間之和最小為目標的聯合調度優化模型；高超鋒等[12]研究了多個岸橋并行作業中相互干擾而影響岸橋工作效率問題，分析了岸橋工時和懲罰成本的影響。

從以上學者的研究中可見，岸橋調度中主要以船舶在港時間最小化或岸橋作業時間最小化為目標，這求解過程中往往會導致岸橋作業任務分配不均衡的現象。基于此，筆者重點探討基于岸橋作業量的均衡岸橋調度優化問題，提出了一個以岸橋作業量均衡以及作業時間最小化為目標的多目標岸橋調度問題，并設計遺傳算法進行求解。通過具體算例來驗證該調度模型對實際中的集裝箱碼頭設備資源調度均衡性的效果與優勢。

1 問題描述

岸橋調度(QCSP)是指在確定船舶靠泊位置和分配岸橋數量后，在考慮每臺岸橋的作業任務量、開始作業時間、結束作業時間、各個任務間的作業次序等信息對所服務船舶上的任務安排特定岸橋進行裝卸服務，以確保船舶任務能夠在規定的時間內完成。

筆者主要研究基于單船任務分配量均衡的岸橋調度優化問題。如圖1，所需要作業的集裝箱分布在船舶的不同貝位上。由于在港時間的長短往往取決于船舶最后一個集裝箱裝卸完工的時間長短，為了使船舶在港時間盡可能的短，必須遵循多臺岸橋并行作業、船舶任務分配均衡性的原則，使得服務于同一艘船舶的所有岸橋完工時間盡可能地接近或相等，這樣在保證船舶在最短時間內完成所有的裝卸任務的同時，可以避免或減少岸橋設備資源閑置或浪費的現象。

圖1 岸橋調度問題概述Fig.1 QC scheduling problem

國內集裝箱碼頭中，岸橋通常為軌道式岸橋，受電纜坑和電纜長度的限制，每臺岸橋必須在固定的軌道上進行移動和作業，不可交叉跨越，且相鄰岸橋在作業過程中要相隔至少一個貝位的安全距離。如圖1中，當岸橋2和岸橋3同時在貝位上作業時，岸橋2作業的貝位號必須要比岸橋3所作業的貝位號大，否則將導致岸橋交叉作業。

2 模型建立

2.1 模型假設

筆者在得到一天(24 h)的所有船舶的岸橋和泊位分配計劃表后，針對單艘船舶建立一個混合整數規劃模型，并期望在完成所有裝卸作業任務后，實現每臺岸橋作業量均衡。對模型假設如下：

1)岸橋的裝卸速度相同，即不同的岸橋作業同一個任務所需的作業時間相同；

2)一臺岸橋一次只能作業一個貝位上的任務，并且岸橋在作業中不會發生突然故障；

3)為了使多目標單位的統一性，筆者將所考慮的岸橋作業量轉化為岸橋的作業時間。

2.2 參數定義

參數具體符號定義如下：

2.3 決策變量

為建立岸橋調度數學模型引入決策變量如下：

2.4 數學模型

在對參數和決策變量的定義后，筆者基于岸橋作業量均衡情況下建立了岸橋多目標混合整數規劃模型。

目標函數：

(1)

(2)

(3)

約束條件：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

ci+Tj≤cj, ?i,j∈φ

(13)

(14)

(15)

(16)

Zij+Zji=1,ifdQ<1, ?i,j∈φ

(17)

(18)

?i,j∈Ω,li

(19)

(20)

(21)

Tk,ci≥0, ?i∈Ω,?k∈Q

(22)

(23)

3 遺傳算法求解

基于建立的混合整數規劃模型，筆者將通過設計遺傳算法分別以岸橋作業完成時間最小化、以作業量最均衡、作業量最均衡且作業完成時間最小化為目標進行岸橋調度優化，并對3種目標所生成的調度方案進行比較，以驗證模型可行性。

3.1 染色體的設計及初始解的生成

染色體設計方法采用交互式的編碼方式(圖2)：假設有2臺岸橋，10個作業任務。在每臺岸橋上，每條染色體代表岸橋所分配作業任務順序的一個可能方案，包含兩個數量的基因值以及兩部分不同的編碼體系。在第1部分中，每個基因表示一個任務，基因的序列表示任務從左往右進行作業的順序，基因值隨機產生，而且不會被其他基因復制；在第2部分，每個基因表示對應于第1部分相應位置所作業的岸橋，其基因值基于所作業的岸橋數量隨機產生。

圖2 染色體設計Fig.2 Chromosome design

由圖2可以知道，岸橋1分配了5個任務，其作業順序依次為6，9，2，8和1；岸橋2所分配任務的作業順序為4，7，10，3，5。這樣在所提到的遺傳算法中，隨機生成了初始解。

3.2 適應度函數的計算及選擇操作

目標函數是基于岸橋作業量均衡的情況下最小化任務的最大完工時間。鑒于該模型是一個多目標混合整數規劃模型，因此在求解過程中采用帕累托[13]最優解的方法通過引入加權系數來將多目標函數標準化為一個單目標函數，以此來表示染色體的適應度函數。

g=1,2

(24)

(25)

適應度函數的權重設置如式(26)：

(26)

染色體適應度函數計算為

F(ak)=ω1·f1+ω2·f2

(27)

同時，在選擇操作上，采納輪盤賭的方法進行選擇操作。

3.3 遺傳運算

遺傳運算主要包括交叉(crossover)操作和變異(mutation)操作兩個部分，這是實現遺傳算法的精髓，也是變化最多的地方。

3.3.1 交叉操作

筆者根據M．GEN等[14]所提到有序交叉法來處理所需作業的任務序列，具體的交叉步驟如下：

第1步：在第一父代的第1部分隨機選擇部分染色體，與此同時在該父代的第2部分的對應位置選擇相應染色體。

第2步：將該染色體拷貝，然后放入子代所對應位置。

第3步：刪除來自于第二父代所存在的與子代相同的基因(如本例中刪除父代2的相應與子代1重復的7，10，2，3)，剩余的基因根據第二父代從左到右的作業順序放入到子代空缺的位置。

第四步：重復1～3的步驟來復制第二個子代。

圖3用一個例子演示了順序交叉的做法。

3.3.2 變異操作

變異的目的是防止種群被局限于局部最優，筆者使用的變異方法是隨機選擇兩個元素然后交換它們的位置，具體以圖4為例。

圖4 變異操作的說明Fig.4 Variation operation instruction

3.4 算例實驗及結果分析

為了驗證上述模型及算法的有效性，筆者以一艘小規模的集裝箱船舶裝卸操作為例對岸橋進行調度研究。遺傳算法參數如表1。

表1 遺傳算法參數設置

3.4.1 數據輸入

假設一艘小規模集裝箱船舶靠岸，船舶上共有9個貝位需要進行集裝箱裝卸操作，各貝位的集裝箱量以及貝位間任務優先級等具體信息如表2。

表2 已知的任務信息

現分配3臺岸橋至該船舶，3臺岸橋的最早可用時間均為0時刻，并且各岸橋的單機作業效率相同。已知岸橋在單個貝位的移動時間t=0.004 h，岸橋1的初始位置在貝位16，岸橋2初始位置在貝位12，岸橋3的初始位置在貝位10，岸橋首個任務距離信息以及兩兩任務距離信息如表3及表4。

表3 岸橋首個任務距離

注：單位距離為一個貝位距離。

表4 兩兩任務距離

(續表4)

dij123456789105543201234466543101233776542101228876532101199876432100109876432100

注：單位距離為一個貝位距離。

3.4.2 岸橋調度模型結果與分析

根據3.2小節所提出的權系數處理方法，對于以作業量最均衡以及作業量最均衡且作業完成時間最小化為目標的多目標優化。根據式(26)使用MATLAB得到兩個權系數為：ω1=0.24，ω2=0.86。由算例2的信息數據并考慮岸橋移動情況，分別以岸橋作業完成時間最小化和以作業量最均衡以及作業量最均衡且作業完成時間最小化為目標進行岸橋調度優化，3種不同目標所生成的調度方案及各岸橋具體作業情況如表5。

表5 不同目標下生成的調度方案及岸橋作業結果

(續表5)

方案目標岸橋作業順序作業時間Tk/h等待時間Tw/h移動時間tk/h完工時間Ck/h3岸橋作業量最均衡&作業完成時間最小化QC-19—8—1010.80.0000.01210.812QC-26—311.64.3840.04016.024QC-37—1—4—5—212.01.5400.08413.624

分別對3種目標所生成的調度方案的岸橋作業完成時間和岸橋作業時間進行比較，如圖5。

圖5 不同目標下各岸橋作業完成時間及作業時間Fig.5 QC operation time and completion time with different targets

在以作業完成時間最小化為目標的調度方案中，3臺岸橋的最大完工時間為12.84 h，各岸橋間作業完成時間的標準差僅為0.998 h，波動性較小。同時從圖5(a)可見，岸橋在等待和移動時間浪費上比較少。但從圖5(b)可見，相比其他兩種目標的方案，岸橋作業時間卻參差不齊，由于各岸橋間作業量分配不均衡導致任務最大完工時間增加；在以作業量最均衡為目標的調度方案中，岸橋作業時間標準差為0.189 h，3臺岸橋間作業量分配趨于一致，但由于各岸橋作業完成時間的波動性較大最終導致任務最大完工時間增加，為18.12 h。而且從圖6可以看出各岸橋間移動、等待時間相差較大，特別是岸橋2和岸橋3在作業過程中等待時間分別長達4.84和6.46 h，岸橋在無效作業時間上浪費較大；在以作業完成時間最小化和作業量最均衡多目標的調度方案中，岸橋間最大完工時間為16.024 h，岸橋作業標準差為0.499 h，在兩個目標之間尋求一定的平衡點，一定程度上減少了岸橋無效作業時間，有效提高了岸橋的作業效率。

圖6 不同目標下各岸橋移動等待時間Fig.6 QC moving and waiting time with different targets

此外，從圖5中數據可以得到該多目標方案的作業完成時間比以作業量最均衡為目標的調度方案結果減少了近11.57%，岸橋的作業時間標準差比以作業完成時間最小化為目標的調度方案結果減少了近33.8%。因此，在岸橋調度中考慮岸橋的作業均衡性是有必要的,從長遠的角度來看，極大地提高了岸橋資源的整體利用率，減少了岸橋無效作業時間，從而提升碼頭整體作業能力。

4 結 語

筆者研究了基于貝位任務岸橋單船調度優化問題，建立一個基于岸橋作業均衡的船舶完工時間最小化的多目標混合整數規劃問題，并設計遺傳算法進行求解。鑒于該兩個目標已統一為相同的單位量綱，因此通過設定相應權重ω1，ω2將多目標問題轉化為單目標線性問題。并通過實例分別對以岸橋作業完成時間最小化為目標、作業量最均衡為目標、作業量最均衡且作業完成時間最小化為目標的3種目標結果進行比較分析，得出在岸橋調度過程中，考慮岸橋作業量均衡有助于提高岸橋的利用率，減少岸橋無效作業時間，從而有效縮短船舶在港時間，降低碼頭經營運作成本，提高港口的整體運作效率和服務水平。但在集裝箱碼頭調度問題中，基于單船的岸橋調度并不能保證碼頭作業整體的優化，因此下一步將對岸橋、集卡、場橋聯合調度優化問題展開深入研究。

[1] DAGANZO C F. The crane scheduling problem[J].TransportationResearchPartB:Methodological,1989,23(3):159-175.

[2] KIM K H,PARK Y M. A crane scheduling method for port container terminals[J].EuropeanJournalofOperationalResearch,2004,156:752-768.

[3] LEGATO P,TRUNFIO R,MEISEL F. Modeling and solving rich quay crane scheduling problems[J].Computers&OperationsResearch,2012,39(9):2063-2078.

[4] CHUNG S H，CHOY K L. A modified genetic algorithm for quay crane scheduling operations[J].ExpertSystemswithApplications,2012,39(4):4213-4221.

[5] CHUNG S H,CHAN F T S. A workload balancing genetic algorithm for the quay crane scheduling problem[J].InternationalJournalofProductionResearch,2013,51(16)：4820-4834.

[6] 曾慶成，高宇．集裝箱碼頭裝卸橋調度優化模型與算法[J]．計算機工程與應用，2006(32):217-219． ZENG Qingcheng,GAO Yu. Model and algorithm for quay crane scheduling in container terminals[J].ComputerEngineeringandApplications,2006(32):217-219.

[7] 周鵬飛，康海貴.面向隨機環境的集裝箱碼頭泊位-岸橋分配方法[J].系統工程理論與實踐，2008，28(1):161-169. ZHOU Pengfei，KANG Haigui. Study on berth and quay-crane allocation under stochastic environments in container terminal[J].SystemsEngineeringTheory&Practice,2008,28(1):161-169.

[8] 曾慶成，胡祥培，楊忠振．集裝箱碼頭泊位分配-裝卸橋調度干擾管理模型[J]．系統工程理論與實踐，2010，30(11):2026-2035. ZENG Qingcheng,HU Xiangpei,YANG Zhongzhen. Model for disruption management of berth allocation & quay crane scheduling in container terminals[J].SystemsEngineeringTheory&Practice,2010,30(11):2026-2035.

[9] 范志強，樂美龍．最小化最大完工時間與等待時間的岸橋作業調度雙目標優化及其遺傳算法[J]．系統管理學報，2013，22(1):120-127. FAN Zhiqiang,LE Meilong. A genetic algorithm to minimize the makespan and waiting time for the bi-objective quay crane scheduling problem[J].JournalofSystems&Management,2013,22(1):120-127.

[10] 范志強．考慮任務優先約束的同類岸橋作業調度優化[J]．運籌與管理，2013，22(2):235-242. FAN Zhiqiang. Modeling and solving uniform quay crane scheduling problem with task precedence constraints[J].OperationsResearchandManagementScience,2013,22(2):235-242.

[11] 徐遠琴，韓曉龍．集卡與岸橋及場橋聯合調度模型優化[J]．重慶交通大學學報(自然科學版)，2013，32(2):318-320. XU Yuanqin,HAN Xiaolong. United scheduling model optimization of yard truck,quay crane and yard crane[J].JournalofChongqingJiaotongUniversity(NaturalScience),2013,32(2):318-320.

[12] 高超鋒，胡志華.岸橋并行作業效率約束下泊位與岸橋集成分派[J].重慶交通大學學報(自然科學版)，2014，33(3):72-78. GAO Chaofeng,HU Zhihua. Berth-crane allocation constrained by parallel operation efficiency of quay cranes[J].JournalofChongqingJiaotongUniversity(NaturalScience),2014,33(3):72-78.

[13] 王昕昕.岸邊集裝箱起重機動態配置與貝位調度多目標問題研究[D].上海:上海海事大學，2014. WANG Xinxin.DynamicMulti-ObjectiveResearchonQCsSchedulingasedontheBayTask[D]. Shanghai:Shanghai Maritime University，2014.

[14] GEN M,CHENG R.GeneticAlgorithmsandEngineeringOptimization[M]. New York:John Wiley,1996.

Quay Crane Scheduling Optimization Considering Operation Balance at Container Terminal

LE Meilong, XU Genlong, WEN Hongrui

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, P.R.China)

In order to improve the balance of resources allocation at container terminal, and then to improve the balance of the operators’ assigned tasks and the utilization rate of the quay crane resources, a quay crane allocation optimization problem, considering operation balance between quay cranes at container terminal, was proposed. A quay crane scheduling optimization model based on the quay crane operation balance at container terminal was established, in order to balance the quantities of the containers and the operational time of quay crane operation. And a genetic algorithm was designed to solve the model. By comparing the results of three different goals, it is concluded that considering the operation balance in the quay crane scheduling process is helpful to improve the utilization rate of quay crane and reduce the quay crane invalid operation time, so as to improve the whole operation capability of the container terminal.

traffic and transportation engineering; container terminal; operation balance; quay crane; scheduling optimization; genetic algorithm

10.3969/j.issn.1674-0696.2016.03.31

2015-12-24；

2015-03-14

國家自然科學基金項目(71171129，71471110)；上海市科委科研計劃項目(111510501900，12dz1124802)；上海市教委科研項目(11YZ137))

樂美龍(1968—)，男，浙江寧波人，教授，博士，博士生導師，主要從事物流規劃與管理，港航運作優化方面的研究。E-mail：lemeilong@126.com。

徐根龍(1989—)，男，浙江江山人，碩士研究生，主要從事岸橋調度優化方面的研究。E-mail：croger4463@163.com。

U691+3

A

1674-0696(2016)03-155-07