丁 玲,梁承姬
(上海海事大學(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)濟效益和競爭力。
岸橋調(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ù)。
設(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的。
將集裝箱船舶上連續(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)的時間表。
筆者所應(yīng)用的數(shù)據(jù)中,岸橋最早可用時間都為0時刻,岸橋在相鄰貝位之間的單位移動時間為1 min,岸橋作業(yè)時的安全距離是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.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é)果
針對岸橋調(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.