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

劉 悅，謝 謝

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

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

劉 悅1，謝 謝2

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

1 引言

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

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

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

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

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

2 問題描述

圖2 動態(tài)停泊計劃舉例

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

2.1 問題假設(shè)

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

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

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

（3）每艘進港船的卸載時間依賴于它所停靠的泊位。盡管在同一個泊位上的卸船機卸載能力是相同的，但是不同泊位上所配備的卸船機卸載能力是不同的。因此第三個假設(shè)適用于可以在多個泊位上進行卸載操作的原料船。

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

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

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

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

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

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

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

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

li：船i的長度（包括水平安全距離）。

ai：船i的到達時間。

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

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

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

rjm：泊位j上的長度段m的可利用時間。

決策變量：

ci：船i的離港時間。

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

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

3 拉格朗日松弛

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

3.1 松弛問題的模型

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

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

那么拉格朗日對偶問題為：

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

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

(LRi)Minimize ZLi≡

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

3.2 求解子問題

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

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

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

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

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

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

那么式（16）就等價于：

滿足約束式（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，找到使得下式成立的組合：

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

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

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

性質(zhì)1在拉格朗日松弛算法第一次迭代過程中，對于每艘船i(i∈Ω)其所對應(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的離港時間加1，τhj等于船h在泊位j上的末尾停泊長度段加1，h=1，2，…，g，這里g為泊位j上的遺留船總數(shù)。

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

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

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

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

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

3.3 尋找可行解

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

性質(zhì)3如果任意未被安排泊位的船i可以?？吭诓次籮，則其對應(yīng)的矩形左下端點可占用泊位-時間平面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的離港時間加1，τhj是泊位j上已安排泊位船h的末尾停靠長度段加1，h=1，2，…，g+fj，這里g為泊位j上遺留船總數(shù)，fj為泊位j上所有已安排泊位的可行船總數(shù)。

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

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

在以下啟發(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的船將其按照到達時間的升序排列。

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

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

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

3.4 更新拉格朗日乘子

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

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

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

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

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

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

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

4 計算實驗

本文使用50個實際問題來測試拉格朗日松弛算法的性能。所提出的算法用C++語言編碼，在PC（CPU：Inter Core2 2.93 GHz，內(nèi)存：2 GB）上進行性能測試。

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

原料物流；停泊計劃；拉格朗日松弛

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)域為復(fù)雜網(wǎng)絡(luò)、智能計算；謝謝（1981—），女，博士，講師，研究領(lǐng)域為生產(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