大型水運(yùn)樞紐船舶閘室連續(xù)排擋模型及算法研究

陳登峰 李一博 汪磊 姚紅云 楊俊毅

DOI：10.3976/j.issn.1002-4026.20230069

收稿日期：2023-04-20

基金項(xiàng)目：云南交投科研項(xiàng)目（YCIC-YF-2021-12）；重慶市教育委員會(huì)青年項(xiàng)目（KJQN202100715）；重慶交通大學(xué)研究生科研創(chuàng)新項(xiàng)目（2022S0035）

作者簡(jiǎn)介：陳登峰（1990—），男，博士研究生，工程師，研究方向?yàn)楣芳八愤\(yùn)輸。E-mail：1184361775@qq.com

*通信作者，李一博（1999—），男，碩士研究生，研究方向?yàn)楣芳八愤\(yùn)輸。Tel：19936080200， E-mail：LiybJacob@yeah.net

摘要：為提高內(nèi)河通航設(shè)施船舶通航效率，提高通航設(shè)施工作能力，提出一種可以求解考慮船舶順序入閘和不考慮船舶順序入閘兩種情況的船舶閘室連續(xù)排擋模型和算法。利用二維裝箱問題模型建立船舶閘室連續(xù)排擋模型，采用貪婪策略思想，提出船舶閘室連續(xù)排擋模型求解算法。根據(jù)百色樞紐工程生成仿真到閘船舶船型數(shù)據(jù)，用算法進(jìn)行閘室排擋計(jì)算。結(jié)果表明，在隨機(jī)生成90艘船舶的情況下，考慮船舶到閘順序的排擋結(jié)果需要使用47個(gè)閘次，閘次平均占用率為76.424%，不考慮船舶到閘順序的排擋結(jié)果需要使用45個(gè)閘次，閘次平均占用率為76.821%，模型和算法能夠?qū)Σ煌闆r下船舶閘室進(jìn)行有效連續(xù)排擋。

關(guān)鍵詞：內(nèi)河航運(yùn)；船舶排擋；二維裝箱；貪婪策略

中圖分類號(hào)：U641.7??? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：1002-4026（2024）03-0121-10

開放科學(xué)（資源服務(wù)）標(biāo)志碼（OSID）：

Continuous gear shifting model and algorithm of ship lock chambers

in a large water-transport hub

CHEN Dengfeng1，2，3，LI Yibo2*，WANG Lei3，YAO Hongyun2，YANG Junyi3

（1. Yunnan Highway Engineering Supervision and Consultancy Co.， Ltd.， Kunming 650021，China;

2. College of Traffic &Transportation，Chongqing Jiaotong University，Chongqing 400074，China;

3. Bose Hub General Aviation Investment Co.， Ltd.，Baise 533000，China）

Abstract∶To enhance the navigation efficiency of ships in inland waterway navigation facilities and increase their operational capacity， a continuous gear shifting model and algorithm for ship lock chambers are proposed. This model comprises two scenarios： considering and not considering the sequence of ships entering the lock . First， a two-dimensional packing problem model was employed to establish a continuous gear shifting model for ship lock chambers. Then， an algorithm for solving the aforementioned continuous gear shifting model based on a greedy strategy was proposed. Finally， simulated ship data for vessels arriving at the lock was generated based on the Baise Junction Project. The proposed algorithm was used to calculate the lock chamber gear arrangement. Results indicate that， in the case of randomly generated data for 90 ships， 47 lock cycles were required for the gear arrangement considering the ship arrival sequence， with an average occupancy rate of 76.424%. However， only 45 locks were needed for the gear arrangement when the ship arrival sequence was not considered， with an average occupancy rate of 76.821%. The proposed model and algorithm can effectively shift gears continuously in the ship lock chamber under various conditions.

Key words∶inland water transport；ship gear shifting；two-dimensional packing; greedy strategy

在內(nèi)河航運(yùn)中，船舶一般利用通航設(shè)施克服水位落差，常見的通航設(shè)施包括船閘、升船機(jī)以及結(jié)合兩種通航水工建筑物的“船閘+升船機(jī)”復(fù)合通航設(shè)施。通航設(shè)施的工作效率影響航道的暢通和高效，船舶在通過通航設(shè)施時(shí)，需要進(jìn)入閘室，閘室的利用率和使用數(shù)量是影響通航設(shè)施工作效率的重要因素之一［1］。為優(yōu)化內(nèi)河水運(yùn)樞紐通航設(shè)施通航效率，必須對(duì)船舶閘室分配問題進(jìn)行分析，降低船舶在通航時(shí)的閘室使用數(shù)量，最大化閘室利用率。

船舶閘室排擋問題是一個(gè)復(fù)雜的組合優(yōu)化問題，在國(guó)內(nèi)外學(xué)者中得到了廣泛的關(guān)注與研究。近年來，涉及船舶閘室分配的研究主要集中在傳統(tǒng)算法、深度學(xué)習(xí)、多目標(biāo)優(yōu)化、模擬仿真等多個(gè)方面［2-4］。傳統(tǒng)算法研究包括貪心算法、動(dòng)態(tài)規(guī)劃算法、遺傳算法［5］等，這些算法通過對(duì)船舶的數(shù)量、尺寸、航行時(shí)間等因素進(jìn)行考慮，制定出不同的閘室分配方案［6］。近年來，深度學(xué)習(xí)技術(shù)的發(fā)展為船舶閘室分配問題的研究帶來了新的思路。利用神經(jīng)網(wǎng)絡(luò)等深度學(xué)習(xí)技術(shù)［7-10］，可以從大量的歷史數(shù)據(jù)中提取規(guī)律，從而制定出更為準(zhǔn)確的閘室分配方案。目前船舶排擋方法大多針對(duì)單一閘室內(nèi)的船舶排擋進(jìn)行求解，由于閘室內(nèi)可放置船舶較少，大量研究采用智能算法進(jìn)行求解，浪費(fèi)大量算力，且求解不穩(wěn)定，不適用于工程應(yīng)用。因此，本文提出一種可以應(yīng)用于工程領(lǐng)域，進(jìn)行連續(xù)求解的船舶閘室連續(xù)排擋模型。

本文首先利用二維裝箱模型［11］建立船舶閘室連續(xù)排擋模型，隨后采用貪婪策略分別建立考慮船舶到閘順序的閘室排擋算法和不考慮船舶到閘順序的閘室排擋算法［12］。最后，以百色樞紐工程為例，隨機(jī)生成到閘船舶船型，對(duì)模型及算法進(jìn)行驗(yàn)證。

1? 船舶閘室連續(xù)排擋問題

船舶閘室分配問題是指在船舶通過通航設(shè)施時(shí)，通過調(diào)整船舶在閘室內(nèi)擺放的位置，達(dá)到通航設(shè)施最優(yōu)通航效率［13］。不合理的閘室分配會(huì)導(dǎo)致等待時(shí)間過長(zhǎng)、航運(yùn)效率低下等問題。在建立閘室連續(xù)排擋問題模型時(shí)，需要定義閘室信息和船舶信息。

將第n個(gè)閘室船舶信息定義為Bn，Bn=W，H，n，其中W和H表示閘室的寬度和長(zhǎng)度，一般為固定數(shù)值。在船舶信息定義中，用ai表示第i艘船舶ai=hi，wi，i，其中hi和wi表示船舶包含安全距離在內(nèi)的寬度和長(zhǎng)度，船舶之間安全距離應(yīng)根據(jù)相關(guān)規(guī)范標(biāo)準(zhǔn)確定，至少不小于船舶長(zhǎng)度或?qū)挾鹊?0%，船舶申報(bào)到達(dá)的船型信息，根據(jù)優(yōu)先規(guī)則排列后記為A=a1，a2，…，ai。

船舶在通航設(shè)施閘室進(jìn)行排擋時(shí)，需要遵守船頭在前的規(guī)定，在閘室內(nèi)時(shí)不能進(jìn)行180°反轉(zhuǎn)或90°轉(zhuǎn)置。以船舶自左向右通行為例，船舶從閘室左側(cè)進(jìn)入，右側(cè)駛出，通航設(shè)施中船舶閘室排擋示意見圖1。

如圖1所示，船舶a1、a2在即將進(jìn)入船閘Bn前進(jìn)行申請(qǐng)，通過審核后，在船閘閘室內(nèi)進(jìn)行排列。將第n個(gè)閘次中第j艘船舶記為cn，j=hn，j，wn，j，n，j，其中wn，j和hn，j分別代表該船的寬和長(zhǎng)。第n閘次通過船舶后，以預(yù)約調(diào)度時(shí)段內(nèi)通航設(shè)施閘室利用率F最大為目標(biāo)，船舶排擋后平均閘室利用率見式（1）：

max F=∑n∑jhn，jwn，jNWH? ，（1）

其中，N表示閘次數(shù)量，當(dāng)每個(gè)閘室的利用率達(dá)到最大時(shí)，可使需要使用的總閘室數(shù)量最少。因此，可以將問題轉(zhuǎn)化為求解二維裝箱問題。

2? 船舶閘室連續(xù)排擋問題模型

2.1? 二維裝箱問題模型

船舶閘室排擋問題類似于二維裝箱［14］問題，二維裝箱問題是指將一組二維矩形物體裝入最少數(shù)量的二維箱子。二維裝箱問題是NP（non-deterministic polynomially）難問題，即沒有已知的多項(xiàng)式時(shí)間算法可以解決它。因此，通常使用啟發(fā)式算法、貪心算法、分支定界算法等來解決這個(gè)問題。二維裝箱問題在生產(chǎn)和物流領(lǐng)域有廣泛的應(yīng)用，例如貨物裝箱、板材下料、紙張裁剪等。

通航設(shè)施閘室分配問題類似于二維裝箱問題的2BP（2D bin packing）問題。在2BP問題中，待裝物體可以是規(guī)則的幾何圖形，也可以是不規(guī)則的多邊形。該問題的目標(biāo)是將一組大小不等的矩形物體排列在若干大小相等的矩形箱子中，以最小化使用的箱子數(shù)量為目標(biāo)。物體的擺放需滿足物體不超出箱子邊界，且物體邊緣需平行于箱子邊緣；箱中物體兩兩互不重疊兩個(gè)約束條件。二維矩形裝箱問題示意圖見圖2。

如上圖所示，二維裝箱問題的2BP問題中，aB，i表示第i個(gè)矩形物品，aB，i=wB，i，hB，i，i，其中wB，i和hB，i分別表示矩形物體aB，i的長(zhǎng)和寬。箱子寬度和高度定義為WB和HB將放入第n箱子的第j矩形物體的左下角坐標(biāo)表示為xL，n，j，yL，n，j，右上角表示為xR，n，j，yR，n，j，目標(biāo)函數(shù)為滿足所有物體填裝的最少使用箱數(shù)min F=n。

通過上述規(guī)則和符號(hào)定義，對(duì)2BP問題建立約束，以箱子左下角為原點(diǎn)的笛卡爾坐標(biāo)系，箱子的右下角、左上角、右上角坐標(biāo)分別表示為WB，0、0，HB、WB，HB，對(duì)2BP問題進(jìn)行建立滿足要求的約束函數(shù)，如下：

0≤xL，n，j≤WB|HB， 0≤xR，n，j≤WB|HB，（2）

0≤yL，n，j≤WB|HB， 0≤yR，n，j≤WB|HB，（3）

xR，n，j－xL，n，j，yR，n，j－yL，n，j∈WB，HB，HB，WB，（4）

xL，n，m－xR，n，j， xL，n，m－xR，n，i， yL，n，m－yR，n，j， yL，n，j－yR，n，m≥0 ，（5）

其中，式（2）、式（3）表示矩形物體不能超出箱子邊界；式（4）表示矩形物體應(yīng)與箱子正交，即矩形的4條邊都與箱子平行；xL，n，m，yL，n，m表示箱子中已存在的矩形物體m左下角坐標(biāo)，式（5）表示放入箱子的矩形物體不能與原箱中物體重疊。

2.2? 船舶閘室排擋問題模型

船舶閘室排擋模型是以二維裝箱模型為基礎(chǔ)，在二維裝箱模型的描述中，模型中需要放置進(jìn)箱子中的矩形物體可以轉(zhuǎn)置，矩形物體進(jìn)入箱子的順序可以任意打亂，對(duì)于船舶在閘室中的排擋模型而言，船舶通航在確定優(yōu)先級(jí)之后應(yīng)該服從FCFS（first come first serve）規(guī)則，但是服從FCFS規(guī)則的船舶可能會(huì)降低閘室利用率。船舶進(jìn)入通航設(shè)施的目的是通過通航設(shè)施，所以，在進(jìn)入通航設(shè)施閘室時(shí)，只能船頭先進(jìn)入閘室，不能進(jìn)行任意反轉(zhuǎn)。

以二維裝箱問題模型為基礎(chǔ)進(jìn)行改進(jìn)，建立以二維裝箱模型為基礎(chǔ)的船舶閘室排擋問題模型，相對(duì)于二維裝箱問題，船舶閘室排擋問題具有以下特點(diǎn)：

（1）船舶在閘室內(nèi)無法進(jìn)行180°反轉(zhuǎn)和90°轉(zhuǎn)置排列，在模型中僅表現(xiàn)為無法進(jìn)行90°轉(zhuǎn)置；

（2）在預(yù)約通航階段可通行閘次確定，船舶在當(dāng)前調(diào)度周期內(nèi)無法排擋時(shí)，需要安排進(jìn)下一個(gè)調(diào)度周期進(jìn)行排擋；

（3）船舶排擋位置確定后，需要生成船舶進(jìn)入閘室方案。

以二維裝箱問題模型為基礎(chǔ)，對(duì)船舶閘室以左下角為基礎(chǔ)，建立笛卡爾坐標(biāo)系。船舶閘室排擋模型見式（6）～（9）：

0≤xn，j≤W，0≤xn，j+wn，j≤W ，（6）

0≤yn，j≤H，0≤yn，j+hn，j≤H ，（7）

wn，j，hn，j∈W，H ，（8）

xn，k－xn，j，xn，k+wn，k－xn，j+wn，k，yn，k－yn，j，yn，k+hn，k－yn，j+hn，k≥0，k>j>0 ，（9）

式中，xn，j，yn，j表示在閘室n中第j艘船舶的左下角坐標(biāo)；wn，j和hn，j分別表示在閘室n中第j艘船舶的長(zhǎng)度和寬度；xn，k，yn，k表示閘室中已有的第k艘船舶左下角的坐標(biāo)。式（6）～（7）表示船舶不能超出閘室邊界；式（8）表示船舶長(zhǎng)和寬只能平行于閘室的長(zhǎng)和寬；將閘室中已有船舶長(zhǎng)和寬分別記為wn，k和hn，k，式（9）表示新置入船舶和閘室內(nèi)已有的船舶不能重疊。

3? 船舶排擋模型求解算法及流程

3.1? 船舶排擋模型求解

二維裝箱問題是指在給定一定數(shù)量的物品和若干個(gè)尺寸相同的箱子的情況下，如何將所有物品裝入盡可能少的箱子中。常用的固定型二維裝箱問題求解算法包括Best Fit算法、First Fit算法，二者都是經(jīng)典的啟發(fā)式算法，其思想都是在每個(gè)箱子中盡量放入更多的物品，從而減少箱子的數(shù)量。Best Fit算法將所有待裝箱物品按照寬度從大到小排序，然后依次將每個(gè)物品放入當(dāng)前剩余空間最小的那個(gè)箱子中；而First Fit算法則是將所有待裝箱物品按照寬度從大到小排序，然后依次將每個(gè)物品放入第一個(gè)可以容納它的箱子中，如果沒有箱子可以容納該物品，則新開一個(gè)箱子。

船舶閘室排擋問題模型和二維裝箱模型存在差異，為求解船舶閘室排擋問題，在進(jìn)行船舶閘室排擋模型求解時(shí)，以貪婪策略思想為基礎(chǔ)。貪婪策略是一種常見的算法思想，具體是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。對(duì)于船舶閘室排擋模型而言，不從整體最優(yōu)上加以考慮，雖然在某種意義上可能會(huì)得到問題的局部最優(yōu)解，但是由于閘次排擋并無后效性，即當(dāng)前模型的狀態(tài)與之前或之后的模型狀態(tài)無關(guān)，只與當(dāng)前狀態(tài)有關(guān)，所以貪婪策略可以適用。

在船舶閘室排擋模型中，將可調(diào)度優(yōu)化時(shí)段內(nèi)的每一個(gè)閘次船舶位置和船舶數(shù)量的求解當(dāng)作子問題，進(jìn)行逐次求解。當(dāng)所有的閘次中船舶數(shù)量均為最大可置入量，且所有船舶均被排擋時(shí)，子問題的結(jié)果組合起來即為所有預(yù)約船舶的通航排擋閘次結(jié)果，此時(shí)閘次的使用量可以認(rèn)為是最少的。

以船舶通過通航設(shè)施以由左向右的方式通航，排擋過程可以分為3個(gè)步驟：

（1）將需要船舶由左上角向右，向下放入閘室內(nèi)，在放入船舶之后，將剩余閘室空間分為兩個(gè)空間碎片，由于一般通航設(shè)施閘室橫向長(zhǎng)度遠(yuǎn)大于縱向，在船舶閘室排擋中采取縱向分割方式，將未利用的閘室空間分為兩個(gè)空間碎片，閘室內(nèi)沒有其他船舶時(shí)的排擋空間碎片劃分方式見圖3。如圖3所示，當(dāng)?shù)谝凰掖癮1進(jìn)入通航設(shè)施閘室B后，由于閘室將其放入通航設(shè)施閘室的右下角，對(duì)空間縱向分割，為空間碎片1和空間碎片2，此時(shí)空間碎片1面積大于空間碎片2面積。

（2）當(dāng)閘室中已經(jīng)存在船舶時(shí)，閘室空間會(huì)存在多個(gè)被縱向切割的空間碎片，將空間碎片由小到大依次與當(dāng)前需要排擋船舶的大小進(jìn)行對(duì)比，當(dāng)出現(xiàn)第一個(gè)可放置當(dāng)前船舶空間時(shí)，將船舶由空間碎片左上角向右、向下放入閘室中，若所有空間碎片均無法放置當(dāng)前需要排擋船舶時(shí)，當(dāng)前閘次船舶排擋結(jié)束。閘室存在船舶時(shí)當(dāng)前船舶排擋方法見圖4。如圖4所示，船舶a1的空間碎片劃分完成后，當(dāng)船舶a2所需占用的面積小于空間碎片2大小時(shí)，將船舶a2放置入空間碎片2中，若船舶a2所需閘室空間占用面積大于空間碎片2且小于空間碎片1時(shí)，將船舶a2置入空間碎片1中。當(dāng)船舶a2進(jìn)入閘室后，需要重新進(jìn)行空間碎片的劃分，若閘室空間存量大于最小船舶長(zhǎng)度，依舊進(jìn)行縱向劃分，如圖4（a）所示。若不大于最小船舶長(zhǎng)度，則進(jìn)行橫向分割，如圖4（b）所示。

（3）單一閘次裝箱結(jié)束后，將閘次排擋后的船舶數(shù)量存儲(chǔ)，隨后對(duì)下一個(gè)閘次進(jìn)行裝箱，依次計(jì)算所需數(shù)據(jù)，依次存儲(chǔ)。在進(jìn)行計(jì)算時(shí)，對(duì)船舶閘室建立二維笛卡爾坐標(biāo)系，按照改進(jìn)二維裝箱模型的船舶閘室排擋模型建立約束。模型的求解主要包括第一艘船舶入閘、空間碎片劃分和船舶空間碎片比較三個(gè)部分。

模型的計(jì)算如下：當(dāng)前閘次內(nèi)第1艘船舶ai入閘時(shí)，船舶的長(zhǎng)度為hi，寬度為wi，閘室的長(zhǎng)寬記為W，H，令x1，k+w1，k=W，h1，k=0，將船舶放入閘室右下角，船舶左下角的坐標(biāo)為W－w1，k，0。

空間碎片以縱向方式劃分，存在的兩個(gè)空間碎片，將第m個(gè)空間碎片位置表示為wL，m，k，hL，m，k，wR，m，k，hR，m，k，分別表示為空間碎片的左下角坐標(biāo)和右上角坐標(biāo)。如當(dāng)?shù)?艘船舶放置后，存在的兩個(gè)空間碎片分別為0，0W－w1，k，H和W－w1，k，h1，kW，H，后續(xù)待閘船舶依照此規(guī)則再依次對(duì)每個(gè)船舶進(jìn)行位置計(jì)算，當(dāng)一個(gè)閘次內(nèi)船舶數(shù)量充足，無法放入后續(xù)待閘船舶時(shí)，進(jìn)入下一個(gè)閘次的船舶拍檔計(jì)算。

3.2? 船舶排擋模型求解

采用上文求解方法，在進(jìn)行考慮船舶順序過閘時(shí)船舶閘室連續(xù)排擋模型中，將船舶按照到達(dá)次序以FCFS的規(guī)則進(jìn)行排擋處理。通過船舶入閘信息A=a1，a2，…，ai得到預(yù)約通航船舶的入閘順序和每艘船舶的安全距離。

根據(jù)上述模型及求解方法，考慮船舶順序過閘船舶連續(xù)閘次排擋模型求解流程見圖5。

如圖5所示，在進(jìn)行船舶排擋之前，首先對(duì)需要排擋船舶的優(yōu)先級(jí)進(jìn)行確認(rèn)，得到船舶入閘實(shí)際順序，隨后依照安全距離計(jì)算方法對(duì)船舶進(jìn)行安全距離計(jì)算，在本文的仿真中，這個(gè)過程不進(jìn)行體現(xiàn)。

得到船舶實(shí)際在閘室中所需占用的空間大小以及入閘順序后，當(dāng)閘室中無其他船舶存在時(shí)，將待閘船舶按照排擋規(guī)則置入空閘室中，隨后進(jìn)行空間碎片劃分，將剩余空間縱向劃分為兩個(gè)空間碎片，與下一艘待閘船舶所需占用空間大小進(jìn)行對(duì)比，確認(rèn)船舶可置入的位置，并劃分新的空間碎片，除第一艘船舶以外，其他船舶置入后均進(jìn)行空間碎片劃分，若所有空間碎片無法滿足下一艘待閘船舶入閘時(shí)，即使后續(xù)船舶存在可以裝入當(dāng)前閘室船舶，不考慮將其排擋入當(dāng)前閘次，當(dāng)前閘次船舶排擋結(jié)束，進(jìn)行下一個(gè)閘次排擋。所有閘次排擋結(jié)束后，輸出所有閘室排擋信息和船舶在閘室內(nèi)排擋位置。

3.3? 不考慮船舶順序過閘連續(xù)排擋算法

不考慮船舶順序過閘的排擋方法是指當(dāng)提前獲得所有船舶到閘信息A=a1，a2，…，ai后，當(dāng)閘室內(nèi)沒有船舶時(shí)，將待閘中編號(hào)最小的船舶按照排擋規(guī)則放置入閘室內(nèi)，隨后按編號(hào)順序，將后續(xù)所有船舶與閘室中存在的空間碎片進(jìn)行比較，若存在空間碎片可以放置，則在空間碎片中放入該船舶，若無法放置，則依次判斷下一艘船舶是否可放入閘室內(nèi)。

不考慮船舶過閘順序的船舶連續(xù)排擋算法求解流程見圖6。

如上圖所示，不考慮船舶順序通航的船舶閘室排擋算法中，當(dāng)下一艘船舶無法在當(dāng)前閘室中進(jìn)行排擋后，會(huì)依次對(duì)后續(xù)船舶進(jìn)行排擋處理，直到所有船舶計(jì)算完畢，在當(dāng)前閘室內(nèi)放入所有可過閘船舶后，才會(huì)進(jìn)行下一個(gè)閘次的船舶排擋計(jì)算。其他排擋步驟與考慮船舶順序通航的連續(xù)排擋算法相同。

4? 仿真實(shí)驗(yàn)

為驗(yàn)證本文算法，采用百色樞紐通航工程數(shù)據(jù)進(jìn)行計(jì)算，百色樞紐通航工程通航設(shè)施由25 m水頭差的省水船閘、長(zhǎng)度約4 km的中間渠道、提升高度88.8 m的全平衡鋼絲繩卷揚(yáng)垂直升船機(jī)組成，線路全長(zhǎng)約4 384 m。閘室效尺寸為111.0 m×12.0 m×4.7 m（長(zhǎng)×寬×水深），設(shè)計(jì)年單向通過能力為6.02×106 t。百色樞紐通航工程建成后構(gòu)想見圖7。

由于百色樞紐通航工程尚未完工，隨機(jī)船舶信息進(jìn)行排擋，百色樞紐通航工程中預(yù)計(jì)通航船舶的信息及各種船型比例見表1。

由于在預(yù)期船舶閘室占比中，小型船舶被劃分入大中型船舶中，對(duì)此進(jìn)行修正，并且考慮到未來可能會(huì)存在執(zhí)法船等小型船舶通過通航設(shè)施，增加其他小型船舶信息，將其他小型船舶設(shè)置的占比為總到閘船舶數(shù)量的15%修正后船型信息及比例見表2。

按照百色樞紐工程通航仿真船舶信息及比例，生成90艘船舶信息，并按照生成順序進(jìn)行排列，隨機(jī)生成的船舶信息見圖8。

考慮船舶到閘順序，采用模型及算法對(duì)船舶進(jìn)行排擋，排擋后結(jié)果見圖9（a）。閘室平均占用率為76.424%，需要47個(gè)閘次放行所有船舶。不考慮船舶到閘順序，采用模型及算法對(duì)船舶進(jìn)行排擋，排擋后結(jié)果見圖9（b）。閘室平均占用率為76.821%，需要45個(gè)閘次放行所有船舶。根據(jù)求解結(jié)果可以看到，模型在考慮船舶到閘順序和不考慮船舶到閘順序兩種情況下都具有較好的求解能力。

在考慮船舶到閘順序的情況下，閘室的利用率較高，但仍存在一定的空閑空間。這是因?yàn)樵谶@種情況下，優(yōu)先考慮公平服務(wù)，對(duì)閘室填充效果相對(duì)不那么關(guān)注。因此，船舶可以自由進(jìn)出閘室，沒有進(jìn)行預(yù)約的要求。然而，由于船舶之間的到閘順序不同，可能會(huì)導(dǎo)致一些閘室在某些時(shí)間段內(nèi)沒有充分利用，從而浪費(fèi)了一部分資源，這種入閘模式船舶較少時(shí)，且通過時(shí)間不確定的情況。

相比之下，在不考慮船舶到閘順序的情況下，閘室的利用率相對(duì)更高。這是因?yàn)樵谶@種情況下，船舶可以按照先到先得的原則進(jìn)入閘室，充分利用閘室資源。然而，由于忽視了船舶到閘順序的因素，當(dāng)多艘船舶同時(shí)到達(dá)閘室時(shí)，可能由于改變船舶入閘隊(duì)列，導(dǎo)致船舶之間的沖突和擁堵情況增加。

5? 結(jié)論

本文利用二維裝箱模型，建立了船舶閘室排擋模型，并提出一種以貪婪策略為基礎(chǔ)的求解船舶閘室連續(xù)排擋模型的算法，最后進(jìn)行仿真實(shí)驗(yàn)，根據(jù)仿真結(jié)果可以得到如下結(jié)論：

（1）船舶閘室連續(xù)排擋模型及求解算法可以有效對(duì)船舶進(jìn)行閘室排擋；

（2）考慮船舶到閘順序的排擋方法與不考慮船舶到閘順序的排擋方法均可以采用本文提出的船舶閘室連續(xù)排擋模型進(jìn)行求解；

（3）不考慮船舶到閘順序的排擋方法可以更高效地使船舶進(jìn)行通航，考慮船舶到閘順序的排擋方法更具有公平性，可以在實(shí)際工作中根據(jù)需求靈活采用不同方法進(jìn)行排擋。

參考文獻(xiàn)：

［1］季彬. 水利樞紐船舶過閘—泊位聯(lián)合調(diào)度模型與方法研究［D］. 武漢： 華中科技大學(xué)， 2018.

［2］GOLIAS MM， BOILE M， THEOFANIS S. Berth scheduling by customer service differentiation： a multi-objective approach［J］. Transportation Research Part E： Logistics and Transportation Review， 2009， 45（6）： 878-892. DOI： 10.1016/j.tre.2009.05.006.

［3］YUAN Y B， JI B， YUAN X H， et al. Lockage scheduling of Three Gorges-Gezhouba Dams by hybrid of chaotic particle swarm optimization and heuristic-adjusted strategies［J］. Applied Mathematics and Computation， 2015， 270： 74-89. DOI： 10.1016/j.amc.2015.08.009.

［4］GOLIAS MM， BOIL M， THEOFANIS S， et al. A multi-objective decision and analysis approach for the berth scheduling problem［M］//Project Management Techniques and Innovations in Information Technology. Pennsylvania： IGI Global， 2012： 1-20. DOI： 10.4018/978-1-4666-0930-3.ch001.

［5］鄧偉， 鄺祝芳， 余紹軍， 等. 基于遺傳算法的三峽-葛洲壩船閘閘室編排算法［J］. 人民長(zhǎng)江， 2016， 47（24）： 55-59. DOI： 10.16232/j.cnki.1001-4179.2016.24.012.

［6］王偉， 黃濤. 基于隨機(jī)排擋的船閘通過能力研究［J］. 水運(yùn)工程， 2021（1）： 162-167. DOI： 10.16233/j.cnki.issn1002-4972.20201228.035.

［7］ZHANG D F， SHI L Y， LEUNG S C H， et al.A priority heuristic for the guillotine rectangular packing problem［J］. Information Processing Letters， 2016， 116（1）： 15-21. DOI： 10.1016/j.ipl.2015.08.008.

［8］BAKER B S， COFFMAN E G Jr， RIVEST R L. Orthogonal packings in two dimensions［J］. SIAM Journal on Computing， 1980， 9（4）： 846-855. DOI： 10.1137/0209064.

［9］CHAZELLE. The bottom-left bin packing heuristic： an efficient implementation［C］. IEEE Transactions on Computers. 1983， 32（8）： 697-707. DOI： 10.1109/TC.1983.1676307.

［10］BURKE E K， KENDALL G， WHITWELL G. A new placement heuristic for the orthogonal stock-cutting problem［J］. Operations Research， 2004， 52（4）： 655-671. DOI： 10.1287/opre.1040.0109.

［11］陽名鋼， 陳夢(mèng)煩， 楊雙遠(yuǎn)， 等. 求解二維裝箱問題的強(qiáng)化學(xué)習(xí)啟發(fā)式算法［J］. 軟件學(xué)報(bào)， 2021， 32（12）： 3684-3697. DOI： 10.13328/j.cnki.jos.006161.

［12］李泳龍， 吳禮國(guó)， 周定科. 基于多種排擋策略的船閘通過能力仿真研究［J］. 水運(yùn)工程， 2023（S1）： 119-124. DOI： 10.16233/j.cnki.issn1002-4972.20230104.050.

［13］甘金明， 吳潔明. 船閘調(diào)度信息管理及閘室排擋調(diào)度優(yōu)化設(shè)計(jì)［J］. 梧州學(xué)院學(xué)報(bào)， 2014， 24（3）： 1-6. DOI： 10.3969/j.issn.1673-8535.2014.03.001.

［14］ZHANG X P， FU X D， YUAN X H. Co-evolutionary strategy algorithm to the lockage scheduling of the Three Gorges Project［C］//2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application. Wuhan， China： IEEE， 2009： 583-587. DOI： 10.1109/PACIIA.2008.347.