基于改進A*算法的內河水網航線規劃及應用

潘明陽 劉乙賽 李琦 李超 陳志體

摘要：為避免船舶擱淺、撞橋等事故的發生，研究針對復雜內河水網的航線規劃算法及其應用模式。根據航道通航條件，設計內河水網的有向拓撲網絡，并從添加航道約束條件、優化代價函數和估價函數三個方面對A *算法進行改進，實現針對不同船舶參數的最優航線規劃。結合船舶助航APP研究航線規劃算法的應用方法，并以東莞水系為場景進行算法測試。結果表明，改進的A *算法能夠很好地應用于內河水網的航線規劃，而且可在手機移動終端高效運行。研究的航線規劃算法和應用模式對保障復雜水網的船舶航行安全具有重要的意義。

關鍵詞： 內河水網; 改進A *算法; 航線規劃; 船舶助航APP

中圖分類號： U697.31;TP399 ? ?文獻標志碼： A

Abstract： To avoid accidents such as ship grounding and ship bridge collision， a route planning algorithm and its application mode for complex inland waterway network are researched. According to waterway navigation conditions， a directed topological network for inland waterway network is designed， and the A * algorithm is improved from three aspects of adding channel constraint conditions， optimizing the cost function and the valuation function to realize the optimal route planning for different ship parameters.The route planning algorithm is applied in a ship navigation-aid APP， and is tested with Dongguan waterway network as the scene. The results show that the improved A * algorithm can be well applied to the route planning of the inland waterway network， and it can run efficiently in the mobile phone terminal. The route planning algorithm and its application mode are of great significance to ensure the ship navigation safety of complex waterway network.

Key words： inland waterway network; improved A * algorithm; route planning; ship navigation-aid APP

珠江水系是一個由西江、北江、東江和珠江三角洲諸河匯聚而成的復合水系，全長2 214 km，是我國境內第三長河流。珠江水系支流眾多，水道縱橫交錯，尤其是珠江三角洲諸河形成了稠密的水網，大小河流上百條。珠江水系的航道復雜多變，給通航船舶的航行安全帶來了很大的麻煩，水系內常常發生由駕駛員不熟悉航道特點所導致的擱淺和撞橋等事故。據不完全統計，2016—2017年珠江水系內發生大大小小的撞橋事故近十起，造成了重大的經濟損失和社會影響[1]。廣東內河航道和海事等管理部門為改善通航環境采取了諸多措施，尤其是近年來利用信息化手段，研發了數字航道、智慧海事監管平臺等系統，通過電子巡航等動態監管手段來保障航道的通航安全。然而到目前為止大多數研究是從監管的角度出發的，少有從船舶的角度出發專門研究如何合理規劃航線以更好地規避航行風險的。雖然不少在內河航行的船舶已經安裝了電子海圖系統，但這些設備存在著數據陳舊、無法獲取實時航道信息等問題，而且不具備根據最新數據進行航線規劃的功能。

以往關于航線規劃或設計的研究大多聚焦于海上航行，利用海圖水深、航道和障礙物等數據尋找出單條可通航航線，例如：李源惠等[2]提出了一種基于動態網格模型的航線自動生成方法，該方法利用電子海圖信息進行航線設計;張莉等[3]提出了一種基于電子海圖的航線多尺度生成方法，實現海圖航線的多尺度自動生成;范云生等[4]提出了一種基于電子海圖柵格化的全局路徑規劃方法，用于無人水面艇的全局路徑規劃。與這類非連通式場景不同，內河水系不僅形成了網絡結構，而且其不同航路的通航條件差異很大，因此內河水系路徑規劃面臨著更多的水上航行約束。路徑規劃是人工智能領域的一個重要研究領域，用于解決可拓撲為點線網絡的規劃問題，在移動機器人、無人機、地圖導航等領域應用廣泛。路徑規劃算法主要有人工勢場法、柵格法、遺傳算法、神經網絡算法和A *算法等[5]，其中A *算法以其高效的全局優化路徑搜索能力，在機器人路徑規劃[6-7]、駕車路徑規劃[8-9]、層次衛星網絡[10]等基于離散拓撲網絡的路徑規劃中發揮了重要作用。然而，目前在水上導航領域關于內河水網航線自動規劃的研究比較少見。

本文從為船舶服務的角度出發，根據船舶自身的條件（船舶高度、吃水等），結合航道通航條件（航道等級、水深和橋梁凈空高度等），應用A *算法為船舶智能地規劃出一條最優航線，并通過基于電子航道圖的船舶助航APP為船舶提供助航服務，以盡可能地避免船舶擱淺、撞橋等事故。

1 應用場景

本文研究的應用場景為珠江三角洲諸河中的東莞轄區，見圖1。東莞轄區位于珠江入海口，轄區內水網稠密，包括東江、東莞水道、太平水道、倒運海水道、中堂水道、麻涌水道、洪屋渦水道、大汾北水道、南丫水道、潢涌水道、寒溪河和大汾南水道等大小河流100多條，航道錯綜復雜，并呈網狀結構。此外，東莞轄區內航道還具有如下一些特點：（1）大多為天然航道，航道等級多，河床高程和可通航凈寬差異大;（2）航道直通入海，受上游季節性的豐枯水期影響以及下游海水的潮汐影響，水位變化復雜;（3）橋梁密集（例如東莞水道萬江橋至石龍南橋段約18 km的航道中有9座橋梁），而且大多數橋梁由于建造年代較早（最早的是1907年完工的），其通航凈空較小。

東莞轄區的航道內遍布港口、大橋和交叉口，不僅加大了船舶擱淺、撞橋等安全風險，而且容易導致船舶航線規劃不合理，造成貨運延誤，產生經濟損失。因此，如何有效地利用電子航道圖、航道維護尺度和橋梁監管等數據，更好地為通航船舶服務，從而提高轄區的通航安全和效率，成為東莞航道建設與管理的當務之急。

2 航線規劃算法

2.1 內河水網數據結構設計

為利用A *算法進行航線規劃，對東莞轄區的水網地理數據進行了重新設計和組織。如圖2（圖1中虛線框的局部放大）所示，將航道拆分為一個個航段（圖中的L1、L2、L3和L4），每個航段的端點（如圖中的沙田游艇俱樂部、楊公洲中、南大大橋、上屯和必潭州等）除了可能是航道交叉節點外，還可能是對應著碼頭（如圖中的烏沙洲頭、南大大橋、南角圍和陽南洲等）等可成為航線起止點的關鍵節點。此外每個航道還包含構成航段幾何形狀的普通轉向點（如圖中的W1、W2、W3、W4、W5、W6），以及在其間的橋梁（如圖中的東江大橋、南大大橋）。

整個水網的數據結構見圖3。圖3中，節點數據表用于存放節點信息，包括節點編號、節點名稱、節點類型（航道交叉點或碼頭）和節點位置（即經緯度坐標）等。如果節點類型為碼頭關鍵節點，可關聯其相應數據表獲取詳細信息。航段數據表存放由兩個節點組成的航段信息，包括航段編號、航段名稱、起點編號、終點編號、航段等級、維護水深、維護航寬、航段長度、交通管制狀態等。通過該表建立起整個水網的拓撲結構。轉向點數據表按順序存放每個航段從起點到終點的轉向點信息，包括轉向點編號和名稱、所屬航段編號、轉向點的經緯度坐標等，用于繪制完整的規劃航線。橋梁數據表存儲橋梁基本信息，包括編號、名稱、所在航段編號、凈空高度、橋孔寬度、橋梁的經緯度坐標等，并通過航段編號與航段進行關聯。

2.2 改進A *算法

A *算法是一種在靜態網絡中求解最短路徑最有效的方法，它不僅利用代價函數計算從出發節點開始的代價，而且利用估價函數計算當前節點到目標的期望代價，在綜合評估代價函數和估價函數后再進行全局最優的寬度優先搜索。A *算法是一種啟發式算法，其估價函數能夠將搜索導向目標節點，從而大大提升算法效率。然而，在蜿蜒曲折、復雜多變的內河水網中為船舶進行航線規劃，并不只是簡單的尋找最短路徑，而是找出能保障船舶安全通航的最優航線。因此，在利用A *算法進行航線規劃時，需要根據內河通航條件以及船舶的參數等具體約束對A *算法進行改進。

2.2.1 添加通航約束條件

根據船舶的吃水、船舶高度等信息，添加航道的通航約束條件，使不滿足通航條件的航道不參與航線規劃。增加的航道約束主要包括以下幾點：

（1）水深約束：如果航段維護水深小于船舶吃水與富余水深之和，則判斷該航段不滿足安全通航條件。

（2）凈高約束：如果航段中包含橋梁，而且只要有橋梁的凈高小于船舶高度與富余高度之和，或者橋孔寬度小于船舶寬度與富余寬度之和，則判斷該航段不滿足安全通航條件。

（3）交通規則約束：如果航段有水上交通規則管制，而且航道的可通航方向與規劃航線方向相背，則判斷該航段不滿足安全通航條件。

增加通航約束條件不僅滿足船舶在航道安全通行的最低要求，而且能過濾不符合通航條件的航段，減少水網搜索節點個數，提高搜索效率。

2.2.2 改進A *算法的代價函數

對于在內河中行駛的船舶，最短的航線不一定是最適合的，過橋或通過相對低等級的航段都意味著風險的提升。因此，根據航道特征對經典A *算法中只計算距離的代價函數進行改進，使得節點的代價變為航段等級、途經橋梁數量和距離的加權結果，改進后的代價函數如下：g（n）=ni=1（ω1Li+ω2Bi+ω3Ci）

（1）式中：n是待擴展節點;g（n）是從出發節點到節點n的代價;下標i代表從出發節點到節點n之間的節點序號;Li代表第i個節點與前一節點間航段的等級信息，按慣例其數值越低，航段等級越高，航道維護尺度越好，越有利于船舶安全通行;Bi代表第i個節點與前一節點間所包含的橋梁數量，數量越少意味著撞橋風險越小;Ci代表第i個節點與前一節點間的實際距離;ω1、ω2和ω3分別代表航段等級、橋梁數量和距離的權重值，滿足ω1+ω2+ω3=1，它們的具體數值通過不斷的實驗來確定。該代價函數的3項指標是同方向的作用關系，即：距離越短越好、橋梁數量越少越好、航段等級越低越好，而且它們的數值量級相差不大，避免出現權重不敏感問題。

2.2.3 改進A *算法的估價函數

2.3 基于改進A *算法的航線規劃

基于上述內河水網數據結構將東莞水系的航道組織為一個搜索區域，下面以沙田游艇俱樂部與必潭洲之間的航道（見圖4）為例，說明基于改進A *算法的航線規劃算法。

（1）確定航線規劃的起點和終點。圖4a中，設A和B分別為在地圖上選出的起點和終點。為在已設定的搜索區域進行路徑規劃，需要將A和B映射到水網中的節點，分別對應圖中的“沙田游艇俱樂部”和“必潭洲”，代表在搜索區域的出發節點和目標節點。該映射過程通過距離優先法來確定。

（2）基于A *算法，創建空的Open表和Closed表。Open表記錄所有在尋找最優航線時會被考慮的節點，Closed表記錄已經擴展過不會再被考慮的節點。在Open表中添加起點“沙田游艇俱樂部”。

（3）從Open表彈出第一個節點，判斷是否為目標節點，若是則規劃結束，否則將該節點放入Closed表并進行節點擴展，即從水網中獲取所有與它相鄰的節點（如圖4中的“烏沙洲頭”“楊公洲中”等）。

（4）對新擴展出的節點進行可否通航判斷。首先檢索出與新節點連接的航段，根據航道屬性與船舶屬性添加約束條件，判斷其通航屬性是否有該方向上的交通管制標記，若是則將新節點放入Closed表，否則放入Open表;其次，將航段的航道尺度屬性（維護水深）與船舶吃水進行比較，判斷船舶是否能夠安全通過該航段，若是則將新節點放入Open表，否則放入Closed表;最后，檢索出該航段上所有橋梁的實時信息包括基于水位變化的凈空高度和凈寬，比較船舶高度與橋梁凈空高度、船舶寬度與橋梁凈寬，如果滿足通航要求則將新節點放入Open表，否則放入Closed表。如圖4b中：“沙田游艇俱樂部”與“烏沙洲頭”之間的航段，由于等級太低，水深小于船舶2 m吃水，不滿足通航要求，因此將節點“烏沙洲頭”放入Closed表;節點“楊公洲中”滿足通航條件，因此將其放入Open表。

（5）設定估價函數（見圖4c）。根據改進的代價函數和估計代價函數計算Open表中每個節點的估價函數值f，f=g+h，其中：g為從起始節點到該節點的實際距離與航道等級、航道包含的橋梁數量的加權結果，加權方法見式（1）;h為從該節點到目標節點的估計距離，計算方法見式（3）。然后，對Open表中的節點按估價函數值由小到大的順序進行排序。

（6）跳轉到第3步進行循環，直到目標節點出現，找到最優航線，或者直到Open表為空，航線規劃失敗。航線規劃結果如圖4d所示。

2.4 算法效率對比分析

為驗證上述航線規劃算法的效率，設計經典A *算法和只添加航道約束條件的A *算法進行對比。對比測試時，對于同樣的條件，隨機選取20組起點和終點，分別利用3種算法進行航線規劃，然后對比在利用3種算法進行航線規劃的過程中搜索的節點總數、規劃航線中包含的橋梁數量、規劃航線中航道的等級，結果見表1。

由表1可知，對A *算法添加航道約束條件，可以使航線規劃時搜索的節點總數大大減少，從而大幅度提高搜索效率。而且，如果進一步改進估價函數，優先考慮包含的橋梁數量少、平均等級高的航道，并優化啟發信息，則可以在提高搜索效率的同時規劃出更加合理和安全的航線。

3 智能航線規劃應用

3.1 系統架構

基于上述航線規劃算法，開發“東莞航道公共信息服務”船舶助航APP，進行應用和驗證。如圖5所示，系統包括服務器和APP客戶端。服務器端運行東莞航道指揮監測系統，維護東莞航道基本數據，包括航道基礎信息、電子航道圖和航道水網數據，其中橋梁的實時凈空和凈寬數據隨水位變化實時更新。為支撐航道公共信息服務，服務端還提供各類航道信息的Web Service數據接口。APP客戶端基于Android開發，從服務器端的Web Service接口獲取數據，并完成助航和信息服務功能。為支持離線應用，APP客戶端可對電子航道圖、航道水網和橋梁等基礎信息進行前端緩存，當服務器端更新數據后進行下載提醒。

在規劃航線時，船舶用戶需要輸入起點、終點、船寬、船高和吃水等參數。如果APP客戶端聯網，則基于服務器端最新的數據利用上述航線規劃算法獲取最優航線;如果APP客戶端離線，則基于緩存數據進行航線規劃，但由于無法獲取實時橋梁凈空和凈寬數據，所得航線無法體現水位的影響。

3.2 APP應用效果

如圖6a所示，APP具有航道圖瀏覽、導航規劃和其他信息服務功能。如圖6b所示，在進行航線規劃時，用戶既可以從節點列表中選擇起點和終點，也可以在航道圖上點選，系統會自動將其映射到對應的節點。如圖6c所示，規劃出的航線將顯示在電子航道圖上，且規劃航線上的橋梁標識有凈空高度信息。組成航線的所有航段以表格形式展示，可顯示各航段等級、水深和航寬等詳細信息。一旦開始導航，系統將實時進行語音提醒，包括航向航速提醒、航道交叉口提醒、橋梁提醒等。

3.3 APP航線規劃效率分析

為驗證改進的A *算法在APP客戶端的航線規劃效率，采用3部不同配置的手機（見表2）進行測試。選取珠江水系東莞轄區的水網數據（表3）進行航線規劃。

由圖7可見，本文提出的航線規劃算法可在主流配置的手機移動終端高效運行，即使手機的配置較低，對于東莞轄區內的任何航線規劃都能在毫秒的時間量級上完成。

與傳統的ECS（electronic chart system，電子海圖系統）相比，船舶助航APP不僅成本低廉，而且推廣和普及速度極快，可迅速地將最新航道信息提供給水域內的所有船舶并為之提供助航服務。目前船舶助航APP已經在東莞航道局轄區試運行，為該區域航行的船舶提供航道公共信息服務，取得了良好的社會反響。

4 結 論

本文針對內河水系特點，從為船舶服務的角度出發，研究了內河航線規劃算法并進行了應用。研究結果表明：充分考慮航海特色對內河水網數據進行精心設計，諸如對成熟的路徑規劃算法——A *算法稍加改進，可以解決內河水網的航線規劃問題，從而為船舶提供更智能的助航服務，避免擱淺、撞橋等事故，更好地保障船舶航行安全;改進算法能夠在配置較低的手機終端上高效運行，通過APP的形式進行應用，并以最快的速度、最方便的渠道進行普及和推廣。

目前，針對海上智能船舶、無人駕駛船舶已經開展了一系列的研究[11]，內河船舶的智能化和無人駕駛亦將成為后續的研究熱點，航線自動規劃也將是其中最為關鍵的技術之一。圍繞智能航線規劃，后續可以做的研究有：進行航線規劃算法的優化以適應更大范圍水域（如整個珠江水系）的應用;結合人工智能的其他技術不斷完善算法的實用性和智能性，如研究潮汐和水位預測模型，結合船舶航速更準確地計算船舶航行至橋梁附近時的凈空高度和寬度，從而更好地滿足船舶借助潮汐進行通航的需求，或者基于AIS數據評估和預測航道擁堵情況并作為估價函數的考慮因子，以更好地滿足實時性的需求。

參考文獻：

[1] 余丹亞.偶發的船撞橋事件背后的必然性分析[J].珠江水運， 2018（5）： 101-103. DOI： 10.14125/j.cnki.zjsy.2018.05.051.

[2] 李源惠， 潘明陽， 吳嫻.基于動態網格模型的航線自動生成算法[J].交通運輸工程學報， 2007， 7（3）： 34-39.

[3] 張莉， 金一丞， 汪柱， 等.電子海圖的航線多尺度生成方法[J].測繪科學， 2011， 36（5）： 197-199. DOI： 10.16251/j.cnki.1009-2307.2011.05.022.

[4] 范云生， 趙永生， 石林龍， 等.基于電子海圖柵格化的無人水面艇全局路徑規劃[J].中國航海， 2017， 40（1）： 47-52， 113.

[5] 張廣林， 胡小梅， 柴劍飛， 等.路徑規劃算法及其應用綜述[J].現代機械， 2011（5）： 85-90. DOI： 10.13667/j.cnki.52-1046/th.2011.05.014.

[6] GURUJIA K， AGARWAL H， PARSEDIYA D K. Time-efficient A * algorithm for robot path planning[J]. Procedia Technology， 2016， 23： 144-149.DOI： 10.1016/j.protcy.2016.03.010.

[7] FERNANDES E， COSTA P， LIMA J. Towards an orientation enhanced Astar algorithm for robotic navigation[C]//2015 IEEE International Conference on Industrial Technology （ICIT）， Seville， Spain， 2015： 3320-3325. DOI： 10.1109/ICIT.2015.7125590.

[8] PAN Hu， GUO Chen， WANG Zhaodong. Research for path planning based on improved Astar algorithm[C]// 2017 4th International Conference on Information， Cybernetics and Computational Social Systems （ICCSS）， Dalian， China， 2017： 225-230. DOI： 10.1109/ICCSS.2017.8091416.

[9] CHENG Liping， LIU Chuanxi，YAN Bo. Improved hierarchical A-star algorithm for optimal parking path planning of the large parking lot[C]//Proceeding of the IEEE International Conference on Information and Automation， Hulunbeier， China， 2014： 695-698. DOI： 10.1109/ICInfA.2014.6932742.

[10] JI Xuezhi， LIU Lixiang， ZHAO Pei， et al. A-star algorithm based on-demand routing protocol for hierarchical LEO/MEO satellite networks[C]//2015 IEEE International Congference on Big Data， Santa Clara， USA， 2015： 1545-1549. DOI： 10.1109/BigData.2015.7363918.

[11] 高宗江， 張英俊， 孫培廷， 等.無人駕駛船舶研究綜述[J].大連海事大學學報， 2017， 43（2）： 1-7. DOI： 10.16411/j.cnki.issn1006-7736.2017.02.001.

（編輯 賈裙平）