鄭紅星,于 凱

(大連海事大學(xué)交通運(yùn)輸管理學(xué)院,遼寧大連116026)

基于混合遺傳算法的混堆箱區(qū)內(nèi)場(chǎng)橋調(diào)度研究

鄭紅星*,于 凱

(大連海事大學(xué)交通運(yùn)輸管理學(xué)院,遼寧大連116026)

所謂混堆模式下集裝箱箱區(qū)內(nèi)場(chǎng)橋調(diào)度問題,是指在固定時(shí)段內(nèi),將有限的場(chǎng)橋資源在混堆模式集裝箱港口堆場(chǎng)的單個(gè)箱區(qū)內(nèi)進(jìn)行分配和排序,以最大限度地減少該時(shí)段內(nèi)所有任務(wù)的等待成本和場(chǎng)橋非裝卸成本為目標(biāo),并保證不能超過場(chǎng)橋的作業(yè)強(qiáng)度極限.在充分考慮了多場(chǎng)橋作業(yè)時(shí)須有安全距離和不能相互跨越,以及內(nèi)外集卡的優(yōu)先級(jí)有差異和集卡等待時(shí)間有上限等現(xiàn)實(shí)約束下,對(duì)此問題構(gòu)建了非線性數(shù)學(xué)規(guī)劃模型.基于問題自身的特點(diǎn)設(shè)計(jì)了基于任務(wù)排序的染色體結(jié)構(gòu),用融入禁忌搜索的混合遺傳算法進(jìn)行求解.最后通過實(shí)例分析證明了模型和算法的有效性.

水路運(yùn)輸;系統(tǒng)工程;場(chǎng)橋調(diào)度;混合遺傳算法;混堆箱區(qū)

1 引 言

隨著集裝箱貿(mào)易量的日益增長(zhǎng),以及港口自身堆場(chǎng)面積有限,許多集裝箱港口采用混堆模式來進(jìn)行堆存,該模式下堆場(chǎng)的相關(guān)問題是當(dāng)前港口研究的熱點(diǎn)之一.很多國內(nèi)外學(xué)者對(duì)混堆模式下港口的堆場(chǎng)進(jìn)行了研究.Gambardella L.M等提出了混堆模式下集裝箱堆存的優(yōu)化模型[1];王斌研究了滾動(dòng)周期內(nèi)進(jìn)出口隨機(jī)箱量最佳分配方法[2];鄭紅星等在滾動(dòng)式計(jì)劃的基礎(chǔ)上,以新增集裝箱壓箱數(shù)最小為目標(biāo)構(gòu)建了箱位指派優(yōu)化模型,并設(shè)計(jì)了相應(yīng)的啟發(fā)式算法求解[3].

就混堆模式下堆場(chǎng)作業(yè)效率和效益而言,箱區(qū)內(nèi)場(chǎng)橋的調(diào)度是其中的關(guān)鍵.對(duì)于場(chǎng)橋調(diào)度問題,很多國內(nèi)外相關(guān)學(xué)者都進(jìn)行了較深入的研究,其中單場(chǎng)橋調(diào)度文獻(xiàn)有:Kim H.K.等研究了單個(gè)場(chǎng)橋?qū)ν饧ǖ慕幌浜腿∠淙蝿?wù)的作業(yè)序列問題[4];韓曉龍研究了裝船過程中單臺(tái)龍門吊的最優(yōu)路徑問題[5];W.C.Ng等在一個(gè)給定了裝卸量且各任務(wù)就緒時(shí)間不同的堆場(chǎng)內(nèi)研究場(chǎng)橋調(diào)度問題[6].多場(chǎng)橋調(diào)度的文獻(xiàn)有:Wenkai L等考慮了更多的現(xiàn)實(shí)約束,建立多場(chǎng)橋調(diào)度模型,并使用啟發(fā)式和水平滾動(dòng)算法求解[7];Matthew E.H.P等建立了多場(chǎng)橋?qū)崟r(shí)控制系統(tǒng),利用仿真進(jìn)行了分析[8];樂美龍,林艷艷等考慮場(chǎng)橋?qū)嶋H作業(yè)約束,建立多場(chǎng)橋混合整數(shù)規(guī)劃模型并設(shè)計(jì)了兩階段啟發(fā)式算法[9],但只考慮了兩臺(tái)場(chǎng)橋的調(diào)度.

綜上,針對(duì)混堆模式下堆場(chǎng)的研究主要集中在各箱區(qū)作業(yè)箱量的平衡和不同箱型的箱位指派上,對(duì)于該模式下堆場(chǎng)的其他方面研究甚少.而對(duì)于堆場(chǎng)單箱區(qū)內(nèi)場(chǎng)橋調(diào)度的研究,大都針對(duì)分堆模式,且假定該箱區(qū)內(nèi)作業(yè)場(chǎng)橋的數(shù)量既定,并沒有考慮該數(shù)量是否合理.

本文針對(duì)在混堆模式下的堆場(chǎng)內(nèi),假定一段時(shí)間內(nèi)各任務(wù)位置及對(duì)應(yīng)集卡到達(dá)時(shí)刻都已知,考慮內(nèi)外集卡優(yōu)先級(jí)別的差異,構(gòu)建了單箱區(qū)內(nèi)場(chǎng)橋調(diào)度優(yōu)化模型,以該時(shí)段內(nèi)所有任務(wù)的等待成本、場(chǎng)橋非裝卸成本(場(chǎng)橋移動(dòng)成本和空閑等待成本)最小化為目標(biāo),設(shè)計(jì)了混合遺傳算法求解模型,最后用實(shí)例驗(yàn)證了算法與模型的有效性.

本文與已有文獻(xiàn)的主要不同之處如下:

(1)考慮集卡到達(dá)堆場(chǎng)指定作業(yè)位置時(shí)間的影響,該因素直接影響場(chǎng)橋的調(diào)度方案,而以往文獻(xiàn)大多未考慮;

(2)研究外集卡在堆場(chǎng)等待時(shí)限對(duì)場(chǎng)橋調(diào)度的影響,在現(xiàn)有文獻(xiàn)中,大多欠考慮這方面的因素;

(3)研究?jī)?nèi)外集卡優(yōu)先級(jí)對(duì)混堆模式下場(chǎng)橋調(diào)度的影響,在已有文獻(xiàn)中基本沒有涉及;

(4)研究箱區(qū)中場(chǎng)橋的配置與調(diào)度集成優(yōu)化,在現(xiàn)有文獻(xiàn)中大多只研究場(chǎng)橋配置既定的調(diào)度問題,而不考慮配置是否合理.

2 問題描述

在混堆箱區(qū)內(nèi)某個(gè)箱位對(duì)應(yīng)的箱型可能是進(jìn)口箱、出口箱、進(jìn)箱、待提箱其中的一個(gè),等待服務(wù)的集卡包括內(nèi)外集卡且它們的作業(yè)時(shí)間和要求也各不相同,從而導(dǎo)致場(chǎng)橋調(diào)度更復(fù)雜,如圖1所示.因此在某一固定時(shí)段內(nèi),只有給混堆箱區(qū)配備合理臺(tái)數(shù)的作業(yè)場(chǎng)橋,并確定這些場(chǎng)橋的合理作業(yè)順序,才能既滿足客戶的服務(wù)水平,又不至于使港方的成本過高.

圖1 一個(gè)混堆集裝箱箱區(qū)示意圖Fig.1 The schematic diagram of a mixture storage block

本文研究的是混堆模式下集裝箱港口的某箱區(qū),在某段時(shí)間內(nèi)各任務(wù)貝位和集卡到達(dá)時(shí)間已知的場(chǎng)橋調(diào)度優(yōu)化問題.為了最大限度地同步優(yōu)化箱區(qū)內(nèi)場(chǎng)橋配置以及各場(chǎng)橋的作業(yè)序列,文中構(gòu)建了一個(gè)以該時(shí)段內(nèi)所有任務(wù)的等待成本、場(chǎng)橋非裝卸成本最小化為目標(biāo),并保證當(dāng)配有多臺(tái)場(chǎng)橋時(shí),場(chǎng)橋間須有安全距離且不能跨越的調(diào)度模型.

3 場(chǎng)橋調(diào)度模型

3.1 模型假設(shè)

(1)單個(gè)混堆箱區(qū)內(nèi)最多配置3臺(tái)場(chǎng)橋,至少配置1臺(tái)場(chǎng)橋.

(2)所有任務(wù)位于同一混堆箱區(qū),箱位既定且各任務(wù)對(duì)應(yīng)集卡的到達(dá)時(shí)刻可知.

(3)各場(chǎng)橋的勞動(dòng)時(shí)長(zhǎng)均不得超過其勞動(dòng)強(qiáng)度上限值.

(4)當(dāng)箱區(qū)內(nèi)配置多臺(tái)場(chǎng)橋時(shí),橋間不能穿越且有一定的安全作業(yè)距離.

(5)外集卡超過等待上限后其優(yōu)先級(jí)高于未超過上限的內(nèi)集卡,內(nèi)集卡超過等待上限后服務(wù)優(yōu)先級(jí)最高,場(chǎng)橋必須為其服務(wù).

3.2 模型建立

參數(shù)描述:m為場(chǎng)橋編號(hào);n為某時(shí)段箱區(qū)內(nèi)任務(wù)總數(shù);Xim為場(chǎng)橋m第i個(gè)裝卸的任務(wù)編號(hào);Y為某時(shí)段箱區(qū)內(nèi)配置的場(chǎng)橋數(shù);Km為場(chǎng)橋m裝卸的總?cè)蝿?wù)數(shù);r(Xim)為任務(wù)Xim的對(duì)應(yīng)集卡到達(dá)作業(yè)位置時(shí)刻;h(Xim)為場(chǎng)橋m裝卸任務(wù)Xim需要的時(shí)間;t(Xim)為場(chǎng)橋m完成第i次裝卸的任務(wù)的時(shí)刻;Fm為場(chǎng)橋m完成其任務(wù)集中最后一個(gè)任務(wù)的時(shí)刻;W(Xim)為0-1變量且當(dāng)Xim對(duì)應(yīng)集卡是內(nèi)卡時(shí)取0,否則取1;C(Xim)為任務(wù)Xim對(duì)應(yīng)的集卡等待單位時(shí)間的成本,而且變量具體取值為

d(X(i-1)m,Xim)表示場(chǎng)橋m從任務(wù)X(i-1)m移動(dòng)至任務(wù)Xim處所需的時(shí)間;B(Xim)為場(chǎng)橋m第i次裝卸的任務(wù)所處貝位;B(X0m)為計(jì)劃期初場(chǎng)橋m所處的貝位號(hào);B0為一個(gè)箱區(qū)內(nèi)總的貝位數(shù);為t時(shí)刻場(chǎng)橋m所處的貝位;為0;bsafe為相鄰場(chǎng)橋間留有的安全作業(yè)貝位數(shù);t(X0m)用于定義初始的系統(tǒng)當(dāng)前時(shí)刻為0;C為場(chǎng)橋空閑單位時(shí)間的成本;C0為場(chǎng)橋大車移動(dòng)單位時(shí)間需要的成本;T1為內(nèi)集卡的等待時(shí)間上限值;T2為外集卡的等待時(shí)間上限值;V0為場(chǎng)橋大車移動(dòng)速度;l0為單個(gè)貝位的長(zhǎng)度;T為單個(gè)計(jì)劃期時(shí)長(zhǎng).上述參量中Xim、Km、Y是模型的決策變量.

目標(biāo)函數(shù) Minf=α·(f1+f2)+(1-α)·f3

約束條件

以上式中m=1,2,…,Y.

在上述模型中,目標(biāo)式中的f1為場(chǎng)橋空閑成本,用每臺(tái)場(chǎng)橋完成其最后任務(wù)的時(shí)刻,減去該場(chǎng)橋用于裝卸和大車移動(dòng)的時(shí)間,然后匯總乘以單位時(shí)間空閑成本;f2為場(chǎng)橋移動(dòng)成本,用每臺(tái)場(chǎng)橋完成所有任務(wù)的大車移動(dòng)時(shí)間乘以單位時(shí)間移動(dòng)成本,然后匯總;f3為所有集卡總的等待成本,用每個(gè)集卡的作業(yè)完成時(shí)間減去該集卡的到達(dá)時(shí)間和裝卸時(shí)間,并視集卡不同類型再減去30 min(即當(dāng)為內(nèi)集卡時(shí),只要等待就會(huì)產(chǎn)生等待費(fèi)用;當(dāng)為外集卡時(shí),等待時(shí)間超過30 min才會(huì)產(chǎn)生等待成本),最后匯總并乘以單位時(shí)間的集卡等待成本.對(duì)于權(quán)重值α,本文將在算法中為兩部分設(shè)置權(quán)重(實(shí)際工作中可參考決策者的偏好或港口具體情況而定),并以加權(quán)總成本作為目標(biāo)函數(shù)值.

約束(1)保證任一個(gè)任務(wù)的完成時(shí)刻不早于該任務(wù)到達(dá)時(shí)刻與裝卸時(shí)間之和;約束(2)為某任務(wù)完成時(shí)刻、集卡到達(dá)時(shí)刻、裝卸時(shí)長(zhǎng)等之間的等式約束;約束(3)為場(chǎng)橋從某任務(wù)行走到下一任務(wù)所需時(shí)間的等式約束;約束(4)、(5)、(6)共同保證了一個(gè)任務(wù)只能由一臺(tái)場(chǎng)橋裝卸且只能被裝卸一次;約束(7)保證場(chǎng)橋之間不會(huì)出現(xiàn)穿越同時(shí)保證留有安全作業(yè)距離;約束(8)保證在計(jì)劃時(shí)段內(nèi)任意時(shí)刻各場(chǎng)橋均不能跑出箱區(qū);約束(9)為任務(wù)等待單位時(shí)間的成本取值約束;約束(10)為內(nèi)外集卡的判斷并賦值為1,0;約束(11)保證各任務(wù)的等待時(shí)間不能超過對(duì)應(yīng)上限;約束(12)保證各場(chǎng)橋的作業(yè)時(shí)間不超過計(jì)劃期的80%,即不超過最大勞動(dòng)強(qiáng)度;約束(13)為各參數(shù)取值約束;約束(14)為決策變量的范圍約束.

4 模型求解

針對(duì)模型的特點(diǎn),本文設(shè)計(jì)了混合遺傳算法(HGA),把TS的記憶功能引入到GA進(jìn)化過程之中并用TS算法增強(qiáng)GA的爬山能力,具體算法如下所述.

4.1 染色體編碼

采用實(shí)數(shù)編碼,一個(gè)調(diào)度方案對(duì)應(yīng)的染色體長(zhǎng)度為(任務(wù)數(shù)+場(chǎng)橋數(shù)-1),各基因值為任務(wù)編號(hào),“0”基因?yàn)椴煌瑘?chǎng)橋間的間隔符號(hào),例如10任務(wù)由3臺(tái)場(chǎng)橋共同裝卸的一個(gè)調(diào)度方案對(duì)應(yīng)的染色體結(jié)構(gòu)及說明如圖2所示.

圖2 染色體編碼展示Fig.2 The show of chromosome coding

4.2 初始種群的生成

在生成初始種群時(shí),要滿足約束(4)、(5)、(6),以保證生成的染色體無重復(fù)的基因值.還須滿足當(dāng)有兩臺(tái)作業(yè)場(chǎng)橋時(shí)保證染色體中“0”不能處于基因鏈的首尾位,三臺(tái)作業(yè)場(chǎng)橋時(shí)保證染色體中有2個(gè)“0”基因,且“0”不能處于基因鏈的首位或出現(xiàn)兩個(gè)“0”相鄰的情況,避免生成的染色體無意義.

4.3 適值函數(shù)

算法中個(gè)體的適值函數(shù)用個(gè)體的目標(biāo)值函數(shù)變化而成.為滿足約束(7),當(dāng)個(gè)體對(duì)應(yīng)方案出現(xiàn)跨越或干擾時(shí)該類個(gè)體的適值將被明顯區(qū)分,如下式:

在算法中計(jì)算f(Xi)時(shí)引入一懲罰規(guī)則來滿足約束(11),當(dāng)個(gè)體對(duì)應(yīng)的方案有集卡超過等待上限,給該個(gè)體的目標(biāo)值加上一個(gè)M(一較大的正數(shù))值作為懲罰.

4.4 選擇操作

考慮到當(dāng)一個(gè)箱區(qū)內(nèi)配備多臺(tái)場(chǎng)橋作業(yè)時(shí),各代種群中有較多個(gè)體對(duì)應(yīng)的方案會(huì)有干擾或跨越.為了避免選擇該類個(gè)體,文中采用以下選擇流程:

Step 1 在當(dāng)前種群任意選擇一個(gè)體,撥一次輪盤產(chǎn)生一隨機(jī)數(shù).

Step 2 若當(dāng)前個(gè)體滿足被選條件且該個(gè)體對(duì)應(yīng)方案無干擾或跨越,則選擇此個(gè)體進(jìn)入交叉池,否則返回step 1.

Step 3 盤點(diǎn)已選的個(gè)體總數(shù),如果達(dá)到種群容量就停止選擇操作,否則,轉(zhuǎn)回step 1.

4.5 交叉操作

針對(duì)染色體編碼特點(diǎn),本文采用順序交叉,如圖3所示,具體步驟如下:

Step 1 隨機(jī)選擇兩個(gè)交叉點(diǎn)X,Y確定兩父體中將被復(fù)制到子代的基因片段,并初步得到兩個(gè)不完整的子代a、b.

Step 2 對(duì)兩個(gè)父?jìng)€(gè)體從第二個(gè)交叉點(diǎn)Y后開始列出原基因碼順序,得到兩個(gè)父?jìng)€(gè)體的基因碼排列.

Step 3 從父體1、父體2的基因碼排列中分別刪掉父體2、父體1已復(fù)制到子代的基因碼,分別得到排列a'、b'.

Step 4 對(duì)a,從第二個(gè)交叉點(diǎn)開始按順序?qū)⑴帕衎'的基因碼從左往右填入對(duì)應(yīng)的基因位并替換“×”.對(duì)b做同樣操作,完成后得到兩個(gè)完整的子個(gè)體.

當(dāng)箱區(qū)內(nèi)場(chǎng)橋的數(shù)量是三臺(tái)時(shí),染色體中有兩個(gè)“0”出現(xiàn),此時(shí)可能會(huì)刪除過多的“0”導(dǎo)致個(gè)體不一樣長(zhǎng).因此本文規(guī)定刪除排列出的基因碼是按照“只刪首次重復(fù)基因”規(guī)則,這樣可防止以上錯(cuò)誤情況出現(xiàn).

4.6 禁忌變異操作

考慮模型的特點(diǎn),本文設(shè)計(jì)了“禁忌變異(TSM)算子”.

鄰域設(shè)計(jì):文中鄰域構(gòu)造采用解(染色體)的簡(jiǎn)單變化實(shí)現(xiàn),即交換染色體中除了“0”之外的任意兩個(gè)基因位的值.鄰居數(shù)為C2n,當(dāng)任務(wù)數(shù)較大時(shí)鄰居過多,因此采用選擇目標(biāo)升序排列,并選前20%的鄰居作為候選集合.

禁忌表:文中選取的禁忌對(duì)象有兩類,一類是,導(dǎo)致目標(biāo)值變大超過30%的解被禁.另一類是,交換基因值后出現(xiàn)場(chǎng)橋穿越或干擾的所有對(duì)象被禁.禁忌長(zhǎng)度為

特赦規(guī)則:當(dāng)候選集中目標(biāo)值最好的個(gè)體被禁,如果此個(gè)體的目標(biāo)值小于當(dāng)前最優(yōu)值,則解禁.

TS的終止原則:當(dāng)?shù)螖?shù)達(dá)到終止上限Kmax時(shí)終止.

禁忌變異算子求解流程如圖4所示.

圖3 染色體交叉過程Fig.3 The crossover process of chromosomes

圖4 禁忌變異流程Fig.4 The process of TSM

4.7 HGA終止規(guī)則

對(duì)于HGA的終止規(guī)則,本文采用當(dāng)算法的迭代次數(shù)達(dá)到預(yù)設(shè)的上限時(shí)終止計(jì)算.

4.8 HGA的性能分析

為了獲知本文設(shè)計(jì)的HGA是否提高了傳統(tǒng)GA的性能,分別用GA和HGA求解某具體問題.針對(duì)一箱區(qū)內(nèi)具有較多裝卸任務(wù)的場(chǎng)橋調(diào)度問題進(jìn)行求解,相關(guān)實(shí)驗(yàn)數(shù)據(jù)如表1、表2所示.

對(duì)于GA和HGA的染色體編碼、生成初始種群、適值計(jì)算、個(gè)體的選擇等均采用上文提出的方式.在實(shí)驗(yàn)中,GA及HGA使用的遺傳參數(shù)為:群體大小300,交叉概率和變異概率分別為0.4和0.08,終止代為1 000.最終GA搜索到900代左右目標(biāo)值收斂于1 600元.對(duì)于HGA僅搜索到650代左右目標(biāo)值就收斂于1 400元.圖5和圖6分別給出了使用HGA和GA的搜索過程.

表1 箱區(qū)內(nèi)任務(wù)情況Table 1 The task condition in a mixture storage block

表2 模型中相關(guān)參數(shù)取值Table 2 The parameter values of the model

圖5 HGA的搜索過程Fig.5 The search process of HGA

圖6 GA的搜索過程Fig.6 The search process of GA

從圖6可以看出,GA的收斂速度比較緩慢而且群體的均值不穩(wěn)定,目標(biāo)值400代左右首次穩(wěn)定,在第580代開始爬山.而觀察圖5可知HGA的收斂很迅速且群體的均值較穩(wěn)定,目標(biāo)值230代左右首次穩(wěn)定,很快在第320代就開始爬山,并在650代停止搜索.因此,針對(duì)本文提出的調(diào)度模型, HGA相比傳統(tǒng)GA更有效.

5 實(shí)例分析

5.1 實(shí)例描述

某集裝箱港口內(nèi)某混堆箱區(qū)2個(gè)小時(shí)內(nèi)有26個(gè)需裝卸任務(wù),各任務(wù)位置、對(duì)應(yīng)集卡到達(dá)時(shí)間、裝卸時(shí)長(zhǎng)、對(duì)應(yīng)集卡類型等具體見表3;場(chǎng)橋移動(dòng)速度、行走和空閑成本率、內(nèi)外卡等待成本率等參數(shù)見表4.

表3 箱區(qū)內(nèi)任務(wù)情況Table 3 The task condition in a block

表4 參數(shù)取值Table 4 Parameter value

5.2 結(jié)果分析與比較

采用MATLAB軟件編程實(shí)現(xiàn)HGA,實(shí)驗(yàn)在Intel Pentium Dual-Core T2080 1.73GHz的處理器, 2GB內(nèi)存的PC上進(jìn)行,并設(shè)置種群大小Popsize為300,交叉概率Pc為0.4,變異概率為Pm= 0.08,HGA的最大迭代次數(shù)為1 000,禁忌變異操作中算法迭代上限Kmax為500.

經(jīng)多次實(shí)驗(yàn),系統(tǒng)最優(yōu)值隨著遺傳代數(shù)增加收斂效果如圖7所示,在第940代,目標(biāo)值收斂于1 355.24元.對(duì)應(yīng)的配置作業(yè)場(chǎng)橋數(shù)為2,調(diào)度方案為YC1:2→1→5→9→12→15→23→22→17→19; YC2:6→3→4→7→8→11→14→18→10→16→13→21→20→25→24→26,該方案的相應(yīng)評(píng)價(jià)指標(biāo)值見表5.為了直觀看出方案是否出現(xiàn)場(chǎng)橋間跨越或干擾,繪制了兩臺(tái)場(chǎng)橋的實(shí)時(shí)行走路徑,如圖8所示,從圖中可看出兩場(chǎng)橋路徑無交點(diǎn),即求得的優(yōu)化調(diào)度方案確實(shí)未出現(xiàn)場(chǎng)橋間的干擾或跨越.

圖7 目標(biāo)值收斂過程Fig.7 Convergence process of objective value

圖8 兩場(chǎng)橋?qū)崟r(shí)行走路徑Fig.8 Real-time paths of two yard cranes

表5 優(yōu)化調(diào)度方案評(píng)價(jià)表Table 5 The evaluation table of optimized scheme

在集裝箱堆場(chǎng)實(shí)際工作中,通常采用的場(chǎng)橋調(diào)度規(guī)則為先到先服務(wù)(FCFS)和就近原則(Adjacent).針對(duì)文中案例,采用上述兩個(gè)規(guī)則得出的調(diào)度方案與方案的各項(xiàng)評(píng)價(jià)指標(biāo)值如表6和表7所示.

表6 傳統(tǒng)調(diào)度規(guī)則下的場(chǎng)橋調(diào)度方案Table 6 The YC scheduling based on common rules

表7 FCFS與Adjacent的調(diào)度方案評(píng)價(jià)表Table 7 The evaluation table of scheme(FCFS&Adjacent)

對(duì)比表5和表7,可以看出三個(gè)方案中:采用文中模型得出調(diào)度方案的目標(biāo)總成本(對(duì)應(yīng)表中的加權(quán)成本)和場(chǎng)橋總空閑成本最低,同時(shí)完成所有集卡裝卸任務(wù)的總時(shí)間最短,并且所有的集卡完成時(shí)限都未超等待上限(內(nèi)卡10分鐘,外卡30分鐘).從以上對(duì)比分析可知,同采用傳統(tǒng)調(diào)度規(guī)則相比,文中模型求得的調(diào)度方案更合理.

6 研究結(jié)論

混堆模式下集裝箱堆場(chǎng)的作業(yè)量和頻次非常大,如何有效地利用有限數(shù)量的場(chǎng)橋以保證堆場(chǎng)的工作效率和效益具有重要的現(xiàn)實(shí)意義.本文針對(duì)混堆模式下港口的單箱區(qū)某時(shí)段內(nèi)的場(chǎng)橋調(diào)度問題,重點(diǎn)考慮內(nèi)外集卡的優(yōu)先級(jí)、場(chǎng)橋間不可跨越和需有安全距離,以及集卡等待時(shí)間的上限4個(gè)方面,建立了場(chǎng)橋調(diào)度優(yōu)化模型,設(shè)計(jì)了混合遺傳算法進(jìn)行求解.算例結(jié)果表明,本文提出的場(chǎng)橋調(diào)度模型能確定箱區(qū)配置作業(yè)場(chǎng)橋的合理數(shù)量及其作業(yè)序列,并在保證堆場(chǎng)作業(yè)效率的同時(shí)降低生產(chǎn)運(yùn)營成本,可為混堆模式下場(chǎng)橋的實(shí)時(shí)調(diào)度提供決策支持.

本文研究中將各任務(wù)需要的裝卸時(shí)間視為已知,但實(shí)際作業(yè)中由于倒箱的影響,會(huì)使得某些任務(wù)的裝卸時(shí)長(zhǎng)有所偏差.因此在本文研究基礎(chǔ)上,可將倒箱問題加入研究中.

[1] Gambardella L M,Mastrolilli M,Rizzoli A E,et al.An optimizationmethodologyforintermodalterminal management[J].Journal of Intelligent Manufacturing, 2001,12(5/6):521-534.

[2] 王斌.集裝箱堆場(chǎng)基于混堆的滾動(dòng)式計(jì)劃堆存方法[J].系統(tǒng)工程學(xué)報(bào),2005,20(5):466-471. [WANG B,Method of planned rolling period of a container yard based on mixture storage[J].Journal of Systems Engineering,2005,20(5):466-471.]

[3] 鄭紅星,杜亮,董鍵.混堆模式下集裝箱堆場(chǎng)箱位指派優(yōu)化模型[J].交通運(yùn)輸系統(tǒng)工程與信息,2012,12 (1):153-159.[ZHENG H X,DU L,DONG J, Optimization modeloncontainerslotallocationin container yard with mixed storage mode[J],Journal of Transportation SystemsEngineeringandInformation Technology,2012,12(1):153-159.]

[4] Kim H K,Lee K M,Hwang H.Sequencing delivery and receiving operations for yard cranes in port container terminals[J].Int.J.Production Economics,2003,84 (3):283-292.

[5] 韓曉龍.集裝箱港口龍門吊的最優(yōu)路徑問題[J].上海海事大學(xué)學(xué)報(bào),2005,26(2):39-41.[HAN X L. Routing problem of transfer crane at container terminals [J].Journal of Shanghai Maritime University,2005, 26(2):39-41.]

[6] W C Ng,K L Mak.An effective heuristic for scheduling a yard crane to handle jobs with different ready times [J].Engineering Optimization,2005,37(8):867-877. [7] Wenkai L,Yong W,M E H P,et al.Discrete time model and algorithms for container yard crane scheduling [J].European Journal of Operational Research,2009, 198(1):165-172.

[8] Matthew EHP,YongW,WenkaiLi,etal. Development and simulation analysis of real-time yard crane control systems for seaport container transshipment terminals[J].OR Spectrum,2009,31(4):801-835.

[9] 樂美龍,林艷艷,范志強(qiáng).基于兩階段啟發(fā)式算法的多場(chǎng)橋作業(yè)調(diào)度研究[J].武漢理工大學(xué)學(xué)報(bào),2012, 34(1):60-65.[LE M L,LIN Y Y,FAN Z Q, Research on multi-yard-crane scheduling problem based on two-phase heuristic algorithm[J],Journal of Wuhan University of Technology,2012,34(1):60-65. ]

Yard Crane Scheduling in the Mixture Storage Block Based on Hybrid Genetic Algorithm

ZHENG Hong-xing,YU Kai
(Transportation Management College,Dalian Maritime University,Dalian 116026,Liaoning,China)

The yard crane scheduling problem in the mixture storage container terminal's block involves the allocation of limited yard crane resource and the scheduling of loading and unloading tasks on each block in the mixture storage container terminal,in order to reduce the waiting cost of all tasks and the non-load and non-unload cost of all operating yard cranes during the fixed span,as well as assure those operating yard crane's operation strength not passing the strength limit.Under the real constraints of non-crossing of yard cranes and keeping safe distance when multi-yard cranes are working together,along with different priority level between the inner truck and outer truck,and those trucks'waiting time limit,the non-linear mathematical planning model is set up.A hybrid genetic algorithm(HGA)is proposed according to the characteristics of the problem which is based on the tabu search algorithm,and the chromosome representation is structured on the sequence of tasks.Finally,the model and the algorithm are proved by one real example.

waterway transportation;systems engineering;yard crane scheduling;hybrid genetic algorithm;mixture storage container terminal's block

U693

: A

U693

A

1009-6744(2013)05-0150-09

2013-01-28

2013-05-10錄用日期:2013-06-14

國家自然科學(xué)基金(71202108);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(017229).

鄭紅星(1971-),男,河北遷安人,博士,副教授.

*通訊作者:zhredstar@yahoo.cn