劉 悅，謝 謝

1.遼寧信息職業(yè)技術(shù)學(xué)院 軟件工程系，遼寧 遼陽 111000 2.沈陽大學(xué) 制造集成自動(dòng)化重點(diǎn)實(shí)驗(yàn)室，沈陽 110044

求解動(dòng)態(tài)停泊計(jì)劃問題的拉格朗日松弛算法

劉 悅1，謝 謝2

1.遼寧信息職業(yè)技術(shù)學(xué)院 軟件工程系，遼寧 遼陽 111000 2.沈陽大學(xué) 制造集成自動(dòng)化重點(diǎn)實(shí)驗(yàn)室，沈陽 110044

1 引言

作為中國(guó)最重要的鋼鐵制造商，寶鋼每年擁有超過上千萬噸的原材料。其中大約95%的原材料由水路運(yùn)輸至寶鋼原料碼頭進(jìn)行卸載，之后由碼頭皮帶運(yùn)輸機(jī)連接岸上的皮帶運(yùn)輸機(jī)將它們運(yùn)至指定料場(chǎng)。伴隨著年鋼產(chǎn)量的迅速增加，寶鋼所需的原材料也迅猛增長(zhǎng)，因此使得寶鋼原料碼頭上最昂貴的泊位資源顯得十分有限。這就迫切需要制定一個(gè)有效的進(jìn)港原料船停泊計(jì)劃來提高整個(gè)碼頭的生產(chǎn)率。原料碼頭的整個(gè)海岸線長(zhǎng)度通常會(huì)被劃分為幾個(gè)泊位，但是由于進(jìn)港原料船之間差別很大，所以在實(shí)際操作中在碼頭進(jìn)行卸載的原料船經(jīng)常會(huì)出現(xiàn)跨越原有泊位邊界的情況。為了與實(shí)際停泊計(jì)劃的要求相一致，本文將一個(gè)可同時(shí)?？慷鄺l原料船的連續(xù)泊位空間看作一個(gè)泊位。目標(biāo)為最小化總權(quán)重服務(wù)時(shí)間為目標(biāo)函數(shù)來為進(jìn)港原料船分配泊位空間，其中服務(wù)時(shí)間包括原料船到港后等待靠泊的時(shí)間和卸料時(shí)間。

近年來，關(guān)于停泊計(jì)劃問題已引起了一些學(xué)者的關(guān)注，然而與現(xiàn)有文獻(xiàn)相比，本文所提出的問題有如下幾個(gè)特點(diǎn)：（1）與Park and Kim[1-2]，Imai等學(xué)者[3-4]研究只有一個(gè)連續(xù)泊位的停泊計(jì)劃問題不同，本文研究有多個(gè)連續(xù)泊位的停泊計(jì)劃問題。（2）區(qū)別于Imai等學(xué)者[5-6]，Nishimura和Imai[7]，將碼頭上的離散停泊區(qū)域看作一個(gè)“泊位”，本文把整個(gè)連續(xù)的位置空間稱作一個(gè)“泊位”。由于本文所研究的停泊計(jì)劃問題只為原料船指定停泊位置但并不同時(shí)考慮卸船機(jī)的分配問題，所以主原料碼頭上的多臺(tái)卸船機(jī)認(rèn)為是相同的。如圖1所示，主原料碼頭和副原料碼頭構(gòu)成了兩個(gè)連續(xù)泊位。（3）按照本文所提出方法制定的停泊計(jì)劃為每一艘進(jìn)港船指定停泊泊位、在選定泊位上的具體停泊位置和開始卸料時(shí)間。（4）在計(jì)劃展望期開始時(shí)不是所有的進(jìn)港原料船都已經(jīng)到港。在計(jì)劃展望期開始時(shí)每一個(gè)泊位上僅部分泊位長(zhǎng)度是可利用的，即在泊位上存在上一個(gè)計(jì)劃展望期未完成全部卸載操作而遺留到當(dāng)前計(jì)劃展望期繼續(xù)進(jìn)行卸載的原料船。

圖1 寶鋼的連續(xù)泊位

大部分關(guān)于連續(xù)泊位停泊計(jì)劃問題的研究都假定在計(jì)劃展望期開始時(shí)，不存在上一個(gè)展望期內(nèi)未卸載完而延續(xù)到下一個(gè)計(jì)劃展望期繼續(xù)卸載的進(jìn)港船。本文所考慮的計(jì)劃展望期開始時(shí)在每一個(gè)連續(xù)泊位上并非所有的泊位長(zhǎng)度都可利用的停泊計(jì)劃問題是更接近于實(shí)際停泊計(jì)劃的一類問題。

本文所研究的停泊計(jì)劃問題可以用幾何方法在圖2所示的兩個(gè)泊位-時(shí)間平面上表示出來。每一個(gè)泊位-時(shí)間平面與主原料碼頭或副原料碼頭相對(duì)應(yīng)。橫軸對(duì)應(yīng)泊位的物理長(zhǎng)度，縱軸對(duì)應(yīng)計(jì)劃展望期。進(jìn)港原料船的泊位安排通過相應(yīng)泊位-時(shí)間平面上的矩形來表示。矩形的橫邊表示船的物理長(zhǎng)度，它的縱邊表示船在相應(yīng)泊位上的卸載時(shí)間。從上一個(gè)計(jì)劃展望期遺留下來的船用灰色的矩形表示，這些矩形的橫邊仍然表示船的長(zhǎng)度，而其縱邊表示該船在當(dāng)前計(jì)劃展望期上所剩余的卸料時(shí)間。

2 問題描述

圖2 動(dòng)態(tài)停泊計(jì)劃舉例

本文所研究的問題主要是對(duì)在泊位時(shí)間平面中代表進(jìn)港原料船的矩形進(jìn)行調(diào)度，其目的是在保證每個(gè)矩形都不與同一平面上的其他矩形相重疊的前提下使得目標(biāo)函數(shù)最小。本章為所研究的問題建立一個(gè)數(shù)學(xué)模型，該模型的特點(diǎn)是首先把連續(xù)泊位長(zhǎng)度和計(jì)劃展望期劃分為許多個(gè)長(zhǎng)度或時(shí)間段，使得整個(gè)泊位-時(shí)間平面被分割成許多方格。該模型通過確保每個(gè)方格最多只能被一艘船占用來避免重疊。該問題的建模方式可以被視為與Guan et al.[8]相似的多處理器任務(wù)調(diào)度問題[9-11]。這里船是工件，而經(jīng)過劃分后的每一個(gè)泊位長(zhǎng)度段可以看作是處理器。

2.1 問題假設(shè)

在給出模型前，先對(duì)問題做以下假設(shè)。

（1）假設(shè)原料船只有在完成卸載操作后才可以移動(dòng)，即在開始卸載后不允許變更泊位。在實(shí)際原料碼頭的卸船過程中，除非有優(yōu)先級(jí)很高的船急需泊位（如已經(jīng)延誤的外輪或運(yùn)送生產(chǎn)緊缺原料的船到港）否則一般不會(huì)對(duì)正在卸載的船更換泊位。這是因?yàn)槿魏螌?duì)卸載過程的干擾都會(huì)造成由相關(guān)原料船的額外等待時(shí)間和卸船機(jī)的調(diào)整時(shí)間而引起的高額費(fèi)用，所以該假設(shè)是合理的。

（2）不允許疊放?？?。這種停泊方式通常在海軍基地發(fā)生，但在鋼鐵企業(yè)原料碼頭卻不允許出現(xiàn)。

（3）每艘進(jìn)港船的卸載時(shí)間依賴于它所?？康牟次弧１M管在同一個(gè)泊位上的卸船機(jī)卸載能力是相同的，但是不同泊位上所配備的卸船機(jī)卸載能力是不同的。因此第三個(gè)假設(shè)適用于可以在多個(gè)泊位上進(jìn)行卸載操作的原料船。

（4）假設(shè)整個(gè)計(jì)劃展望期和每個(gè)泊位的總長(zhǎng)度被劃分為許多小的時(shí)間或長(zhǎng)度段，這樣每個(gè)泊位-時(shí)間平面就可以被分割成許多個(gè)方格。

2.2 數(shù)學(xué)模型

下面給出用于定義問題的參數(shù)和決策變量。

Ω：在整個(gè)計(jì)劃展望期內(nèi)將要到達(dá)的進(jìn)港原料船集合。該集合可以被劃分成三個(gè)子集：Ω1={1，2，…，N1}是只能在主原料碼頭進(jìn)行卸載的原料船集合；Ω2= {1，2，…，N2}是只能在副原料進(jìn)行卸載的原料船集合；Ω3={1，2，…，N3}是那些既可在主原料碼頭又可在副原料碼頭進(jìn)行卸載的原料船集合?；谝陨系亩x，可得Ω= {1，2，…，N}=Ω1∪Ω2∪Ω3，其中 N=N1+N2+N3是進(jìn)港原料船的總數(shù)。

Ψ：泊位集。該集合可以分成兩個(gè)子集：Ψ1={1，2，…，B1}是與主原料碼頭相對(duì)應(yīng)的泊位集；Ψ2={1，2，…，B2}是與副原料碼頭相對(duì)應(yīng)的泊位集。因此得到Ψ={1，2，…，B}= Ψ1∪Ψ2，其中B=B1+B2是泊位總數(shù)。

P：時(shí)間段集，P={1，2，…，T}，其中T是整個(gè)計(jì)劃展望期所分成的時(shí)間段總數(shù)。

Φj：泊位j上的泊位長(zhǎng)度段集，Φj={1，2，…，Qj}，其中Qj是泊位j上泊位長(zhǎng)度段總數(shù)。

pij：船i在泊位j上所需的卸載時(shí)間。

li：船i的長(zhǎng)度（包括水平安全距離）。

ai：船i的到達(dá)時(shí)間。

M：一個(gè)很大的數(shù)。

Ω′：遺留船集。Ω′={1，2，…，N′}，其中 N′是遺留船總數(shù)。

bkj：泊位j上的遺留船k的起始停泊位置。

rjm：泊位j上的長(zhǎng)度段m的可利用時(shí)間。

決策變量：

ci：船i的離港時(shí)間。

原料船的卸載時(shí)間和等待靠泊的時(shí)間之和形成了原料船的總服務(wù)時(shí)間，由于這個(gè)總服務(wù)時(shí)間是評(píng)價(jià)碼頭利用率的一個(gè)重要依據(jù)，因此本文以最小化進(jìn)港原料船的總權(quán)重服務(wù)時(shí)間為目標(biāo)函數(shù)。則模型可表示為：

約束式（2）確保每艘原料船必須被安排在一個(gè)泊位上進(jìn)行卸載。約束式（3）保證分配到某一泊位的各船必須在一個(gè)不間斷的時(shí)間段內(nèi)進(jìn)行卸載操作且占用與船的長(zhǎng)度相對(duì)應(yīng)的連續(xù)泊位長(zhǎng)度段。約束式（4）指明某一泊位-時(shí)間平面上的任意一個(gè)方格最多只能被一艘船占用。該約束保證在同一個(gè)泊位-時(shí)間平面內(nèi)沒有相互重疊的原料船。約束式（5）說明只有在船到達(dá)了原料碼頭后，并且該船所占用的連續(xù)泊位長(zhǎng)度段都可利用的時(shí)候，該船才可以開始卸載操作。約束式（6）表明船的離港時(shí)間是其開始卸載時(shí)間和卸載時(shí)間之和。約束式（7）表明了兩個(gè)決策變量zijkt和 yij之間的關(guān)系。根據(jù)定義，如果zijkt=1，那么 yij=1;類似地，如果 yij=0，那么zijkt=0。約束式（8）和（9）限定某些有固定泊位要求的船必須?？吭谙鄳?yīng)的泊位上。約束式（10）是決策變量約束。

3 拉格朗日松弛

如前所述，本文所研究的問題可以看作是以最小化總權(quán)重服務(wù)時(shí)間為目標(biāo)函數(shù)的多處理器任務(wù)調(diào)度問題。盡管已有文獻(xiàn)針對(duì)連續(xù)泊位停泊計(jì)劃問題提出定理或拉格朗日松弛算法給出了其所研究問題的下界[8，12]，然而由于問題特性的不同，這些下界不能擴(kuò)展應(yīng)用到本文的問題上。因此本文提出了適合求解本文所研究問題的拉格朗日松弛算法。

3.1 松弛問題的模型

從模型的結(jié)構(gòu)可以看出，只有約束式（4）包含了不同原料船。如果將該約束松弛掉，那么原問題就可以被分解為每個(gè)對(duì)應(yīng)一艘船的多個(gè)子問題。引入非負(fù)的拉格朗日乘子{ujmn}將約束式（4）松弛到目標(biāo)函數(shù)中形成松弛問題，表示如下：

滿足約束式（2）～（3），式（5）～（10），且 ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

那么拉格朗日對(duì)偶問題為：

滿足約束式（2）～（3），式（5）～（10），且 ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

在忽略掉常數(shù)項(xiàng)后，該問題可以被分解成每個(gè)對(duì)應(yīng)一艘原料船的多個(gè)子問題。則對(duì)應(yīng)于船i，i∈Ω的子問題表示如下：

(LRi)Minimize ZLi≡

滿足約束式（2）～（3），式（5）～（10），且 ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

3.2 求解子問題

對(duì)應(yīng)于船i的子問題可以按如下步驟求得最優(yōu)解。將式（6）代入式（13），可得：

滿足約束式（2）～（3），（5），（7）～（10），且ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

下面來研究約束式（2），（7）～（9）之間的關(guān)系。當(dāng)zijkt=1時(shí)，可從約束式（7）推出 yij=1?？紤]式（7）～（9），并令Ψi= {1，2，…，Bi}表示可以卸載船i的泊位集合，則對(duì)應(yīng)于船i的子問題變形為：

滿足約束式（2）～（3），（5），（10），且ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

在忽略最后一個(gè)常數(shù)項(xiàng)后，對(duì)應(yīng)于船i的子問題等價(jià)于：

滿足約束式（2）～（3），（5），（10），且ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

那么式（16）就等價(jià)于：

滿足約束式（2），（5），（10），且ujmn≥0，?j∈Ψ，m∈Φj，n∈P。約 束 式（5）表 明 如 果 zijkt=1，那 么 t≥max{ai，m=k，k+m1，a…x，k+l-1(rjm)}。因此子問題被表述為：

i

滿足約束式（2），（10）且ujmn≥0，?j∈Ψ，m∈Φj，n∈P。

因此，令zij*k*t*=1，找到使得下式成立的組合：

就得到對(duì)應(yīng)于船i的子問題最優(yōu)解。

如圖3所示，對(duì)于每艘船i，搜索(j*，k*，t*)的過程是在逐個(gè)掃描各泊位-時(shí)間平面內(nèi)的可能組合來實(shí)現(xiàn)的。在泊位-時(shí)間平面j內(nèi)，搜索過程從時(shí)間段1所對(duì)應(yīng)的第1行上長(zhǎng)度段1開始，到長(zhǎng)度段Qj–li+1結(jié)束。在完成對(duì)第1行上全部可能組合的搜索后，開始進(jìn)行對(duì)應(yīng)于時(shí)間段2的第2行上可能組合的搜索。依此類推，直至完成第T–pij+1行上全部可能組合的搜索后，對(duì)泊位-時(shí)間平面j的搜索結(jié)束，轉(zhuǎn)到下一個(gè)泊位-時(shí)間平面繼續(xù)進(jìn)行，直到將所有可卸載船i的泊位-時(shí)間平面上的組合都搜索完畢即可找到(j*，k*，t*)。

圖3 求解子問題搜索過程示意圖

性質(zhì)1在拉格朗日松弛算法第一次迭代過程中，對(duì)于每艘船i(i∈Ω)其所對(duì)應(yīng)的最優(yōu)組合(j*，k*，t*)=argmj，ki，nt(wit+ wipij)，這里 j∈Ψi，k∈{1，τhj|Chj–1–t≥0}，t∈{ai，C1j，C2j，…，Cgj}且t≥m=k，k+m1，a…x，k+l-1(rjm)，其中Chj等于泊位j上的遺留

i原料船h的離港時(shí)間加1，τhj等于船h在泊位j上的末尾停泊長(zhǎng)度段加1，h=1，2，…，g，這里g為泊位j上的遺留船總數(shù)。

證明 由于在拉格朗日松弛算法第一次迭代過程中，對(duì)于任意的 j∈Ψi，m∈Φj，n∈P，所有的拉格朗日乘子ujmn=0，所以問題簡(jiǎn)化為尋找使得 wit+wipij最小的組合(j*，k*，t*)。

在帶有遺留船的泊位j上，船i所有可能的開始時(shí)間只能是ai，C1j，C2j，…，Cgj中的一個(gè)，并且船i可能?？康钠瘘c(diǎn)位置是1或者是遺留船h的末尾位置加1。但是，在這其中只需考慮那些船i在時(shí)刻t停靠在泊位j上后，此時(shí)在該泊位上依然沒有離港的所有遺留船。

最后，所選的組合(j*，k*，t*)必須保證船i不能與泊位j*上的遺留船重疊。如上所述，可得結(jié)論。

性質(zhì)2令A(yù)*ijt′為針對(duì)船i的搜索過程進(jìn)行至泊位-時(shí)間平面j上第t′行時(shí)所得到的 Aijkt中的最小值。如果存在A*ijt′≤wi(t′+1+pij)，則對(duì)于同一平面j內(nèi) t＞t′并且 k=1， 2，…，Qj的搜索過程可以被省去。

證明 對(duì)于給定的i和 j，wi(t′+1+pij)是泊位-時(shí)間平面j上尚未搜索的T-t′+1行所有組合對(duì)應(yīng)的Aijkt中的最小值的下界。如果此時(shí)有該下界wi(t′+1+pij)＞A*ijt′，則不必再進(jìn)行同一平面上剩余的搜索過程。

3.3 尋找可行解

對(duì)約束式（4）的松弛很容易導(dǎo)致子問題的解不可行。這種不可行性具體表現(xiàn)為在同一個(gè)泊位-時(shí)間平面上的船互相重疊。為了尋找可行解，本節(jié)提出了一種啟發(fā)式算法。該啟發(fā)式的主要任務(wù)就是為子問題的解中互相重疊的船重新分配停泊位置。在給出這個(gè)啟發(fā)式之前，先給出一個(gè)性質(zhì)來指出等待泊位分配的原料船所對(duì)應(yīng)的矩形其左下端點(diǎn)可能占用的所有方格。

性質(zhì)3如果任意未被安排泊位的船i可以?？吭诓次籮，則其對(duì)應(yīng)的矩形左下端點(diǎn)可占用泊位-時(shí)間平面j上以下范圍內(nèi)的方格：k∈{1，τhj|Chj–1–t≥0}，t∈{ai，C1j，C2j，…，Cgj}且t≥m=k，k+m1，a…x，k+l-1(rjm)。其中Chj是泊位j上已安排泊位

i的船h的離港時(shí)間加1，τhj是泊位j上已安排泊位船h的末尾停靠長(zhǎng)度段加1，h=1，2，…，g+fj，這里g為泊位j上遺留船總數(shù)，fj為泊位j上所有已安排泊位的可行船總數(shù)。

證明 該性質(zhì)的證明類似于性質(zhì)1的證明。不同點(diǎn)在于除了要考慮泊位j上的遺留船外，還要考慮已安排泊位的可行船。

性質(zhì)3指出了在泊位-時(shí)間平面j上所有可能改進(jìn)目標(biāo)函數(shù)的長(zhǎng)度段k和時(shí)間段t的組合。由于其他的一些組合不可能改進(jìn)目標(biāo)函數(shù)值，因此不再進(jìn)行對(duì)它們的搜索。

在以下啟發(fā)式算法中只包含性質(zhì)3中指定的組合。令I(lǐng)和Ij代表不可行船集和子問題中分配至泊位j的不可行船集。令Fj代表泊位j上已安排泊位的可行船集。令I(lǐng)=Ф，Ij=Ф，F(xiàn)j=Ф且 j=0。該啟發(fā)式算法步驟如下：

步驟1 j=j+1。如果 j＞B，轉(zhuǎn)到步驟4。否則，i=0且令I(lǐng)j=Ф。將子問題中分配到泊位j的船將其按照到達(dá)時(shí)間的升序排列。

步驟2i=i+1。在給定遺留船和Fj中可行船的情況下，檢驗(yàn)子問題所給出的第i艘船泊位安排是否滿足約束式（4）。如果第i艘船的當(dāng)前泊位安排不違反約束式（4），則將其加入到Fj中；否則將其加入到Ij中。重復(fù)此步驟，直到泊位j上所有船都被加到Fj或Ij中為止。

步驟3選擇Ij中第一艘船作為當(dāng)前船。將其對(duì)應(yīng)矩形的左下端點(diǎn)安排在性質(zhì)3所指定的泊位-時(shí)間平面j上的每一個(gè)方格(k，t)以找到在不與Fj和泊位j上遺留船相重疊的條件下使得目標(biāo)函數(shù)值最小的可行解。如果為當(dāng)前船找到了可行解，則將當(dāng)前船從Ij中刪除并將其加入到Fj中；如果在泊位j不存在當(dāng)前船的可行泊位安排，則將其加入到I中。重復(fù)這一步驟直到Ij為空時(shí)為止。轉(zhuǎn)到步驟1。

步驟4如果I為空，停止。否則，選擇在I中第一艘船作為當(dāng)前船，并且在每個(gè)可以卸載當(dāng)前船的泊位上執(zhí)行步驟3中的類似步驟，但對(duì)于在子問題的解中已經(jīng)被分配給該船的泊位則不執(zhí)行此步驟。

3.4 更新拉格朗日乘子

本文使用次梯度方法來獲得拉格朗日乘子{ujmn}的值。令urjmn為迭代至第r代的乘子，ZUB為最小總權(quán)重服務(wù)時(shí)間的上界，該上界用3.3節(jié)中提到的啟發(fā)式算法求得。在用3.2節(jié)中的方法求解松弛問題后，所得解ZLB作為目標(biāo)函數(shù)的下界。令λr的初始值設(shè)為2，當(dāng)連續(xù)進(jìn)行5次迭代而未改進(jìn)下界時(shí)，λr減半。通過以下的遞推公式用來確定乘子：

在如下性質(zhì)4中的三種情況下，所用到的拉格朗日乘子在各次迭代中均未改變。因此在更新乘子的過程中，可以不必更新這些乘子。

性質(zhì)4令amin為可以在泊位j上進(jìn)行卸載操作的船所具有的最早到達(dá)時(shí)間，asmin為可以在泊位j上進(jìn)行卸載操作的船所具有的次最早到達(dá)時(shí)間，則在以下三種情況ujmn=0：

（1）對(duì)應(yīng)于被遺留船所占用方格的乘子。

（2）對(duì)應(yīng)于泊位j上每一個(gè) m∈{1，2，…，Qj}，n∈{1，2，…，amin–1}的方格的乘子。

（3）對(duì)應(yīng)于泊位j上每一個(gè)m∈{1，2，…，Qj}，n∈amin，…，asmin–1}的方格的乘子。

證明 根據(jù)ujmn≥0的情況下拉格朗日松弛算法原理，如果泊位j上的方格(m，n)在任何時(shí)刻總是被至多一艘船占用的話，則ujmn=0。由于對(duì)應(yīng)于情況（1）中乘子的方格總是只被一艘遺留原料船占用。情況（2）中乘子對(duì)應(yīng)的方格由于在時(shí)刻n沒有船到達(dá)而不被任何船所占用。而對(duì)于情況（3）中乘子對(duì)應(yīng)的方格，如果可在泊位j上進(jìn)行卸載的船中具有最小到達(dá)時(shí)間的那艘船被安排在該泊位上，則這些方格就被該船占用，否則將不被任何船占用。因此，以上結(jié)論得證。

4 計(jì)算實(shí)驗(yàn)

本文使用50個(gè)實(shí)際問題來測(cè)試?yán)窭嗜账沙谒惴ǖ男阅?。所提出的算法用C++語言編碼，在PC（CPU：Inter Core2 2.93 GHz，內(nèi)存：2 GB）上進(jìn)行性能測(cè)試。

本章使用寶鋼原料管制中心提供的一些實(shí)際停泊計(jì)劃來測(cè)試算法性能。為了與實(shí)際原料碼頭的原料船停泊情況相對(duì)應(yīng)，每艘船的長(zhǎng)度和卸載時(shí)間應(yīng)包含分別為20 m 和1 h的安全水平距離和相鄰兩艘進(jìn)港船的間隔時(shí)間。泊位長(zhǎng)度分別是640 m和400 m。表1顯示了3天計(jì)劃展望期內(nèi)共有15艘進(jìn)港船和3艘遺留船情況下的一系列參數(shù)。

寶鋼原料碼頭的進(jìn)港船是在原料日課作業(yè)計(jì)劃的指導(dǎo)下入港停靠的。該計(jì)劃實(shí)際上是基于滾動(dòng)計(jì)劃展望期的方法制定的，即每天都要由計(jì)劃員來制定一個(gè)3天的原料船停泊計(jì)劃，但只為第一天到港的原料船分配泊位。第二天計(jì)劃員再制定下一個(gè)基于3天計(jì)劃展望期的停泊計(jì)劃，依此循環(huán)往復(fù)。在寶鋼實(shí)際泊位停泊計(jì)劃的最小時(shí)間單位是1 h，因此設(shè)定T為72對(duì)應(yīng)于一個(gè)3天的計(jì)劃展望期。這樣與主原料碼頭和副原料碼頭相對(duì)應(yīng)的泊位-時(shí)間平面分別被分割成64×72和40×72個(gè)方格。每個(gè)泊位-時(shí)間平面內(nèi)的一個(gè)方格所代表的實(shí)際含義是10 m-1 h。本章通過從2011年6月到8月期間的日課作業(yè)計(jì)劃中所挑選的50個(gè)實(shí)例來測(cè)試所提出的拉格朗日松弛算法的性能。船數(shù)從8到15之間取值以便包含不同的碼頭資源占用情況。本章所測(cè)試的拉格朗日松弛算法包括未改進(jìn)算法和使用4個(gè)性質(zhì)進(jìn)行加速的改進(jìn)算法。

表1 （a）15艘進(jìn)港船參數(shù)舉例

表1 （b）3艘遺留船的參數(shù)舉例

對(duì)偶間隙是最常用于評(píng)價(jià)拉格朗日松弛算法性能的重要指標(biāo)，它通?？杀硎緸椋ǎㄉ辖纭陆纾?下界）×100%。由于最優(yōu)解一定處于上界和下界之間，因此對(duì)偶間隙表示了由拉格朗日松弛算法所求得的最終目標(biāo)函數(shù)值偏離最優(yōu)解的程度。當(dāng)算法執(zhí)行500次或者對(duì)偶間隙小于0.005時(shí)，拉格朗日松弛算法停止。

表2給出了所有50個(gè)實(shí)例的結(jié)果。從實(shí)驗(yàn)結(jié)果中可以得出以下結(jié)論：

（1）在3天的計(jì)劃展望期內(nèi)原料船的平均到港數(shù)是11.16。

（2）平均來看，拉格朗日松弛算法求解實(shí)際問題所花費(fèi)的計(jì)算時(shí)間和所求得的對(duì)偶間隙都比較理想。以上50個(gè)例子對(duì)偶間隙的平均值為14.62%。盡管以通常的標(biāo)準(zhǔn)來看，該平均對(duì)偶間隙有些偏大，但是從以拉格朗日松弛算法研究連續(xù)泊位停泊計(jì)劃的實(shí)驗(yàn)結(jié)果來看，本文所求得的對(duì)偶間隙屬于正常范圍。

（3）未改進(jìn)的拉格朗日松弛算法求解50個(gè)實(shí)例所需的運(yùn)行時(shí)間從19.16 s到39.25 s之間不等，而其平均運(yùn)行時(shí)間是26.78 s。而改進(jìn)拉格朗日松弛算法的運(yùn)行時(shí)間則顯著減少，平均降至3.56 s。這表明改進(jìn)拉格朗日松弛算法對(duì)寶鋼實(shí)際停泊計(jì)劃可以在較短的運(yùn)行時(shí)間內(nèi)求得近優(yōu)解。

5 結(jié)論

本文以最小化總權(quán)重服務(wù)時(shí)間為目標(biāo)函數(shù)研究了鋼鐵企業(yè)原料碼頭具有多個(gè)連續(xù)泊位的動(dòng)態(tài)停泊計(jì)劃問題。該問題的特點(diǎn)是有兩個(gè)或兩個(gè)以上連續(xù)泊位且在計(jì)劃開始執(zhí)行時(shí)每一泊位上僅有部分泊位長(zhǎng)度可利用。本文為該問題建立了一個(gè)數(shù)學(xué)模型來充分表述寶鋼實(shí)際停泊計(jì)劃問題的特性。提出了一種改進(jìn)拉格朗日松弛算法來求解該問題，該算法用到了4個(gè)性質(zhì)分別刪除子問題求解、獲得可行解和更新乘子等步驟中的不必要搜索過程從而大幅度地減少算法運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果表明改進(jìn)的拉格朗日松弛算法能在半分鐘內(nèi)求得問題近優(yōu)解。

表2 50個(gè)寶鋼真實(shí)停泊計(jì)劃問題計(jì)算結(jié)果

[1]Park K，Kim K.Berth scheduling for container terminals by using a sub-gradientoptimization technique[J].Journalof the Operational Research Society，2002，53（9）：1054-1062.

[2]Park K，Kim K.A scheduling method for berth and quay cranes[J].OR Spectrum，2003，25（1）：1-23.

[3]Imai A，Sun X，Nishimura E，et al.Berth allocation in a container port：using a continuous location space approach[J]. Transportation Research Part B，2005，39（3）：199-221.

[4]Imai A，Chen H C，Nishimura E，et al.The simultaneous berth and quay crane allocation problem[J].Transportation Research Part E，2008，44（5）：900-920.

[5]Imai A，Nishimura E，Papadimitriou S.The dynamic berth allocation problem for a container port[J].Transportation Research Part B，2001，35（4）：401-417.

[6]Imai A，Nishimura E，Hattori，M，et al.Berth allocation at indented berths for mega-containerships[J].European Journal of Operational Research，2007，179（2）：579-593.

[7]Nishimura E，Imai A，Papadimitriou S.Berth allocation planning in the public berth system by genetic algorithms[J]. European Journal of Operational Research，2001，131（2）：282-292.

[8]Guan Y，Xiao W Q，Cheung R，et al.A multiprocessor task scheduling model for berth allocation：heuristic and worstcase analysis[J].Operations Research Letters，2002，30（5）：343-350.

[9]Chen J，Lee C Y.General multiprocessor task scheduling[J]. Naval Research Logistics，1999，46（1）：57-74.

[10]Manaa A，Chu C B.Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors[J].European Journal of Industrial Engineering，2010，4（3）：265-279.

[11]Lee C Y，Cai X.Scheduling one and two-processor tasks on two parallel processors[J].IIE Transactions，1999，31（5）：445-455.

[12]Guan Y，Cheung R.The berth allocation problem：models and solution methods[J].OR Spectrum，2004，26（1）：75-92.

LIU Yue1,XIE Xie2

1.Department of Software Engineering,Liaoning Information Vocational Technical College,Liaoyang,Liaoning 111000,China
2.Key Laboratory of Manufacturing and Integrated Automation,Shenyang University,Shenyang 110044,China

A dynamic berth planning problem encountered in the iron and steel industry is investigated.The dynamic features reflect that the docks have two or more berths with continuous berth sections and the berth sections on the same berth are not simultaneously available at the planning start time period.This problem is formulated as a 0-1 hybrid mathematical model.An improved Lagrangian relaxation algorithm is presented for the solution in a reasonable running time by introducing four properties to speed up the procedures of solving the sub-problems,updating Lagrangian multipliers and obtaining feasible solutions, respectively.Computational results including 50 real-size problems show that the improved algorithm can reduce more than 80%of the running time of unimproved heuristics.

raw material logistics;berth planning;Lagrangian relaxation

研究鋼鐵企業(yè)原料碼頭動(dòng)態(tài)停泊計(jì)劃問題，其動(dòng)態(tài)特征主要體現(xiàn)在原料船動(dòng)態(tài)到達(dá)并有兩個(gè)或兩個(gè)以上連續(xù)泊位且在停泊計(jì)劃開始執(zhí)行時(shí)每一泊位上僅有部分泊位長(zhǎng)度可利用。針對(duì)這個(gè)問題，建立了一個(gè)數(shù)學(xué)模型并設(shè)計(jì)了改進(jìn)拉格朗日算法在很短的時(shí)間內(nèi)求得了近優(yōu)解。在改進(jìn)算法中使用了所提出的四個(gè)性質(zhì)來分別加速求解子問題、乘子更新和獲得可行解的過程。通過包含50個(gè)實(shí)際規(guī)模問題的算法性能實(shí)驗(yàn)表明改進(jìn)的拉格朗日松弛算法相比未改進(jìn)算法減少了80%的運(yùn)行時(shí)間。

原料物流；停泊計(jì)劃；拉格朗日松弛

A

TP13

10.3778/j.issn.1002-8331.1207-0398

LIU Yue,XIE Xie.Lagrangian relaxation algorithm for dynamic berth planning problem.Computer Engineering and Applications,2013,49（5）：241-247.

劉悅（1979—），女，講師，研究領(lǐng)域?yàn)閺?fù)雜網(wǎng)絡(luò)、智能計(jì)算；謝謝（1981—），女，博士，講師，研究領(lǐng)域?yàn)樯a(chǎn)作業(yè)優(yōu)化管理。E-mail：liaoyangliuyue@163.com

2012-07-25

2012-09-25

1002-8331（2013）05-0241-07

CNKI出版日期：2012-10-23 http://www.cnki.net/kcms/detail/11.2127.TP.20121023.1539.001.html