• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2014-04-28 06:13:14梁承姬
      關(guān)鍵詞:等待時間調(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.

      猜你喜歡
      等待時間調(diào)度船舶
      給學(xué)生適宜的等待時間
      ——國外課堂互動等待時間研究的現(xiàn)狀與啟示
      《船舶》2022 年度征訂啟事
      船舶(2021年4期)2021-09-07 17:32:22
      《調(diào)度集中系統(tǒng)(CTC)/列車調(diào)度指揮系統(tǒng)(TDCS)維護手冊》正式出版
      船舶!請加速
      一種基于負(fù)載均衡的Kubernetes調(diào)度改進算法
      BOG壓縮機在小型LNG船舶上的應(yīng)用
      虛擬機實時遷移調(diào)度算法
      船舶壓載水管理系統(tǒng)
      中國船檢(2017年3期)2017-05-18 11:33:09
      意大利:反腐敗沒有等待時間
      公民與法治(2016年2期)2016-05-17 04:08:28
      顧客等待心理的十條原則
      視野(2015年14期)2015-07-28 00:01:44
      娱乐| 藁城市| 勐海县| 桓仁| 共和县| 屏东市| 开原市| 长岛县| 五台县| 南京市| 高安市| 济南市| 上虞市| 焦作市| 瑞安市| 龙游县| 北辰区| 抚宁县| 南开区| 肇州县| 杭锦后旗| 乌拉特后旗| 肇东市| 克山县| 辽宁省| 涿州市| 元氏县| 泸水县| 囊谦县| 达尔| 嘉兴市| 于田县| 孝感市| 宁晋县| 白玉县| 齐齐哈尔市| 尚义县| 沅陵县| 右玉县| 浏阳市| 南投市|