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

黃曼綺，魏雨?yáng)|

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

0 引 言

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

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

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

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

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

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

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

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

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

式中：Di，Dj分別表示船舶i和j從起點(diǎn)到目的地所用時(shí)間。

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

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

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

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

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

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

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

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

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

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

以船舶航線無(wú)向路徑網(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)化算法，通過(guò)反復(fù)調(diào)整記憶庫(kù)內(nèi)解變量，使函數(shù)隨著迭代次數(shù)不斷收斂實(shí)現(xiàn)目標(biāo)優(yōu)化求解算法，該算法可調(diào)參數(shù)較少，應(yīng)用較為廣泛。但其隨機(jī)生成節(jié)點(diǎn)時(shí)，會(huì)出現(xiàn)復(fù)雜多峰情況，導(dǎo)致算法迭代收斂效果不佳。所以對(duì)其進(jìn)行改進(jìn)處理，利用改進(jìn)和聲搜索算法按照船舶最優(yōu)航線生成多維指標(biāo)，從多個(gè)維度挖掘并生成船舶最優(yōu)航線，其詳細(xì)過(guò)程如下：

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

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

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

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

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

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

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

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

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

2.1 初始航線生成測(cè)試

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語(yǔ)

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