馮明波

(南通航運(yùn)職業(yè)技術(shù)學(xué)院，江蘇 南通 226010)

?

基于改進(jìn)多目標(biāo)遺傳算法的船閘調(diào)度方法

馮明波

(南通航運(yùn)職業(yè)技術(shù)學(xué)院，江蘇 南通 226010)

針對目前我國內(nèi)河航運(yùn)船閘調(diào)度采用手工編制調(diào)度計(jì)劃方式速度慢、調(diào)度水平低、缺乏科學(xué)性的現(xiàn)狀，通過對單閘多目標(biāo)調(diào)度問題進(jìn)行建模，并基于改進(jìn)的SPEA設(shè)計(jì)了模型求解算法，對船閘調(diào)度系統(tǒng)進(jìn)行優(yōu)化，為提高船閘通航能力提供了技術(shù)支持。

船閘；多目標(biāo)調(diào)度；遺傳算法

0 引言

目前我國內(nèi)河航運(yùn)的船閘調(diào)度基本采用手工編制調(diào)度計(jì)劃的方式，調(diào)度計(jì)劃編制速度慢、調(diào)度水平低、缺乏科學(xué)性，從而導(dǎo)致船閘使用效率低下，使得本就存在的船閘資源稀缺與航運(yùn)總量急升之間的矛盾日益加大，極大地制約了我國內(nèi)河航運(yùn)的發(fā)展步伐。本文對內(nèi)河航運(yùn)船閘調(diào)度方法進(jìn)行研究，建立調(diào)度問題的數(shù)學(xué)模型，并基于對調(diào)度方案的多角度考慮提出針對調(diào)度模型的多目標(biāo)調(diào)度求解算法。

1 多目標(biāo)船閘調(diào)度模型

船閘調(diào)度問題可以描述為：在特定時(shí)間段內(nèi)，有若干船舶提出通過船閘申請，調(diào)度問題即是在現(xiàn)有船閘空間有限的前提下，合理為每一艘船舶安排通過船閘的時(shí)間和空間，從而達(dá)到減少船舶等候時(shí)間、提高船閘利用效率等目標(biāo)。

根據(jù)調(diào)度問題中包含船閘的數(shù)量，該調(diào)度問題可分為單閘調(diào)度和多閘調(diào)度，本文主要針對單閘調(diào)度展開研究。根據(jù)調(diào)度范圍的時(shí)間特性，船閘調(diào)度問題可分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度，本文針對靜態(tài)調(diào)度問題進(jìn)行研究。

在對船閘調(diào)度問題進(jìn)行建模時(shí)，需要考慮以下問題：

(1)為了簡化問題，本文將所有船舶視為矩形狀且有方向性，即船舶的頭部必須向前。船閘同樣定義為矩形形狀。

(2)為了規(guī)避船舶之間潛在的碰撞風(fēng)險(xiǎn)，為每艘船舶定義一個(gè)安全區(qū)域，即其船身(實(shí)際為其對應(yīng)的矩形框)向外擴(kuò)展一定的區(qū)域，在該區(qū)域內(nèi)不可以安置其他船舶。對于不同的船舶類型，其安全區(qū)域大小不同。

(3)待調(diào)度船舶具有不同的身份：包含必須在本調(diào)度周期安排過閘的船舶(如特殊身份船舶)和一般船舶；包含經(jīng)過前期多次調(diào)度仍未安排過閘的船舶以及本次調(diào)度前新加入的船舶。

1.1 變量與符號定義

(1)船閘調(diào)度問題所需的符號定義

M：待調(diào)度船舶數(shù)量；

nc：本調(diào)度周期包含的調(diào)度閘次數(shù)量；

Ll、Wl：船閘矩形的長、寬；

li、wi：船舶i矩形的長、寬；

ldi、wdi：船舶i的安全區(qū)域的長、寬；

wti：本調(diào)度周期起始時(shí)刻船舶i已經(jīng)等待的時(shí)間；

wtiMAX：船舶i允許的最長等待時(shí)間；

I：必須在本調(diào)度周期安排過閘的船舶序號集合，包括特殊身份船舶和等待時(shí)間已經(jīng)超過規(guī)定時(shí)限的船舶；

Tc：一個(gè)閘次的時(shí)間，假設(shè)每個(gè)閘次的執(zhí)行時(shí)間相等，即Tc為一固定值。

(2)該調(diào)度問題的決策變量

xi,j：船舶i在閘次j中安排在船閘中的X坐標(biāo)；

yi,j：船舶i在閘次j中安排在船閘中的Y坐標(biāo)；

flagi：船舶i在本調(diào)度周期是否被調(diào)度標(biāo)識。

上述變量中，xi,j和yi,j分別為船舶左下角點(diǎn)相對于船閘坐標(biāo)系的X、Y坐標(biāo)值。船閘坐標(biāo)定義為：以船閘的左下角點(diǎn)為原點(diǎn)，與船舶按規(guī)定停泊后的頭尾連線平行的方向?yàn)閅軸，船舶橫向方向?yàn)閄軸。

1.2 約束條件

船閘調(diào)度問題的約束條件如下：

xi,j∈{-1,[0,Wl]}

(1)

yi,j∈{-1,[0,Ll]}

(2)

(3)

xi,j+wi+wdi

(4)

yi,j+li+ldi

(5)

?i∈Iflagi=1

(6)

(7)

(8)

?i1,i2∈{1,2,…,M} if (i1≠i2)∧(?j st.

(9)

(10)

(11)

式(9)中定義的Overlapi1,i2表示在同一閘次內(nèi)調(diào)度的兩艘船舶i1和i2是否存在重疊的標(biāo)識，其計(jì)算比較復(fù)雜，以下給出詳細(xì)計(jì)算過程：

為簡化分析過程，假定以船舶i1為參照，判斷船舶i2是否與其有重疊區(qū)域。兩船重疊分為2種情況，以船舶i2矩形的4個(gè)角點(diǎn)是否至少有1個(gè)落入船舶i1矩形區(qū)域內(nèi)進(jìn)行劃分，如式(12)所示：

if (LDIni1,i2)∨(LUIni1,i2)∨(RDIni1,i2)∨

(RUIni1,i2)∨(WInci1,i2)∨(LInci1,i2)∨(AInci1,i2) then LDIni1,i2=true

else Overlapi1,i2=false

(12)

式中：LDIni1,i2、LUIni1,i2、RDIni1,i2、RUIni1,i2分別為判斷船舶i2矩形左下角、左上角、右下角和右上角是否落入船舶i1矩形內(nèi)的標(biāo)識，可統(tǒng)一由下式確定：

if (xLDIni1,j

else PTlni1,i2=false

(13)

式中：xLDi,j、xRUi,j、yLDi,j和yRUi,j分別表示船舶i矩形的左下角和右上角點(diǎn)的X和Y坐標(biāo)；xPTi2,j、yPTi2,j和PTIni1,i2為形式化變量，分別從{xLDi2,j, xLUi2,j, xRDi2,j, xRUi2,j}、{yLDi2,j,yLUi2,j,yRDi2,j, yRUi2,j}和{ LDIni1,i2，LUIni1,i2，RDIni1,i2，RUIni1,i2}中取值(3個(gè)變量取值序號一一對應(yīng))從而組成4個(gè)公式。其中xLUi,j、xRDi,j、yLUi,j和yRDi,j分別表示船舶i矩形的左上角和右下角點(diǎn)的X和Y坐標(biāo)。

對于船舶i2矩形的4個(gè)角點(diǎn)均未落入船舶i1矩形區(qū)域內(nèi)的情況，又分為2種情況：一是船舶i2在橫向跨度(X方向)上包含i1在橫向上的跨度區(qū)域(對應(yīng)于式(12)的WInci1,i2)；二是船舶i2在縱向跨度(Y方向)上包含i1在縱向上的跨度區(qū)域(對應(yīng)于式(12)的LInci1,i2)。如果2種情況均滿足，則對應(yīng)于船舶i2將船舶i1包含在其矩形框內(nèi)(對應(yīng)于式(12)的AInci1,i2)。而情況1與情況2的區(qū)別僅在于判斷方向?yàn)閄軸還是Y軸，因此下面僅以情況1(即WInci1,i2的計(jì)算)為例展開分析。滿足情況1的兩船關(guān)系又分為4種情形，其中3種情形如圖1所示(第4種情形為船舶i2將船舶i1包含在其矩形框內(nèi))。圖中實(shí)形框?yàn)榇癷1，3個(gè)虛形框分別對應(yīng)于3種情形下船舶i2的位置。這3種情形可統(tǒng)一描述為：在Y軸方向，只要船舶i2的左下角點(diǎn)或者右上角點(diǎn)位于船舶i1的左下角點(diǎn)和右上角點(diǎn)之間即可，因此可由下式確定：

圖1 船舶i2橫向跨越船舶i1時(shí)兩者重疊情況示意圖

(14)

而船舶i2在橫向跨度(X方向)上包含船舶i1在橫向上的跨度區(qū)域的判斷條件為：

(15)

(16)

同理：

xRUi2,j

(17)

在以上計(jì)算WInci1,i2和LInci1,i2的公式中均忽略了船舶i2將船舶i1包含在其矩形框內(nèi)的情形，因此需單獨(dú)計(jì)算AInci1,i2：

AInci1,i2=(xLDi1,j>xLDi2,j)∧(yLDi1,j>

yLDi2,j)∧(xRUi1,jyRUi2,j)

(18)

由此，兩船重疊判斷式(12)所需條件均可計(jì)算得出。

1.3 調(diào)度指標(biāo)

考慮以下2個(gè)船閘調(diào)度指標(biāo)：

一個(gè)是從用戶的角度出發(fā)，要求所有船舶的等待調(diào)度時(shí)間盡量短。為了簡便計(jì)算，在此僅考慮船舶在本調(diào)度周期內(nèi)等待的時(shí)間：

(19)

另一個(gè)是從交通管理部門的角度出發(fā)要求更高的通過率，因此要求在當(dāng)前調(diào)度周期內(nèi)安排盡量多的船舶過閘：

(20)

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

本文建立的船閘調(diào)度模型是典型的NP-hard問題，目前遺傳算法、蟻群算法和粒子群算法等智能搜索算法在該類問題的求解得到了廣泛應(yīng)用并取得了良好的效果。本文建立的船閘調(diào)度模型是一個(gè)多目標(biāo)調(diào)度問題，針對這類問題一種簡單的方式是采用加權(quán)求和的方式將多目標(biāo)調(diào)度轉(zhuǎn)化成單目標(biāo)調(diào)度問題，但是正如上一節(jié)所介紹，本調(diào)度問題所提出的2個(gè)指標(biāo)分別從航運(yùn)管理部門和用戶角度出發(fā)，二者之間在某種程度上存在一定的沖突，難以確定相對權(quán)值，該方法存在一定限制。目前針對多目標(biāo)調(diào)度問題應(yīng)用比較多的是多目標(biāo)遺傳算法，如NPGA、NSGA和NSGA-II，以及SPEA和SPEA-II等[2-5]。其中SPEA基于Pareto支配理論進(jìn)行設(shè)計(jì)，基于“支配個(gè)體所有Pareto解所支配個(gè)體的數(shù)量總和”這一隱含信息對個(gè)體周圍的密度進(jìn)行評價(jià)，能夠避免設(shè)置其他算法涉及的小生境參數(shù)這一難題[6]。本文基于SPEA算法對多目標(biāo)船閘調(diào)度問題進(jìn)行求解。

2.1 算法流程

本文基于SPEA算法設(shè)計(jì)多目標(biāo)船閘調(diào)度算法流程如圖2所示。

2.2 染色體編碼與種群初始化

定義染色體：s=[(j1,x1,j1,y1,j1),(j2,x2,j2,y2,j2),…, (jM,xM,jM,yM,jM)]，染色體包含M組基因，每組基因?yàn)?個(gè)三元組，對應(yīng)于1艘船的調(diào)度閘次、在該閘次中安排在船閘的X和Y坐標(biāo)。染色體長度為3×M，且基因取值-1的大幅度減少。在交叉和變異計(jì)算時(shí)，以1個(gè)三元組基因?yàn)閱挝贿M(jìn)行。

圖2 多目標(biāo)船舶調(diào)度算法流程

在進(jìn)行種群初始化時(shí)，要求生成1組對應(yīng)于模型可行解的染色體，并且盡量使這些可行解具有較高指標(biāo)，即對應(yīng)于較優(yōu)解，為后面的種群進(jìn)化奠定較好基礎(chǔ)。本文基于貪婪算法思想設(shè)計(jì)種群初始化策略，該策略生成1個(gè)染色體的過程如下：

step1:從待調(diào)度船舶集合中隨機(jī)選取1艘船i；

step2:在剩余閘次的空間資源內(nèi)對船舶i進(jìn)行排閘；

step2.1：在未遍歷閘次集合中隨機(jī)選擇1個(gè)閘次j；

step2.2：調(diào)取閘次j的已安排船舶集合Bj，基于式(9)判斷船舶i是否可以安排進(jìn)閘次j，如是則將船舶i加入集合Bj，并將船舶i安排的閘次j及在船閘中的坐標(biāo)更新至染色體對應(yīng)的位置中，進(jìn)入step3；否則進(jìn)入step2.3；

step2.3：未遍歷閘次集合是否為空，如是則將染色體對應(yīng)船舶i的基因三元組置為(-1,-1,-1)，并進(jìn)入step3；否則將閘次j從未遍歷閘次集合中去除并返回step2.1；

step3：將傳播i從待調(diào)度船舶集合中去除。判斷待調(diào)度船舶集合是否為空，如是則過程結(jié)束，輸出染色體；否則返回step1。

上述過程反復(fù)執(zhí)行N次，即可得到對應(yīng)于N個(gè)可行解的染色體集合，即初始種群。由于該過程在選擇船舶和閘次的過程中均為隨機(jī)選取，因此可以產(chǎn)生不同的可行解。

2.3 主要遺傳算子設(shè)計(jì)

2.3.1 適應(yīng)值計(jì)算

本文對SPEA進(jìn)行改進(jìn)，提出個(gè)體適應(yīng)值的計(jì)算方法。SPEA存在一個(gè)缺點(diǎn)，即容易產(chǎn)生適應(yīng)值相同的個(gè)體，尤其針對幾個(gè)相互接近而又不具有Pareto支配關(guān)系的個(gè)體，SPEA很難有效地區(qū)分它們的適應(yīng)值[7]。這是因?yàn)镾PEA在針對一個(gè)個(gè)體進(jìn)行適應(yīng)值計(jì)算式只考慮到支配該個(gè)體的Pareto解，而該個(gè)體所支配其他個(gè)體的情況并非被考慮，而后者是區(qū)分相似個(gè)體的重要因素，對此本文對SPEA的個(gè)體適應(yīng)值計(jì)算方法進(jìn)行改進(jìn)如下：

(21)

式中：fitness(xi)為個(gè)體的適應(yīng)值；PDStrSum(xi)為所有Pareto支配xi的個(gè)體的強(qiáng)度和(稱為支配解強(qiáng)度和)；Str(xi)為xi的強(qiáng)度，即所有被xiPareto支配的個(gè)體數(shù)量；StrEqu(xi)為所有xi與具有相同支配解強(qiáng)度和的個(gè)體集合。

2.3.2 交叉和變異算子

交叉算子以兩個(gè)個(gè)體相對應(yīng)的一對三元組為單位執(zhí)行。為了保持種群的多樣性，針對三元組設(shè)計(jì)兩種交叉模式：一種是整體交換，即將兩艘船舶被安排的閘次和在閘坐標(biāo)整體交換；另一種是局部交換，即不改變船舶的原調(diào)度閘次，僅交換在閘距離。針對個(gè)體I1和I2，交叉算子過程如下:

step1：在I1和I2上各隨機(jī)選擇基因三元組t1和t2；

step2：生成[0,1]之間的隨機(jī)數(shù)，將該隨機(jī)數(shù)與事先設(shè)定閾值比較，如隨機(jī)數(shù)大則進(jìn)入step3，否則進(jìn)入step4；

step3：執(zhí)行整體交換，即將t1放到I2上而將t2放到I1上，進(jìn)入step5；

step4：執(zhí)行局部交換，即將I1中t1上的后2個(gè)數(shù)組成的二元組與I2中t2上的后2個(gè)數(shù)組成的二元組進(jìn)行交換，進(jìn)入step5；

step5：針對交叉后的I1和I2上的三元組t1和t2進(jìn)行微調(diào)，即加入較小隨機(jī)數(shù)。

交叉過程的step5目的是進(jìn)一步增加種群多樣性，防止種群在船閘少數(shù)幾個(gè)坐標(biāo)點(diǎn)附近陷入局部解。為了進(jìn)一步提高算法的解空間搜索能力，需進(jìn)一步執(zhí)行變異操作，變異算子與交叉算子的step5類似，只是加入的是一個(gè)較大隨機(jī)數(shù)，并且在個(gè)體的每個(gè)三元組均執(zhí)行變異操作。

算法執(zhí)行完交叉和變異算子后得到新的種群，但是新種群中個(gè)體對應(yīng)的解是否為可行解難以保證，因此要針對新種群的每一個(gè)個(gè)體進(jìn)行可行化轉(zhuǎn)化，即針對個(gè)體上每一個(gè)基因三元組對照上一節(jié)給出的約束條件組依次判斷是否違反，如是，則將該三元組置為(-1，-1，-1)。

2.4 算法實(shí)例驗(yàn)證

本文基于VC6.0對提出的模型與算法進(jìn)行了實(shí)現(xiàn)，算法運(yùn)行在IntelCorei7 2.5GHz平臺下，內(nèi)存為4.0GB，操作系統(tǒng)為Win10。為了模擬多種規(guī)模的船舶調(diào)度問題，船舶數(shù)量和尺寸、船閘尺寸等在給定區(qū)間內(nèi)隨機(jī)取值。為了對算法進(jìn)行驗(yàn)證，將該算法與基于“先到先服務(wù)”原則的貪婪算法進(jìn)行比較，比較指標(biāo)C設(shè)計(jì)如下：

C=PD1,2/PD2,1

(22)

2種算法同時(shí)運(yùn)行K次，得到2組各K個(gè)調(diào)度結(jié)果，令本文設(shè)計(jì)的求解算法序號為1，貪婪算法序號為2，PDi,j表示算法i得到的K個(gè)調(diào)度結(jié)果中Pareto支配算法j得到的K個(gè)調(diào)度結(jié)果的個(gè)數(shù)之和。因此，C值越大表明算法1的性能越優(yōu)于算法2。算法運(yùn)行結(jié)果見表1。

表1 算法運(yùn)行結(jié)果

由表1可以看出，在隨機(jī)生成的6個(gè)實(shí)例中，C值均大于1，說明本文提出的算法相比貪婪算法具有明顯的優(yōu)勢。

3 結(jié)論

本文針對現(xiàn)階段我國內(nèi)河船閘使用效率低下，導(dǎo)致本就存在的船閘資源稀缺與航運(yùn)總量急升之間的矛盾日益明顯，極大地制約了我國內(nèi)河航運(yùn)的發(fā)展步伐等問題，對內(nèi)河航運(yùn)船閘調(diào)度進(jìn)行了研究；建立了該問題的調(diào)度約束滿足的多目標(biāo)船閘調(diào)度模型，并基于改進(jìn)的SPEA設(shè)計(jì)了該多目標(biāo)調(diào)度問題的求解算法；最后通過算法實(shí)例驗(yàn)證了該算法的可行性和有效性，為船閘調(diào)度系統(tǒng)優(yōu)化、船閘的高效運(yùn)行提供了建議方案和技術(shù)支持。

[1] 蔡恩澤. 內(nèi)河水運(yùn)“金”濤拍岸[J].決策與信息,2011(5)：35-37.

[2] 馮明月,李國輝,易先清，等. 一種求解多目標(biāo)柔性JSP的正交遺傳算法[J].系統(tǒng)仿真學(xué)報(bào),2009,21(15)：4682-4690.

2016-04-13

江蘇省交通運(yùn)輸科技項(xiàng)目(2014C03-05)

馮明波(1977—)，男，講師，研究方向?yàn)檩啓C(jī)管理。

U641.7

A