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

馮明波

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

?

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

馮明波

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

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

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

0 引言

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

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

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

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

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

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

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

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

1.1 變量與符號(hào)定義

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

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

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

Ll、Wl：船閘矩形的長(zhǎng)、寬；

li、wi：船舶i矩形的長(zhǎng)、寬；

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

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

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

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

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

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

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

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

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

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

1.2 約束條件

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

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)識(shí)，其計(jì)算比較復(fù)雜，以下給出詳細(xì)計(jì)算過(guò)程：

為簡(jiǎn)化分析過(guò)程，假定以船舶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)識(shí)，可統(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è)變量取值序號(hào)一一對(duì)應(yīng))從而組成4個(gè)公式。其中xLUi,j、xRDi,j、yLUi,j和yRDi,j分別表示船舶i矩形的左上角和右下角點(diǎn)的X和Y坐標(biāo)。

對(duì)于船舶i2矩形的4個(gè)角點(diǎn)均未落入船舶i1矩形區(qū)域內(nèi)的情況，又分為2種情況：一是船舶i2在橫向跨度(X方向)上包含i1在橫向上的跨度區(qū)域(對(duì)應(yīng)于式(12)的WInci1,i2)；二是船舶i2在縱向跨度(Y方向)上包含i1在縱向上的跨度區(qū)域(對(duì)應(yīng)于式(12)的LInci1,i2)。如果2種情況均滿(mǎn)足，則對(duì)應(yīng)于船舶i2將船舶i1包含在其矩形框內(nèi)(對(duì)應(yīng)于式(12)的AInci1,i2)。而情況1與情況2的區(qū)別僅在于判斷方向?yàn)閄軸還是Y軸，因此下面僅以情況1(即WInci1,i2的計(jì)算)為例展開(kāi)分析。滿(mǎn)足情況1的兩船關(guān)系又分為4種情形，其中3種情形如圖1所示(第4種情形為船舶i2將船舶i1包含在其矩形框內(nèi))。圖中實(shí)形框?yàn)榇癷1，3個(gè)虛形框分別對(duì)應(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è)是從用戶(hù)的角度出發(fā)，要求所有船舶的等待調(diào)度時(shí)間盡量短。為了簡(jiǎn)便計(jì)算，在此僅考慮船舶在本調(diào)度周期內(nèi)等待的時(shí)間：

(19)

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

(20)

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

本文建立的船閘調(diào)度模型是典型的NP-hard問(wèn)題，目前遺傳算法、蟻群算法和粒子群算法等智能搜索算法在該類(lèi)問(wèn)題的求解得到了廣泛應(yīng)用并取得了良好的效果。本文建立的船閘調(diào)度模型是一個(gè)多目標(biāo)調(diào)度問(wèn)題，針對(duì)這類(lèi)問(wèn)題一種簡(jiǎn)單的方式是采用加權(quán)求和的方式將多目標(biāo)調(diào)度轉(zhuǎn)化成單目標(biāo)調(diào)度問(wèn)題，但是正如上一節(jié)所介紹，本調(diào)度問(wèn)題所提出的2個(gè)指標(biāo)分別從航運(yùn)管理部門(mén)和用戶(hù)角度出發(fā)，二者之間在某種程度上存在一定的沖突，難以確定相對(duì)權(quán)值，該方法存在一定限制。目前針對(duì)多目標(biāo)調(diào)度問(wèn)題應(yīng)用比較多的是多目標(biāo)遺傳算法，如NPGA、NSGA和NSGA-II，以及SPEA和SPEA-II等[2-5]。其中SPEA基于Pareto支配理論進(jìn)行設(shè)計(jì)，基于“支配個(gè)體所有Pareto解所支配個(gè)體的數(shù)量總和”這一隱含信息對(duì)個(gè)體周?chē)拿芏冗M(jìn)行評(píng)價(jià)，能夠避免設(shè)置其他算法涉及的小生境參數(shù)這一難題[6]。本文基于SPEA算法對(duì)多目標(biāo)船閘調(diào)度問(wèn)題進(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è)三元組，對(duì)應(yīng)于1艘船的調(diào)度閘次、在該閘次中安排在船閘的X和Y坐標(biāo)。染色體長(zhǎng)度為3×M，且基因取值-1的大幅度減少。在交叉和變異計(jì)算時(shí)，以1個(gè)三元組基因?yàn)閱挝贿M(jìn)行。

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

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

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

step2:在剩余閘次的空間資源內(nèi)對(duì)船舶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)更新至染色體對(duì)應(yīng)的位置中，進(jìn)入step3；否則進(jìn)入step2.3；

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

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

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

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

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

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

(21)

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

2.3.2 交叉和變異算子

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

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

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

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

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

本文基于VC6.0對(duì)提出的模型與算法進(jìn)行了實(shí)現(xiàn)，算法運(yùn)行在IntelCorei7 2.5GHz平臺(tái)下，內(nèi)存為4.0GB，操作系統(tǒng)為Win10。為了模擬多種規(guī)模的船舶調(diào)度問(wèn)題，船舶數(shù)量和尺寸、船閘尺寸等在給定區(qū)間內(nèi)隨機(jī)取值。為了對(duì)算法進(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ì)的求解算法序號(hào)為1，貪婪算法序號(hào)為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é)果見(jiàn)表1。

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

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

3 結(jié)論

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

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

[2] 馮明月,李國(guó)輝,易先清，等. 一種求解多目標(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