多航道下船舶最佳導(dǎo)航路線選擇方法

郎賓超

(交通運(yùn)輸部北海航海保障中心天津航標(biāo)處，天津 300456)

0 引 言

近年來，船舶航行的發(fā)展水平得到了較大提高。從技術(shù)角度來看，航行設(shè)備和技術(shù)的不斷更新和改進(jìn)，為船舶航行提供了更多的支持和保障。現(xiàn)代化的航行儀器，例如雷達(dá)、自動(dòng)化控制系統(tǒng)等，都在較大程度上提高了船舶的導(dǎo)航精度和安全性[1]。船舶航線路線選擇的意義在于確保船舶和貨物的安全和有效運(yùn)輸，選擇合適的航線可以減少船舶在海上遇到自然災(zāi)害風(fēng)險(xiǎn)，同時(shí)也可以降低航行時(shí)間和成本[2]。航線選擇需要考慮多種因素，包括天氣條件、海洋地理環(huán)境等[3]。正確選擇航線可以提高船舶和貨物的安全性，降低船舶運(yùn)輸成本，具有較高的意義[4]。

有學(xué)者對(duì)導(dǎo)航路線規(guī)劃方法進(jìn)行研究，王童等[5]提出基于分層深度強(qiáng)化學(xué)習(xí)的移動(dòng)機(jī)器人導(dǎo)航方法，該方法應(yīng)用強(qiáng)化學(xué)習(xí)方法，對(duì)機(jī)器人導(dǎo)航路線進(jìn)行訓(xùn)練，獲取最佳行走路線，但該方法無法進(jìn)行遠(yuǎn)程導(dǎo)航路線選擇，僅能夠在小范圍使用。胡湘蘭等[6]提出基于多目標(biāo)進(jìn)化算法的自駕游用戶導(dǎo)航規(guī)劃方法，該方法對(duì)多種行駛路線進(jìn)行目標(biāo)優(yōu)化，獲取最佳軌跡，但該方法在選擇最佳路線時(shí)需要耗費(fèi)大量的時(shí)間。

為解決上述方法中存在的問題，本文研究多航道下船舶最佳導(dǎo)航路線選擇方法，保障船舶航行安全穩(wěn)定。通過選擇最優(yōu)的航道，提高航行效率，降低船舶損失率。傳統(tǒng)意義上，船舶通常只能在單一航道上航行，而在多航道的情況下，船舶可以根據(jù)實(shí)際情況選擇最優(yōu)的航道進(jìn)行航行，以達(dá)到更高的效率和安全性。

1 船舶最佳導(dǎo)航路線選擇

1.1 多航道下導(dǎo)航路線當(dāng)量計(jì)算

在求解多航道下船舶的最佳導(dǎo)航路線之前，需要將所有航道處理為統(tǒng)一的等效長(zhǎng)度。同時(shí)，需要考慮船舶航道的實(shí)際網(wǎng)絡(luò)狀態(tài)及其影響程度，以獲取相應(yīng)的影響因子。此外，還要充分考慮船舶航行的風(fēng)險(xiǎn)性，并結(jié)合現(xiàn)實(shí)航行導(dǎo)航中存在的風(fēng)險(xiǎn)因素，例如導(dǎo)航有效寬度、高度、風(fēng)向、風(fēng)速以及水流速度等因素[7]，分 別 將這 些 因 素設(shè) 為 α1， α2， α3， α4， α5，并 通過 下式對(duì)其進(jìn)行計(jì)算：

式中：航行節(jié)點(diǎn)i與j的導(dǎo)航路線由Eij表示；Eij的影響因子系數(shù)為為包含影響因子狀態(tài)下經(jīng)過導(dǎo)航路線Eij位置所需時(shí)間；為不包含影響因子狀態(tài)下經(jīng)過導(dǎo)航路線Eij所需時(shí)間。

當(dāng)獲取導(dǎo)航路線的影響因子后，可結(jié)合路線實(shí)際長(zhǎng)度與影響程度系數(shù)計(jì)算得出當(dāng)量長(zhǎng)度，如下式：

式中；Ls為 實(shí)際測(cè)試到的導(dǎo)航路線長(zhǎng)度。Ld為導(dǎo)航路線當(dāng)量長(zhǎng)度；根據(jù)計(jì)算結(jié)果繼續(xù)進(jìn)行現(xiàn)場(chǎng)模擬分析，經(jīng)反復(fù)模擬獲取Ls的平均值，并再次通過式（3）計(jì)算導(dǎo)航路線當(dāng)量長(zhǎng)度。計(jì)算航道起始點(diǎn)與目的地之間每個(gè)可通行航道相應(yīng)的當(dāng)量長(zhǎng)度，并結(jié)合改進(jìn)迪克斯特拉（Dijstra）算法尋找當(dāng)量長(zhǎng)度最小的路徑，將其作為多航道下船舶最佳導(dǎo)航路線。

1.2 基于迪克斯特拉（Dijstra）算法最短路徑選取

Dijstra 算法是一種最短路徑搜索算法，該算法應(yīng)用貪心策略，對(duì)兩點(diǎn)之間的最短路徑進(jìn)行尋優(yōu)。該算法假設(shè)每一點(diǎn)均存在一對(duì)標(biāo)號(hào)其中，dj是指起始點(diǎn)s到目的地j的最短路徑長(zhǎng)度，而從s到j(luò)的最短航線內(nèi)的前一點(diǎn)為pj， 通過如下過程，求解起始點(diǎn)s到目的地j的最短航線。

步驟1初始化。設(shè)起始點(diǎn)：ds=0，ps為空，并將多航道上的其他點(diǎn)設(shè)為dt=∞，當(dāng)針對(duì)不同點(diǎn)搜尋最佳導(dǎo)航線路時(shí)，pt不同；標(biāo)記起始點(diǎn)，設(shè)k=s，并將其他點(diǎn)設(shè)為未標(biāo)記狀態(tài)。

步驟2對(duì)全部已標(biāo)記的點(diǎn)k和與其相連未標(biāo)記的點(diǎn)j之間距離進(jìn)行檢查，并表示為：

式中，Lkj表示點(diǎn)k到點(diǎn)j的直接連接距離。

步驟3搜尋下一個(gè)點(diǎn)，從全部未標(biāo)記的點(diǎn)中，挑選dj值最小的點(diǎn)i，如下：

通過式（5）找到對(duì)應(yīng)點(diǎn)i，并對(duì)其進(jìn)行標(biāo)記。

步驟4對(duì)點(diǎn)i的前一點(diǎn)進(jìn)行尋找，并表示為點(diǎn)u，同時(shí)設(shè)i=u。

步驟5標(biāo)記點(diǎn)i，若全部的點(diǎn)均完成標(biāo)記，則完成最佳路線選擇，若未完成標(biāo)記，則返回步驟1 繼續(xù)尋找。

通過這一算法的計(jì)算，可以有效獲取船舶的最佳航行路線，但隨著標(biāo)記點(diǎn)增多，該方法循環(huán)次數(shù)也會(huì)延長(zhǎng)，導(dǎo)致計(jì)算時(shí)間增加，為此，研究改進(jìn)Dijstra 算法，快速實(shí)現(xiàn)船舶最佳導(dǎo)航路線選擇。

1.3 基于改進(jìn)Dijstra 算法的船舶最佳導(dǎo)航路線選擇

1.3.1 導(dǎo)航路線數(shù)據(jù)存儲(chǔ)與初始化

在進(jìn)行多航道下船舶最佳導(dǎo)航路徑選擇之前，還需要采取有效方式，對(duì)路線選擇過程產(chǎn)生的數(shù)據(jù)進(jìn)行存儲(chǔ)[8]。

1）標(biāo)記節(jié)點(diǎn)集

該集合是指在導(dǎo)航路線選擇過程全部被選取過、途徑的節(jié)點(diǎn)集合，這些節(jié)點(diǎn)根據(jù)先后順序生成一個(gè)鏈表，以此反映最短導(dǎo)航路線信息。

2）待選擇節(jié)點(diǎn)

對(duì)仍未進(jìn)行選擇，且即將進(jìn)行選擇的節(jié)點(diǎn)進(jìn)行存儲(chǔ)。

完成全部使用信息的存儲(chǔ)后，即完成最短路線選擇準(zhǔn)備。

1.3.2 最佳導(dǎo)航路線選擇實(shí)現(xiàn)

由于傳統(tǒng)Dijstra 算法在計(jì)算過程中的效率不高，導(dǎo)致導(dǎo)航路線選擇需要耗費(fèi)大量的系統(tǒng)內(nèi)存，因此本文結(jié)合數(shù)據(jù)存儲(chǔ)與初始化，研究基于改進(jìn)后的Dijstra 算法最佳導(dǎo)航路線選擇，具體步驟如下：

步驟1選擇起始節(jié)點(diǎn)，并搜尋與其存在連接的節(jié)點(diǎn)，將這些節(jié)點(diǎn)存儲(chǔ)為待選擇節(jié)點(diǎn)J，依次計(jì)算這些節(jié)點(diǎn)的方向夾角，假設(shè)待選擇節(jié)點(diǎn)坐標(biāo)為 (x,y)，初始節(jié)點(diǎn)坐標(biāo)為目標(biāo)位置節(jié)點(diǎn)坐標(biāo)為 (xz,yz)，此時(shí)，兩連線方向夾角可通過如下公式計(jì)算：

式中： θ表示導(dǎo)航路線總轉(zhuǎn)向角度，u1和u2依次表示初始節(jié)點(diǎn)與目標(biāo)位置節(jié)點(diǎn)的方向夾角。通過方向夾角的計(jì)算，可在導(dǎo)航最短路線的基礎(chǔ)上，選取更合適的導(dǎo)航路線，當(dāng)獲取夾角最小的節(jié)點(diǎn)，即將存放在標(biāo)記節(jié)點(diǎn)集合中，將該節(jié)點(diǎn)作為新的節(jié)點(diǎn)開始下一節(jié)點(diǎn)選擇。

步驟2分析步驟1 選擇的節(jié)點(diǎn)是否為目標(biāo)位置節(jié)點(diǎn)，若是，則完成路線選擇，否則繼續(xù)通過步驟1 選擇下一節(jié)點(diǎn)。

步驟3將全部搜索到的節(jié)點(diǎn)存儲(chǔ)到標(biāo)記節(jié)點(diǎn)集中，并將該集合內(nèi)的節(jié)點(diǎn)存儲(chǔ)為鏈表數(shù)據(jù)，實(shí)現(xiàn)最佳船舶導(dǎo)航路線選擇。

2 實(shí)驗(yàn)分析

在電子海圖平臺(tái)對(duì)實(shí)際海洋環(huán)境進(jìn)行模擬，在該環(huán)境下進(jìn)行船舶最佳導(dǎo)航路線選擇，在實(shí)驗(yàn)過程中，設(shè)計(jì)航行20 個(gè)節(jié)點(diǎn)，并規(guī)劃多條航道，對(duì)本文構(gòu)建的航線選擇方法進(jìn)行驗(yàn)證。

選取1 號(hào)、2 號(hào)、8 號(hào)節(jié)點(diǎn)作為初始節(jié)點(diǎn)，分析這些節(jié)點(diǎn)分別到達(dá)15 號(hào)、19 號(hào)、20 號(hào)節(jié)點(diǎn)的導(dǎo)航路線結(jié)果，分析結(jié)果如圖1 所示。

圖1 最佳導(dǎo)航路線選擇結(jié)果分析Fig. 1 Analysis of the best navigation route selection results

可知，經(jīng)過本文方法的選擇后，可有效獲取每一目標(biāo)點(diǎn)到達(dá)目的地的最佳導(dǎo)航路線。其中，1 號(hào)目標(biāo)點(diǎn)分別經(jīng)過13 號(hào)點(diǎn)、16 號(hào)點(diǎn)到達(dá)15 號(hào)點(diǎn)，2 號(hào)目標(biāo)點(diǎn)分別經(jīng)過18 號(hào)點(diǎn)到達(dá)19 號(hào)點(diǎn)，而8 號(hào)目標(biāo)點(diǎn)則經(jīng)過9 號(hào)點(diǎn)、18 號(hào)點(diǎn)到達(dá)20 號(hào)點(diǎn)，每一條選擇的路線均保持最短航行距離，可在多條航道下保持最短航線行駛。

分析節(jié)點(diǎn)1 達(dá)到目的地點(diǎn)20 時(shí)，在不同風(fēng)速風(fēng)向及水流速度影響下，每一路線的當(dāng)量長(zhǎng)度情況，分析結(jié)果如表1 所示。

表1 每一路線的當(dāng)量長(zhǎng)度分析Tab. 1 Equivalent length analysis for each route

可知，在不同風(fēng)速與水流速度下，本文方法均可快速、有效獲取起始點(diǎn)到目的地之間多航道路線的當(dāng)量長(zhǎng)度，通過分析可以看出，這些路線均在240～280 km 之間，并未存在較大差距，從這些路線中選取最短的導(dǎo)航路線，即為最佳導(dǎo)航路線。因此，本文方法可獲取每條航道線路的當(dāng)量長(zhǎng)度，為后續(xù)路線選擇提供有利依據(jù)。

選擇點(diǎn)4、點(diǎn)5、點(diǎn)7 節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，將其他點(diǎn)均作為目的地，分析應(yīng)用本文方法選擇每一目的地最佳導(dǎo)航路線時(shí)所需的時(shí)間，分析結(jié)果如表2 所示。

表2 最佳導(dǎo)航路線選擇時(shí)間Tab. 2 Best navigation route selection time

可知，當(dāng)將每一節(jié)點(diǎn)作為目的地節(jié)點(diǎn)時(shí)，本文方法均能夠快速實(shí)現(xiàn)最佳導(dǎo)航路線選擇，挑選出最合適的導(dǎo)航路線，且在選擇過程中，并未消耗大量的時(shí)間，其中，每一路線的選擇時(shí)間均在20 s 以下，說明本文方法具有良好的應(yīng)用效果。

將1 號(hào)、2 號(hào)、3 號(hào)節(jié)點(diǎn)作為船舶航行起始點(diǎn)，分析每一起始點(diǎn)到不同目的地時(shí)的路徑長(zhǎng)度與總轉(zhuǎn)向角度，以此驗(yàn)證本文方法的路線選擇能力，分析結(jié)果如圖2 所示。

圖2 路線選擇能力分析Fig. 2 Analysis of route selection capability

可以看出，經(jīng)過本文方法進(jìn)行每一節(jié)點(diǎn)的導(dǎo)航路線選擇后，均可保持較低的航行路徑長(zhǎng)度以及總轉(zhuǎn)向角度，說明該方法選擇的導(dǎo)航路線是最短路線，可有效降低船舶航行開銷。

3 結(jié) 語

本文研究多航道下船舶最佳導(dǎo)航路線選擇方法，衡量多航道下導(dǎo)航路線當(dāng)量，從而選取最合適的船舶航行路線，并針對(duì)該導(dǎo)航路線選擇方法進(jìn)行模擬測(cè)試實(shí)驗(yàn)，分析該方法的應(yīng)用效果，經(jīng)過實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)，該方法具有良好的路線選擇能力。