□ 吳嘉楊

一、船舶過閘問題描述

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

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

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

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

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

二、船舶過閘模型建立

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

(二)約束條件二:閘室界限約束。第i艘船舶內(nèi)任意一點在閘室坐標系中可表示為(ui，vi)∈Rwi×li，易知對于每一艘船舶 li＞ wi，故 xi＜ ui＜ xi+ziwi且 yi＜ vi＜ yi+zili。將閘室內(nèi)的每一艘船舶投影到坐標軸上，船舶之間的相對關系位置可以分為五種情況討論，分別為第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ù)不同的目標函數(shù)，建立模型。

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

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

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

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

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

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

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

三、算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

［1］張瑋，廖鵬，粱應辰，宋德星．船閘通過能力計算中的若干問題研究［J］．武漢理工大學學報(交通科學與工程版)，2005

［2］王娜．背包問題的研究與算法設計［D］．昆明理工大學，2012

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