董良才　孫思韻

摘要：

針對集裝箱碼頭岸橋調(diào)度問題，以集裝箱箱組為切入點(diǎn)，綜合考慮岸橋干擾約束及作業(yè)單元優(yōu)先順序約束，以最小化船舶作業(yè)時(shí)間以及岸橋作業(yè)時(shí)間為目標(biāo)，建立混合整數(shù)規(guī)劃模型.利用多種算法進(jìn)行求解對比，并針對新穎的螢火蟲算法進(jìn)行研究，提出兩種改進(jìn)的螢火蟲算法以克服其運(yùn)行時(shí)間較長及易陷入局部最優(yōu)的缺陷.實(shí)例分析表明，兩種改進(jìn)后的螢火蟲算法能有效解決岸橋調(diào)度問題，其相關(guān)理論對提高岸橋的作業(yè)效率以及集裝箱碼頭服務(wù)水平具有一定借鑒意義.

關(guān)鍵詞：

岸橋調(diào)度； 螢火蟲算法； 遺傳算法； 模擬退火算法； 岸橋干擾

中圖分類號： U691.5

文獻(xiàn)標(biāo)志碼： A

0 引 言

岸橋是在碼頭前沿裝卸集裝箱的主要設(shè)備，其運(yùn)作效率直接關(guān)系到整個集裝箱港口的運(yùn)作效率.岸橋調(diào)度問題就是給岸橋分配作業(yè)單元并確定作業(yè)單元的先后順序，使集裝箱船舶能夠盡快完成裝卸作業(yè).

DAGANZO[1]首次提出裝卸多艘集裝箱船舶的岸橋調(diào)度問題，將每艘集裝箱船舶劃分為多個船區(qū)，要求在任何時(shí)刻某一船區(qū)最多只能容納一臺岸橋進(jìn)行作業(yè)，以最小化所有集裝箱船舶的累計(jì)延誤成本為目標(biāo)函數(shù).PETERKOFSKY等[2]利用分支定界法求解上述問題.這兩篇文獻(xiàn)的目標(biāo)函數(shù)都是最小化船舶的延遲成本，但沒有考慮岸橋之間的互相干擾以及作業(yè)單元間的先后順序.

對岸橋調(diào)度模型的研究綜述如下.

KIM等[3]研究單船岸橋調(diào)度問題，以最小化岸橋完工時(shí)間以及岸橋總完工時(shí)間為目標(biāo)，以集裝箱箱組作為作業(yè)單元，利用分支定界法進(jìn)行求解.MOCCIA等[4]考慮岸橋在同一條軌道上運(yùn)行，岸橋不能交叉，且需要留有安全間隔，由此構(gòu)建了新的岸橋調(diào)度模型，并利用CPLEX求解.孫俊清等[5]對KIM等[3]的模型進(jìn)行修改，考慮不同岸橋裝卸能力的差異，以所有到港船舶的等候服務(wù)時(shí)間最短為目標(biāo)，利用模擬退火算法（Simulated Annealing Algorithm， SAA）對其求解.LEE等[6]建立了考慮岸橋干擾約束的岸橋調(diào)度模型，并利用遺傳算法（Genetic Algorithm， GA）對其求解.韓笑樂等[7]考慮

岸橋作業(yè)調(diào)度問題的其他約束，建立了考慮優(yōu)先順序約束和岸橋碰撞約束的數(shù)學(xué)模型，并利用啟發(fā)式算法進(jìn)行求解.董良才等[8]提出基于時(shí)間窗的岸橋調(diào)度模型，并考慮艙蓋板的約束，將一個貝位的裝卸單元分為6個大類，并利用GA進(jìn)行求解.LEGATO等[9]提出包含各種實(shí)際約束的模型，并利用分支定界法以及Petri網(wǎng)進(jìn)行求解.范志強(qiáng)等[10]分析了岸橋支援對船舶裝卸作業(yè)效率的影響，發(fā)現(xiàn)減少岸橋的等待時(shí)間有利于岸橋支援，建立了雙目標(biāo)混合模型，設(shè)計(jì)了GA進(jìn)行求解，并求出問題的下界.

對岸橋調(diào)度算法的研究綜述如下.

王輝球[11]對岸橋調(diào)度問題的復(fù)雜度進(jìn)行討論，并證明了此問題為NP難問題，利用GA對考慮安全間隔的岸橋調(diào)度模型進(jìn)行求解.MARCELLO等[12]運(yùn)用禁忌搜索算法對考慮岸橋互相干擾的岸橋調(diào)度模型進(jìn)行求解.李晨等[13]考慮岸橋不可交叉、安全距離以及甲板開閉的約束，推導(dǎo)出岸橋的總完工時(shí)間，采用GA進(jìn)行求解.MEISEL等[14]用JAVA平臺對不同案例求解得出基準(zhǔn)值，對不同的模型進(jìn)行評價(jià).楊明珠[15]對單船岸橋調(diào)度問題進(jìn)行研究，利用改進(jìn)的貪婪算法求解.CHUNG等[16]利用改進(jìn)的GA對KIM等[3]的模型進(jìn)行求解，利用次序雜交的方式對兩部分編碼進(jìn)行交叉操作.KAVESHGAR等[17]利用GA對KIM等[3]的模型進(jìn)行求解，改善初始種群規(guī)則以提高運(yùn)行速度，提出一種新的編碼方式，使得維數(shù)減少.范志強(qiáng)等[18]考慮了不同岸橋的效率差異，并利用GA對其求解.董良才等[19]對全岸線岸橋的調(diào)度問題進(jìn)行研究，建立模型，采用基于段的編碼方式對模型進(jìn)行求解.NGUYEN等[20]將GA與遺傳規(guī)劃結(jié)合對岸橋調(diào)度問題進(jìn)行求解.

目前岸橋調(diào)度問題是集裝箱碼頭研究的一大熱點(diǎn)，但對岸橋在實(shí)際作業(yè)中的安全距離以及作業(yè)單元由艙蓋板劃分而導(dǎo)致的作業(yè)單元優(yōu)先順序的考慮并不充分.而YANG[21]提出的螢火蟲算法（Firefly Algorithm，F(xiàn)A）在其他領(lǐng)域的應(yīng)用結(jié)果表明，F(xiàn)A能較好地解決NP難問題，并且能較好地與其他算法結(jié)合，在解決離散編碼問題上具有獨(dú)特的方法，但至今仍未見將其應(yīng)用到岸橋調(diào)度問題上.故本文擬在充分考慮岸橋調(diào)度各實(shí)際因素的基礎(chǔ)上建立更完備的岸橋調(diào)度模型，并引入新型FA，通過結(jié)合其他啟發(fā)式算法的優(yōu)良特征，設(shè)計(jì)符合岸橋調(diào)度模型的算法，為岸橋調(diào)度問題提供更切合實(shí)際的解決方案.

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

集裝箱船舶?？看a頭后，碼頭安排一定數(shù)量岸橋?qū)ζ溥M(jìn)行裝卸作業(yè).岸橋調(diào)度就是合理安排每臺岸橋作業(yè)單元順序使得船舶與岸橋的作業(yè)時(shí)間最短.集裝箱裝卸作業(yè)單元的劃分方式有基于貝位區(qū)域、基于獨(dú)立貝位以及基于集裝箱箱組的劃分方式，其中基于集裝箱箱組劃分方式的岸橋調(diào)度問題最具復(fù)雜性.本文基于集裝箱箱組進(jìn)行研究.

由于船舶甲板與船艙以艙蓋板劃分，將一個大貝內(nèi)的集裝箱根據(jù)甲板卸箱、艙內(nèi)卸箱、艙內(nèi)裝箱、甲板裝箱進(jìn)行劃分，將劃分后的集裝箱箱組作為一個作業(yè)單元.同一個大貝內(nèi)的作業(yè)順序要符合先卸船、后裝船、卸船先卸甲板箱、裝船先裝艙內(nèi)箱的約束.岸橋作業(yè)時(shí)必須防止互相干擾，主要包括：①岸橋不能相互交叉；②岸橋間必須留有一定的安全距離.

數(shù)學(xué)模型的建立將基于假設(shè)條件：

（1）每臺岸橋有且僅有一個作業(yè)單元為初始與終了作業(yè)單元；

（2）在任何時(shí)刻，一個作業(yè)單元只能容納一臺岸橋?qū)ζ溥M(jìn)行作業(yè)；

（3）岸橋一旦開始一個作業(yè)單元，就要先完成該作業(yè)單元所有任務(wù)才能移至下一作業(yè)單元繼續(xù)作業(yè).

1.1 符號定義

i，j為作業(yè)單元編號，隨貝位變大而變大；k為岸橋編號，隨貝位變大而變大；n為作業(yè)單元總數(shù)量；m為岸橋的總數(shù)量；t為相鄰兩個作業(yè)單元間的岸橋移動時(shí)間；M為一個足夠大的正數(shù)；li為第i個作業(yè)單元所在貝位；lk，0為岸橋k的起始貝位；lk，T為岸橋k的終了貝位；pi為第i個作業(yè)單元的處理時(shí)間；rk為岸橋k的最早可用時(shí)間；α1為岸橋最長完工時(shí)間的權(quán)重；α2為岸橋總完工時(shí)間的權(quán)重；Ω為所有作業(yè)單元的集合；ψ為不可同時(shí)進(jìn)行的作業(yè)單元集合；φ為具有優(yōu)先作業(yè)順序的作業(yè)單元集合；

1.2 決策變量

1.3 模型描述

式（1）為岸橋調(diào)度問題的目標(biāo)函數(shù)，以最小化岸橋最長完工時(shí)間和岸橋總完工時(shí)間為目標(biāo).式（2）確保岸橋的最長完工時(shí)間必須大于等于所有岸橋的最長完工時(shí)間.式（3）和（4）表示每臺岸橋都有且僅有一個作業(yè)單元作為其初始與終了作業(yè)單元.式（5）表示每個作業(yè)單元都必須由一臺岸橋獨(dú)立完成.式（6）表示同一時(shí)刻一臺岸橋只能為一個作業(yè)單元服務(wù)，直到完成該作業(yè)單元后才可繼續(xù)下一作業(yè)單元.式（7）為對每臺岸橋完工時(shí)間的約束，每臺岸橋完工時(shí)間應(yīng)大于等于其終了作業(yè)單元的完工時(shí)間.式（8）為每臺岸橋的最早可用時(shí)間約束，每臺岸橋的初始作業(yè)單元開始時(shí)間應(yīng)該大于等于其最早可用時(shí)間.式（9）表示在同一臺岸橋上兩個相鄰作業(yè)單元之間的時(shí)間約束.式（10）為作業(yè)單元先后作業(yè)時(shí)間約束.式（11）表示岸橋在作業(yè)過程中不能交叉.式（12）表示由于岸橋干擾約束，作業(yè)單元i與作業(yè)單元j不能同時(shí)進(jìn)行作業(yè).式（13）為岸橋間安全距離的約束.式（14）表示具有優(yōu)先作業(yè)約束的作業(yè)單元.式（15）為01變量約束.式（16）表示對任意作業(yè)單元與岸橋，其作業(yè)時(shí)間均大于等于0.

該模型在KAVESHGAR等[17]于2012年提出的岸橋調(diào)度模型基礎(chǔ)上進(jìn)行修改，并加入約束式（13），充分考慮岸橋間安全距離約束.

2 算法設(shè)計(jì)

分別對3種基本算法（GA，SAA和FA）進(jìn)行算法設(shè)計(jì)（其中GA與SAA不在本文進(jìn)行贅述），主要針對FA的不足，將多種群GA和模擬退火機(jī)制與其結(jié)合，設(shè)計(jì)出一種融合模擬退火機(jī)制和遺傳算子的多種群螢火蟲算法（簡稱為HFA），并根據(jù)FA易陷入局部最優(yōu)的缺點(diǎn)設(shè)計(jì)出多種群自適應(yīng)螢火蟲算法（簡稱為SFA）.

2.1 螢火蟲算法

FA是由劍橋大學(xué)的YANG[21]提出的，根據(jù)螢火蟲成蟲發(fā)光原理產(chǎn)生的.螢火蟲彼此吸引的原因取決于兩個要素，即自身亮度和吸引度.螢火蟲的發(fā)光亮度取決于目標(biāo)函數(shù)值，發(fā)光亮度越高表示越優(yōu)，相對發(fā)光亮度則體現(xiàn)了螢火蟲所處位置的好壞并決定了螢火蟲的移動方向.吸引度決定了螢火蟲的移動距離.如果發(fā)光亮度相同，則螢火蟲會隨機(jī)移動.

螢火蟲相對發(fā)光亮度為

式中：

I0為螢火蟲最大發(fā)光亮度，即自身（rij=0處）發(fā)光亮度；γ為光強(qiáng)吸收系數(shù)；rij為螢火蟲i，j之間的距離；β0為最大吸引度，即rij=0處的吸引度，吸引度與距離成反比；xi，xj分別為螢火蟲i，j的空間位置；α為步長因子，是區(qū)間[0，1]之間的常數(shù)；λ為[0，1]上服從均勻分布的隨機(jī)數(shù).岸橋調(diào)度問題的FA步驟如下.

步驟1

初始化基本參數(shù)：n（螢火蟲數(shù)目），β0，γ，α，最大迭代次數(shù).

步驟2 初始化螢火蟲位置.計(jì)算螢火蟲目標(biāo)函數(shù)值并以此作為其自身亮度，將不符合岸橋干擾約束的解的目標(biāo)函數(shù)值設(shè)為一個極大值.

步驟3 判斷是否符合作業(yè)單元優(yōu)先順序約束，若符合則執(zhí)行步驟4，否則對解的編碼進(jìn)行調(diào)整.

步驟4 根據(jù)式（17）和（18）計(jì)算I和β.

步驟5 每個螢火蟲與其他螢火蟲比較I，決定螢火蟲的移動方向.若存在具有更高發(fā)光亮度的螢火蟲，則按式（19）向其移動.若不存在更優(yōu)解，則隨機(jī)移動.

步驟6 滿足終止條件后結(jié)束，輸出最優(yōu)解，否則，重復(fù)步驟2～5.

2.2 結(jié)合GA和模擬退火機(jī)制的螢火蟲算法（HFA）

考慮到FA兩兩比較造成求解時(shí)間成倍增加，將種群分為多子群；各子群采用并行GA，且交叉變異參數(shù)各不相同，加大搜索區(qū)域；在GA交叉變異環(huán)節(jié)加入模擬退火機(jī)制（Metropolis抽樣），增強(qiáng)其局部尋優(yōu)能力；將各子群中的最優(yōu)解放入主群中，在主群中利用FA求解.在協(xié)作尋優(yōu)時(shí)分別采用移民算子及人工選擇算子.HFA的主要步驟如下.

步驟1 設(shè)定控制參數(shù)：子種群個數(shù)

L，子種群規(guī)模N，各子種群交叉概率Pc，變異概率Pm，溫度冷卻系數(shù)q，初始溫度T0和結(jié)束溫度Tend.

步驟2 隨機(jī)產(chǎn)生L個初始種群.各種群按照各自的交叉、變異概率進(jìn)行尋優(yōu)，分別計(jì)算個體適應(yīng)度函數(shù)值并判斷是否符合約束條件，并按基本GA進(jìn)行尋優(yōu).

步驟3 執(zhí)行協(xié)作尋優(yōu)，從各子種群中找出最優(yōu)個體和最差個體，將最優(yōu)個體放入主群中，并將前一種群中最優(yōu)個體代替當(dāng)前種群中最差個體.

步驟4 在主群中按2.1節(jié)進(jìn)行FA尋優(yōu)，對I進(jìn)行兩兩比較，若有更優(yōu)的螢火蟲，則螢火蟲按式（19）移動，否則保留當(dāng)前解.

步驟5 判斷主群中的解是否滿足作業(yè)單元優(yōu)先順序，若滿足則執(zhí)行步驟6，否則對編碼進(jìn)行調(diào)整.

步驟6 判斷是否滿足終止條件，若滿足則輸出結(jié)果，否則重復(fù)步驟2～5.

2.3 多種群自適應(yīng)螢火蟲算法（SFA）

將種群分為多個子群，并對各子群采用不同的

α，β0，γ，提高搜索區(qū)域，將各子群的最優(yōu)解放到主群中并利用FA進(jìn)行求解.最初求解時(shí)采用一個較大的α，使算法能更好地完成全局搜索，隨迭代次數(shù)增加，α逐漸減小，使算法能快速收斂.為防止陷入局部最優(yōu)，設(shè)定一個迭代次數(shù)間隔，若在迭代次數(shù)間隔內(nèi)沒有更新最優(yōu)解，則認(rèn)為其可能陷入局部最優(yōu)，進(jìn)而將α設(shè)為一個較大值，使其跳出局部最優(yōu).SFA的尋優(yōu)步驟如下.

步驟1 初始化算法的基本參數(shù)：

L，n（各子種群中的螢火蟲數(shù)目），β0，γ，α，最大迭代次數(shù)，判定是否陷入局部收斂的迭代次數(shù)t′.

步驟2 分別對各子種群分配β0，γ，α.各子種群分別按各自的參數(shù)進(jìn)行并行FA尋優(yōu).

步驟3 判斷各子種群在t′內(nèi)有沒有更新最優(yōu)解，若沒有，則判定其陷入局部最優(yōu)，此時(shí)將α設(shè)為一個較大的值，使其盡快跳出局部最優(yōu).

步驟4 進(jìn)行協(xié)作尋優(yōu)，使用移民算子將前一子種群中的最優(yōu)值替換后一子種群中的最差值.使用人工選擇算子將各子種群中的最優(yōu)值放入主群中.

步驟5 對主群進(jìn)行FA尋優(yōu).

步驟6 判斷在tn次數(shù)內(nèi)有沒有更新最優(yōu)解，若沒有，則判定其陷入局部最優(yōu)，此時(shí)將α設(shè)為一個較大的值，使其盡快跳出局部最優(yōu).

步驟7 滿足終止條件后結(jié)束，輸出最優(yōu)解，否則，重復(fù)步驟2～6.

3 算例分析

分別對兩個算例進(jìn)行分析，算例來自文獻(xiàn)[14]，目前單船岸橋調(diào)度問題主要采用該案例進(jìn)行方法比較.采用小規(guī)模算例對3種基本算法進(jìn)行對比，采用大規(guī)模算例對兩種改進(jìn)FA進(jìn)行對比.目標(biāo)函數(shù)權(quán)重采用α1=0.9，α2=0.1，且岸橋在相鄰大貝的移動時(shí)間為1 min，兩臺岸橋的安全距離為1個大貝.

3.1 小規(guī)模算例

小規(guī)模算例為2臺岸橋?qū)σ凰揖哂?0個大貝和10個集裝箱箱組的船舶進(jìn)行裝卸作業(yè)，采用3種基本算法對其求解，并對比算法性能，挖掘各自特點(diǎn).表1為算例數(shù)據(jù).作業(yè)單元間存在先后順序，第4個作業(yè)單元必須優(yōu)先于第5個作業(yè)單元進(jìn)行處理，第9個作業(yè)單元必須優(yōu)先于第10個作業(yè)單元進(jìn)行處理.岸橋準(zhǔn)備時(shí)間不考慮，岸橋初始位置分別在02貝和06貝.

由表2和圖1可知，GA最優(yōu)，SAA最差，而FA運(yùn)行時(shí)間遠(yuǎn)大于另兩種算法的運(yùn)行時(shí)間.

3.2 大規(guī)模算例

大規(guī)模算例為3臺岸橋?qū)?艘具有10個大貝和20個集裝箱箱組的船舶進(jìn)行裝卸作業(yè)，利用兩種改進(jìn)的FA對其求解，將模型中所提出的約束條件在結(jié)果中體現(xiàn)，并對算法性能進(jìn)行分析.表3為算例數(shù)據(jù).岸橋3由于需要先完成其他任務(wù)，在裝卸作業(yè)開始30 min后加入作業(yè)，

4 結(jié) 論

本文在現(xiàn)有文獻(xiàn)基礎(chǔ)上對岸橋作業(yè)調(diào)度進(jìn)行分

析，建立符合實(shí)際情況的岸橋調(diào)度問題模型，考慮岸橋不可交叉及安全距離約束，首次加入由艙蓋板劃分的作業(yè)單元優(yōu)先順序約束，使結(jié)果更具有應(yīng)用性.

在算法設(shè)計(jì)上，利用遺傳算法（GA）、模擬退火算法（SAA）、螢火蟲算法（FA）分別對岸橋調(diào)度問題進(jìn)行求解，并對結(jié)果進(jìn)行比較分析，得到兩種改進(jìn)的FA.HFA將多種群遺傳算法和模擬退火機(jī)制加入FA中，極大地改善了FA收斂速度慢的缺陷.SFA改善了FA易陷入局部最優(yōu)的缺陷.本文為FA在岸橋調(diào)度問題中的使用奠定了基礎(chǔ)，并且成功將FA與成熟算法結(jié)合得到更優(yōu)的結(jié)果，也驗(yàn)證了FA在NP難問題中的適用性.

參考文獻(xiàn)：

[1]

DAGANZO C F. The crane scheduling problem[J]. Transportation Research Part B Methodological， 1989， 23（3）： 159175.

[2]PETERKOFSKY R I， DAGANZO C F. A branch and bound solution method for the crane scheduling problem[J]. Transportation Research Part B Methodological， 1990， 24（3）： 159172.

[3]KIM K H， PARK Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research， 2004， 156（3）： 752768.

[4]MOCCIA L， CORDEAU J F， GAUDIOSO M， et al. A branchandcut algorithm for the quay crane scheduling problem in a container terminal[J]. Naval Research Logistics， 2005， 53（1）： 4549.

[5]孫俊清， 李平， 韓梅. 裝卸橋調(diào)度問題及其混合智能優(yōu)化算法GASA[C]//第26屆中國控制會議論文集.北京： 北京航空航天大學(xué)出版社， 2007： 9296.

[6]LEE D H， WANG H Q， MIAO L X. Quay crane scheduling with noninterference constraints in port container terminals[J].Transportation Research Part E Logistics & Transportation Review， 2008， 44（1）： 124135.

[7]韓笑樂， 梁亮， 陸志強(qiáng)， 等. 集裝箱碼頭岸吊作業(yè)調(diào)度建模及調(diào)度策略研究[J]. 工業(yè)工程與管理， 2009， 14（5）： 2026.

[8]董良才， 丁以中， 宓為建. 基于時(shí)間窗的集裝箱裝卸橋調(diào)度[J]. 上海海事大學(xué)學(xué)報(bào)， 2011， 32（1）： 17.

[9]LEGATO P， TRUNFIO R， MEISEL F. Modeling and solving rich quay crane scheduling problems[J]. Computers & Operations Research， 2012， 39（4）： 20632078.

[10]范志強(qiáng)， 樂美龍. 最小化最大完工時(shí)間與等待時(shí)間的岸橋作業(yè)調(diào)度雙目標(biāo)優(yōu)化及其遺傳算法[J]. 系統(tǒng)管理學(xué)報(bào)， 2013， 22（1）：120127.

[11]王輝球. 集裝箱岸吊的調(diào)度模型和算法研究[D]. 北京： 清華大學(xué)， 2006.

[12]MARCELLO S， CORDEAU J F， LAPORTE G， et al. A tabu search heuristic for the quay crane scheduling problem[J]. Journal of Scheduling， 2007， 10（4）： 327336.