基于多維度數(shù)據(jù)挖掘的船舶最優(yōu)航線路線生成研究

黃曼綺，魏雨東

(電子科技大學(xué)成都學(xué)院 計算機(jī)學(xué)院，四川 成都 611731)

0 引 言

在經(jīng)濟(jì)全球化發(fā)展大趨勢下，國家之間貿(mào)易交流日益頻繁，而大宗貨物運輸通常使用海運方式[1]。面對較為復(fù)雜多樣的海洋航行環(huán)境以及海上運輸線路存在交叉的問題，為船舶規(guī)劃最優(yōu)航行線路是海上運輸行業(yè)重點研究方向[2]。當(dāng)前也有很多學(xué)者研究船舶最優(yōu)航線生成方法，王立鵬等[3]提出的船舶航線規(guī)劃算法，該算法通過建立船舶航行時回轉(zhuǎn)與降速模型得到船舶航線數(shù)據(jù)，再通過分析海圖航線規(guī)劃和陸地物標(biāo)之間的關(guān)系，最后利用四叉樹和不規(guī)則邊界檢測方式生成船舶航線。韓志豪等[4]提出深度強化學(xué)習(xí)的航線生成方法，該方法將電子海圖上的航線作為初始數(shù)據(jù)，利用深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)對電子海圖上的航線進(jìn)行采樣處理后，輸出船舶航行最優(yōu)航線。但是上述2 種方法生成的航線均存在無法規(guī)避較小障礙物、生成線路不是最佳線路問題，為此本文研究基于多維度數(shù)據(jù)挖掘的船舶最優(yōu)航線生成方法。

1 船舶最優(yōu)航線生成方法

1.1 基于多維度數(shù)據(jù)挖掘的初始航線生成

挖掘官方電子海圖（eiectronic navigational charts，ENCs）的海域港口、陸地物標(biāo)（島嶼、礁石）等多維度坐標(biāo)數(shù)據(jù)，并將每個港口、陸地物標(biāo)看作一個節(jié)點，使用改進(jìn)隨機(jī)路徑圖（improved probabilistic roadmap，IPRM）方法生成船舶航行初始航線，其詳細(xì)過程如下：

從官方電子海圖中挖掘到海域港口、陸地物標(biāo)節(jié)點數(shù)據(jù)后，在船舶航行起點與目的地空間內(nèi)選擇N個節(jié)點，連接這些節(jié)點后，將起點和目的地之間的連線和該連線附近的障礙物邊緣區(qū)域作為關(guān)鍵區(qū)域，對該區(qū)域進(jìn)行節(jié)點擴(kuò)充處理后，得到船舶初始無向路徑網(wǎng)絡(luò)圖G(V,E)，其中V表示無向路徑網(wǎng)絡(luò)圖內(nèi)涵蓋的節(jié)點集，E表示船舶起點和目的地之間所有可能的路線集。當(dāng)船舶初始全局航線內(nèi)存在動態(tài)障礙物（有其他船舶穿過）時，需考慮動態(tài)障礙物躲避問題。此時需對官方電子海圖每8 h 更新一次，重新生成船舶航線無向路徑網(wǎng)絡(luò)圖即可。

1.2 最優(yōu)航線路線生成多維指標(biāo)設(shè)置

在一條航線上，可能存在2 艘或者多艘船舶同目的地相同的情況。當(dāng)線路生成不合理時，船舶出發(fā)或者到達(dá)目的地時潮汐較大或過小均影響船舶出入港，因此需從潮汐、船舶安全航行距離多個維度設(shè)置最優(yōu)航線路線生成多維指標(biāo)。

1）船舶航行安全距離指標(biāo)

2 艘或者多艘船舶向同一目的地航行時，相鄰2 艘船舶中，后一艘船舶的航速不得高于前一艘船舶。假設(shè)用i和j表示從同一位置出發(fā)的2 艘船舶，其初始距離可看作0，若該2 艘保持相應(yīng)安全距離，則前方船舶j需始終比后方船舶i多航行 6Li的距離。假設(shè)船舶同向航行時間為t，其表達(dá)公式為：

式中：Di，Dj分別表示船舶i和j從起點到目的地所用時間。

2 艘船舶航行速度滿足如下條件：

式中：Vi，Vj分別表示船舶i和j的航速；t′表示前方船舶j比i先航行的時長。

由式（1）和式（2）綜合可得到2 艘船舶安全航行時間間隔，其表達(dá)式為：

式中：Xi j表示船舶的前方船舶i是否為j的判斷閾值，若是則取值為1，反之則為0。

2）航線目的地潮汐時間指標(biāo)

受潮汐運動影響，船舶無法實現(xiàn)全時間通航。為保障船舶到達(dá)港口附近時能高效進(jìn)港，需要假設(shè)該港口入港航段為單向通航。假設(shè)船舶平均吃水為D，在潮汐狀態(tài)下，每小時時間點漲潮高度為已知數(shù)值，則按照潮汐測量通用公式，在1 小時內(nèi)漲潮函數(shù)線性表達(dá)式為：

式中：Z表示潮汐量；zd表示初始低潮汐量；k表示1 個小時內(nèi)漲潮差值；t˙表示漲潮持續(xù)時間。通過該公式結(jié)果，并結(jié)合當(dāng)時農(nóng)歷日期即可得到船舶進(jìn)目的地港口的可通航時間T。

由于船舶大多數(shù)均滿載貨物，其入港時吃水較深，入港時則需乘潮，其到達(dá)目的地進(jìn)入港口潮汐時刻約束條件如下：

式中：Qi表示船舶通過港口入港報告線時刻；GCp用于判斷時間段p是否為高潮時刻，若是則取值1，反之則取值為0；BHip用于判斷時間段p是否小于高潮時刻，若是則取值1，反之則取值為0；Φ表示隨機(jī)常數(shù)；表示潮汐開始時刻；表示潮汐結(jié)束時刻。

1.3 最優(yōu)航線生成方法

以船舶航線無向路徑網(wǎng)絡(luò)圖G(V,E)為基礎(chǔ)，依據(jù)船舶最優(yōu)航線生成多維指標(biāo)，使用改進(jìn)和聲搜索算法生成船舶航行最優(yōu)航線。和聲搜索算法（harmony search,HS）是數(shù)據(jù)挖掘算法內(nèi)的智能優(yōu)化算法，通過反復(fù)調(diào)整記憶庫內(nèi)解變量，使函數(shù)隨著迭代次數(shù)不斷收斂實現(xiàn)目標(biāo)優(yōu)化求解算法，該算法可調(diào)參數(shù)較少，應(yīng)用較為廣泛。但其隨機(jī)生成節(jié)點時，會出現(xiàn)復(fù)雜多峰情況，導(dǎo)致算法迭代收斂效果不佳。所以對其進(jìn)行改進(jìn)處理，利用改進(jìn)和聲搜索算法按照船舶最優(yōu)航線生成多維指標(biāo)，從多個維度挖掘并生成船舶最優(yōu)航線，其詳細(xì)過程如下：

G(V,E)X={x1,x2,···,xn}

假設(shè)內(nèi)的任意備選解由表示，由多個船舶航線線路組成和聲搜索記憶庫，其表達(dá)式如下：

式中：HM表示和聲搜索記憶庫；Xi表示船舶的全局航線；U表示和聲搜索記憶庫內(nèi)的航線數(shù)量；f(·)表示評價航線生成質(zhì)量的適應(yīng)度函數(shù)。令R表示任意船舶航行線路，則航線生成質(zhì)量適應(yīng)度函數(shù)表達(dá)式為：

式中：Pi和Pi+1均為航程內(nèi)S的轉(zhuǎn)向點；S表示航程公里數(shù)；n表示轉(zhuǎn)向點總數(shù)。

在和聲搜索算法內(nèi)引入遺傳算法，使用遺傳算法在和聲搜索記憶庫內(nèi)通過交叉航線、消除節(jié)點以及微調(diào)節(jié)點位置后，生成最優(yōu)船舶航線，其過程如下：

從HM內(nèi)隨機(jī)選擇2 條新航線，當(dāng)這2 條航線符合遺傳算法的交叉條件后，使用遺傳算法對其進(jìn)行交叉處理，生成2 條新的航線。若線路和交點為pc；和表示線路內(nèi)起點到轉(zhuǎn)向點之間線路節(jié)點；和表示轉(zhuǎn)向點到目的地線路節(jié)點；，，，，，均表示節(jié)點標(biāo)記。此時會交叉生成2 條新的航行路線，其表達(dá)式為：

將新生成的2 條航線與未交叉前的原航線進(jìn)行對比分析，將高質(zhì)量的2 條航線存儲到記憶庫內(nèi)。將記憶庫內(nèi)所有航線均進(jìn)行交叉操作后，對記憶庫內(nèi)航線進(jìn)行節(jié)點消除和微調(diào)處理。假設(shè)r表示隨機(jī)數(shù)，PA表示航線節(jié)點消除概率（通常取值為0.2），當(dāng)r＜PA時，

通過式（10）和式（11）生成新航線后，將新生成的航線與記憶庫內(nèi)適應(yīng)度最差的航線進(jìn)行比較，選擇適應(yīng)度數(shù)值最高的航線作為最優(yōu)航線。

2 實驗分析

2.1 初始航線生成測試

以一艘船舶作為實驗對象，使用本文方法生成其初始航線，結(jié)果如圖1 所示。

圖1 船舶初始航線生成結(jié)果Fig.1 Initial route generation results of ships

可知，當(dāng)該船需要從起點航行到目的地時，使用本文方法可生成若干條航線，且每條航線均可到達(dá)目的地，同時涵蓋所有中轉(zhuǎn)節(jié)點和轉(zhuǎn)向點。該結(jié)果證明，使用本文方法可有效獲取較為全面的船舶初始航線，也從側(cè)面說明本文方法具備較好的航線生成能力。

2.2 最優(yōu)航線生成測試

以一般船舶為實驗對象，使用本文方法生成其最優(yōu)航線路線，結(jié)果如圖2 所示。

圖2 船舶最優(yōu)航線路線生成結(jié)果Fig.2 Generation result of optimal ship route

分析可知，使用本文方法可有效在初始航線中生成最優(yōu)航線，且該路線在所有路線中航程最短，在該最優(yōu)航線內(nèi)，僅存在一個轉(zhuǎn)向點，航線上無中轉(zhuǎn)節(jié)點，可較大程度降低船舶航行耗時。綜上結(jié)果，本文方法可有效生成最優(yōu)航線。

以10 艘船舶作為實驗對象，使用本文方法生成這10 艘船舶最優(yōu)航線。將每條最優(yōu)航線的適應(yīng)度值作為衡量指標(biāo)，測試本文方法生成最優(yōu)航線能力，結(jié)果如圖3 所示。

圖3 最優(yōu)航線適應(yīng)度值Fig.3 Optimal route line fitness value

分析可知，本文方法生成的船舶航線的適應(yīng)度數(shù)值始終在0.985～0.995 波動，說明本文方法生成航線較為準(zhǔn)確，也是最優(yōu)航線，應(yīng)用效果較好。

3 結(jié) 語

本文研究基于多維度數(shù)據(jù)挖掘的船舶最優(yōu)航線生成方法，考慮船舶航行安全距離和港口潮汐時間多維度，并以其作為挖掘最優(yōu)航線指標(biāo)，最終生成最優(yōu)航線。經(jīng)過實驗驗證：本文方法可有效生成最優(yōu)航線，且所生成的最優(yōu)航線適應(yīng)度數(shù)值較高，應(yīng)用效果較好。