劉瑞杰，秦 放，翟 悅，王立娟

(大連科技學院信息科學系，遼寧 大連 116052)

0 引言

三峽船閘是當今世界上級數(shù)最多、規(guī)模最大的雙線五級連續(xù)船閘。三峽船閘的建成及投入運行極大地改善了宜昌至重慶600多公里的航道條件，促進了長江中上游經(jīng)濟和水運的快速發(fā)展，截止到2012年，長江沿線從事內(nèi)河運輸?shù)拇斑_到9.17萬艘，貨物通過量突破18億噸。在如此繁忙的航道上，處于咽喉地位的三峽船閘正面臨著巨大壓力，三峽船閘的“瓶頸現(xiàn)象”日益突出。數(shù)據(jù)表明，在目前正常情況下，三峽船閘每天最多能安排過閘船舶150艘次左右，但每天的過閘需求多達160～180艘次，運輸繁忙季節(jié)超過200艘次［1］，船舶待閘已呈現(xiàn)常態(tài)化趨勢。這使得大量船舶滯留三峽壩區(qū)，給三峽大壩造成極大的安全隱患，同時也使整個航道的水運成本上升、效率下降。因此，在三峽現(xiàn)有船閘的基礎(chǔ)上，研究提高三峽船閘通過能力的相關(guān)技術(shù)問題，對于發(fā)揮三峽工程綜合效益和保障沿江經(jīng)濟社會可持續(xù)發(fā)展具有十分重要的意義。

目前，國內(nèi)外學者對如何提高船閘通過能力的相關(guān)問題已經(jīng)做了許多有益的研究［2-14］。本文在分析影響船閘通過能力因素的基礎(chǔ)上，給出一種提高船閘通過能力的船閘編排的模擬退火算法，取得了較好的優(yōu)化結(jié)果。

1 船閘通過能力的影響因素分析

在船閘設(shè)計時，衡量船閘通過能力的一個指標在《船閘總體設(shè)計規(guī)范》(JTJ 305-2001)中按式(1)所示［5］。

P—年過閘船舶總載重噸位(t);

n—日平均過閘次數(shù)(次);

N—年通航天數(shù)(d);

G—一次過閘平均噸位(t)。

由公式(1)可知，計算船閘通過能力的指標P由3部分構(gòu)成:日平均過閘次數(shù)n、年通航天數(shù)N和一次過閘平均噸位G。日平均過閘次數(shù)n是根據(jù)船舶進出閘、閘門啟閉以及灌泄水等時間因素進行計算確定。在目前正常情況下，三峽船閘單線日運行閘次數(shù)只有14～16個，本文不研究如何通過提高日平均過閘次數(shù)來提高船閘通過能力。因此，在后續(xù)的討論過程中，把日平均過閘次數(shù)看作是一個常數(shù)值。

年通航天數(shù)N是根據(jù)特定航道船閘的統(tǒng)計資料確定。而在船閘實際運行時，船閘通航天數(shù)具有隨機性，也就是說，該參數(shù)是不受控制的，當然也就無法通過研究N來提高船閘通過能力。因此，在后續(xù)的討論過程中，把年通航天數(shù)看作是一個常數(shù)值。

一次過閘平均噸位G主要取決于每艘船的大小和每閘次中能夠容納的船舶數(shù)量，即與船舶噸位或尺度以及閘室有效面積利用率等因素有關(guān)。本文正是從提高一次過閘平均噸位的角度來研究船閘通過能力提高的問題，即把日平均過閘次數(shù)和年通航天數(shù)都取一個常數(shù)值。這樣，提高船閘實際通過能力的問題可以轉(zhuǎn)化為求一次過閘噸位最大值的問題，即:

P實際—實際年過閘船舶總載重噸位(t);

n和N的含義同式(1);

Gi—船閘實際運行時第i次過閘噸位(t)。

由式(2)可知，只要提高每一次的過閘噸位，即求max( Gi)，就可以提高P實際，即提高船閘實際通過能力。

2 參數(shù)Gi的確定和船閘編排的問題描述

第i次過閘噸位Gi的確定可采用類似計算一次過閘平均噸位G的計算方法——船隊排列法［6-7］來計算。

船隊排列法是通過對不同船型、船隊加以組合來確定一次過閘平均噸位的，這種思想對確定參數(shù)Gi是非常適合的，也就是說，本文提出的一次過閘噸位是針對船閘實際運行時，根據(jù)每一次有過閘需求的船舶組合來確定的。然而該方法在計算一次過閘平均噸位時卻存在許多問題，這當然一方面是由于我國從事內(nèi)河航運的船型、船隊型式繁多，另一方面是由于各種船舶到閘是隨機的，因此設(shè)計船型組合及其占全年過閘的比例都是難以合理確定的。但船隊排列法對確定參數(shù)Gi是不存在上述問題的，因為，在船閘實際運行時，待閘船舶是已知的，對確定參數(shù)Gi而言，只需要在所有等待過閘的船舶中按照某種策略和規(guī)則找出最優(yōu)的船舶組合。這實際上就是一個在給定的有限區(qū)域內(nèi)(閘室)盡可能多地安排過閘船舶(小區(qū)域)，從而提高船閘實際通過能力的問題。該問題可以用如下數(shù)學語言描述:

SL(L，W)表示長為L，寬為W的船閘閘室。對于三峽船閘，其閘室長280米，寬34米。

(1)安排到閘室內(nèi)的船舶兩兩互不重疊;

(2)安排到閘室內(nèi)的船舶不能超出閘室的邊界;

(3)安排到閘室內(nèi)的船舶不能任意旋轉(zhuǎn)，即船頭方向必須與過閘方向一致，且船身與閘門側(cè)壁平行。

3 船閘編排問題的模擬退火算法

模擬退火算法［15］是由Kirkpatrick等學者提出的一種能夠避免陷入局部最優(yōu)的隨機搜索算法，該算法是對固體物理退火過程的模擬，即給固體充分加熱，然后緩慢地讓它冷卻降溫，直到固體內(nèi)部粒子獲得最小晶格能量狀態(tài)。同時把Metropolis準則引入到算法之中，這樣，使得模擬退火算法除了接受改進解以外，還以一定概率接受非改進解(即劣質(zhì)解)，從而可以跳出局部最優(yōu)。這一有別于局部搜索算法的特征使模擬退火算法在求解組合優(yōu)化問題中有著廣泛的應(yīng)用。

3.1 船閘編排問題的模擬退火算法要素的構(gòu)建

(1)解空間:解空間可表示為有過閘需求且等待過閘船舶集合S的所有子集的集合。

(2)目標函數(shù):目標函數(shù)為編排到閘室內(nèi)的船舶面積之和占閘室有效面積的比率。即f(s1，s2，…，sb)

(3)鄰域結(jié)構(gòu):從當前解S'cur的集合中去掉一個船舶構(gòu)成 S″cur，所有不在 S'cur中且能夠在 S″cur的基礎(chǔ)上編排到閘室內(nèi)的船舶和S″cur共同組成的集合稱為當前解的鄰域結(jié)構(gòu)。新解S'new是隨機從鄰域結(jié)構(gòu)中選一個解作為新解。

(4)目標函數(shù)差:Δf=f(S'cur)-f(S'new)。

3.2 船閘編排問題的模擬退火算法描述

Step1 采用貪婪算法產(chǎn)生初始解，初始化退火溫度T0;

Step2 在溫度Ti時重復如下操作:

(1)隨機從當前解S'cur的鄰域結(jié)構(gòu)中選一個可行解S'new。

(2)計算 Δf，如果 Δf＜0，接收新解 S'new，轉(zhuǎn) Step 2;否則，依照概率 exp(-Δf/Ti)＞random［0，1］接收新解 S'new，random［0，1］是［0，1］區(qū)間內(nèi)的隨機數(shù)。

Step3 令Ti+1=αTi，i=i+1，其中 α 是初始參數(shù)(0 ≤α ≤1)，這里取 0.95;若滿足收斂條件，給出船閘編排結(jié)果，退火過程結(jié)束;否則，轉(zhuǎn)Step2。

3.3 實驗結(jié)果

求解三峽船閘編排問題的模擬退火算法已在Windows XP系統(tǒng)的PC上仿真實現(xiàn)。為了簡化計算，在該算法的實現(xiàn)細節(jié)上做了簡化處理，即把三峽船閘閘室的有效面積在程序?qū)崿F(xiàn)時看作是一個長280米，寬34米的矩形區(qū)域的面積，所有待閘船舶在水平面上的投影區(qū)域在程序?qū)崿F(xiàn)時看作是長為船舶總長，寬為船舶總寬的矩形區(qū)域。本文通過2個實例來檢驗該算法的有效性。第一個實例使用文獻［9］中的第一組數(shù)據(jù)，結(jié)果如圖1所示(圖中的數(shù)字代表待閘船舶的編號)。

圖1 文獻［9］中第一組數(shù)據(jù)的拍檔圖

對第一個實例的說明:

(1)在文獻［9］中給出的北線閘室的長為280米，寬為32.8米，本計算結(jié)果同樣也采用此數(shù)據(jù)。

(2)應(yīng)用本算法，無論針對文獻［9］中的3組數(shù)據(jù)的哪一組，都能把該組中的所有數(shù)據(jù)排完，這說明本算法在求解三峽船閘編排問題上是有效的，這里只給出了使用文獻［9］中的第一組數(shù)據(jù)拍檔圖。

第二個實例是從2013年5月20日長江三峽通航管理局當天發(fā)布的三峽—葛洲壩兩壩調(diào)度計劃簡表計劃中的所有過閘船舶中隨機抽取了部分船舶信息(如表1所示)進行船閘編排，共有24艘待閘船舶，應(yīng)用本算法對這24艘待閘船舶進行編排，閘室有效面積利用率為95.42%，結(jié)果如圖2所示。

圖2 表1中數(shù)據(jù)的拍檔圖

表1 船舶信息

4 結(jié)束語

本文從船閘實際運行的角度出發(fā)，在分析船閘通過能力影響因素的基礎(chǔ)上，給出了一種提高船閘實際通過能力的模擬退火方法，通過上述實例試驗結(jié)果表明，模擬退火算法在提高船閘實際通過能力問題上是有效的，這為提高船閘實際通過能力提供了新的思路和方法。

［1］唐冠軍.關(guān)于盡快建設(shè)長江三峽水利樞紐船舶過壩新通道的建議［EB/OL］.http://www.cjhy.gov.cn/hangyundongtai/dianziqikan/hangyunzazhi/201304/t20130422_233934.html，2013-04-22.

［2］廖鵬.內(nèi)河船閘通過能力研究進展［J］.水利水運工程學報，2009(3):34-40.

［3］郭濤.三峽船閘通過能力分析［J］.水運工程，2011(12):112-116.

［4］張義軍.提高三峽船閘通過能力之措施［J］.水運管理，2012，34(6):13-15.

［5］張瑋，廖鵬，昊玲莉，等.船閘通過能力主要影響因素［J］.交通運輸工程學報，2004，4(3):108-110.

［6］陶桂蘭，張瑋，丁堅，等.船閘1次過閘平均噸位的確定［J］.水運工程，2003(4):50-52.

［7］廖鵬，張瑋.船閘一次過閘平均噸位計算模型［J］.東南大學學報:自然科學版，2010，40(1):207-212.

［8］劉云峰，齊歡.DFS算法在三峽永久船閘優(yōu)化編排中的應(yīng)用［J］.計算機工程，2002，28(8):224-226.

［9］孫波，齊歡，張曉盼，等.三峽-葛洲壩聯(lián)合調(diào)度系統(tǒng)閘室編排快速算法［J］.計算機技術(shù)與發(fā)展，2006(12):15-17.

［10］肖恒輝，齊歡，王小平.船舶調(diào)度閘外編排算法［J］.交通運輸工程學報，2007，7(1):26-29.

［11］張曉盼，齊歡，袁曉輝.三峽工程兩壩聯(lián)合通航調(diào)度的混合模擬退火算法［J］.控制理論與應(yīng)用，2008，25(4):708-711.

［12］劉雯麗.貪婪算法在船閘編排問題的應(yīng)用［J］.電腦知識與技術(shù)，2011，7(10):2417-2418.

［13］商劍平，吳澎，唐穎.基于計算機仿真的船閘聯(lián)合調(diào)度方案研究［J］.水運工程，2011(9):199-204.

［14］趙春鵬.船閘調(diào)度優(yōu)化與仿真［D］.大連:大連海事大學，2012.

［15］Kirkpatrick S，Gelatt C D Jr，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220:671-680.