基于作業(yè)均衡的集裝箱碼頭岸橋作業(yè)調(diào)度優(yōu)化

樂美龍，徐根龍，文洪蕊

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

基于作業(yè)均衡的集裝箱碼頭岸橋作業(yè)調(diào)度優(yōu)化

樂美龍，徐根龍，文洪蕊

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

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

交通運輸工程；集裝箱碼頭；作業(yè)均衡；岸橋；調(diào)度優(yōu)化；遺傳算法

0 引 言

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

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

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

1 問題描述

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

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

圖1 岸橋調(diào)度問題概述Fig.1 QC scheduling problem

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

2 模型建立

2.1 模型假設(shè)

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

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

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

3)為了使多目標(biāo)單位的統(tǒng)一性，筆者將所考慮的岸橋作業(yè)量轉(zhuǎn)化為岸橋的作業(yè)時間。

2.2 參數(shù)定義

參數(shù)具體符號定義如下：

2.3 決策變量

為建立岸橋調(diào)度數(shù)學(xué)模型引入決策變量如下：

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

在對參數(shù)和決策變量的定義后，筆者基于岸橋作業(yè)量均衡情況下建立了岸橋多目標(biāo)混合整數(shù)規(guī)劃模型。

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

(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 遺傳算法求解

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

3.1 染色體的設(shè)計及初始解的生成

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

圖2 染色體設(shè)計Fig.2 Chromosome design

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

3.2 適應(yīng)度函數(shù)的計算及選擇操作

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

g=1,2

(24)

(25)

適應(yīng)度函數(shù)的權(quán)重設(shè)置如式(26)：

(26)

染色體適應(yīng)度函數(shù)計算為

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

(27)

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

3.3 遺傳運算

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

3.3.1 交叉操作

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

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

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

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

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

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

3.3.2 變異操作

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

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

3.4 算例實驗及結(jié)果分析

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

表1 遺傳算法參數(shù)設(shè)置

3.4.1 數(shù)據(jù)輸入

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

表2 已知的任務(wù)信息

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

表3 岸橋首個任務(wù)距離

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

表4 兩兩任務(wù)距離

(續(xù)表4)

dij123456789105543201234466543101233776542101228876532101199876432100109876432100

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

3.4.2 岸橋調(diào)度模型結(jié)果與分析

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

表5 不同目標(biāo)下生成的調(diào)度方案及岸橋作業(yè)結(jié)果

(續(xù)表5)

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

分別對3種目標(biāo)所生成的調(diào)度方案的岸橋作業(yè)完成時間和岸橋作業(yè)時間進行比較，如圖5。

圖5 不同目標(biāo)下各岸橋作業(yè)完成時間及作業(yè)時間Fig.5 QC operation time and completion time with different targets

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

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

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

4 結(jié) 語

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

[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] 曾慶成，高宇．集裝箱碼頭裝卸橋調(diào)度優(yōu)化模型與算法[J]．計算機工程與應(yīng)用，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] 周鵬飛，康海貴.面向隨機環(huán)境的集裝箱碼頭泊位-岸橋分配方法[J].系統(tǒng)工程理論與實踐，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] 曾慶成，胡祥培，楊忠振．集裝箱碼頭泊位分配-裝卸橋調(diào)度干擾管理模型[J]．系統(tǒng)工程理論與實踐，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] 范志強，樂美龍．最小化最大完工時間與等待時間的岸橋作業(yè)調(diào)度雙目標(biāo)優(yōu)化及其遺傳算法[J]．系統(tǒng)管理學(xué)報，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] 范志強．考慮任務(wù)優(yōu)先約束的同類岸橋作業(yè)調(diào)度優(yōu)化[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] 徐遠(yuǎn)琴，韓曉龍．集卡與岸橋及場橋聯(lián)合調(diào)度模型優(yōu)化[J]．重慶交通大學(xué)學(xué)報(自然科學(xué)版)，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] 高超鋒，胡志華.岸橋并行作業(yè)效率約束下泊位與岸橋集成分派[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版)，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] 王昕昕.岸邊集裝箱起重機動態(tài)配置與貝位調(diào)度多目標(biāo)問題研究[D].上海:上海海事大學(xué)，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

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

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

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

U691+3

A

1674-0696(2016)03-155-07