基于優先隊列回溯算法的電子航道圖航路規劃設計

馬志云 施俊羽

摘 要：電子航道圖航路規劃是指長江航道中的船舶利用自然水深航行，對于不吃水船舶要結合航道實際情況和船舶航行基礎，對航路進行合理規劃。本文利用優先隊列回溯算法，設計電子航道圖航路規劃。從實驗結果可以看出，此算法能夠對航道進行快速、精準、合理的規劃，運行速度快，航道規劃需求得到滿足，具有較強實用性。

關鍵詞：優先隊列回朔算法;電子航道圖;航路規劃

中圖分類號：U612.2? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? 文章編號：1006—7973（2021）03-0072-03

航運作為國民經濟基礎產業，在服務性行業和綜合運輸體系中具有重要地位，其占地少、能耗比較小、成本低、運能比較大，促進了航運的發展。在科學技術和信息技術不斷發展的過程中，航運以數字航運、智能航運作為主要發展目標。在大型化、信息化船舶數量的現代航運技術不斷發展和使用的過程中，電子航道要求權威、精準、豐富的支持。所以，為了促進航運發展，滿足社會需求，要求實現電子航道圖航路的規劃設計[1]。

1航道規劃中的問題

航路規劃目的就是以船舶在長江中的吃水進行航路的合理規劃，使船舶在長江中能夠順利航行，并且對長江航道最大通行量進行保證，提高經濟效益。通過幾何觀點分析，問題主要包括：C指約束集，S指資源集，E指需求集，最終目標為需求集中全部元素處于集合S中，從而使映射滿足約束集[2]。

結合實際情況，需求集是指船舶集E={1，2，3，....}，通過此編號能夠實現傳播具體信息的提取，比如傳播長度、寬度、載重量、航速等。

資源集指的是長江斷面集S={1，2，3，...}，元素指的是斷面編號，從而得到斷面基本信息，包括斷面分叉、斷面測點深度等信息。主要硬約束包括：

其一，航路水深。在航路水深規劃過程中，要求大于船舶吃水，確定在規劃航路中船舶能夠安全的運行;

其二，航路寬度。使航路寬度設置為船舶寬度的2.0B-4.5B，在行駛過程中，船舶會受到水流、風向的影響，軌跡無法平行與航路，那么導航中的船舶左右擺動;

其三，航路底邊和船舶富裕間距。為了避免由于岸吸導致船舶存在擱淺的問題，要求保此河底一定的距離[3]。

2航路規劃算法

2.1優先隊列

優先隊列指的是以臨近排序思想作為基礎，實現數據集排序，對比小范圍記錄，將重復記錄精準提取。通過所抽取的字段實現關鍵字創建，之后排序，并且尋找數據庫中固定范圍中隊列匹配記錄[4]。

2.2創建環境模型

在規劃航路前，要先在內部世界模型中實現環境障礙物表示模型的創建，使規劃航路時搜索量得到降低?，F代國內外對環境建模方法進行研究，包括拓撲圖法、可視圖法、單元數法等，本文使用柵格法實現建模。此方法主要原理就是使船舶工作空間劃分多個小柵格，每個小柵格接近周圍柵格，創建柵格地圖。內河水域通航環境對比海洋環境，影響因素比較復雜[5]。所以，利用優化隊列回溯算法規劃全局路徑，通過電子航道圖得出船舶工作過程中環境信息，通過柵格對船舶工作空間進行劃分，創建柵格地圖，使船舶運動軌跡與環境中信息在柵格地圖中進行存儲，包括不完全可行、完全不可行、完全可行的柵格。先使不完全可行柵格在完全不可行柵格中創建，障礙柵格為安全可行柵格，表示為涂黑的方塊。船舶起始位置柵格值得就是起始柵格和船舶目標位置柵格，最后對柵格環境編號進行劃分[6]。

模型創建后進行存儲，利用行列劃分矩陣存儲的方法實現柵格存儲，創建數組與柵格的關系，圖1為柵格環境模型。對建模復雜性進行考慮，使船舶在柵格運行過程中定義八種，詳見圖2。電子航道圖能夠提供給船舶全局環境的信息來源，通過以上創建的環境模型，對電子航道圖進行柵格化，使電子航道劃分的柵格具有相同的大小，利用柵格地圖標記值存儲環境信息[7]。

2.3算法描述

利用節點到目標節點的初始節點最小代價途徑估計模型表示為：

公式中的g（n）指的是前個節點到目前節點需要的代價和，m（n）為前個節點在目前節點運動所花費的代價，h（n）為實際環境節點n到目標節點的曼哈頓距離，（xn，yn）指的是節點n坐標值，（xgoal，ygoal）指的是目標節點坐標值。

3實驗效果和分析

先導入原始數據，用戶要輸入航道水深、航寬、彎曲半徑，計算機以實際需求計算航道，使用戶輸入參數得到滿足。使航標點在已經規劃航道中添加，對規劃河道利用優先隊列回溯算法正確規劃航道，滿足航道寬度需求，并且能夠縮小挖鑿區域。

另外，針對不規則航道區域，對測試算法精準性進行分析，觀察自動規劃與實際規劃的航道是否相同。在不規則河道中，通過本算法規劃。兩條航道通航，通過算法對使用哪一條進行選擇。標注航道，將航標點進行顯示。針對不規則河道，尤其是分叉河道，人為觀察是無法對具體通航區域進行判斷的。通過本文算法，左右航道都能夠通航，但是要利用具體計算選擇哪條航道最優，選擇合適算法與結果精準性具有密切關系，圖3為航道規劃的環境模型。

4電子航海圖規劃的建議

我國內河電子航道圖規劃現狀會影響到我國內河航運的發展，為了促進我國內河航運健康發展，針對電子航海圖規劃提出以下建議：

其一，統籌規劃。目前，缺乏電子航海圖航路規劃的統一規劃，在技術方面并沒有政策支持，生產力量分散，缺乏完善管理。所以，要創建強有力協調領導小組，使管理與規劃得到加強。與我國內河航運具體情況結合，實現滿足航路規劃發展、使用和發布的標準制定;

其二，創建資源整合平臺。以我國目前電子航道圖自成體系情況，創建電子航道圖生產與服務平臺，從而實現資源共享，統一發布信息。不僅能夠避免資源浪費與重復開發，還能夠強化管理，提高對外服務能力;

其三，加強合作。對電子航道圖航路規劃的標準進行研發與制定，與國際區域之間的合作得到加強，積極地參與到國際內河電子航道圖協調小組相應會議中，并且及時掌握電子航道圖的發展，有效促進我國航路規劃的發展[8]。

5結束語

目前，我國內河航運在不斷的發展，但是因為內河航運發展比較晚，相應的標準研發也比較晚。所以，就要針對我國內河航運的問題與國內內河航運具體情況，使用智能化航運和電子化航運，設計電子航道圖航路規劃，對相應的標準進行完善，促進我國內河航運快速健康的發展。

參考文獻：

[1]王蘭， 張龍信， 滿君豐，等. 異構計算環境下基于優先隊列劃分的調度算法[J]. 小型微型計算機系統， 2020， 041（002）：303-309.

[2]楊傳印， 黃瑋， 薛少聰，等. 基于優先隊列的時變網絡最短路徑算法[J]. 計算機應用研究， 2019， 36（05）：129-134.

[3]易黎. 一種基于給定目標節點的個性化PageRank算法設計[J]. 計算技術與自動化， 2020， 039（001）：101-105.

[4]陳志軒. 工業無線網絡TSN實時優先隊列調度算法研究[J]. 軟件工程與應用， 2019， 8（6）：8.

[5]萬平. 基于A-star算法的航路規劃算法設計與仿真研究[J]. 中國水運.航道科技， 2018， 000（004）：P.58-65.

[6]胡陽， 張謐， 王玲，等. 人工智能用于船舶航線優化的有效方案[J]. 科技創新導報， 2019， v.16;No.503（35）：143+145.

[7] Lu Xuan Xuan， Zhao Rui， Zhao Zhiming， et al. Research and Application of Optimization of Electronic Channel Map Making Based on Maritime Charting [J]. China Water Transport （first half month），2018000（010）：32-35.

[8] Xu Ning， Zhao Zhiming， Lu Xuanxuan， et al. J]. on Construction of Electronic Navigation Map and Safety Management Platform for Inland Waterways Henan Science and Technology ，2019000（010）：24-26.