考慮干涉和優(yōu)先度的多目標(biāo)岸橋調(diào)度策略

丁 玲，梁承姬

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

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

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

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

1 問題描述

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

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

圖1 岸橋調(diào)度示意圖

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

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

2 模型建立

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

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

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

約束條件為:

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

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

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

算法步驟如下:

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

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

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

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

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

(7)得到岸橋調(diào)度初始可行解，結(jié)束。

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

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

4 數(shù)值實驗

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

4．1 算法驗證

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

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

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

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

4．2 多目標(biāo)與單目標(biāo)結(jié)果的對比

4．2．1 模型求解

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

表2 多目標(biāo)結(jié)果

表3 單目標(biāo)結(jié)果

圖2 單目標(biāo)的岸橋調(diào)度

圖3 多目標(biāo)的岸橋調(diào)度

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

4．2．2 算例分析

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

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

表4 單目標(biāo)與多目標(biāo)的比較結(jié)果

5 結(jié)論

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

［1］ 范志強，樂美龍．最小化最大完工時間與等待時間的岸橋作業(yè)［J］．系統(tǒng)管理學(xué)報，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．