丁 玲，梁承姬

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

岸橋調度是集裝箱港口重要操作之一，岸橋作業(yè)效率的高低直接影響集裝箱港口的經濟效益，優(yōu)化岸橋操作［1］，對有效地提高港口的效率和競爭力有重要意義。

DAGANZO［2］首次提出岸橋調度問題，他假設每艘船舶從長度上按照船艙來分，目的是使所有的集裝箱船舶盡早離開港口，從而最小化船舶的延遲成本。DAGANZO等［3］在上述研究基礎上，提出了一種更加精確的方法來加速裝卸作業(yè)，他們把一個裝卸操作定義為一個任務，并且考慮了任務之間的優(yōu)先順序。KIM等［4］主要研究船舶貝位任務的岸橋調度問題，考慮到了任務之間的優(yōu)先和干涉關系，建立了混合整數(shù)規(guī)劃模型，提出了一種精確的啟發(fā)式算法求解該模型。LEE［5］則證明了 QCSP(quay crane scheduling problem)是NP完全問題，考慮了岸橋之間的干涉關系而沒有考慮岸橋在船艙之間的移動時間，以最小化船艙的最大完成時間為目標，并運用遺傳算法進行求解。MOCCIA等［6］注意到KIM等的模型中岸橋之間干涉的可能性，對模型做了相關的改進，改進的模型包含了岸橋的移動時間和同一貝位里任務之間的優(yōu)先關系，為了限制岸橋完成時間的上下界，以最小化岸橋的最大完成時間為目標，提出了一種BC算法來求解岸橋調度問題，求解結果比KIM得出的結果更加精確。MARCELLO等［7］描述了由KIM等提出的關于岸橋調度問題的模型，運用搜索問題和禁忌搜索算法對路徑問題和調度問題分別求解。NATHAN［8］基于上述模型，建立了數(shù)學模型，運用一種改進的遺傳算法來求解岸橋調度問題，并且使用新的程序來計算決策變量的更加嚴密的上下界。CHUNG等［9］提出的模型考慮了岸橋之間的優(yōu)先約束和干涉情況，并提出了一種改進的遺傳算法來求解QCSP。范志強等建立了岸橋作業(yè)調度雙目標混合整數(shù)規(guī)劃模型，其優(yōu)化目標是最小化最大完工時間和岸橋等待時間，提出了一種遺傳算法進行求解。

岸橋調度就是分配岸橋來處理裝卸操作，安排岸橋作業(yè)船舶的任務順序。上述文獻考慮到最小化任務的最大完工時間，但沒有考慮處理岸橋的等待時間和移動時間，忽略了岸橋在船舶之間進行支援的情況。筆者旨在研究多目標的岸橋調度問題，即在最小化任務的最大完工時間的同時，盡量減少岸橋的移動時間和等待時間，便于岸橋進行支援，優(yōu)化岸橋操作，加快港口的整體運作效率，以提高港口經濟效益和競爭力。

1 問題描述

岸橋調度問題中，一般可以把任務定義為:①集裝箱組;②完整的貝位;③貝位區(qū)域［10］。

研究單一的集裝箱船舶，船舶從長度上按貝位來劃分，如圖1所示，這些貝位都裝載著一些集裝箱，定義一組相似的集裝箱為一個任務。

圖1 岸橋調度示意圖

由于岸橋需要在軌道上移動，需要考慮干涉問題，岸橋干涉問題主要為:①不交叉，即岸橋不能交叉操作。②安全，即鄰近的岸橋必須保持安全距離。

優(yōu)先度則需要考慮由于受到集裝箱位置、屬性、船舶結構等因素影響，某些集裝箱裝缷作業(yè)之間必須滿足一定的先后順序，如在裝載作業(yè)時，同一個貝位中的任務，只有先完成船艙里的作業(yè)任務才能作業(yè)甲板上的任務;在卸載作業(yè)時，同一貝位里的任務，只有先作業(yè)甲板上的任務才能作業(yè)船艙里的任務。

2 模型建立

設定一系列任務為 Ω ={1，2，3，…，n}和岸橋集合 K={1，2，3，…，k}，此處的每一個任務即為岸橋的裝載或者卸載操作，即有k臺岸橋服務集裝箱船舶上的Ω個任務，包括甲板上和船艙里的裝載和卸載操作。假設:①岸橋在同樣的軌道上運行，不能相互交叉。②岸橋之間的安全距離是一個貝位。③一些任務必須在其他任務之前完成，一些任務不能同時執(zhí)行。

以下符號用于筆者的問題描述中。①集合:Ω為任務的集合;ψ為不能同時執(zhí)行的作業(yè)集合;Φ為有優(yōu)先順序的任務集合。②索引:i，j為任務的索引;K為岸橋的索引。③變量:pi為岸橋處理一個任務的時間;li為任務i的位置(以船舶的貝位表示)為岸橋k開始作業(yè)的位置，一般以貝位來表示(0代表虛擬任務)為岸橋k作業(yè)完成后所在的最終位置，以貝位來表示(T代表虛擬任務);rk為岸橋k開始作業(yè)的時間;t為岸橋在相鄰貝位之間的單位移動時間;tij為岸橋從任務i所在的貝位移動到任務j所在貝位的時間(tij=t×|li－lj|)為岸橋從初始位置移到第一個任務j所在位置需要的時間為岸橋完成最后任務j后，移到最終位置所需時間，一般為 0;M為足夠大的整數(shù);α1為分配給任務的最大完成時間的權重;α2為分配給岸橋移動時間的權重;α3為分配給岸橋等待時間的權重。④決策變量:yi，k=1，岸橋k執(zhí)行任務為i，否則為0;x，岸橋 k 執(zhí)行完任務 i后執(zhí)行j，否則為0;zi，j=1，任務j的開始時間不早于任務 i的完成時間，否則為0;d為岸橋總的移動時間;Di為任務i的完成時間;m為岸橋總的等待時間;Yk為岸橋k的完成時間;W為任務的最大完成時間。

考慮到來港的船舶比較多，裝卸作業(yè)一般涉及到相互協(xié)調問題，需要更好的調度方法，且在多個目標之間具有相同的單位，因此設定相應的權重 α1，α2，α3，轉化為如下目標函數(shù)。

約束條件為:

式(1)表示最小化任務的最大完成時間的同時，減少岸橋的移動時間和等待時間;式(2)定義了W為最大任務的完成時間;式(3)表示每個任務只能由一臺岸橋作業(yè);式(4)表示每臺岸橋只有一個初始任務;式(5)表示每臺岸橋只有一個最終任務;式(6)、式(7)表示yik與的關系;式(8)表示每個任務都按照既定的順序作業(yè);式(9)表示一些任務之間存在優(yōu)先關系，即任務i執(zhí)行完后才能執(zhí)行任務j;式(10)表示任務j的完成時間比任務i的完成時間加上任務j的處理時間和任務i，j所在的兩個貝位之間的移動時間要大;式(11)表示一些任務不能同時作業(yè);式(12)表示岸橋作業(yè)時不能發(fā)生干涉;式(13)表示任務j的完成時間比任務i的完成時間加上任務j的處理時間要大;式(14)表示第一個任務的完成時間比岸橋初始位置移到第一個任務的移動時間加上第一個任務的處理時間要大;式(15)表示最后一個任務的完成時間加上岸橋從最后一個任務移到最終位置的時間等于岸橋的完成時間;式(16)表示岸橋總的移動時間;式(17)表示岸橋完工時間減去移動時間和任務的總處理時間為岸橋總的等待時間;式(18)表示W，m，d的權重關系;式(19)定義了，yik，zij為 0，1 變量;式(20)定義了 Di，W，m，d都是不小于0的。

3 岸橋調度的啟發(fā)式算法

將集裝箱船舶上連續(xù)的貝位，根據岸橋的臺數(shù)劃分為若干個貝位區(qū)域。一方面岸橋的移動范圍變得有限;另一方面可以減少岸橋的移動次數(shù)或者岸橋的移動時間，加快岸橋的作業(yè)效率。表示貝位集合表示岸橋的集合，ck為分配給岸橋k的任務作業(yè)完成時間，β為終止條件的權重。

算法步驟如下:

(2)計算每個任務理想的處理時間，若任務i，j在同一貝位里，sij表示任務i完成后作業(yè)任務j的準備時間，且，則

(3)?b ∈ B，任務 i，j在同一貝位 b中，將 i，j按照大小，從小到大排列，若任務j在任務i之前，而zij=1，則將任務j調到任務i后面。

(4)根據式(9)計算Db，貝位b的完成時間，即貝位中任務的最大完成時間。

(5)計算貝位區(qū)域Bk中的所有貝位的完成時間，要考慮滿足式(12)，將貝位區(qū)域Bk中的貝位按照從小到大排列，若任務i位于貝位b1中，任務j位于貝位b2中，zij=1而貝位b2在b1之前作業(yè)，則需要調整貝位b1，b2的作業(yè)順序。

(6)計算船舶上所有貝位區(qū)域的完成時間，即各岸橋的完成時間ck，為了達到均衡，如Ck，Ck，Ck+1，中較大者設為k1，較小者設為k2，b1為 Bk1中 Db最小的貝位，則Bk1=Bk1/{b1}，Bk2=Bk2∪{b1}，轉步驟(3)，否則轉步驟(7)。

(7)得到岸橋調度初始可行解，結束。

上述算法中，步驟(1)主要是劃分作業(yè)區(qū)域;步驟(2)是計算每個任務的理想處理時間;步驟(3)是基于最短距離法對貝位里的任務進行排序;步驟(4)是計算各貝位的作業(yè)完成時間;步驟(5)是對同一貝位區(qū)域內的貝位進行作業(yè)排序;步驟(6)是計算出各貝位區(qū)域的完成時間，并比較相鄰區(qū)域之間完成時間的大小，選擇相差值最大的兩個區(qū)域，進行任務的調整，直到滿足結束條件。步驟(7)是得到各岸橋的作業(yè)時間表。

該算法步驟(7)得到的是基本可行解，為了得到更優(yōu)解，進行局部搜索。在每臺岸橋的任務集合中任意地選取兩個任務，變換它們的作業(yè)順序，滿足上述的約束條件，重新計算各任務的完成時間，如果結果更優(yōu)則更新時間表，直到求出結果最優(yōu)的時間表。

4 數(shù)值實驗

筆者所應用的數(shù)據中，岸橋最早可用時間都為0時刻，岸橋在相鄰貝位之間的單位移動時間為1 min，岸橋作業(yè)時的安全距離是1個貝位。

4．1 算法驗證

啟發(fā)式算法中，β值需要通過多次實驗，對運算時間和解的質量進行權衡比較才能得出來，通過實驗，β可取5%。

啟發(fā)式算法與Cplex求解的結果比較如表1所示。假設有2臺岸橋6個任務，為了避免人為因素，任務的處理時間從［20，100］中隨機選取，首先選取一個小規(guī)模的數(shù)據，分別計算啟發(fā)式算法與Cplex的結果，進行比較。

表1 啟發(fā)式算法與Cplex求解的結果比較

從表1的結果中可知啟發(fā)式算法在一定時間的允許下，可以求解出較優(yōu)解。

4．2 多目標與單目標結果的對比

4．2．1 模型求解

采用文獻［2］中的數(shù)據，運用算法對該模型進行求解，設定 α1=0．6，α2=0．2，α3=0．2，算法運行10次，求解結果如表2所示，同時為了與僅考慮單目標的模型進行對比，設定α1=1，α2=0，α3=0，求解結果如表3所示。單目標和多目標的岸橋調度分別如圖2和圖3所示。

表2 多目標結果

表3 單目標結果

圖2 單目標的岸橋調度

圖3 多目標的岸橋調度

由上述結果可知岸橋調度的多目標與單目標中任務的最大完成時間相比稍差一點，而在移動時間和等待時間上更優(yōu)，可以方便岸橋之間的支援，提高岸橋效率。

4．2．2 算例分析

通過不同規(guī)模的數(shù)據，對單目標和多目標的岸橋調度結果進行比較，采用上述數(shù)據，處理時間從［20，100］中任意產生，岸橋臺數(shù)從2增加至6，任務數(shù)量從10增加至25。

由上述結果可知，多目標岸橋調度與單目標岸橋調度的結果差不多，不過當岸橋臺數(shù)一樣，增加工作量，岸橋的移動時間會增加;工作量相同時，增加岸橋臺數(shù)，岸橋的移動時間會減少，而岸橋的等待時間會增加，即發(fā)生干涉情況的幾率會增大;對于任務的最大完成時間，在同樣的作業(yè)量下，會隨岸橋的數(shù)量減少而減少，比較結果如表4所示。

表4 單目標與多目標的比較結果

5 結論

針對岸橋調度問題的一些特性和約束，提出了一種岸橋調度的啟發(fā)式算法，并通過驗證證明，該算法能在一定時間的允許下得到滿意解。實驗結果證明多目標岸橋調度問題比單目標岸橋調度問題更能有效地提高岸橋效率，增加港口的經濟效益。

［1］ 范志強，樂美龍．最小化最大完工時間與等待時間的岸橋作業(yè)［J］．系統(tǒng)管理學報，2013，22(1):120 －127．

［2］ DAGANZO C F．The crane scheduling problem［J］．Transportation Research Part B，1989，23(3):159 －175．

［3］ DAGANZO C F，PETERKOFSKY R I．A branch and bound solution method for the crane scheduling problem［J］．Transportation Research B，1990，24(3):159－172．

［4］ KIM K H，PARK Y M．A crane scheduling method for port container terminals［J］．European Journal of Operational Research，2004，156(1):752 －768．

［5］ LEE D H．Quay crane scheduling with non－interference constraints in port container terminals［J］．Transportation Research Part E，2008，44(1):124 －135．

［6］ MOCCIA L，CORDEAU J F，GAUDIOSO M．A branch－and－cut algorithm for the quay crane scheduling problem in a container terminal［J］．Naval Research Logistics，2006，53(1):45 －59．

［7］ MARCELLO S，JEAN F C．A tabu search heuristic for the quay crane scheduling problem［J］．Journal of Scheduling，2007，10(4 －5):327 －336．

［8］ NATHAN N．An efficient genetic algorithm for solving the quay crane scheduling problem［J］．Expert Systems with Applications，2012，39(2):13108 －13117．

［9］ CHUNG S H，CHOY K L．A modified genetic algorithm for quay crane scheduling operations［J］．Expert Systems with Applications，2012，39(1):4213 －4221．

［10］ BIERWIRTH C，MEISEL F．A fast heuristic for quay crane scheduling with interference constraints［J］．Journal of Scheduling，2009，12(1):345 －360．