基于優(yōu)先隊(duì)列回溯算法的電子航道圖航路規(guī)劃設(shè)計(jì)

馬志云 施俊羽

摘 要：電子航道圖航路規(guī)劃是指長江航道中的船舶利用自然水深航行，對(duì)于不吃水船舶要結(jié)合航道實(shí)際情況和船舶航行基礎(chǔ)，對(duì)航路進(jìn)行合理規(guī)劃。本文利用優(yōu)先隊(duì)列回溯算法，設(shè)計(jì)電子航道圖航路規(guī)劃。從實(shí)驗(yàn)結(jié)果可以看出，此算法能夠?qū)降肋M(jìn)行快速、精準(zhǔn)、合理的規(guī)劃，運(yùn)行速度快，航道規(guī)劃需求得到滿足，具有較強(qiáng)實(shí)用性。

關(guān)鍵詞：優(yōu)先隊(duì)列回朔算法;電子航道圖;航路規(guī)劃

中圖分類號(hào)：U612.2? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? 文章編號(hào)：1006—7973（2021）03-0072-03

航運(yùn)作為國民經(jīng)濟(jì)基礎(chǔ)產(chǎn)業(yè)，在服務(wù)性行業(yè)和綜合運(yùn)輸體系中具有重要地位，其占地少、能耗比較小、成本低、運(yùn)能比較大，促進(jìn)了航運(yùn)的發(fā)展。在科學(xué)技術(shù)和信息技術(shù)不斷發(fā)展的過程中，航運(yùn)以數(shù)字航運(yùn)、智能航運(yùn)作為主要發(fā)展目標(biāo)。在大型化、信息化船舶數(shù)量的現(xiàn)代航運(yùn)技術(shù)不斷發(fā)展和使用的過程中，電子航道要求權(quán)威、精準(zhǔn)、豐富的支持。所以，為了促進(jìn)航運(yùn)發(fā)展，滿足社會(huì)需求，要求實(shí)現(xiàn)電子航道圖航路的規(guī)劃設(shè)計(jì)[1]。

1航道規(guī)劃中的問題

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

結(jié)合實(shí)際情況，需求集是指船舶集E={1，2，3，....}，通過此編號(hào)能夠?qū)崿F(xiàn)傳播具體信息的提取，比如傳播長度、寬度、載重量、航速等。

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

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

其二，航路寬度。使航路寬度設(shè)置為船舶寬度的2.0B-4.5B，在行駛過程中，船舶會(huì)受到水流、風(fēng)向的影響，軌跡無法平行與航路，那么導(dǎo)航中的船舶左右擺動(dòng);

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

2航路規(guī)劃算法

2.1優(yōu)先隊(duì)列

優(yōu)先隊(duì)列指的是以臨近排序思想作為基礎(chǔ)，實(shí)現(xiàn)數(shù)據(jù)集排序，對(duì)比小范圍記錄，將重復(fù)記錄精準(zhǔn)提取。通過所抽取的字段實(shí)現(xiàn)關(guān)鍵字創(chuàng)建，之后排序，并且尋找數(shù)據(jù)庫中固定范圍中隊(duì)列匹配記錄[4]。

2.2創(chuàng)建環(huán)境模型

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

模型創(chuàng)建后進(jìn)行存儲(chǔ)，利用行列劃分矩陣存儲(chǔ)的方法實(shí)現(xiàn)柵格存儲(chǔ)，創(chuàng)建數(shù)組與柵格的關(guān)系，圖1為柵格環(huán)境模型。對(duì)建模復(fù)雜性進(jìn)行考慮，使船舶在柵格運(yùn)行過程中定義八種，詳見圖2。電子航道圖能夠提供給船舶全局環(huán)境的信息來源，通過以上創(chuàng)建的環(huán)境模型，對(duì)電子航道圖進(jìn)行柵格化，使電子航道劃分的柵格具有相同的大小，利用柵格地圖標(biāo)記值存儲(chǔ)環(huán)境信息[7]。

2.3算法描述

利用節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的初始節(jié)點(diǎn)最小代價(jià)途徑估計(jì)模型表示為：

公式中的g（n）指的是前個(gè)節(jié)點(diǎn)到目前節(jié)點(diǎn)需要的代價(jià)和，m（n）為前個(gè)節(jié)點(diǎn)在目前節(jié)點(diǎn)運(yùn)動(dòng)所花費(fèi)的代價(jià)，h（n）為實(shí)際環(huán)境節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的曼哈頓距離，（xn，yn）指的是節(jié)點(diǎn)n坐標(biāo)值，（xgoal，ygoal）指的是目標(biāo)節(jié)點(diǎn)坐標(biāo)值。

3實(shí)驗(yàn)效果和分析

先導(dǎo)入原始數(shù)據(jù)，用戶要輸入航道水深、航寬、彎曲半徑，計(jì)算機(jī)以實(shí)際需求計(jì)算航道，使用戶輸入?yún)?shù)得到滿足。使航標(biāo)點(diǎn)在已經(jīng)規(guī)劃航道中添加，對(duì)規(guī)劃河道利用優(yōu)先隊(duì)列回溯算法正確規(guī)劃航道，滿足航道寬度需求，并且能夠縮小挖鑿區(qū)域。

另外，針對(duì)不規(guī)則航道區(qū)域，對(duì)測試算法精準(zhǔn)性進(jìn)行分析，觀察自動(dòng)規(guī)劃與實(shí)際規(guī)劃的航道是否相同。在不規(guī)則河道中，通過本算法規(guī)劃。兩條航道通航，通過算法對(duì)使用哪一條進(jìn)行選擇。標(biāo)注航道，將航標(biāo)點(diǎn)進(jìn)行顯示。針對(duì)不規(guī)則河道，尤其是分叉河道，人為觀察是無法對(duì)具體通航區(qū)域進(jìn)行判斷的。通過本文算法，左右航道都能夠通航，但是要利用具體計(jì)算選擇哪條航道最優(yōu)，選擇合適算法與結(jié)果精準(zhǔn)性具有密切關(guān)系，圖3為航道規(guī)劃的環(huán)境模型。

4電子航海圖規(guī)劃的建議

我國內(nèi)河電子航道圖規(guī)劃現(xiàn)狀會(huì)影響到我國內(nèi)河航運(yùn)的發(fā)展，為了促進(jìn)我國內(nèi)河航運(yùn)健康發(fā)展，針對(duì)電子航海圖規(guī)劃提出以下建議：

其一，統(tǒng)籌規(guī)劃。目前，缺乏電子航海圖航路規(guī)劃的統(tǒng)一規(guī)劃，在技術(shù)方面并沒有政策支持，生產(chǎn)力量分散，缺乏完善管理。所以，要?jiǎng)?chuàng)建強(qiáng)有力協(xié)調(diào)領(lǐng)導(dǎo)小組，使管理與規(guī)劃得到加強(qiáng)。與我國內(nèi)河航運(yùn)具體情況結(jié)合，實(shí)現(xiàn)滿足航路規(guī)劃發(fā)展、使用和發(fā)布的標(biāo)準(zhǔn)制定;

其二，創(chuàng)建資源整合平臺(tái)。以我國目前電子航道圖自成體系情況，創(chuàng)建電子航道圖生產(chǎn)與服務(wù)平臺(tái)，從而實(shí)現(xiàn)資源共享，統(tǒng)一發(fā)布信息。不僅能夠避免資源浪費(fèi)與重復(fù)開發(fā)，還能夠強(qiáng)化管理，提高對(duì)外服務(wù)能力;

其三，加強(qiáng)合作。對(duì)電子航道圖航路規(guī)劃的標(biāo)準(zhǔn)進(jìn)行研發(fā)與制定，與國際區(qū)域之間的合作得到加強(qiáng)，積極地參與到國際內(nèi)河電子航道圖協(xié)調(diào)小組相應(yīng)會(huì)議中，并且及時(shí)掌握電子航道圖的發(fā)展，有效促進(jìn)我國航路規(guī)劃的發(fā)展[8]。

5結(jié)束語

目前，我國內(nèi)河航運(yùn)在不斷的發(fā)展，但是因?yàn)閮?nèi)河航運(yùn)發(fā)展比較晚，相應(yīng)的標(biāo)準(zhǔn)研發(fā)也比較晚。所以，就要針對(duì)我國內(nèi)河航運(yùn)的問題與國內(nèi)內(nèi)河航運(yùn)具體情況，使用智能化航運(yùn)和電子化航運(yùn)，設(shè)計(jì)電子航道圖航路規(guī)劃，對(duì)相應(yīng)的標(biāo)準(zhǔn)進(jìn)行完善，促進(jìn)我國內(nèi)河航運(yùn)快速健康的發(fā)展。

參考文獻(xiàn)：

[1]王蘭， 張龍信， 滿君豐，等. 異構(gòu)計(jì)算環(huán)境下基于優(yōu)先隊(duì)列劃分的調(diào)度算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2020， 041（002）：303-309.

[2]楊傳印， 黃瑋， 薛少聰，等. 基于優(yōu)先隊(duì)列的時(shí)變網(wǎng)絡(luò)最短路徑算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2019， 36（05）：129-134.

[3]易黎. 一種基于給定目標(biāo)節(jié)點(diǎn)的個(gè)性化PageRank算法設(shè)計(jì)[J]. 計(jì)算技術(shù)與自動(dòng)化， 2020， 039（001）：101-105.

[4]陳志軒. 工業(yè)無線網(wǎng)絡(luò)TSN實(shí)時(shí)優(yōu)先隊(duì)列調(diào)度算法研究[J]. 軟件工程與應(yīng)用， 2019， 8（6）：8.

[5]萬平. 基于A-star算法的航路規(guī)劃算法設(shè)計(jì)與仿真研究[J]. 中國水運(yùn).航道科技， 2018， 000（004）：P.58-65.

[6]胡陽， 張謐， 王玲，等. 人工智能用于船舶航線優(yōu)化的有效方案[J]. 科技創(chuàng)新導(dǎo)報(bào)， 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.