基于模擬退火算法的三峽船閘編排

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

Gi—船閘實(shí)際運(yùn)行時第i次過閘噸位(t)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step2 在溫度Ti時重復(fù)如下操作:

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

(2)計(jì)算 Δ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)的隨機(jī)數(shù)。

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

對第一個實(shí)例的說明:

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

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

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

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

表1 船舶信息

4 結(jié)束語

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

［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ìn)展［J］.水利水運(yùn)工程學(xué)報，2009(3):34-40.

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

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

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

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

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

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

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

［10］肖恒輝，齊歡，王小平.船舶調(diào)度閘外編排算法［J］.交通運(yùn)輸工程學(xué)報，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］商劍平，吳澎，唐穎.基于計(jì)算機(jī)仿真的船閘聯(lián)合調(diào)度方案研究［J］.水運(yùn)工程，2011(9):199-204.

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

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