□ 吳嘉楊

一、船舶過(guò)閘問(wèn)題描述

為了提升航道通過(guò)能力，人工制造上游調(diào)節(jié)水庫(kù)，在航道上通常建設(shè)一些水利樞紐，稱為船閘。船舶過(guò)閘問(wèn)題即是給定船閘閘室大小，在待閘區(qū)如何選擇過(guò)閘船舶從而使得待閘區(qū)中的船舶能夠盡快通過(guò)大壩。

在過(guò)閘流程上進(jìn)行分析基礎(chǔ)上，船舶過(guò)閘的方式因排擋方案的不同而不同。以最為常見(jiàn)的最優(yōu)過(guò)閘排擋方案為例，船舶過(guò)閘模型的描述如下:給定船閘閘室寬度為W，長(zhǎng)度為L(zhǎng)，易知 L ＞W(wǎng)，待閘船舶集合 S={S1，S2，L，Sm}，第 i艘船的長(zhǎng)度為li，寬度為wi(此處船舶的長(zhǎng)度l和寬度w均包含了橫縱向安全間隔，下同)，船舶噸位為ti，船舶過(guò)閘變量zi=(1，0)，表示第i艘船是否過(guò)閘。

過(guò)閘模型目標(biāo)為如何選擇過(guò)閘船舶使得本次過(guò)閘的船總噸位或載貨總噸位或利用率為最大值。

在此模型中，一次過(guò)閘選擇的船舶是為最優(yōu)配比、滿足噸位最大的條件，待閘區(qū)中的某一艘船可能永遠(yuǎn)無(wú)法過(guò)閘，由此，可以以另一種思路即假設(shè)我們事先知曉了很長(zhǎng)時(shí)間段內(nèi)到來(lái)的所有船舶S={S1，S2，L，Sm}，并知曉其中任意一艘船舶Si的長(zhǎng)度為li，寬度為wi，船舶噸位為ti。

過(guò)閘模型目標(biāo)為如何選擇過(guò)閘船舶使得在所有船舶都能過(guò)閘的情況下，所使用的閘次最少。

二、船舶過(guò)閘模型建立

(一)約束條件一:閘室界限約束。一般船閘閘室長(zhǎng)度比寬度數(shù)值要大，故以船閘閘室左下頂點(diǎn)為原點(diǎn)，長(zhǎng)寬為兩條數(shù)軸建立平面直角坐標(biāo)系，閘室區(qū)域可表示為RW×L，則第i艘船的左下頂點(diǎn)坐標(biāo)在閘室坐標(biāo)系中表示為(xi，yi)，在閘室內(nèi)所占區(qū)域?yàn)镽wi×li。船舶停靠在閘室內(nèi)必須滿足船舶的四個(gè)數(shù)學(xué)頂點(diǎn)必須在閘室內(nèi)，即:0≤xi≤xi+ziwi≤W且0≤yi≤yi+zili≤L。

(二)約束條件二:閘室界限約束。第i艘船舶內(nèi)任意一點(diǎn)在閘室坐標(biāo)系中可表示為(ui，vi)∈Rwi×li，易知對(duì)于每一艘船舶 li＞ wi，故 xi＜ ui＜ xi+ziwi且 yi＜ vi＜ yi+zili。將閘室內(nèi)的每一艘船舶投影到坐標(biāo)軸上，船舶之間的相對(duì)關(guān)系位置可以分為五種情況討論，分別為第j艘船舶在第i艘船舶上方，第j艘船舶在第i艘船舶下方，第j艘船舶在第i艘船舶左方，第j艘船舶與第i艘船舶重疊。

只要排除最后一種情況，則滿足船舶兩兩不重疊條件。即:(2xj-2xi+zjwj-ziwi)2≥(zjwj+ziwi)或(2yj-2yi+zjlj-zjlj)2≥(zjlj+zili)2。

(三)約束條件三:閘室內(nèi)船舶排列列數(shù)約束。通常為了使船舶停泊在閘室內(nèi)更加安全，只允許放下兩列船，則可以將船舶的兩邊錨定到閘室的兩條邊上，約束條件為xi=0 or xi+ziwi=W。

由以上約束條件根據(jù)不同的目標(biāo)函數(shù)，建立模型。

模型一:目標(biāo)函數(shù)為總噸位最重。

為求得最優(yōu)配比模型，本目標(biāo)函數(shù)只考慮船舶總噸位。故過(guò)閘最優(yōu)配比方案過(guò)閘模型為。Z=max∑ziti

模型二:目標(biāo)函數(shù)為總過(guò)閘次數(shù)最少。

對(duì)于另一種過(guò)閘模型，由于船型分布是離散的，可以根據(jù)船型，列出所需要的所有過(guò)閘模式，設(shè)共有o種，即最終需要過(guò)閘的次數(shù)為o，建立二維矩陣Bmo，對(duì)矩陣中任一元素bik(i=1，2，L，m k=1，2，L，o)的意義為第 i艘船舶是否進(jìn)入第k種過(guò)閘模式，則bik=1或0。

易知任意一艘船舶至少且只能進(jìn)入一種過(guò)閘模式，即∑bik=1(i=1，2，L，m)。

而對(duì)任意一個(gè)過(guò)閘模式，依然需要滿足船舶兩兩不重疊，且船體在閘室區(qū)域內(nèi)的條件，每一個(gè)過(guò)閘模式中，最多只能排兩列船舶，則此模型為:min o

兩種模型為船舶過(guò)閘問(wèn)題的兩種思考方向，可視為對(duì)偶模型，且均為NP-Hard模型，雖然最優(yōu)解一定存在，但在二項(xiàng)式時(shí)間內(nèi)無(wú)法找出最優(yōu)解，所以模型需要用另外的方法解出，相較于二維裝箱模型，船舶過(guò)閘的模型與其類似，但船舶過(guò)閘模型的目標(biāo)與二維裝箱模型有一定的差異，即過(guò)閘目標(biāo)中加入了船舶價(jià)值系數(shù)，即船舶噸位;相較于背包模型，也有一定差異，即船舶過(guò)閘模型考慮了每一艘船的擺放位置。故本次研究中假設(shè)所有設(shè)計(jì)船型的寬度加上橫向安全距離后都不大于閘室寬度的一半長(zhǎng)，針對(duì)模型一，兩列船舶排列由于互不侵占，可以對(duì)每一列進(jìn)行單獨(dú)計(jì)算，由此可以將這種模型轉(zhuǎn)化為背包模型進(jìn)行求解;針對(duì)模型二，船舶過(guò)閘模式不再是二維過(guò)閘模式，而是一維過(guò)閘模式，對(duì)模式的窮舉則可以采用一維切割的窮舉法列舉。

三、算法介紹

(一)背包問(wèn)題算法介紹。由于閘室寬度在基礎(chǔ)資料中已經(jīng)給定為定值，且此定值滿足在任何情況下都可以容納兩艘任意型號(hào)船舶并排排列，而閘室內(nèi)因?yàn)榘踩紤]最多容納兩列船舶過(guò)閘，因此可以去掉原約束條件中的所有寬度約束，原問(wèn)題簡(jiǎn)化為:Z=max∑ziti∑zili≤L即為0-1背包模型。

如此，將每一艘待閘船舶看作待入背包的物品，閘室看作背包，則船舶過(guò)閘問(wèn)題可以用背包問(wèn)題來(lái)進(jìn)行模擬。在上述對(duì)背包問(wèn)題的解法當(dāng)中，由于閘室長(zhǎng)度與待閘船舶的數(shù)量均有限制，故可以采用動(dòng)態(tài)規(guī)劃法精確求解。

將所有待閘區(qū)n艘船舶按序排列(S1，S2，L，Sn)，則每一艘船舶Si的長(zhǎng)度為li，載重噸位為ti，過(guò)閘系數(shù)為zi。設(shè)閘室長(zhǎng)度為L(zhǎng)。建立矩陣An×L，Aij的意義為將船舶序列前i艘船放入長(zhǎng)為j的閘室當(dāng)中的最大過(guò)閘重量∑zsts，cs=0，1。

對(duì)任意第i艘船來(lái)說(shuō)，此次過(guò)閘只有兩種情況即通過(guò)或不通過(guò)，若通過(guò)則此次過(guò)閘問(wèn)題可轉(zhuǎn)化為求前i-1艘船放入長(zhǎng)為j-li的閘室當(dāng)中的最大過(guò)閘重量。即Aij=Ai-1，j-li(zi=1)。

若第i艘船此次過(guò)閘不通過(guò)，則問(wèn)題可轉(zhuǎn)化為求前i-1艘船放入長(zhǎng)為j的閘室當(dāng)中的最大過(guò)閘重量。即Aij=Ai-1，j(zi=0)。

而此船本次過(guò)閘是否通過(guò)則取決于Ai-1，j和Ai-1，j-li+wi的大小，若Ai-1，j-li+wi大，則取此船;否則不取此船。

由此計(jì)算出的An×L矩陣后，再由后向前查找根據(jù)Aij與Ai-1，j是否相等來(lái)確定此船是否通過(guò)船閘。最后得到本次過(guò)閘噸位∑ziwi。

再根據(jù)已經(jīng)確定的一次過(guò)閘時(shí)間，利用一定的概率分布條件，確定在此時(shí)間內(nèi)到達(dá)船舶的噸位級(jí)別加入到本次剩余的船舶序列中，為下一次背包算法循環(huán)提供參數(shù)。

(二)線性規(guī)劃算法介紹。在船隊(duì)過(guò)閘問(wèn)題中，由于船型組合及噸位已在基礎(chǔ)資料中給定，要求得相對(duì)確定的閘室有效面積的最大一次過(guò)閘平均噸位，我們可以進(jìn)行逆向思維，即假定有一定數(shù)量(數(shù)量較大)的待閘船舶，我們需要求得如何以最少閘次將所有船舶輸送過(guò)壩，用所有待閘船舶的總噸位/最少需求次數(shù)，最終得到最大一次過(guò)閘平均噸位。即G=∑g/最少過(guò)閘次數(shù)。

于是船舶過(guò)閘問(wèn)題就可以轉(zhuǎn)化為一個(gè)二維切割模型，又在基礎(chǔ)資料中已經(jīng)論證船閘寬度為34 m，根據(jù)代表船型的寬度取值范圍我們知道，閘室內(nèi)一定能夠停泊兩列船舶，且船舶停靠方向與閘室長(zhǎng)邊水平。由此我們可以只計(jì)算半寬船閘內(nèi)的船舶排列方式，將二維切割模型轉(zhuǎn)化為一維切割模型。

參考上文中對(duì)約束條件的簡(jiǎn)化，易知原模型可以簡(jiǎn)化為線性規(guī)劃模型。

對(duì)于船舶過(guò)閘問(wèn)題，設(shè)計(jì)代表船型數(shù)量有限，故可以采用窮舉的方式確定船舶過(guò)閘模式。

在閘室的某一特定長(zhǎng)度(L)下，取代表船型中最短船舶長(zhǎng)度(Wmin)，則此半寬船閘的最大船舶容納數(shù)(K)由下式求得:K=L/Wmin

定義一種新的組合運(yùn)算方法:F(m，n)。意義為在a1，a2，a3，L，amm種數(shù)量充分的物體中，取出n個(gè)物體的不同取法的數(shù)量。在船舶過(guò)閘問(wèn)題中，由于絕大部分方案的過(guò)閘艘次小于最大船舶容納數(shù)(K)，所以既有船閘類型數(shù)量確定的條件下，我們需要再加入一類船舶，此類船舶長(zhǎng)度為0，是過(guò)閘船舶數(shù)量與最大船舶容納數(shù)(K)相等。設(shè)入閘船舶類型數(shù)量為N，則半寬船閘過(guò)閘船舶全組合數(shù)量為F(N，K)。

易知:F(1，K)=1，F(xiàn)(N，1)=N，可以通過(guò)以下方法建立矩陣遞歸算出此半寬船閘過(guò)閘船舶組合方式的數(shù)量。F(N，K)=F(N，K-1)+F(N-1，K)

利用計(jì)算機(jī)窮舉出所有半寬船閘過(guò)閘船舶組合方式后，再遍歷每一種方式，舍棄不可用組合方式。剩下的組合方式F有效(N，K)即是線性規(guī)劃模型中的約束條件。建立線性規(guī)劃模型對(duì)原問(wèn)題進(jìn)行求解。

［1］張瑋，廖鵬，粱應(yīng)辰，宋德星．船閘通過(guò)能力計(jì)算中的若干問(wèn)題研究［J］．武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版)，2005

［2］王娜．背包問(wèn)題的研究與算法設(shè)計(jì)［D］．昆明理工大學(xué)，2012

［3］田大肥．二維裝箱問(wèn)題的遺傳算法求解［J］．艦船電子工程，2014