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

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

(武漢理工大學 內河航運技術湖北省重點實驗室， 武漢 430063)

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

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

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

(武漢理工大學 內河航運技術湖北省重點實驗室， 武漢 430063)

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

水路運輸；群橋水域；環境建模；航路規劃；內罰-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

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

1 航路規劃建模

1.1群橋水域通航環境特征分析

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

1.2群橋水域環境建模

為簡化計算，對長度和距離等變量進行無量綱化處理。在計算過程中，可將距離和長度等變量除以船長實現無量綱化，因此需要選取適當的船型作為無量綱化基準。這里選取內河3 000噸級船舶為代表船型，其長度L為110 m。選擇長江武漢段4座橋梁進行建模，并在模型中設置2處沉船，其安全半徑取2L。結合研究目的，暫時不考慮群橋水域交通流影響。群橋水域船舶通航環境模型見圖1。

圖1 群橋水域船舶通航環境模型

2 航路規劃代價函數建模

2.1代價函數選取

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

2.1.1航路長度代價

為方便計算，首先將航路規劃問題轉化為求多維函數極值問題，將原坐標轉換為以航路規劃起始點和目標點連線為橫軸的新坐標系x′Oy′，θ為原坐標系xOy與新坐標系x′Oy′的夾角。轉換關系為

(1)

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

當船舶沿著航路Lij航行時，船舶的航路長度代價J1的計算模型為

(2)

2.1.2礙航物礙航代價

當障礙物中心與該段航路距離大于安全半徑時，N個障礙物對其產生的總礙航代價J2為

(3)

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

若障礙物中心與該邊的距離小于安全半徑，則再將各段航路分10段，取相應的點計算產生的礙航代價。障礙物礙航代價示意見圖2。

圖2 障礙物礙航代價示意

礙航代價的計算式為

(4)

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

2.1.3航路平滑代價

2.2約束條件分析

船舶在橋區航行時會受到航道條件、氣象水文條件、船舶操縱性和交通流條件等條件限制，群橋水域船舶航路規劃的約束條件應有多種。由于氣象水文條件和交通流條件屬于動態變量，因此這里只考慮可航水域邊界和船舶操縱性等靜態約束條件。

2.2.1可航水域邊界

在航船舶受水動力影響會產生一定的下沉量，因此除考慮本船的吃水情況以外，還須考慮留有一定的富余水深。由于內河水域的等深線均為不規則曲線，因此很難找到精確的可航水域邊界。這里將可航水域邊界簡化為2條直線，直線中間的區域即為船舶可航水域。各航路規劃點的縱坐標所對應的邊界值分別記作ylb和yup。

2.2.2轉向角

由于船舶自身慣性較大，因此其在受限水域一旦開始轉向將很難及時停止。轉向角過大會導致船舶不得不通過操較大的舵角來控制該局面，而內河可航水域范圍相對較小，一旦所操舵角過大而又回舵不及時，將導致船舶駛出航道或造成其他危險。因此，在航路規劃時應保證規劃航路的轉向角限制在一定的范圍內。這里將轉向角臨界值記為θ0。

2.2.3相鄰轉向點距離

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

2.3航路代價建模

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

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

(5)

根據以上模型求解所得的最小值即為航路規劃的最優值，該最優值表示沿當前航路航行時船舶和經過障礙物的最近距離的倒數與航程之和最小，且航路最光滑。在安全的基礎上，該值越小表示航路越優。

3 PF-PSO航路規劃

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

3.1內罰-PSO航路規劃

內點懲罰函數主要通過逐步縮小懲罰因子系數使目標函數中懲罰項隨迭代次數增加對整個目標函數的影響程度逐漸減小，函數逐漸收斂于最優解。采用內點懲罰函數的方法對多約束群橋水域航路規劃目標函數進行處理，構造懲罰函數為

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

(6)

初始懲罰因子通常可取0.1和0.01等值，經試驗，初始懲罰因子取0.1和0.01時算法的求解精度和收斂代數并未出現顯著變化。這里初始懲罰因子選擇0.1，運用PSO算法對模型進行求解，航路規劃結果和收斂情況分別見圖3和圖4。

圖3 內罰函數航路規劃結果

圖4 內罰函數航路規劃迭代曲線

由圖3可知，運用內罰-PSO算法求得的全局最優值為42.48，算法大約在130次迭代之后即進入穩定收斂，收斂速度較快。

3.2外罰-PSO航路規劃

外點懲罰函數主要通過逐步擴大懲罰因子系數使目標函數中的懲罰部分隨迭代次數增加對不符合約束條件解的懲罰作用越來越大，在迭代中逐步被淘汰，函數迭代所求解逐步向最優解靠攏。對群橋水域多約束航路規劃目標函數進行處理，當所求解滿足約束條件時，目標函數由式(4)計算；當不滿約束條件時，目標函數為

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

(7)

經多次驗證，初始懲罰因子暫取2。運用PSO算法求解，航路規劃結果和收斂情況分別見圖5和圖6。

圖5 外罰函數航路結果

圖6 外罰函數航路規劃迭代曲線

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

3.3懲罰函數PSO航路規劃結果分析

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

4 結束語

以提高群橋水域通航安全為目標，以航路規劃為切入點，分析群橋水域通航環境特征，建立群橋水域航路代價模型，并從船舶操縱性角度分析群橋水域船舶航路規劃的約束條件，建立多約束群橋水域航路規劃代價函數。分別采用內罰-PSO和外罰-PSO算法實現群橋水域多約束航路規劃，并對所求解進行對比分析，得出內罰-PSO算法無論是在求解精度上還是收斂速度上均略優于外罰-PSO算法的結論。此外，暫未考慮群橋水域內交通流對規劃航路的影響，后期可考慮開展動態環境群橋水域航路規劃的研究。

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

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

[3] 林巧. 重慶菜園壩橋群河段橋梁間距與通航條件研究[D]. 重慶：重慶交通大學, 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]. 計算機技術與發展, 2015(1): 87-90.

[8] 厙向陽, 蔡院強, 董立紅. 新的基于多目標優化的推薦算法[J]. 計算機應用, 2015，35(1): 162-166.

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

[10] 李宜萱, 金治群, 程軍蕊，等. 一種基于AEA算法的改進的懲罰函數法[J]. 計算機與應用化學, 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

國家自然科學基金(51109173)；中央高校基本科研業務費專項資金(2013-Ⅱ-019)

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

1000-4653(2016)02-0067-04