毛 星，胡少英，徐希濤 ，李寧寧

(南瑞集團(tuán)(國網(wǎng)電力科學(xué)研究院)有限公司,江蘇 南京 211000)

0 引 言

作為一個(gè)河網(wǎng)密度極大，最大值達(dá)12.7 km/km2、海岸線達(dá)3.2萬公里的國家，水運(yùn)是我國最主要的貨運(yùn)手段之一。當(dāng)前我國水路運(yùn)輸不斷發(fā)展，長江水運(yùn)通道已超過密西西比河和萊茵河，成為世界上最繁忙、運(yùn)量最大的內(nèi)河運(yùn)輸通道。但是目前我國的貨運(yùn)周轉(zhuǎn)量承擔(dān)值只有49.77%，與發(fā)達(dá)國家的75%相比，相差懸殊。究其原因，船閘通航能力成為制約水路運(yùn)輸效率的最突出問題[1-2]，因此解決船閘調(diào)度過程中船舶待閘時(shí)間長、閘室利用率低等問題是提高船閘通航能力、增加航運(yùn)周轉(zhuǎn)量的關(guān)鍵[3]。

目前內(nèi)河航運(yùn)主要采用人工編排調(diào)度計(jì)劃的調(diào)度方式，人工排船時(shí)通常選擇減少單次過閘船數(shù)、降低閘室利用率的方式來緩解過閘等待時(shí)間長的問題，調(diào)度過程慢、調(diào)度水平低、缺乏科學(xué)性，而且人工排檔方法太過依賴人為決策，對決策者個(gè)人的經(jīng)驗(yàn)、知識、能力等要求很高，決策的科學(xué)性較低。因此，提高船閘通航能力的核心是采用科學(xué)有效的調(diào)度方法[4-6]。

閘室編排根據(jù)船舶報(bào)到時(shí)間和優(yōu)先級別，將船舶排入閘室內(nèi)，可以用二維空間上的裝箱模型來描述[7-8]，是一個(gè)典型的NP完全問題[9]。目前以二維裝箱模型解決船閘排檔問題常見的方法有快速編排算法、貪婪算法、二維優(yōu)化編排啟發(fā)式算法等[10-14]，這些算法在大多數(shù)情況下能取得較高的閘室利用率，但是在編排過程中只注重局部最優(yōu)選擇，不進(jìn)行回溯處理，很容易錯(cuò)過真正的最優(yōu)解[15]。本文針對船閘調(diào)度過程中的多種決策因素，建立調(diào)度問題的數(shù)學(xué)模型，給出了基于多目標(biāo)遺傳算法的求解過程。

1 船閘調(diào)度問題模型

船閘調(diào)度問題可以分為單閘調(diào)度和多船閘聯(lián)合調(diào)度，本文只考慮船舶通過單個(gè)船閘的情況。單閘調(diào)度問題是指在有限的船閘空間內(nèi)，使每條船舶通過的時(shí)間最短。包括2個(gè)目標(biāo)函數(shù)和3個(gè)約束條件。

1.1 目標(biāo)函數(shù)

船閘調(diào)度過程中主要考慮2個(gè)調(diào)度指標(biāo)，一個(gè)是從船主角度出發(fā)，要求船舶的等待調(diào)度時(shí)間最短，另一個(gè)是從船閘管理的角度出發(fā)，要求每一閘室內(nèi)所有船舶占用總面積最大。因此具體的實(shí)現(xiàn)方法為：

1)構(gòu)建船舶等待調(diào)度時(shí)間最短目標(biāo)函數(shù)F1：

(1)

2)構(gòu)建閘室利用率最大目標(biāo)函數(shù)F2：

(2)

其中：M表示船閘中的待閘船舶數(shù)；i表示第i艘船舶；Ti0表示船舶報(bào)到時(shí)間；Ti1表示船舶過閘時(shí)間；flagi表示第i艘船舶能否排進(jìn)該閘次，能則為1，否則為0；Si表示第i艘船舶的面積；A表示該閘次的閘室面積。

1.2 約束條件

1)所有選中的船舶必須能夠排入船閘：

(3)

2)每條船舶的尺寸不能超過閘室的尺寸：

0

(4)

0

(5)

3)同一閘次的船舶相互不重疊：

i1x+i1l

(6)

i2x+i2l

(7)

i1y+i1w

(8)

i2y+i2w

(9)

其中，任意船舶i1,i2∈{1,2,…,M}，x、y為船舶在閘室內(nèi)的橫坐標(biāo)和縱坐標(biāo)，l、w為船舶的長度和寬度，L、W為閘室的長度和寬度。

2 多目標(biāo)船閘調(diào)度算法求解

圖1 實(shí)現(xiàn)算法流程圖

普通的多目標(biāo)遺傳算法，針對相互接近而又不具有Pareto支配關(guān)系的個(gè)體，SPEA很難有效地區(qū)分它們的適應(yīng)度[16-18]，容易產(chǎn)生適應(yīng)度相同的個(gè)體，導(dǎo)致算法計(jì)算效率低下。鑒于此種現(xiàn)象，本文提出一種高效、合理的船閘調(diào)度方式，具體的實(shí)現(xiàn)方法如圖1所示。

2.1 染色體編碼

借鑒生物進(jìn)化過程，將船閘排檔結(jié)果定義為進(jìn)化對象的個(gè)體，進(jìn)行染色體編碼，具體的方法如下：

假設(shè)船閘中有M艘待閘船舶，用M艘待閘船舶表示染色體內(nèi)所包含的M組基因，基因內(nèi)ji表示第i艘船舶被調(diào)度的閘次，xi,fi和yi,fi分別表示第i艘船舶安排于船閘中的X、Y坐標(biāo)，則染色體編碼的編碼公式如下：

s=[(j1,x1,f1,y1,f1),(j2,x2,f2,y2,f2),…,(jM,xM,fM,yM,fM)]

其中，s表示船閘中M艘船舶的一種排船方式。

2.2 種群初始化

在初始化種群時(shí)，要求生成一組滿足目標(biāo)解的染色體，并且這些解盡量具有較高的指標(biāo)。本文采用貪婪算法的思想進(jìn)行種群初始化，具體過程如下：

1)從待閘船舶中隨機(jī)選擇一條船放入閘室。

2)在閘次集合中隨機(jī)選擇一個(gè)閘次對該船舶進(jìn)行排閘。

3)判斷該船舶能否排進(jìn)該閘次，如果能，進(jìn)入步驟4，如果不能，進(jìn)入步驟5。

4)更新染色體，更新待閘船舶，進(jìn)入步驟1，直至待閘船舶列表為空。

5)更新閘次集合，重新進(jìn)入步驟3，直至閘次集合為空，并將基因更新為(-1,-1,-1)。

6)上述過程反復(fù)執(zhí)行N次，即可得到N組滿足目標(biāo)解的染色體集合，即初始種群，也就是船閘中M艘船舶的N種排船方式。種群規(guī)模越大越可能找到全局解，但運(yùn)行時(shí)間也相對較長，一般N在40～100之間取值。

2.3 個(gè)體適應(yīng)度計(jì)算

計(jì)算個(gè)體適應(yīng)度，具體的實(shí)現(xiàn)算法如下：

其中：xm表示船閘中M艘船舶的第m種排船方式，即個(gè)體m；Fitness(xm)是個(gè)體m的適應(yīng)度，SumMation(xm)是Pareto支配xm的個(gè)體的強(qiáng)度和，S(xm)是xm的強(qiáng)度，SET(xm)是所有xm與具有相同個(gè)體的強(qiáng)度和的集合；xn表示船閘中M艘船舶的第n種排船方式，即個(gè)體n；S(xn)是xn的強(qiáng)度。

遺傳算法中個(gè)體適應(yīng)度用于計(jì)算被選擇的概率，遺傳結(jié)束后，適應(yīng)度最高的個(gè)體將作為最優(yōu)解。

2.4 遺傳操作

遺傳算法的操作算子主要有選擇、交叉和變異3種，分別模擬了自然界的生物繁衍、交配和基因突變。

選擇算子的作用就是從群體中選出比較適應(yīng)環(huán)境的個(gè)體繁殖到下一代，選擇算子計(jì)算的基礎(chǔ)是個(gè)體的適應(yīng)度評價(jià)值。本文采用比例選擇的思路設(shè)計(jì)選擇算子，個(gè)體被選擇的概率如下：

其中：Pm表示個(gè)體被選中的概率，即該種排船方式能被選中遺傳給下一代的概率；Fitness(xm)是個(gè)體m的適應(yīng)度值；N表示初始種群的數(shù)量，即N種排船方式。

交叉算子是將2個(gè)個(gè)體的基因的一部分片段互相交換，從而產(chǎn)生2個(gè)新的個(gè)體，其過程：按照選擇算子隨機(jī)從初始化的種群中選擇2個(gè)父代個(gè)體，在隨機(jī)產(chǎn)生的交叉點(diǎn)處，進(jìn)行2個(gè)個(gè)體的交叉操作，產(chǎn)生2個(gè)新的個(gè)體。

變異算子是隨機(jī)選擇個(gè)體和個(gè)體的某一位進(jìn)行變異操作。

遺傳操作需要對選擇出的個(gè)體組成的種群反復(fù)按序進(jìn)行選擇操作、交叉操作和變異操作，從全局的角度進(jìn)行評估決策，輸出滿足調(diào)度需求的最優(yōu)排檔方案。當(dāng)遺傳操作GEN次之后，即進(jìn)化GEN代之后，則將進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，得到最優(yōu)排船方法，終止計(jì)算。

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

本次試驗(yàn)以長洲船閘三號閘室2017年6月每天船舶過閘數(shù)據(jù)資料為例，長洲船閘是世界上通過能力最大的內(nèi)河船閘群。利用優(yōu)化多目標(biāo)遺傳算法進(jìn)行閘室編排，并與目前采用的人工編排方式進(jìn)行閘室利用率和平均待閘時(shí)間的比較，結(jié)果如表1和表2所示。

表1 長洲船閘三號閘室6月份平均閘室利用率 單位：%

表2 長洲船閘三號閘室6月份平均待閘時(shí)間 單位：min

由表1和表2可見，優(yōu)化多目標(biāo)遺傳算法的船閘智能調(diào)度方法與傳統(tǒng)人工編排的方法相比，閘室利用率從75.23%提高到78.00%，船舶平均待閘時(shí)間縮短28 min，體現(xiàn)了算法的科學(xué)性，提高了船閘通航能力。

4 結(jié)束語

本文針對內(nèi)河航道船閘調(diào)度存在的問題，考慮多種調(diào)度指標(biāo)和約束條件，借鑒生物進(jìn)化過程的啟發(fā)式搜索算法，建立多個(gè)目標(biāo)函數(shù)，提出了基于多目標(biāo)遺傳算法的調(diào)度模型，并對適應(yīng)度計(jì)算方法進(jìn)行優(yōu)化改進(jìn)，通過實(shí)例驗(yàn)證了該方法科學(xué)性和有效性，為船舶調(diào)度和船閘運(yùn)行提供了決策輔助功能。

參考文獻(xiàn)：

[1] 孫波. 三峽-葛洲壩聯(lián)合調(diào)度系統(tǒng)閘室編排研究[D]. 武漢:華中科技大學(xué), 2006.

[2] 劉瑞杰,秦放,翟悅,等. 基于模擬退火算法的三峽船閘編排[J]. 計(jì)算機(jī)與現(xiàn)代化, 2013(11):65-67.

[3] 張瑋,廖鵬,吳玲莉,等. 船閘通過能力主要影響因素[J]. 交通運(yùn)輸工程學(xué)報(bào), 2004(3):108-110.

[4] Wang Hongfeng, Yang Shengxiang, Ip W H, et al. Adaptive primal-dual genetic algorithms in dynamic environments[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009,39(6):1348-1361.

[5] 陳明輝,盛黎. 蘇北運(yùn)河船閘智能排檔調(diào)度研究及應(yīng)用[J]. 中國水運(yùn)(下半月), 2016,16(4):75-77.

[6] 高蕾,吳婷. 隔代遺傳算法在船舶調(diào)度系統(tǒng)中的應(yīng)用[J]. 艦船科學(xué)技術(shù), 2017(4):61-63.

[7] Kirkpatrick S, Jr G C, Vecchi M P. Optimization by simulated annealing[M]// Readings in Computer Vision: Issues, Problems, Principles, and Paradigms. 1983,220(4598):606-615.

[8] 蔣金山,林正春. 用自適應(yīng)遺傳算法解二維裝箱問題[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2008,25(7):244-246.

[9] 湯巖,胡俊敏,武立豐. 一種改進(jìn)的二維裝箱問題的混合遺傳算法[J]. 集美大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006,11(3):258-262.

[10] 劉云峰，齊歡. 二維優(yōu)化編排啟發(fā)式算法及其在三峽永久船閘調(diào)度決策系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(jī)與現(xiàn)代化, 2002(1):1-3.

[11] 王曉華. 算法的樂趣[M]. 北京:人民郵電出版社, 2015.

[12] 王小平,阮茜. 基于蟻群算法的船舶過閘計(jì)劃優(yōu)化模型[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011,39(8):100-103.

[13] 吳小濤,袁曉輝，Muhammad Adnan Ikram. 基于擬人策略的三峽永久閘室編排新算法[J]. 水電能源科學(xué), 2015(5):148-151.

[14] Neto R F T, Filho M G. An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed[J]. Computers & Operations Research, 2011,38(9):1286-1293.

[15] 李楠,李桂華,尹劍平. 湘江船閘的過閘調(diào)度算法研究[J]. 水運(yùn)工程, 2013(3):171-175.

[16] 馮明波. 基于改進(jìn)多目標(biāo)遺傳算法的船閘調(diào)度方法[J]. 江蘇船舶, 2016(4):30-33.

[17] 李凱. 一種基于改進(jìn)遺傳算法的圖著色算法[J]. 計(jì)算機(jī)與現(xiàn)代化, 2017(2):6-11.

[18] 公茂果,焦李成,楊咚咚,等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào), 2009,20(2):271-289.