鄒春明， 趙俊超， 楊 柯， 徐言民， 高如江， 金 城， 陳 敏

(武漢理工大學(xué) 內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室， 武漢 430063)

ZOU Chunming， ZHAO Junchao, YANG Ke， XU Yanmin， GAO Rujiang， JIN Cheng， CHEN Min

基于懲罰-PSO的群橋水域多約束航路規(guī)劃

鄒春明， 趙俊超， 楊 柯， 徐言民， 高如江， 金 城， 陳 敏

(武漢理工大學(xué) 內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室， 武漢 430063)

為保障群橋水域通航安全和橋梁自身安全，以長江武漢段橋梁為研究對(duì)象，分析群橋水域通航環(huán)境特征，得出群橋水域具有橋梁間距小、通航孔交錯(cuò)分布、橋梁軸線不平行和交通流復(fù)雜等結(jié)論。在此基礎(chǔ)上，建立群橋水域通航環(huán)境模型，以航路長度代價(jià)、礙航物礙航代價(jià)和航路平滑代價(jià)為目標(biāo)建立群橋水域航路規(guī)劃代價(jià)模型，從船舶操縱性角度分析群橋水域船舶航路規(guī)劃的約束條件，分別采用內(nèi)罰-PSO和外罰-PSO方法實(shí)現(xiàn)群橋水域多約束航路規(guī)劃，規(guī)劃出船舶在給定條件下的最優(yōu)航路。通過對(duì)比分析發(fā)現(xiàn)，內(nèi)罰-PSO算法無論是在求解精度上還是收斂速度上均略優(yōu)于外罰-PSO算法，可很好地應(yīng)用于群橋水域航路規(guī)劃研究中。

水路運(yùn)輸；群橋水域；環(huán)境建模；航路規(guī)劃；內(nèi)罰-PSO；外罰-PSO

ZOUChunming，ZHAOJunchao,YANGKe，XUYanmin，GAORujiang，JINCheng，CHENMin

Abstract: For navigation safety in multi-bridge waters and the safety of the bridges, as the illustrative example, the Wuhan section of the Yangtze River are investigated, which reveals the characteristics of the area: small bridge interval, zigzag distribution of bridge navigation holes, unparallel bridge axis and complex traffic flow. The environment model of the multi-bridge area is built and the route cost model is established factoring in the costs associated with the route length, the hinder degree and the smoothness of the path. The multi constraints of the route planning are set based on maneuverability of the ship. The algorithms for interior penalty PSO and exterior penalty PSO are used to solve the route planning cost model respectively. The results show that either penalty PSO algorithm works but the interior penalty PSO has better performance than exterior penalty PSO in both calculation precision and convergence speed.

Keywords: waterway transportation; multi-bridge water area; environment modeling; route planning; interior penalty PSO; exterior penalty PSO

隨著我國沿江省市經(jīng)濟(jì)高速發(fā)展，大量跨江橋梁呈集群化建設(shè)，以近距離多橋梁為特征的群橋河段已在多個(gè)水域形成。目前船撞橋事故時(shí)有發(fā)生，研究群橋水域通航安全問題的必要性日益凸顯。由于橋梁集群建設(shè)的情況是近幾年才出現(xiàn)的，且群橋水域正在形成，因此在國內(nèi)外針對(duì)橋區(qū)通航安全的研究[1-3]中，有關(guān)群橋水域通航安全的研究尚未系統(tǒng)化，有關(guān)航路規(guī)劃的研究主要集中在機(jī)器人[4]和無人機(jī)[5]方面，而有關(guān)船舶航路規(guī)劃[6]，尤其是限制水域航路規(guī)劃的研究相對(duì)較少。隨著自動(dòng)控制技術(shù)不斷發(fā)展，對(duì)橋梁船舶自主航行理論體系進(jìn)行研究是提高橋區(qū)船舶通航安全的關(guān)鍵。對(duì)此，結(jié)合群橋水域通航環(huán)境特點(diǎn)，開展群橋水域航路規(guī)劃研究，為實(shí)現(xiàn)群橋水域船舶自主航行提供理論支撐。

1 航路規(guī)劃建模

1.1群橋水域通航環(huán)境特征分析

群橋水域最突出的特征是橋梁與橋梁的間隔較小。橋梁通航孔交錯(cuò)也是群橋水域的一個(gè)重要特點(diǎn)。由于不同橋梁所處的地理位置、水文等要素、建造年份及設(shè)計(jì)理念不同，群橋水域橋梁通航孔跨度不盡相同，通航孔交錯(cuò)現(xiàn)象十分明顯；受長江水流方向變化、水文條件變化、深泓變化、兩岸地理?xiàng)l件及交通規(guī)劃等因素影響，不同橋梁軸線一般不會(huì)在同一個(gè)方向上。此外，群橋河段交通流量較大，航道內(nèi)可能會(huì)存在礁石、沉船等障礙物，客觀上增大了群橋水域船舶航行的難度。

1.2群橋水域環(huán)境建模

為簡(jiǎn)化計(jì)算，對(duì)長度和距離等變量進(jìn)行無量綱化處理。在計(jì)算過程中，可將距離和長度等變量除以船長實(shí)現(xiàn)無量綱化，因此需要選取適當(dāng)?shù)拇妥鳛闊o量綱化基準(zhǔn)。這里選取內(nèi)河3 000噸級(jí)船舶為代表船型，其長度L為110 m。選擇長江武漢段4座橋梁進(jìn)行建模，并在模型中設(shè)置2處沉船，其安全半徑取2L。結(jié)合研究目的，暫時(shí)不考慮群橋水域交通流影響。群橋水域船舶通航環(huán)境模型見圖1。

圖1 群橋水域船舶通航環(huán)境模型

2 航路規(guī)劃代價(jià)函數(shù)建模

2.1代價(jià)函數(shù)選取

船舶航行時(shí)需考慮燃油和障礙物等信息，航路規(guī)劃的主要任務(wù)是尋找一條從起始點(diǎn)(xs,ys)到目標(biāo)點(diǎn)(xf,yf)的航程最短且與障礙物無碰撞的路徑。

2.1.1航路長度代價(jià)

為方便計(jì)算，首先將航路規(guī)劃問題轉(zhuǎn)化為求多維函數(shù)極值問題，將原坐標(biāo)轉(zhuǎn)換為以航路規(guī)劃起始點(diǎn)和目標(biāo)點(diǎn)連線為橫軸的新坐標(biāo)系x′Oy′，θ為原坐標(biāo)系xOy與新坐標(biāo)系x′Oy′的夾角。轉(zhuǎn)換關(guān)系為

(1)

將起始點(diǎn)與目標(biāo)點(diǎn)的連線分為d+1份，在每個(gè)等分點(diǎn)處作橫軸的垂線，從起始點(diǎn)到目標(biāo)點(diǎn)按順序取各垂線上的任意一點(diǎn)組成一個(gè)船舶航路序列點(diǎn)，根據(jù)航路點(diǎn)縱坐標(biāo)組成的向量y=(ys，y1，y2，…，yd，yf)即可確定一條唯一的路徑。

當(dāng)船舶沿著航路Lij航行時(shí)，船舶的航路長度代價(jià)J1的計(jì)算模型為

(2)

2.1.2礙航物礙航代價(jià)

當(dāng)障礙物中心與該段航路距離大于安全半徑時(shí)，N個(gè)障礙物對(duì)其產(chǎn)生的總礙航代價(jià)J2為

(3)

式(2)中：點(diǎn)(x,y)為障礙物(xs,ys)在相鄰路徑點(diǎn)上的投影；式中分母為障礙物中心與當(dāng)前航路段間的距離。

若障礙物中心與該邊的距離小于安全半徑，則再將各段航路分10段，取相應(yīng)的點(diǎn)計(jì)算產(chǎn)生的礙航代價(jià)。障礙物礙航代價(jià)示意見圖2。

圖2 障礙物礙航代價(jià)示意

礙航代價(jià)的計(jì)算式為

(4)

式(4)中：Lij為連接點(diǎn)i與j間的距離；d0.1,k為Lij邊上的1/10分點(diǎn)與第k個(gè)障礙物中心間的距離。

2.1.3航路平滑代價(jià)

2.2約束條件分析

船舶在橋區(qū)航行時(shí)會(huì)受到航道條件、氣象水文條件、船舶操縱性和交通流條件等條件限制，群橋水域船舶航路規(guī)劃的約束條件應(yīng)有多種。由于氣象水文條件和交通流條件屬于動(dòng)態(tài)變量，因此這里只考慮可航水域邊界和船舶操縱性等靜態(tài)約束條件。

2.2.1可航水域邊界

在航船舶受水動(dòng)力影響會(huì)產(chǎn)生一定的下沉量，因此除考慮本船的吃水情況以外，還須考慮留有一定的富余水深。由于內(nèi)河水域的等深線均為不規(guī)則曲線，因此很難找到精確的可航水域邊界。這里將可航水域邊界簡(jiǎn)化為2條直線，直線中間的區(qū)域即為船舶可航水域。各航路規(guī)劃點(diǎn)的縱坐標(biāo)所對(duì)應(yīng)的邊界值分別記作ylb和yup。

2.2.2轉(zhuǎn)向角

由于船舶自身慣性較大，因此其在受限水域一旦開始轉(zhuǎn)向?qū)⒑茈y及時(shí)停止。轉(zhuǎn)向角過大會(huì)導(dǎo)致船舶不得不通過操較大的舵角來控制該局面，而內(nèi)河可航水域范圍相對(duì)較小，一旦所操舵角過大而又回舵不及時(shí)，將導(dǎo)致船舶駛出航道或造成其他危險(xiǎn)。因此，在航路規(guī)劃時(shí)應(yīng)保證規(guī)劃航路的轉(zhuǎn)向角限制在一定的范圍內(nèi)。這里將轉(zhuǎn)向角臨界值記為θ0。

2.2.3相鄰轉(zhuǎn)向點(diǎn)距離

船舶對(duì)舵令的響應(yīng)速度受其追隨性影響，追隨性越差，船舶在操舵后開始變向所需的時(shí)間和轉(zhuǎn)向后停止轉(zhuǎn)向所需的時(shí)間越長；此外，船舶從左舵轉(zhuǎn)為右舵時(shí)，其轉(zhuǎn)艏角速度方向變化會(huì)滯后于舵角變化。因此，船舶相鄰轉(zhuǎn)向點(diǎn)間的距離應(yīng)存在一個(gè)臨界值，該臨界值能保證船舶剛好從第1個(gè)轉(zhuǎn)向點(diǎn)順利地轉(zhuǎn)到第2個(gè)轉(zhuǎn)向點(diǎn)。這里將該臨界值記為L0。

2.3航路代價(jià)建模

航路規(guī)劃目標(biāo)函數(shù)包括航路長度、礙航和航路光滑代價(jià)函數(shù)，該問題嚴(yán)格來講屬于多目標(biāo)優(yōu)化問題。目前求解多目標(biāo)優(yōu)化問題的方法主要分為基于單目標(biāo)的多目標(biāo)優(yōu)化和基于啟發(fā)式方法的多目標(biāo)方法2類[7-8]，其中基于單目標(biāo)的多目標(biāo)優(yōu)化方法主要通過應(yīng)用某些已知的知識(shí)將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，通過求解轉(zhuǎn)化后的單目標(biāo)問題得到一個(gè)多目標(biāo)最優(yōu)解，常見的方法有加權(quán)法、約束法、目標(biāo)規(guī)劃法和極大極小法等。這里結(jié)合所研究的目標(biāo)，選擇加權(quán)法處理航路規(guī)劃問題。若將航路長度代價(jià)權(quán)重記作k1，將礙航代價(jià)權(quán)重記作k2，則相鄰航段夾角標(biāo)準(zhǔn)差在目標(biāo)函數(shù)中所占的比重為1-(k1+k2)，優(yōu)化后的群橋水域航路規(guī)劃目標(biāo)函數(shù)為

minJ=k1J1+k2J2+(1-k1-k2)σ

(5)

根據(jù)以上模型求解所得的最小值即為航路規(guī)劃的最優(yōu)值，該最優(yōu)值表示沿當(dāng)前航路航行時(shí)船舶和經(jīng)過障礙物的最近距離的倒數(shù)與航程之和最小，且航路最光滑。在安全的基礎(chǔ)上，該值越小表示航路越優(yōu)。

3 PF-PSO航路規(guī)劃

內(nèi)點(diǎn)懲罰函數(shù)法和外點(diǎn)懲罰函數(shù)法[9-10]是目前常用的2種約束處理方法。這里可航水域邊界上限由點(diǎn)(5，20)與(69，40)之間的線段確定，可航水域邊界下限由點(diǎn)(5，10)與(69，30)之間的線段確定，船舶轉(zhuǎn)向角臨界值設(shè)為30°；將>10°的相鄰航段夾角的頂點(diǎn)看作船舶的轉(zhuǎn)向點(diǎn)，相鄰轉(zhuǎn)向點(diǎn)間的臨界距離設(shè)定為8倍船長。為簡(jiǎn)便，分別將2種處理方法簡(jiǎn)稱為內(nèi)罰-PSO算法和外罰-PSO算法。

3.1內(nèi)罰-PSO航路規(guī)劃

內(nèi)點(diǎn)懲罰函數(shù)主要通過逐步縮小懲罰因子系數(shù)使目標(biāo)函數(shù)中懲罰項(xiàng)隨迭代次數(shù)增加對(duì)整個(gè)目標(biāo)函數(shù)的影響程度逐漸減小，函數(shù)逐漸收斂于最優(yōu)解。采用內(nèi)點(diǎn)懲罰函數(shù)的方法對(duì)多約束群橋水域航路規(guī)劃目標(biāo)函數(shù)進(jìn)行處理，構(gòu)造懲罰函數(shù)為

minPF=k1J1+(1-k1)J2+(1-k1-k2)σ+

(6)

初始懲罰因子通常可取0.1和0.01等值，經(jīng)試驗(yàn)，初始懲罰因子取0.1和0.01時(shí)算法的求解精度和收斂代數(shù)并未出現(xiàn)顯著變化。這里初始懲罰因子選擇0.1，運(yùn)用PSO算法對(duì)模型進(jìn)行求解，航路規(guī)劃結(jié)果和收斂情況分別見圖3和圖4。

圖3 內(nèi)罰函數(shù)航路規(guī)劃結(jié)果

圖4 內(nèi)罰函數(shù)航路規(guī)劃迭代曲線

由圖3可知，運(yùn)用內(nèi)罰-PSO算法求得的全局最優(yōu)值為42.48，算法大約在130次迭代之后即進(jìn)入穩(wěn)定收斂，收斂速度較快。

3.2外罰-PSO航路規(guī)劃

外點(diǎn)懲罰函數(shù)主要通過逐步擴(kuò)大懲罰因子系數(shù)使目標(biāo)函數(shù)中的懲罰部分隨迭代次數(shù)增加對(duì)不符合約束條件解的懲罰作用越來越大，在迭代中逐步被淘汰，函數(shù)迭代所求解逐步向最優(yōu)解靠攏。對(duì)群橋水域多約束航路規(guī)劃目標(biāo)函數(shù)進(jìn)行處理，當(dāng)所求解滿足約束條件時(shí)，目標(biāo)函數(shù)由式(4)計(jì)算；當(dāng)不滿約束條件時(shí)，目標(biāo)函數(shù)為

minPF=k1J1+(1-k1)J2+(1-k1-k2)×

(7)

經(jīng)多次驗(yàn)證，初始懲罰因子暫取2。運(yùn)用PSO算法求解，航路規(guī)劃結(jié)果和收斂情況分別見圖5和圖6。

圖5 外罰函數(shù)航路結(jié)果

圖6 外罰函數(shù)航路規(guī)劃迭代曲線

由圖5可知，運(yùn)用外罰-PSO算法求得的全局最優(yōu)值為42.697，算法約在145次迭代之后進(jìn)入穩(wěn)定收斂，收斂速度和求解精度均能滿足計(jì)算要求。

3.3懲罰函數(shù)PSO航路規(guī)劃結(jié)果分析

由算例可知，內(nèi)罰-PSO算法和外罰-PSO算法均可搜尋到多種約束條件下的船舶最優(yōu)航路。由于最優(yōu)航路是通過求解代價(jià)函數(shù)的最小值得到的，因此求解所得值越小，認(rèn)為其求解精度越高。內(nèi)罰-PSO算法平均在110～130次迭代之后即進(jìn)入穩(wěn)定收斂，平均全局最優(yōu)值為42.39；6次運(yùn)行中外罰-PSO算法平均在120～150次迭代之后即進(jìn)入穩(wěn)定收斂，平均全局最優(yōu)值為42.56。2種處理方法的運(yùn)行時(shí)間幾乎相等，內(nèi)罰-PSO算法的平均收斂代數(shù)及所求最優(yōu)值略小于外罰-PSO算法，其無論是在收斂速度上還是求解精度上的表現(xiàn)均略優(yōu)于外罰-PSO算法。

4 結(jié)束語

以提高群橋水域通航安全為目標(biāo)，以航路規(guī)劃為切入點(diǎn)，分析群橋水域通航環(huán)境特征，建立群橋水域航路代價(jià)模型，并從船舶操縱性角度分析群橋水域船舶航路規(guī)劃的約束條件，建立多約束群橋水域航路規(guī)劃代價(jià)函數(shù)。分別采用內(nèi)罰-PSO和外罰-PSO算法實(shí)現(xiàn)群橋水域多約束航路規(guī)劃，并對(duì)所求解進(jìn)行對(duì)比分析，得出內(nèi)罰-PSO算法無論是在求解精度上還是收斂速度上均略優(yōu)于外罰-PSO算法的結(jié)論。此外，暫未考慮群橋水域內(nèi)交通流對(duì)規(guī)劃航路的影響，后期可考慮開展動(dòng)態(tài)環(huán)境群橋水域航路規(guī)劃的研究。

[1] 邱野. 順直及彎曲河道條件下橋群合理間距的分析[D]. 長沙：長沙理工大學(xué), 2011.

[2] 陳明. 山區(qū)河流橋群河段橋梁跨度與間距對(duì)通航影響的研究[D]. 重慶：重慶交通大學(xué), 2010.

[3] 林巧. 重慶菜園壩橋群河段橋梁間距與通航條件研究[D]. 重慶：重慶交通大學(xué), 2010.

[4] ASADI S, AZIMIRAD V, ESUAMI, et al. Immune-Wavelet Optimization for Path Planning of Large-Scale Robots[J]. Robotica, 2014, 32(1): 77-95.

[5] ALTMANN A, NIENDORF M, BEDNAR M, et al. Improved 3D Interpolation-Based Path Planning for a Fixed-Wing Unmanned Aircraft[J]. Theory and Applications, 2013，76(1): 185-191.

[6] KUCZKOWSKI L, SMIERZCHALSKI R. Comparison of Single and Multi-Population Evolutionary Algorithm for Path Planning in Navigation Situation[J]. Solid State Phenomena, 2014，210: 166-177.

[7] 劉慧慧. 一種改進(jìn)的粒子群多目標(biāo)優(yōu)化算法研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2015(1): 87-90.

[8] 厙向陽, 蔡院強(qiáng), 董立紅. 新的基于多目標(biāo)優(yōu)化的推薦算法[J]. 計(jì)算機(jī)應(yīng)用, 2015，35(1): 162-166.

[9] 司呈勇, 蘭天, 胡俊杰，等. 關(guān)于懲罰函數(shù)中懲罰系數(shù)的討論[J]. 控制與決策, 2014，29(9): 1707-1710.

[10] 李宜萱, 金治群, 程軍蕊，等. 一種基于AEA算法的改進(jìn)的懲罰函數(shù)法[J]. 計(jì)算機(jī)與應(yīng)用化學(xué), 2014，31(12): 1479-1484.

RoutePlanninginMulti-BridgeWaterAreaUnderMultiConstraintsBasedonPenalty-PSO

(Hubei Inland Shipping Technology Key Laboratory, Wuhan University of Technology, Wuhan 430063, China)

U612.1

A

2016-02-26

國家自然科學(xué)基金(51109173)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(2013-Ⅱ-019)

鄒春明(1969—)，男，湖北云夢(mèng)人，船長，主要從事智能航海相關(guān)研究工作。E-mail:1842645227@qq.com

1000-4653(2016)02-0067-04